Polygon Triangulation in C#

• Download demo project - 26 Kb
• Download source - 54 Kb

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);
    m_alSelectedPts.Add(clickedPt);
    …… …… 
  }
  
  /* 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(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.

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