Area of Irregular Polygon
Alex Tweedly
alex at tweedly.net
Tue Nov 10 19:38:03 EST 2015
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
More information about the use-livecode
mailing list