Triangulating a polygon means breaking it into triangles. This is easy for simply shapes such as rectangles. It’s even easy for convex polygons. It’s more interesting for non-convex polygons.
To triangulate a polygon, first define an ear to be a corner of a polygon that sticks out. More rigorously, three adjacent vertexes form an ear if the angle they form is convex and the triangle they form does not contain any of the polygon’s other points. It can be shown that any polygon with more than three points has at least two ears.
The method used by this program is:
Do While (# vertices > 3)
Find an ear.
Add the ear to the triangle list.
Remove the ear's middle vertex from the polygon.
Loop
Make a triangle from the 3 remaining vertices.
The details aren’t too complicated, but the code is pretty long so I’m not showing it here. Download the example program to see how it works.
For a nice, detailed explanation of this method, see Ian Garton’s Web page.
![[Interview Puzzles Dissected]](http://www.csharphelper.com/interview_puzzles_161_200.jpg)
![[C# 24-Hour Trainer]](http://www.csharphelper.com/csharp24hr_2e_79x100.jpg)
![[Beginning Software Engineering]](http://www.csharphelper.com/sw_eng_tiny.png)
![[C# 5.0 Programmer's Reference]](http://www.csharphelper.com/csharp_prog_ref_80x100.png)
![[Essential Algorithms: A Practical Approach to Computer Algorithms]](http://www.csharphelper.com/essential_algs_81x100.jpg)
![[Mastering Events and Delegates in C#]](http://www.csharphelper.com/mastering_events_61_100.png)
![[Using Interfaces in C#]](http://www.csharphelper.com/using_interfaces_60_100.png)
![[Learning Data Structures and Algorithms]](http://www.csharphelper.com/algs_video_tiny.png)
![[Learning Visual Basic .NET]](http://www.csharphelper.com/vb_video_tiny.png)
This was really handy for triangulating a solid in a CAD program and exporting to a game engine. Free open source on this code right?
I’m glad you found it useful!
Yes, you can use this code as you like. I’d appreciate (but don’t require) an acknowledgement. (I usually also add the URL where I found a technique to my code so I can find it if I need to look it over again later.)
Thank you for your implementation!
However there is a mistake in code, in method FindEar:
you use a method’s parameter (A) as for-loop variable, so if this loop finishes, then A will be equal to num_points and the indexOutOfBounds exception will occur later.
So just set A to num_points – 1 after the loop.
That’s true, but the loop will never finish because any polygon with at least 3 points should have at least 2 ears so the loop will find one.
If the loop does finish, then the code hits an assertion that throws an exception to stop execution so you can debug the program and figure out what happened.