How to order 8 vertices that are known to belong to a cuboid?

Question

Given 8 points in $\mathbb{R}^3$ and the prior knowledge that these points form the vertices of a cuboid, what is a computationally efficient way to order them?

When I say "cuboid" I refer to the set of all achievable shapes when starting from the canonical unit cube centred on the origin and applying independent scaling in x,y, z, then rigid rotation, then translation.

When I say "order", I mean that I want to know the relationships between all the vertices. For instance, with the ordering convention below, I can always say that vertex 1 is connected to vertices 2, 4, and 5 via an edge, and this remains true no matter what cuboid preserving transformation I apply to the points.

(furthest face from the viewpoint is shaded)

I've come up with a bunch of ideas that don't seem elegant, like computing euclidian distances and computing dot products of vectors formed by pairwise combinations of the points. I'm just wondering if there is an "elegant trick" out there.

Answer 1

The following method works for arbitrary parallelepipeds. The faces don't have to be rectangular.

Pick an arbitrary non-zero vector $u$ and compute the dot product of $u$ with each of the eight corner vectors. Unless you are unlucky, the eight dot products will all be different. Now the least dot product and the greatest dot product correspond to corners that are diagonally opposite each other along the line through the body center. The same goes for the second least and second greatest, the third least and third greatest, and so on. So you pair up the corners in this way.

Now translate so that the corner $a$ with least dot product is at the origin. The corresponding change in the dot products is to subtract the least dot product from all of them, so that the least dot product $u\cdot a$ is now $0$ and all others are positive. The two smallest non-zero dot products correspond to corners that are neighbors of $a$; the corners paired with these two are non-neighbors of $a$.

This leaves one pair. One member of that pair will be the sum of the two corners identified as neighbors of $a$ and the other member will be the third neighbor of $a$.

That the two smallest positive dot products correspond to neighbors of $a$ follows from the positivity of the dot products: if $b$, $c$, and $d$ are the neighbors of $a$ (which has been shifted to zero) and $d$ has the greatest dot product among these, then $(b+c)\cdot u$, $(b+d)\cdot u$, $(c+d)\cdot u$, and $(b+c+d)\cdot u$ are certainly all greater than both $b\cdot u$ and $c\cdot u$.

Answer 2

Building on Will's answer, a simple approach if the cuboid is known to be a cube. Take one point, call it 1, and two further points A and B as before. Define 1 to be the origin for vectors $a$ and $b$ to A and B. Let $c = b - a$.

Calculate $\left\|a\right\|:\left\|b\right\|:\left\|c\right\|$. This can be:

• $1:1:1$
  Both A and B are 2-connected to 1. The cube has side $\frac{\left\|a\right\|}{\sqrt{2}}$.

• $1:1:\sqrt{2}$
  Then the triangle formed by 1, A and B is wholly contained in one face (A and B are 1-connected to 1 or A is 1-connected and B is 2-connected on the same face). Wherever the long side is distinguishes the two cases. The cube has side length $\left\|a\right\|$

• $1:\sqrt{2}:\sqrt{3}$. The triangle contains opposite corners of the cube (A or B is 3-connected to 1). The cube has side length $\left\|a\right\|$.

• Permutations of the above.

It remains to determine the orientation of the faces, which is done by checking against one further point.

So we only have to select three points and calculate three lengths. Comparing the ratios of the lengths directly gives us the the configuration of the cube, one further point yields the orientation.

Answer 3

Let us say that two points are:

• 1-connected if they define an edge in your cube (e.g. 1 and 2).
• 2-connected if they are opposite corners of a face (e.g. 1 and 3).
• 3-connected if they are opposite corners of the cube (e.g. 1 and 7).

Pick a point, which we will call 1. Pick two further (distinct) points. These can be

• both 1-connected (with vertex 1). Then they define a face of the cube and you have all further relationships, because the side length of the face yields the offset to the remaining points.
• one is 1-connected and one is 2-connected. These either define a face or an interior triangle of the cube where one edge is the cube diagonal and 1 is not on this edge.
• one is 1-connected and one is 3-connected. The two vertices define a face and the 1-connected edge is perpendicular to this face. The interior triangle is formed by the cube diagonal, one edge (connected to 1) and a face diagonal.
• both are 2-connected. The two vertices define a face and their diagonals with 1 define two further faces. They also define a tetrahedron.
• one is 2-connected and one is 3-connected. The two vertices are on the same edge (not connected to one)and the interior triangle is formed by this edge, a cube diagonal (containing 1) and a face diagonal.

By looking at distances and the interior triangles you can determine which case applies and derive the structure of the cube.

Although this only looks at three points (plus possibly more to check which configuration we have) I think it is a lot more complicated than the Euclidean distance method described here.