Click here to Skip to main content
15,867,568 members
Articles / Programming Languages / C#
Article

Polygon Triangulation in C#

Rate me:
Please Sign up or sign in to vote.
4.83/5 (53 votes)
3 Oct 20043 min read 321.4K   12.5K   111   45
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].

Image 1

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.

Image 2

Figure 2. Polygon

Image 3

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:

Image 4

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:

Image 5

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.

C#
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.

C#
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.

C#
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.

Image 6

Figure 6. User Selected Polygon

Image 7 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

License

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


Written By
Web Developer
Canada Canada
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
PraiseThanks! Pin
Member 1195278426-Sep-19 19:27
Member 1195278426-Sep-19 19:27 
Thanks for this working example. Smile | :)
But, your code is totaly disaster and is not regular c# code, it reminds C/C++ code. Algorithm will by totaly rewriten and it will simplified to 300 rows D'Oh! | :doh:
Bugerror Pin
Member 1176313531-Jul-15 3:40
Member 1176313531-Jul-15 3:40 
BugTriangulation Failure Pin
Himanshu Sahu 21108813-Jan-15 0:09
professionalHimanshu Sahu 21108813-Jan-15 0:09 
GeneralMy vote of 5 Pin
Joezer BH31-Oct-13 5:43
professionalJoezer BH31-Oct-13 5:43 
GeneralMy vote of 5 Pin
Manoj Kumar Choubey21-Feb-12 23:29
professionalManoj Kumar Choubey21-Feb-12 23:29 
QuestionMerging polygons Pin
Patrick Blackman29-Jul-11 9:01
professionalPatrick Blackman29-Jul-11 9:01 
GeneralWrong Polygon Geometry Detection Pin
gomezmateu.oscar29-Sep-10 22:30
gomezmateu.oscar29-Sep-10 22:30 
GeneralVery nice Pin
majoxx11-Apr-09 0:07
majoxx11-Apr-09 0:07 
GeneralText in polygon Pin
saradasrg22-Dec-08 2:01
saradasrg22-Dec-08 2:01 
GeneralDrawing a simple concave polygon... [modified] Pin
gracecm19-Nov-08 3:24
gracecm19-Nov-08 3:24 
Questionif lots of polygons are triangulated,it doesn't work normally. Pin
littleboyyyf27-Oct-08 18:22
littleboyyyf27-Oct-08 18:22 
SuggestionRe: if lots of polygons are triangulated,it doesn't work normally. Pin
Aram Azhari4-May-14 11:38
Aram Azhari4-May-14 11:38 
Generalmy neural triangulator for all polygons Pin
exterior11-Sep-08 11:47
exterior11-Sep-08 11:47 
QuestionCut Polygon Failure Pin
karatecoyote1-Jul-08 12:58
karatecoyote1-Jul-08 12:58 
GeneralHoles Pin
karatecoyote17-Apr-08 5:17
karatecoyote17-Apr-08 5:17 
GeneralRe: Holes Pin
Fiorentino18-May-08 6:12
Fiorentino18-May-08 6:12 
GeneralRe: Holes Pin
karatecoyote19-May-08 9:24
karatecoyote19-May-08 9:24 
GeneralRe: Holes Pin
Fiorentino20-May-08 1:30
Fiorentino20-May-08 1:30 
GeneralRe: Holes Pin
havana75-Jan-11 7:26
havana75-Jan-11 7:26 
QuestionReuse Pin
karatecoyote24-Mar-08 12:36
karatecoyote24-Mar-08 12:36 
GeneralComplex polygons Pin
Leonnik24-Oct-07 10:07
Leonnik24-Oct-07 10:07 
GeneralPointInsidePolygon bugs Pin
jdiegel26-Aug-07 15:45
jdiegel26-Aug-07 15:45 
Questiona bug Pin
sbenhar18-Jul-07 3:15
sbenhar18-Jul-07 3:15 
GeneralWrong trianulation for simple figure Pin
noi7612-Dec-06 6:58
noi7612-Dec-06 6:58 
GeneralRe: Wrong trianulation for simple figure Pin
noi7612-Dec-06 23:42
noi7612-Dec-06 23:42 

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.