Area of Irregular Polygon
Alex Tweedly
alex at tweedly.net
Mon Nov 9 06:57:29 EST 2015
Hi Peter,
No, it doesn't assume convexity - what it does assume is
non-self-overlapping, (loosely aka non-self-intersecting).
A simple but non-convex shape, like (excuse the lack of line-drawing in
email :-)
B C
D
A E
For simplicity, pretend the shape is all in the positive quadrant.
The algorithm adds the area under each line segment - AB, BC, CD, DE, EA
The concavity at D is not significant -
the area under BC includes all the area in the overall rectangle
then we remove the area under CD (the delta-X is negative, so we are
removing it)
then we add back in the area under DE
and finally remove the area under EA.
As Geoff said, it does fail if the shape self-overlaps - the overlap
area is counted twice (which is conceptually a failure, depending on
your intent - if you were measuring the area of cloth needed to
physically realize the shape, then it is correct, if you are measuring
the area to be covered by paint then it would be wrong).
Similarly though less importantly, it "fails" on self-inverting shapes
(e.g. 10,10 100,100 100,10 10,100 10,10) - but what the intent of
that shape is is hard to guess :-)
I'm sure there is a way to test for convexity - for each edge segment
the *following* point must be on or to the left (if anti-clockwise) or
to the right (clockwise) of the extended edge segment - so if you find
at least one of each of left and right, then you have non-convexity.
-- Alex.
On 09/11/2015 10:18, Peter TB Brett wrote:
> On 08/11/2015 00:43, Alex Tweedly wrote:
>> Actually, you should shorten the maths - makes it a bit more efficient
>>
>>
>> function getArea pPts
>> if line 1 of pPts <> line -1 of pPts then return 0
>> put 0 into tArea
>> put empty into oldL
>> repeat for each line L in pPts
>> if oldL is not empty then
>> -- put item 1 of L - item 1 of oldL into dx
>> -- put item 2 of oldL + (item 2 of L - item 2 of oldL)
>> / 2 into avgY
>> -- put dx * avgY into thisArea
>> -- add thisArea to tArea
>> add (item 1 of L - item 1 of oldL) * ( item 2 of oldL + item 2
>> of L) / 2 to tArea
>> end if
>> put L into oldL
>> end repeat
>> return abs(tArea)
>>
>> end getArea
>
> Hi Alex,
>
> It seems to me that this algorithm assumes that the polygon is convex,
> and it will add area that should be subtracted if the polygon isn't
> convex. Am I correct? Is there any way to include a test for convexity?
>
> Peter
>
More information about the use-livecode
mailing list