How to take (N) -simple edges?

Question

In quickhall algo, you need to build a cone over many edges.

An edge is considered a spike with one vertex removed. It is required that adding a vertex to the edge forms a simplex, as if this vertex was simply replaced.

For example, when saving simplexes in the form of vrtices lists for a triangle defined with vertices {p0, p1, p2}, there are: {p1, p2}, {p2, p0}, {p0, p1} - in this index the order. Now, adding a new vertex p to the end of the list of vertices, new triangles: {p1, p2, p}, {p2, p0, p}, {p0, p1, p} They have the same orientation as the original triangle was oblique.

For a triangle, the edge opposite p1 has the reverse order of the remaining vertices. For a tetrahedron, this is for p0 and p2.

What is the right way to store edges, or the right way to find out when you need to reverse the order of the vertices?

Good. In general, storing a set of vertices is simply not enough to represent a simplex if its orientation matters. The same set can be equivalent simplexes with a different volume sign. The list can keep orientation, but it is not trivial to deduce it from the order. Thus, neither sets nor lists are a good solution (for representing both the simplex and its edges).

Answer 1

It is probably best to use a list or set of vertices to represent a simplex; the question is how to solve the order of the vertices. (since I am not completely sure of the exact requirement of an arbitrary-arbitrary quickhull, I will speak generally below ...)

If you alternately replace each vertex v[i] new point p , then the easiest way is to replace it with a replaced point. Thus, for the triangle {v0,v1,v2} you get the new triangles {p,v1,v2} , {v0,p,v1} and {v0,v1,p} .

If you want to change the order of the vertices (for example, so that p at the end), you must remember that replacing any two vertices will change the orientation of the simplex. So, to maintain orientation, you must perform an even number of swaps.

In the above example, replacing p with a finite vertex will change the orientation, unless p is a final vertex. You can fix this by replacing the first two vertices in this case. (note that this is the only solution only for 3-vertex simplexes - it is not applicable for 2-simplexes and one of the multiple solutions for N> 3-simplexes).

You can also look at it as a rotation of the list of vertices of the original 3-simplex. Unfortunately, this only works for odd-vertex simplexes. For a vertex list of size N rotation includes N-1 swaps, so for a simplex with an even number of vertices, the rotation will change orientation.

Answer 2

And the edge of the simplex has no orientation in itself.

Only the N-simplex in N-sizes determines the orientation. It is determined by the transverse product of N vectors pi-p0 (signed volume). For lower-dimensional simulations in a higher space, such a cross-product cannot be built.

For this problem (building new simplexes with edges of another), the edge can be represented by a (ordered) list of vertices and an index where you need to add a new point to make it on the same side as the remote vertex. Given the cyclical order of the list (not sure if it is universal), you can rotate it so that the index is either 0 or 1.