## 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;
private ArrayList m_alSelectedPts=new ArrayList();
private void pnlDraw_MouseUp(object sender, MouseEventArgs e)
{
…… ……
Point clickedPt=new Point(e.X, e.Y);
m_alSelectedPts.Add(clickedPt);
…… ……
}
private void btnCut_Click(object sender, System.EventArgs e)
{
…… ……
CPolygonShape cutPolygon = new CPolygonShape(vertices);
cutPolygon.CutEar();
…… ……
}
public void DrawEarsPolygon(CPolygonShape cutPolygon)
{
…… ……
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;
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;
}
private bool IsEarOfUpdatedPolygon(CPoint2D vertex )
{
CPolygon polygon=new CPolygon(m_aUpdatedPolygonVertices);
……
bool bEar=true;
if (polygon.PolygonVertexType(vertex)=VertexType.ConvexPoint)
{
CPoint2D pi=vertex;
CPoint2D pj=polygon.PreviousPoint(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
bEar=false;
return bEar;
}
public void CutEar()
{
CPolygon polygon=new CPolygon(m_aUpdatedPolygonVertices);
bool bFinish=false;
CPoint2D pt=new CPoint2D();
while (bFinish==false)
{
int i=0;
bool bNotFound=true;
while (bNotFound
&& (i < m_aUpdatedPolygonVertices.Length))
{
pt=m_aUpdatedPolygonVertices[i];
if (IsEarOfUpdatedPolygon(pt))
bNotFound=false;
else
i++;
}
if (pt !=null)
UpdatePolygonVertices(pt);
polygon=new CPolygon(m_aUpdatedPolygonVertices);
if (m_aUpdatedPolygonVertices.Length==3)
bFinish=true;
}
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
{
protected double a;
protected double b;
protected double c;
public CLine(Double angleInRad, CPoint2D point){};
public CLine(CPoint2D point1, CPoint2D point2){};
public CLine(CLine copiedLine){};
public bool Parallel(CLine line){};
public CPoint2D IntersecctionWith(CLine line){};
…… ……
}
public class CLineSegment : CLine
{
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){};
public PolygonType GetPolygonType(){};
public PolygonDirection VerticesDirection();
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