如何取(N)-单纯形边？
在 Quickhull 算法中，需要在一组边上构建一个圆锥体。
一条边被认为是删除了一个顶点的次单纯形。 要求将顶点添加到边将形成单纯形，就好像该顶点刚刚被替换一样。
例如，当将单纯形存储为 vrtice 列表时，对于用顶点 {p0,p1,p2} 定义的三角形，边为：{p1,p2},{p2,p0},{p0,p1} - 按此索引顺序。 现在，当在边顶点列表的末尾添加新顶点 p 时，新三角形为： {p1,p2,p},{p2,p0,p},{p0,p1,p} 它们具有与原始三角形相同的方向三角形是倾斜的。
对于三角形，与 p1 相反的边与剩余顶点的顺序相反。 对于四面体，它适用于 p0 和 p2。
存储边的正确方法是什么，或者找出何时反转顶点顺序的正确方法是什么？
好的。 一般来说，如果顶点的方向很重要，那么存储顶点集合不足以表示单纯形。相同的集合可以表示具有不同体积符号的等价单纯形。 列表可以保留方向，但仅从顺序导出它并不简单。因此，单独的集合和列表都不是好的解决方案（表示单纯形及其边）。
In quickhull algo, there's need to build a cone upon set of edges.
An edge is thought as subsimplex with one vertex removed.
It is required, that adding a vertex to an edge will form a simplex, as if that vertex was just replaced.
For instance, when storing simplices as lists of vrtices, for triangle defined with vertexen {p0,p1,p2} edges are: {p1,p2},{p2,p0},{p0,p1} - in this index order.
Now, when adding new vertex p at the end of edge vertex list, new triangles are: {p1,p2,p},{p2,p0,p},{p0,p1,p} They have the same orientation as if original triangle was slanted.
For triangle, edge opposite to p1 has reversed order of remaining vertices.
For tetrahedron, it is for p0 and p2.
What is proper way of storing edges, or proper way to find out when to reverse vertices order?
Okay.
In general, storing vertex set is just not enough to represent a simplex, if its orientation matters. The same set can represent equivalent simplices with different sign of volume. A list can preserve orientation, but it's not trivial to derive it just from order. Thus, neither sets nor lists alone are not good solution (to represent both simplex and their edges).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
最好使用顶点列表或元组来表示单纯形；问题是如何决定顶点的顺序。 （因为我不完全确定任意维快速船体的确切要求，所以我将在下面概括地说...）
如果您用一个新点依次替换每个顶点
v[i]p，最简单的一致做法就是用它替换它所替换的点。因此，对于三角形{v0,v1,v2}，您将得到新的三角形{p,v1,v2},{v0,p,v1}< /code> 和{v0,v1,p}。如果您想重新排序顶点（例如，使
p位于末尾），那么您应该记住交换任何两个顶点都会反转单纯形的方向。因此，为了保持方向，您必须进行偶数次交换。在上面的示例中，将 p 与最终顶点交换将反转方向，除非 p 已经是最终顶点。在这种情况下，您可以通过交换前两个顶点来解决此问题。 (注意，这是仅针对3顶点单纯形的唯一解——它不适用于2-单纯形，并且是N>3-单纯形的多个解之一)。
您还可以将其视为旋转原始 3-单纯形的顶点列表的问题。不幸的是，这仅适用于奇数顶点单纯形。对于大小为
N的顶点列表，旋转涉及N-1交换，因此对于具有偶数个顶点的单纯形，旋转将改变方向。It is probably best to use a list or tuple of vertices to represent a simplex; the question is how to decide the order of the vertices. (as I am not entirely certain of the exact requirements of an arbitrary-dimentional quickhull, I will speak generally below...)
If you are replacing each vertex
v[i]in turn with a new pointp, the simplest consistent thing to do is to substitute it for the point it replaces. Thus, for triangle{v0,v1,v2}, you will get new triangles{p,v1,v2},{v0,p,v1}, and{v0,v1,p}.If you want to reorder the vertices (e.g., so that
pis at the end), then you should remember that swapping any two vertices will reverse the orientation of the simplex. So, to maintain the orientation, you must do an even number of swaps.In the above example, swapping p with the final vertex will reverse the orientation, unless p is already the final vertex. You can fix this by swapping the first two vertices in that case. (note that this is a unique solution only for 3-vertex simplices -- it is not applicable for 2-simplices, and one of multiple solutions for N>3-simplices).
You could also look at this as a matter of rotating the vertex list of the original 3-simplex. Unfortunately, this only works for odd-vertex simplices. For a vertex list of size
N, rotation involvesN-1swaps, so for a simplex with an even number of vertices, a rotation will change the orientation.并且单纯形的边本身没有方向。
只有 N 维中的 N 单纯形具有定义的方向。
它由 N 个向量 pi-p0（有符号体积）的叉积确定。
对于高维空间中的低维拟形，无法建立这种叉积。
对于这个特殊任务（用另一个边构建新的单纯形），边可以由顶点（有序）列表和索引来表示，在该索引中添加新点以使其与被删除的顶点位于同一侧。
考虑到列表的循环顺序（不确定它是否普遍有效），可以旋转它以使索引为 0 或 1。
And edge of a simplex does not have an orientation by itself.
Only N-simplex in N-dimentions has defined orientation.
It is determined by cross-product of N vectors pi-p0 (signed volume).
For lower dimentional simlices in higher dimentional space such cross-product cannot be built.
For this patricular task (building new simplices with edges of another) an edge can be represented by an (ordered) list of vertices and an index where to add new point to make it on the same side as was removed vertex.
Considering cycling order of list (not sure it is universally valid), it could be rotated so that index is either 0 or 1.