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

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.

Solution 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$.

Solution 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.