Area of Irregular Polygon

[Alex Tweedly]

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
>