Area of Irregular Polygon

[Alex Tweedly]

For the area calculation, it is actually marginally faster without the 
"delete line 1 of p" - i.e. as Geoff Canyon suggested.

The first time through the loop is guaranteed to calculate "0" - so no 
change to the result, and a cost of a very few microseconds.
But doing that "delete line 1 of p" costs you two memory copies of the 
entire variable - one for the delete itself, copying the rest of the 
lines down in place, and another because without the delete, 'p' is 
read-only, so the delete triggers a 'copy-on-write' of the parameter.

For small number of edges in the polygon, it will make negligible 
difference - but for polygons with very large number of points, that 
copying cost will far outweigh the extra pass through the loop.

So omitting the "delete line 1 of p" is more efficient - as well as 
being one line fewer of code.
Geoff C strikes again !

-- Alex.

On 10/11/2015 21:37, [-hh] wrote:
> 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.
> _______________________________________________
> use-livecode mailing list
> use-livecode at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode