算法将边缘集合转换为三角形集合

Question

我已经在程序中实现了多边形三角算法。该算法首先采用一个简单的多边形，被描述为2D点/顶点，然后将其分成Y-单酮部分。完成此操作后，算法然后将每个单调多边形片取分成三角形。

我需要帮助的算法的输入是一系列顶点，以顺时针或逆时针顺序概述了y-单音多边形。该输出都是所有边缘的集合，包括原始多边形，也是三角算法添加的新边缘的集合，以便将此Y-单调件分为三角形零件。如果我只想绘制结果，则可以很好地绘制每个边缘。

但是，这个边的集合没有特定顺序，我需要输出是一个类型的三角形条或的数组，其中每个三角形简单地由3个顶点描述(示例： [a1，a2，a3，b1，b2，b3] ，因为我们有三角形 a 和三角形 b (。

是否有任何常规算法或任何其他方法可以帮助我解决这个问题？速度并不重要，但我更喜欢快速解决方案。

这是用于更好地理解我的问题的程序的伪代码示例：

class Vertex {
 var point;
 var index;
 init(x,y,index){
   point = (x,y)
   self.index = index
 }
}
class Edge {
 var from; // of type Vertex
 var to; // of type Vertex
 init(from, to){
  self.from = from
  self.to = to
 }
}

呼叫getMonotonePiecesOfPolygon(polygon)的调用可以生成许多具有这些顶点和边缘的单调多边形零件之一：

var vertex0 = Vertex(x0,y0,0)
var vertex1 = Vertex(x1,y1,1)
var vertex2 = Vertex(x2,y2,2)
var vertex3 = Vertex(x3,y3,3)
var edge0 = Edge(vertex0, vertex1)
var edge1 = Edge(vertex1, vertex2)
var edge2 = Edge(vertex2, vertex3)
var edge3 = Edge(vertex3, vertex4)

这可能对应于这样的矩形：

         edge0
       0------1
       |      |
 edge3 |      | edge1
       |      |
       3------2 
         edge2

然后，我们可以在数组中提供这些边缘，然后将多边形分为三角形，然后使用三角形方法" makemonotonepolygonintotrianglepieces(('

var edgesArray = [edge0,edge1,edge2,edge3]  
var edgesArray = makePolygonIntoTrianglePieces(edgesArray)

现在edgesArray看起来像这样：

edgesArray == [edge0,edge1,edge2,edge3,newEdge1]

其中

newEdge1.from == vertex0
newEdge1.to == vertex2

，如果我们要画每个边缘，它将对应于这样的多边形：

         edge0
       0------1
       |     |
 edge3 |     | edge1
       |     |
       3------2 
         edge2

现在，这是我问题要解决的部分。我需要一个看起来像这样的数组：

var triangles = [
                 vertex0,vertex3,vertex2, 
                 vertex0,vertex2,vertex1
                ]

或使用三角条(每个三角形由一个新的顶点描述，并从上一个三角形中描述(：

var triangles = [
                 vertex3, vertex2, vertex0,
                 vertex1
                ]  

Answer 1

在您在其中一个注释中指的书的第2章中，它们提出了一个数据结构，称为双连接边缘列表(dcel(。DCEL：S用于存储平面细分，例如三角剖分。根据您的写作，我认为这可能是您要寻找的。

https://en.wikipedia.org/wiki/doubly_connected_edge_list