[C# Helper]
Index Books FAQ Contact About Rod
[Essential Algorithms, Second Edition]

[The Modern C# Challenge]

[WPF 3d, Three-Dimensional Graphics with WPF and C#]

[The C# Helper Top 100]

[Interview Puzzles Dissected]

[C# 24-Hour Trainer]

[Beginning Software Engineering]

[C# 5.0 Programmer's Reference]

[MCSD Certification Toolkit (Exam 70-483): Programming in C#]

Title: Triangulate a polygon in C#

Triangulate polygon

Triangulating a polygon means breaking it into triangles. This is easy for simple 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.

Download the example to experiment with it and to see additional details.

© 2009-2022 Rocky Mountain Computer Consulting, Inc. All rights reserved.