半边数据结构delaunay三角剖分

Question

我正在写半边数据结构的Python delaunay三角剖分。

另外，在三角测量算法中，我尝试只存储半边。我从边缘列表中检索三角形。

但是，这是相当多余的，对吧？我有更多的边缘比描述三角形所需要的更多，因为一个三角形是由一个边缘定义的，并且由于每个边缘都有指向下一个边缘的指针，因此可以轻松地走过。

1是否可以实施Watson算法delaunay只存储一个半边界列表？这会难以走过吗？

在沃森的算法步骤来确定腔内的边缘，我想走在边上，并找到那些在三个以上不同的半边的末端的边缘顶点。

2 /这个属性'多于两个边缘在这个顶点结束'正确的一个适当的标准来放弃Bowyer Watson算法中的边缘吗？

对于遍历网格，我会遍历每个半边。所以，我正在边缘工作，而不是三角形。我在不使用'next'属性的情况下穿过网格，这听起来不太好。

3 /走过网格中三角形的方式是什么，存储为边缘列表？或者如何更好地存储网格，以便让步行更容易？

谢谢！

Answer 1

半边数据结构很好！使用一张面的列表和一个边缘列表，这可能就足够了。