How to take (N)-simplex edges?

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, w开发者_如何学运维hen 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).

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 point p, 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 p is 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 involves N-1 swaps, so for a simplex with an even number of vertices, a rotation will change the orientation.

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.