12,821,674 members (30,917 online)
alternative version

#### Stats

244.4K views
109 bookmarked
Posted 9 Sep 2004

# Polygon Triangulation in C#

, 4 Oct 2004
 Rate this:
Triangulate a polygon by cutting ears in C#

## Background and Theory

Polygon is one of the most important objects we are dealing with when we rendering 2D/3D graphics or processing computational geometry. As a polygon could be very complicated, some restrictions may be applied on implementation. For example, OpenGL does not directly support drawing a concave polygon. When you present OpenGL with a no convex filled polygon, it might not draw as you expect. In most cases, we need to break down a complex polygon as its composed simpler shapes, such as a set of triangles to simplify the problem.

In 1975, Gary Meisters developed the Two-Ears Theorem that proved this attempt is always feasible: Except for triangles, every simple polygon has at least two non-over lapping ears (triangles)[1].

A simple polygon is a polygon with no two non-consecutive edges intersecting. If a diagonal (Pi-1, Pi+1) that bridges Pi lies entirely in the polygon, then the vertex Pi is called an ear. To partitioning the polygon by finding ears, the following lemma is also useful: If a convex vertex Pi is not an ear, then the triangle formed by Pi-1, Pi, Pi+1 contains a concave vertex [2].

Figure 1. Polygon and Ears [3]

The following code present here demonstrates an O(kn) time algorithm for finding ears and partitioning a simple polygon by triangles.

Figure 2. Polygon

Figure 3. Triangulated Polygon

## Program Structure and Sample Code:

Based on Gary Meisters' theory, we always can find an ear from a polygon. If we cut the ear from this polygon, we get a new polygon with one vertex less and a triangle. Repeat this process with the new polygon till the polygon has only three vertices left. The flowchart is as following:

Figure 4. Polygon Triangulation Program Flowchart

This program is written in C#.NET and developed with MS Visual Studio 2003. To use object oriented program technology and make the code re-useable, I structured the program with following classes:

Figure 5. Program Class Diagram

### `PolygonCuttingEarInterface `Namespace:

The frmCuttingEars is the user interface where to receive the user-selected polygon vertices, generate an object of `CPolygonShape `and pass the data to the object, then retrieving the calculated data and presenting a serious of triangles to the user.

```public class frmCuttingEars : System.Windows.Forms.Form
{
…… ……
private System.Windows.Forms.Panel pnlDraw;

//To hold user selected points as polygon vertices:
private ArrayList m_alSelectedPts=new ArrayList();

/* To pick up the user selected points in the panel */
private void pnlDraw_MouseUp(object sender, MouseEventArgs e)
{
…… ……
Point clickedPt=new Point(e.X, e.Y);
…… ……
}

/* Pass data to an object of CpolygonShape and calculate ears: */
private void btnCut_Click(object sender, System.EventArgs e)
{
…… ……
//Convert the received vertices to array of CPoint2D, then:
CPolygonShape cutPolygon =  new CPolygonShape(vertices);
cutPolygon.CutEar();
…… ……
}

/*Receive results from the object and fill triangles: */
public void DrawEarsPolygon(CPolygonShape cutPolygon)
{
…… ……
//Use tempArray to hold the results:
for (int i=0; i < cutPolygon.NumberOfPolygons; i++)
{
int nPoints=cutPolygon.Polygons(i).Length;
Point[] tempArray=new Point[nPoints];
for (int j=0; j < nPoints; j++)
{
tempArray[j].X= (int)cutPolygon.Polygons(i)[j].X;
tempArray[j].Y= (int)cutPolygon.Polygons(i)[j].Y;
}
Graphics gfx=pnlDraw.CreateGraphics();

int nBrush = i % 3;  //Fill triangles in different color
gfx.FillPolygon(m_aBrushes[nBrush], tempArray);
…… ……
}
}
}
```

### `PolygonCuttingEar `Namespace:

The `CpolygonShape `is the class that does all the calculation: find a polygon's ear, cut the ear by deleting the vertex and make an updated polygon. This process will be repeated till the updated polygon is a triangle.

