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@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
