computational-geometry - 如何取(N)-单纯形边？

Question

在 quickhull 算法中，需要在一组边上构建一个锥体。

边被认为是去除了一个顶点的亚单纯形。
需要在边上添加一个顶点将形成一个单纯形，就好像该顶点刚刚被替换一样。

例如，当将单纯形存储为 vrtices 列表时，对于用顶点 {p0,p1,p2} 定义的三角形，边是:{p1,p2},{p2,p0},{p0,p1} - 按照这个索引顺序。
现在，当在边顶点列表的末尾添加新顶点 p 时，新三角形是: {p1,p2,p},{p2,p0,p},{p0,p1,p} 它们的方向与原始三角形相同三角形是倾斜的。

对于三角形，与 p1 相对的边的剩余顶点顺序相反。
对于四面体，它是针对 p0 和 p2。

什么是存储边的正确方法，或找出何时反转顶点顺序的正确方法？

好的。
一般来说，如果方向很重要，存储顶点集不足以表示单纯形。同一个集合可以表示具有不同体积符号的等效单形。列表可以保留方向，但仅从顺序中导出它并非易事。因此，单独的集合和列表都不是好的解决方案(同时表示单纯形及其边)。

Answer 1

最好使用顶点列表或元组来表示单纯形；问题是如何决定顶点的顺序。 (因为我不完全确定任意尺寸快船的确切要求，我将在下面一般性地讲......)

如果您要替换每个顶点 v[i]依次为新点p ，最简单的一致做法是用它替换它所替换的点。因此，对于三角形 {v0,v1,v2} , 你会得到新的三角形 {p,v1,v2} , {v0,p,v1} , 和 {v0,v1,p} .

如果您想对顶点重新排序(例如，使 p 位于末尾)，那么您应该记住，交换任意两个顶点将反转单纯形的方向。因此，为了保持方向，您必须进行偶数次交换。

在上面的示例中，将 p 与最终顶点交换将反转方向，除非 p 已经是最终顶点。在这种情况下，您可以通过交换前两个顶点来解决此问题。 (请注意，这是仅适用于 3-顶点单纯形的唯一解决方案——它不适用于 2-单纯形，以及 N>3-单纯形的多个解决方案之一)。

您也可以将其视为旋转原始 3-单纯形的顶点列表的问题。不幸的是，这只适用于奇数顶点单纯形。对于大小 N 的顶点列表, 轮换涉及 N-1交换，因此对于具有偶数个顶点的单纯形，旋转将改变方向。