CODEWITHSUNDEEP
iosobjective-cgeometrytriangulation
Bassel Shawi
Bassel Shawi

Reputation: 614

Triangulate a polygon in objective c

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?

Upvotes: 0

Views: 978

Answers (1)

Ray Chu
Ray Chu

Reputation: 11

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

Upvotes: 1

Related Questions