Area of Irregular Polygon
-hh
hh at livecode.org
Wed Nov 11 11:32:57 EST 2015
> Alex T. wrote:
> For the area calculation, it is actually marginally faster without the
> "delete line 1 of p" - i.e. as Geoff Canyon suggested.
> ...
> So omitting the "delete line 1 of p" is more efficient - as well as
> being one line fewer of code.
You are right, of course. I read the thread too fast and overlooked the advice of G.C.
It was a silly thing to delete that first line (I'm still a greenhorn). But you are wrong with your last statement, it's only half a line fewer ;-)
I tested again also for other improvements.
[Secondary result is: LC 6 has at least double speed compared to LC 7-8].
Essential effects had the reduction of the "item-getting" in the "old" function (cited below). It's surprising for the area-only computation.
(I also removed the rounding. It's better do have the method of rounding still available.)
(A param "@p" gave here no improvement, tested for large p.)
-- Centroid and area of a non-intersecting, oriented and closed polygon.
-- See https://en.wikipedia.org/wiki/Polygon#Area_and_centroid
-- The following function claims to be the fastest for computing centroid (and area):
function polyCentroidandArea2 p
local A=0, x=0, y=0
put line 1 of p into L1
put item 1 of L1 into x0; put item 2 of L1 into y0
repeat for each line L in p
put item 1 of L into x1; put item 2 of L into y1
put x0 * y1 - x1 * y0 into t
add (x0 + x1) * t to x; add (y0 + y1) * t to y
add t to A; put x1 into x0; put y1 into y0
end repeat
if A is 0 then return false
else return ( true, x/(3*A), y/(3*A) , abs(A/2) )
end polyCentroidandArea2
-- usage:
-- put polyCentroidandArea2(p) into c0
-- if (item 1 of c0) then
-- put item 2 to 3 of c0 into myCentroid
-- put item 4 of c0 into myArea
-- else put "<yourFourLetterWord>" into fld "INFO"
-- Based on a technique by Alex T., Geoff C. and Roger G.
-- Area of a non-intersecting, oriented and closed polygon:
-- The following function claims to be the fastest for computing the area:
function polyArea2 p
local A=0
put line 1 of p into L1
put item 1 of L1 into x0; put item 2 of L1 into y0
repeat for each line L in p
put item 1 of L into x1; put item 2 of L into y1
add x0 * y1 - x1 * y0 to A
put x1 into x0; put y1 into y0
end repeat
return abs(A/2)
end polyArea2
SPEEDTEST with a large non-selfintersecting closed polygon
[The testpoints/testgrahic can be generated by command "testPoints"]
32001 points/lines, 10 repeats. The values "x/y" denote
x=millisecs per computation with the new method above
y=millisecs per computation with the old method below
LC 6.7.8-rc3 centroidAndArea 41/46 ( areaOnly 22/27 )
LC 7.1.1-rc3 centroidAndArea 92/155 ( areaOnly 70/110 )
LC 8.0.0-dp8 centroidAndArea 92/155 ( areaOnly 70/110 )
These were the "old" functions.
> function polyCentroidandArea p
> put line 1 of p into K
> 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
> 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
-- Command creates a polygon with testpoints, deviating randomly
-- its y-coordonates from an approximate ellipse.
-- n0 = num of points, r0 = y-radius, r2 = x-radius, lc = centerpoint
on testPoints lc
local n0=32000, r0=128, r1=10000 --> adjust these values
if lc is empty then
put 0 into x; put 0 into y
else
put item 1 of lc into x; put item 2 of lc into y
end if
if there is no grc "poly" then create grc "poly"
set style of grc "poly" to "polygon"; set lineSize of grc "poly" to 2
set foreColor of grc "poly" to (255,255,0)
set editmode of grc "poly" to "polygon" --> great feature of LC
set randomseed to 1447250307 --> now we get always the same points generated
put 2*pi/n0 into cn; put empty into pts
repeat with j= 0 to n0
put cr & ( x + r1*cos(j*cn), \
y + (r0 + random(64) - (j mod 2)*random(128))*sin(j*cn) ) after pts
end repeat
delete char 1 of pts -- is cr
set points of grc "poly" to pts --> LC engine rounds for us
end testPoints
Note: There arises a lot of identical points or vertical up/down-movements due to rounding when the points of the graphic are set. This has no influence on the results above (a little bit on speed only).
=====
Love is just a four-letter-word.
More information about the Use-livecode
mailing list