Almost as many triangles as points

82 views
Skip to first unread message

Andrew B. Martin

unread,
Feb 21, 2014, 10:15:55 AM2/21/14
to poly...@googlegroups.com
Hello,

I'm using Poly2Tri to decompose shapefile polygons into triangles to make area computations easier.

Right now, I'm testing on simple polygons, and I'm finding that through triangulation I get almost as many triangles as I have points, e.g. 90 triangles from 92 points, or 141 from 144.

Is this normal behaviour?

Regards,
Andrew

obi

unread,
Feb 21, 2014, 11:49:26 AM2/21/14
to poly...@googlegroups.com
A triangulation of an n-sided polygon should have n−2 triangles. So the question turns into why you got 141 triangles from 144 points.


If you play around with a few examples, you quickly discover that every triangulation of an n-sided polygon
has n−2 triangles. You might even try to prove this observation by induction. The base case n = 3
is trivial: there is only one triangulation of a triangle, and it obviously has only one triangle! To
prove the general case, let P be a polygon with n edges. Draw a diagonal between two vertices.
This splits P into two smaller polygons. One of these polygons has k edges of P plus the diagonal,
for some integer k between 2 and n − 2, for a total of k + 1 edges. So by the induction hypothesis,
this polygon can be broken into k − 1 triangles. The other polygon has n − k + 1 edges, and so
by the induction hypothesis, it can be broken into n − k − 1 tirangles

Andrew B. Martin

unread,
Feb 22, 2014, 6:26:22 AM2/22/14
to poly...@googlegroups.com
Good to know; thanks.

I'm going to check out the 144 points to 141 triangles polygon on Monday. I noticed after I posted the above that when I computed the area of its triangles by the shoelace algorithm many come out to have an area of zero. Maybe there's something wrong with it.




obi

unread,
Feb 22, 2014, 8:39:18 AM2/22/14
to poly...@googlegroups.com
Shoelace seems like a convenient way yo compute the area of a simple polygon. So no need to compute the area using the triangles. But you might be doing it as a form of unit test?

Computing the area of a triangle is as simple as taking half the value of the cross product between two of the triangle edges. To get the polygon area you could just sum up the abs value of all these cross products. Then you don't have to worry about the winding order of the triangles. 




Andrew B. Martin

unread,
Feb 22, 2014, 2:37:19 PM2/22/14
to poly...@googlegroups.com
The area computations were part of a unit test, but they're central to my objective. 

I'm trying to find the area of overlap between a circle and polygon for a large number of polygons. I'm first triangulating the polygons and then figuring out the area of overlap between the circle and each polygon's triangles that intersect the circle. 

obi

unread,
Feb 22, 2014, 5:39:25 PM2/22/14
to poly...@googlegroups.com
What about doing something like this ( see attachment )

Algorithm:

1. Traverse the polygon and test if point is inside or outside circle.
2. If a point is inside and next is outside compute the intersection point with circle. 
3. If you connect every second point pair on the circle you will get a new polygon that can be considered outside the circle.
4. Use Sholace to compute its area and subtract from original polygon area then add part of the circle segment area A in picture.

All computations should be doable in one pass over the polygon points so the algorithm to compute the intersection area should be O(n). 


teckning.png

Andrew B. Martin

unread,
Feb 24, 2014, 4:06:28 AM2/24/14
to poly...@googlegroups.com
That was my first idea, but I abandoned it because I thought myself into a knot regarding how to know which intersection points to connect. I was trying the compute the area of the inside part though; computing the outside pieces seems more tractable.

The tricky case is when the first points I check are outside the circle, but then I can just store them to a list and compute that polygon at the end once I've traversed its remaining points. 

Computing intersection points and the area of the circular segments between the intersection chords and the circle are the most expensive parts, so I think this traversal method is worth a try over triangularization and then computing the areas of intersection for each triangle.

obi

unread,
Feb 24, 2014, 8:26:52 AM2/24/14
to poly...@googlegroups.com
You should only have to traverse until you find the first point inside then start and then loop until you get back to it. This will give a algorithm with worst case 0(2*n).
This should be much faster than using triangulation.

Let me know how it goes :). Problem solving is fun.

Andrew B. Martin

unread,
Mar 3, 2014, 8:17:39 AM3/3/14
to poly...@googlegroups.com
Thanks for the tip obi. I implemented the routine at the end of last week.

It runs very quickly and works well for most situations, but there's an edge case that throws a wrench in things.

When I have a situation like in the attached diagram the hatched area gets subtracted from the total polygon area rather than ignored.
This situation works out if I compute the overlap area by that contained in the circle - rather than excluded - but determining whether this case is current is tricky.


edgecase.jpg

obi

unread,
Mar 3, 2014, 10:15:21 AM3/3/14
to poly...@googlegroups.com
Yes I see this is more tricky than at first look..

Thinking a bit more about it you can even have a case like this.
Where the area would have to be computed as 
circle area - area of abcd - two segment areas

I'm certain this kind of algorithm is the solution I just can't see the generic solution.
I would perform the polygon/circle intersections.
This would give a new polygon included the new points. 
So we get a polygon (circular list) where intersection points come in order ABCD
We can also order the point in a circular list according the position on the circle ADCB.
Given that polygon has a know orientation, CW or CCW and given the two lists ABCD, and ADCB. 
Should be all needed to know.. just don't see the solution right away.
polygon_circle_intersection_area.png

Andrew B. Martin

unread,
Mar 3, 2014, 11:01:36 AM3/3/14
to poly...@googlegroups.com
Okay. This gets more complicated the more intersection points there are.

With four intersections points it's either an ABCD or ADCB situation, but with 6 intersections it can be ABCDEF, AFEDCB, AFEBCD or ABCFED, and with 8 intersections there are 8 combinations (shudder).

By tracking the order of intersections points on the polygon and then determining the order they fall on the circle it's not intractable to account for different cases as long as you can be sure of not encountering 8+ intersection points.

A general solution would still be far superior.
Reply all
Reply to author
Forward
0 new messages