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

Question

我已经在我的程序中实现了多边形三角剖分算法。该算法首先采用 simple polygon ，描述为二维点/顶点，并将其拆分为 y-monotone pieces . 完成此操作后，该算法会将每个单调多边形 block 分割成三角形 block 。

我需要帮助的算法输入是一个顶点数组，按顺时针或逆时针顺序勾勒出一个 y 单调多边形。输出是所有边的集合，既有来自原始多边形的边，也有来自三角剖分算法添加的新边，以便将这个 y 单调 block 分割成三角形 block 。如果我只想绘制结果，这非常有用，因为可以只绘制每条边。

但是，这个边集合没有特定的顺序，我需要输出为 triangle strip 类型的数组。 或一个数组，其中每个三角形都由它的 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