```public class CPolygonShape
{
…… ……
private CPoint2D[] m_aUpdatedPolygonVertices;
private  CPoint2D[][] m_aPolygons;
public int NumberOfPolygons
{
get
{
return m_aPolygons.Length;
}
}

public CPoint2D[] Polygons(int index)
{
if (index < m_aPolygons.Length)
return m_aPolygons[index];
else
return null;
}

/* To check whether the Vertex is an ear  */
private bool IsEarOfUpdatedPolygon(CPoint2D vertex )
{
CPolygon polygon=new CPolygon(m_aUpdatedPolygonVertices);
……
bool bEar=true;
if (polygon.PolygonVertexType(vertex)=VertexType.ConvexPoint)
{
CPoint2D pi=vertex;
//previous vertex
CPoint2D pj=polygon.PreviousPoint(vertex);
//next vertex
CPoint2D pk=polygon.NextPoint(vertex);
for (int i=m_aUpdatedPolygonVertices.GetLowerBound(0);
i < m_aUpdatedPolygonVertices.GetUpperBound(0); i++)
{
CPoint2D pt=m_aUpdatedPolygonVertices[i];
if ( !(pt.EqualsPoint(pi)||
pt.EqualsPoint(pj)||pt.EqualsPoint(pk)))
{
if (TriangleContainsPoint(new CPoint2D[] {pj, pi, pk}, pt))
bEar=false;
}
}
}
else  //concave point
bEar=false; //not an ear

return bEar;
}

/*To cut an ear */
public void CutEar()
{
CPolygon polygon=new CPolygon(m_aUpdatedPolygonVertices);
bool bFinish=false;
CPoint2D pt=new CPoint2D();
while (bFinish==false) //UpdatedPolygon
{
int i=0;
bool bNotFound=true;
while (bNotFound
&& (i < m_aUpdatedPolygonVertices.Length)) // till find an ear
{
pt=m_aUpdatedPolygonVertices[i];
if (IsEarOfUpdatedPolygon(pt))
bNotFound=false; //got one, pt is an ear
else
i++;
} //bNotFount
if (pt !=null)
UpdatePolygonVertices(pt);

polygon=new CPolygon(m_aUpdatedPolygonVertices);
if (m_aUpdatedPolygonVertices.Length==3)
bFinish=true;
} //bFinish=false
SetPolygons();
}
}
```

### `GeometryUtility `Namespace:

This namespace includes many generic computational geometry classes and lots of functions that could be re-used for other projects.

```public class CPoint2DD
{
private double m_dCoordinate_X;
private double m_dCoordinate_Y;

public bool InLine(CLineSegment lineSegment) {};
public bool InsidePolygon(CPoint2D[] polygonVertices);
public double DistanceTo(CPoint2D point) {};
…… ……
}

public class CLine
{
//line: ax+by+c=0;
protected double a;
protected double b;
protected double c;

public CLine(CPoint2D point1, CPoint2D point2){};
public CLine(CLine copiedLine){};

public bool Parallel(CLine line){};
public CPoint2D IntersecctionWith(CLine line){};
…… ……
}

public class CLineSegment : CLine
{
//line: ax+by+c=0, with start point and end point
//direction from start point ->end point
private CPoint2D m_startPoint;
private CPoint2D m_endPoint;

public double GetLineSegmentLength(){};
public int GetPointLocation(CPoint2D point){};
…… ……
}

public class CPolygon
{
private CPoint2D[] m_aVertices;
public double PolygonArea(){};

public VertexType PolygonVertexType(CPoint2D vertex){};
//return Concave vertex or convex vertex

public PolygonType GetPolygonType(){};
//return Concave polygon, convex polygon

public PolygonDirection VerticesDirection();
//return clockwise or count clockwise

public bool PrincipalVertex(CPoint2D vertex){};
… …}
```

## Run the Program

To see a demonstration, first you select the way to initialize polygon vertices: you can use the build-in testing data or pick up vertices by clicking the panel, then draw polygon outer lines by clicking Draw Polygon button; Click the Cut Ear button will start to triangulate the polygon, the triangles composed the polygon will be colored on the screen.

To reset program for next demonstration, click the Clean Screen button, you will be able to start over again.

You can use button, main menu, context menu or tool bar button to run the program as your convenient. For assistance or more details of this program, you can use the Help menu or reference the tool tip of each control by moving mouse over the control.

Figure 6. User Selected Polygon

Figure 7. Triangulated Polygon

Please feel free to explore and use the source code here. If you have any suggestions, please let me know and I will keep the code updated.

## Reference

• [1] Meisters, G.H. Polygons have ears. American Mathematical Monthly. June/July 1975, 648-651.
• [2] Polygon, simple polygon and diagonal: http://cgm.cs.mcgill.ca/~godfried/teaching/cg- projects/97/Ian/introduction.html
• [3] Ear Cutting for Simple Polygons: http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/TwoEar/two-ear.htm

A list of licenses authors might use can be found here

## Share

No Biography provided

