Area of Irregular Polygon

-hh hh at livecode.org
Tue Nov 10 16:37:19 EST 2015


In the thread ("Area of irregular Polygon") I've seen a very fast technique.
I tested this technique and found it extremely fast.
Thus I would like to summarize and contribute also the centroid formulas, for our collections.

Look at non-selfintersecting (simple) polygons.
The centroid of such a polygon is a good candidate for rotations of the polygon.

Say you have a map of countries or states of described by such polygons (neglecting all "wholes"). Each polygon has a very lengthy list of points.

If the points (vertices) are 'oriented' (cw or ccw), the formula for its coordinates are given here
https://en.wikipedia.org/wiki/Polygon#Area_and_centroid

What's the fastest way to handle such "shoelace-formulas" (overcrossing two lines of points) in LC?

The noteworthy technique used by Alex T. and Roger G. is essentially the following, walking only one single time through the list of points.

function polyArea p
   put line 1 of p into K; delete line 1 of p
   repeat for each line L in p
     add (item 1 of K) * (item 2 of L) - (item 1 of L) * (item 2 of K) to A
     put L into K
   end repeat
   return abs(A/2)
end polyArea

I tested this technique and found it extremely fast. So I would like to contribute also the centroid formulas for our collections.

We still walk again *one* single time through the list of points, using the wiki-formulas above.

-- function polyCentroidandArea
-- returns in line 1 the centroid of the poly, in line 2 the area
-- p is a list of oriented points, no empty line
-- last line of p = first line of p (we have a closed poly)
-- the points are oriented (CW or CCW)

function polyCentroidandArea p 
   put line 1 of p into K; delete line 1 of p
   put 0 into A; put 0 into x; put 0 into y
   repeat for each line L in p
     put (item 1 of K) * (item 2 of L) - (item 1 of L) * (item 2 of K) into t
     add ((item 1 of K) + (item 1 of L)) * t to x
     add ((item 2 of K) + (item 2 of L)) * t to y
     add t to A; put L into K
   end repeat
   if A is 0 then return "Area is zero"
   else return ( round(x/(3*A)) , round(y/(3*A)) ) & cr & abs(A/2)
end polyCentroidandArea

=====
I donated to Wikipedia.



More information about the Use-livecode mailing list