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
_______________________________________________
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
