Click here to Skip to main content
12,819,727 members (28,306 online)
Click here to Skip to main content
Add your own
alternative version


109 bookmarked
Posted 9 Sep 2004

Polygon Triangulation in C#

, 4 Oct 2004
Rate this:
Please Sign up or sign in to vote.
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);
    …… ……
  /*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
      return m_aPolygons.Length;

  public CPoint2D[] Polygons(int index)
    if (index < m_aPolygons.Length)
      return m_aPolygons[index];
      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)|| 
      if (TriangleContainsPoint(new CPoint2D[] {pj, pi, pk}, pt))
    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
    if (IsEarOfUpdatedPolygon(pt))
      bNotFound=false; //got one, pt is an ear
      } //bNotFount
      if (pt !=null)
      polygon=new CPolygon(m_aUpdatedPolygonVertices);
      if (m_aUpdatedPolygonVertices.Length==3)
    } //bFinish=false

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(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
  //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.


  • [1] Meisters, G.H. Polygons have ears. American Mathematical Monthly. June/July 1975, 648-651.
  • [2] Polygon, simple polygon and diagonal: projects/97/Ian/introduction.html
  • [3] Ear Cutting for Simple Polygons:


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

Web Developer
Canada Canada
No Biography provided

You may also be interested in...

Comments and Discussions

QuestionCut Polygon Failure Pin
karatecoyote1-Jul-08 13:58
memberkaratecoyote1-Jul-08 13:58 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.170308.1 | Last Updated 4 Oct 2004
Article Copyright 2004 by fgshen
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid