I need to triangulate a polygon that could be convex or concave, but it doesn't have holes in it, is there a code or a library for objective-c that does the job?
Asked
Active
Viewed 966 times
0
-
Triangulate in what sense? I mean, do you need graphics? Or some sort of an abstract representation? Or what? – Jun 12 '13 at 08:00
-
Abstract representation – Bassel Shawi Jun 12 '13 at 08:03
-
possible duplicate of [C++ 2D tessellation library?](http://stackoverflow.com/questions/1418831/c-2d-tessellation-library) – Marcelo Cantos Jun 12 '13 at 08:40
-
Voted to close as dup. The other question was about convex polygons, but the answers apply to concave polygons as well. – Marcelo Cantos Jun 12 '13 at 08:41
-
1Why vote to close it? are you giving me an objective-c solution for the problem, as i mentioned i need it in objective-c not objective-c++ – Bassel Shawi Jun 12 '13 at 08:48
1 Answers
1
The best way to triangulate a concave polygon in Objective-C is the ear clipping method. It requires the following steps:
1. Go through each vertex in the polygon and store the convex points in an array - This is harder than it sounds.
You will need to find the left-most point (take the bottom-most point if there are equal x-coords).
Determine if you want to go clockwise or anti-clockwise. If anti-clockwise, find the angle between AB and BC using double angle = atan2(c.y - b.y, c.x - b.x) - atan2(a.y - b.y, a.x - b.x) where B is the vertex point.
Convert the angle from radians to degrees using angle *= 180 / M_PI. If the angle is negative, add the angle by 360 degrees.
Finally, if the angle is < 180 degrees, store the vertex in an array.
2. Find the ear of each point in your convex point array
A point is considered an "ear" if there are no vertices inside the triangle formed by the point and adjacent vertices. You will need to iterate through all points and determine if a point in the polygon lies in the triangle formed by points ABC. You can do this by finding the barycentric coordinate of the fourth point. See determine whether point lies inside triangle. Store the ears in an array.
3. Triangulate the shape
Remove each ear and draw a diagonal between the adjacent points. Discover any new convex points and determine if there are more ears. Add any new ears into the end of the array and continue this step until left with just 3 points (1 triangle). See http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf for more details