## You may also be interested in...

 First Prev Next
 error Member 1176313531-Jul-15 4:40 Member 11763135 31-Jul-15 4:40
 Triangulation Failure Member 1043896313-Jan-15 1:09 Member 10438963 13-Jan-15 1:09
 My vote of 5 Canny Brisk31-Oct-13 6:43 Canny Brisk 31-Oct-13 6:43
 My vote of 5 manoj kumar choubey22-Feb-12 0:29 manoj kumar choubey 22-Feb-12 0:29
 Merging polygons Patrick Blackman29-Jul-11 10:01 Patrick Blackman 29-Jul-11 10:01
 Wrong Polygon Geometry Detection gomezmateu.oscar29-Sep-10 23:30 gomezmateu.oscar 29-Sep-10 23:30
 Very nice majoxx11-Apr-09 1:07 majoxx 11-Apr-09 1:07
 hi all, in my code i need to draw a rectangle and to show 0 or 1 in that can anyone halp me out this is very urgent........ thanks in advance
 Drawing a simple concave polygon... [modified] gracecm19-Nov-08 4:24 gracecm 19-Nov-08 4:24
 if lots of polygons are triangulated,it doesn't work normally. littleboyyyf27-Oct-08 19:22 littleboyyyf 27-Oct-08 19:22
 Re: if lots of polygons are triangulated,it doesn't work normally. Aram Azhari4-May-14 12:38 Aram Azhari 4-May-14 12:38
 my neural triangulator for all polygons exterior11-Sep-08 12:47 exterior 11-Sep-08 12:47
 Cut Polygon Failure karatecoyote1-Jul-08 13:58 karatecoyote 1-Jul-08 13:58
 Holes karatecoyote17-Apr-08 6:17 karatecoyote 17-Apr-08 6:17
 Re: Holes Fiorentino18-May-08 7:12 Fiorentino 18-May-08 7:12
 Re: Holes karatecoyote19-May-08 10:24 karatecoyote 19-May-08 10:24
 Re: Holes Fiorentino20-May-08 2:30 Fiorentino 20-May-08 2:30
 Re: Holes havana75-Jan-11 8:26 havana7 5-Jan-11 8:26
 Reuse karatecoyote24-Mar-08 13:36 karatecoyote 24-Mar-08 13:36
 Complex polygons Leonnik24-Oct-07 11:07 Leonnik 24-Oct-07 11:07
 PointInsidePolygon bugs jdiegel26-Aug-07 16:45 jdiegel 26-Aug-07 16:45
 a bug sbenhar18-Jul-07 4:15 sbenhar 18-Jul-07 4:15
 Wrong trianulation for simple figure noi7612-Dec-06 7:58 noi76 12-Dec-06 7:58
 Re: Wrong trianulation for simple figure noi7613-Dec-06 0:42 noi76 13-Dec-06 0:42
 Re: Wrong trianulation for simple figure Wizard_0130-Dec-06 8:21 Wizard_01 30-Dec-06 8:21
 Re: Wrong trianulation for simple figure Anilkale110-Jan-10 22:58 Anilkale1 10-Jan-10 22:58
 Bug? - CPoint2D.InLine(LineSegment lineSegment) rofu29-Sep-06 5:18 rofu 29-Sep-06 5:18
 Bug with "IntersectedWith" wegnwa10-Mar-06 6:59 wegnwa 10-Mar-06 6:59
 Re: Bug with "IntersectedWith" noi7612-Dec-06 8:24 noi76 12-Dec-06 8:24
 Very skinny triangles Brent_Daignault14-Oct-05 11:54 Brent_Daignault 14-Oct-05 11:54
 Re: Very skinny triangles Fiorentino21-May-08 6:32 Fiorentino 21-May-08 6:32
 Old technique Brent_Daignault14-Oct-05 11:51 Brent_Daignault 14-Oct-05 11:51
 Inline routine eko.pramono10-Oct-05 23:36 eko.pramono 10-Oct-05 23:36
 A small bug Bobik27-Aug-05 22:35 Bobik 27-Aug-05 22:35
 A bug? Paul Selormey7-Aug-05 14:59 Paul Selormey 7-Aug-05 14:59
 Polygon Direction Daniel Carvajal30-May-05 6:03 Daniel Carvajal 30-May-05 6:03
 Very usefull trixcomp4-May-05 13:37 trixcomp 4-May-05 13:37
 Small bug Omer van Kloeten23-Sep-04 8:02 Omer van Kloeten 23-Sep-04 8:02
 Re: Small bug fgshen4-Oct-04 5:35 fgshen 4-Oct-04 5:35
 Regards Matjaz Kupnik22-Sep-04 0:43 Matjaz Kupnik 22-Sep-04 0:43
 Wow Brian Mc14-Sep-04 21:14 Brian Mc 14-Sep-04 21:14
 Good Job! Anonymous10-Sep-04 7:14 Anonymous 10-Sep-04 7:14
 Excellent Job! Zhaohui Xing (Joey)10-Sep-04 7:05 Zhaohui Xing (Joey) 10-Sep-04 7:05
 Last Visit: 31-Dec-99 19:00     Last Update: 26-Mar-17 20:02 Refresh 1