Триангуляция многоугольников на C#

Выполнение триангуляции многоугольника при помощи вырезания ушей на C#

Предпосылки и теория

Многоугольник – это один из самых важных объектов, с которым приходится иметь дело при визуализации 2D/3D графики или обработке вычислительной геометрии. Так как многоугольник может быть очень сложным, на реализацию могут быть наложены некоторые ограничения. Например, OpenGL непосредственно не поддерживает рисование вогнутого многоугольника. Когда вы заставляете OpenGL рисовать невыпуклый закрашенный многоугольник, он может быть нарисован не так, как вы ожидаете. В большинстве случаев приходится разбивать сложный многоугольник на составляющие его простые фигуры, такие как набор треугольников, чтобы упростить задачу.

В 1975 Гарри Мейстерс вывел теорему о двух ушах, доказавшую, что эта попытка всегда выполнима: За исключением треугольников, каждый простой многоугольник имеет как минимум два непересекающихся уха (треугольника).

Простой многоугольник – это многоугольник, у которого нет двух пересекающихся не следующих друг за другом грани. Если диагональ (Pi-1, Pi+1), которая перекрывает (связывает) Pi, полностью лежит в многоугольнике, то вершина Pi называется ухом. Чтобы разделить многоугольник при помощи нахождения ушей, полезна следующая лемма: Если выпуклая вершина Pi не является ухом, то треугольник, образуемый Pi-1, Pi, Pi+1, содержит вогнутую вершину.

Рисунок 1. Многоугольник и уши

Приведенный ниже код демонстрирует алгоритм времени O(kn) для нахождения ушей и разделения простого многоугольника на треугольники.

Рисунок 2. Многоугольник

Рисунок 3. Многоугольник, разбитый на треугольники

Структура программы и код примера

На основании теории Гарри Мейстерса у многоугольника всегда можно найти ухо. Если от этого многоугольника отрезать ухо, то будет получен новый многоугольник, имеющий на одну вершину и треугольник меньше. Повторяйте этот процесс с новым многоугольником до тех пор, пока у многоугольника не останется только три вершины. Блок-схема представлена ниже:

Рисунок 4. Блок-схема программы разбиения многоугольника на треугольники

Эта программа написана в C#.NET и разработана при помощи MS Visual Studio 2003. Чтобы использовать объектно-ориентированную технологию программирования и сделать код многократно-используемым, программу построили на базе следующих классов:

Рисунок 5. Диаграмма классов программы

Пространство имен PolygonCuttingEarInterface

frmCuttingEars – это пользовательский интерфейс, который получает заданные пользователем вершины многоугольника, создает объект CPolygonShape и передает данные объекту, затем возвращает расчетные данные и показывает серию треугольников пользователю.

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

CpolygonShape – это класс, выполняющий все вычисления: нахождение уха многоугольника, отрезание уха путем удаления вершины и создание измененного многоугольника. Этот процесс будет повторяться до тех пор, пока новый многоугольник не окажется треугольником.

 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:

Это пространство имен включает много основных классов вычислительной геометрии и множество функций, которые могут быть повторно использованы для других проектов.

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){};
  … …}
 

Выполнение программы

Чтобы увидеть демонстрацию, сначала выберите способ задания вершин многоугольника: можно использовать встроенные тестовые данные или набрать вершины, щелкая мышкой по панели, затем нарисовать внешние лени(?) многоугольника, щелкая мышкой по кнопке Draw Polygon (Нарисовать многоугольник); Нажатие на кнопку Cut Ear (Вырезать ухо) запустит триангуляцию многоугольника, составляющие многоугольник треугольники будут окрашены на экране.

Чтобы сбросить программу и запустить следующую демонстрацию, нажмите кнопку Clean Screen (Очистить экран), и вы сможете начать демонстрацию заново.

Можно использовать кнопку, главное меню, контекстное меню или кнопку панели инструментов для запуска программы, как вам удобно. Для получения помощи или более подробной информации об этой программе используйте меню помощи или смотрите всплывающую подсказку каждого элемента управления, перемещая курсор мыши над ним.

Рисунок 6. Заданный пользователем многоугольник

Рисунок7. Разбитый на треугольники многоугольник

Не стесняйтесь изучать и использовать приведенный здесь исходный код. Если у вас есть какие-то предложения, сообщите о них, и код будет обновлен.

Скачать демоверсию проекта - 26 Кб

Скачать исходники - 54 Кб