Polygons
I have a requirement to do some manipulation of relatively simple polygons. In particular I have two requirements:
1. Determine the area of the polygon
2. Create a new polygon from the intersection of two existing polygons that includes the area of the first minus the area of the second.
I've had a look at GeneralPath and Polygon, and neither seems to have this sort of functionality. Area is better - looks like I can use the method Area.subtract() to solve point 2, but I still can find nothing to calculate the area of the area (hah).
Does anyone know of an existing routine? I'm aware of techniques like scanline conversion and breaking it down into rectangles. The problem is simplified by the fact that all of the bounding lines are horizontal or vertical.
Thanks,
Tim
[821 byte] By [
TimRyanNZ] at [2007-9-27 22:51:10]
I would triangulate the polygon and then calculate the area of each triangle using Heron's formula.
cont.assuming the polygon is convex of course...
> I would triangulate the polygon and then calculate the
> area of each triangle using Heron's formula.
More precisely, but without Heron: consider one side of the polygon at a time, and follow the corners clockwise. If the two corners belonging to a side are located at (a,b) and (c,d) then the area of the triangle formed by those two points and (0,0) is (bc-ad)/2 -- at least, according to my half-page of crude scribblings (you might want to verify that statement). The area of the polygon is the sum of the areas of those triangles. It doesn't matter whether (0,0) is inside the polygon or not; if it is outside, then some of the triangles will have negative areas.
> More precisely, but without Heron: consider one side
> of the polygon at a time, and follow the corners
> clockwise. If the two corners belonging to a side are
> located at (a,b) and (c,d) then the area of the
> triangle formed by those two points and (0,0) is
> (bc-ad)/2 -- at least, according to my half-page of
> crude scribblings (you might want to verify that
> statement). The area of the polygon is the sum of the
> areas of those triangles. It doesn't matter whether
> (0,0) is inside the polygon or not; if it is outside,
> then some of the triangles will have negative areas.
Well that certainly sounds like a simple solution - only one issue, does this work if the polygon is "convex"?. Thinking about it quickly, I suspect so, but it would be nice to confirm.
Perhaps I should explain what the polygon represents which may help to show what features it COULD have. The polygon is made up of only horizontal and vertical lines, but may include ins and outs like this:
+--+
|| +-+
|| ||
|+--+++
++|
|++
| |
+-+ | |
| | |+--+
| +-+|
+-+
It is guaranteed to be a single polygon with no overlapping lines or internal spaces.
Regards,
Tim
Sorry, I meant does this work if the polygon is "concave" !!
You mean non-convex, don't you? I think that algorithm should work for any polygon at all. Shouldn't be hard to try it out, eh?
> You mean non-convex, don't you? I think that> algorithm should work for any polygon at all.> Shouldn't be hard to try it out, eh?Yup - will do.Thanks,Tim
> If the two corners belonging to a side
> are located at (a,b) and (c,d) then the area of the
> triangle formed by those two points and (0,0) is
> (bc-ad)/2
I don't understand why this works, so in the end I worked out my own algorithm...
( (c-a)d + (d-b)c )/2
...which also works, but only where all lines are horizontal or vertical. It isn't as succinct as DrClap's algorithm, but at least I understand how it works.
I did a bit of drawing to see if (why) the other algorithm worked and it definitely appears to do so, and in simple cases I can see that it does geometrically, but I don't really understand why it always works.
You're in good company: Nobel Prize winner Richard Feynman said "What I cannot create, I do not understand." I don't have a proof for my algorithm, although it's probably straightforward undergraduate math. At least you didn't come back with an example where it didn't work...
As I was happy that my algorithm worked, I thought I'd try yours DrClap. Yes yours also works fine. Thanks for that.Regards,Tim
