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