# Determine which of 8 points make up the 4 corners of a cube's face

I am working on a game program. I have an array of 8 points in 3d space $(X,Y,Z)$ that are the 8 corners of a cube whose $W=H=D$. The 8 points are listed in no particular order. For the sake of determining this algorithm, The cube's center is at the world origin, $(0,0,0)$ but the cube's orientation is not aligned with the Cartesian axis (it's arbitrarily rotated). I'd like to create 6 sets of $4$ points each that represent the faces of the cube but I'm stumped as to how to proceed

Any idea of an algorithm that would help me?

Pick a point $p$, calculate the distance from that point to all the others, three will be the same length and smaller than the other lengths. Call these three points $x_1$, $x_2$, $x_3$. Do the same for $x_1$, $x_2$, $x_3$. Each pair of those will share two points, one will be $p$ the other will be $y_{12}$, $y_{13}$, $y_{23}$ respectively. You just defined three sides by points. Now, pick the only remaining point that hasn't been named. Call it $q$. Run the above algorithm. Done.
• I could add that when you do your original calculation of distances, you already have info of what q is, and even just from there you can speed this up. This is probably the dirtiest algorithm, but writing this should be essentially trivial, which is why I suggested it. If you want an efficient one, I could try harder, but keep in mind that for a cube there is only 8 points, so its not like the speed will really matter, unless you are doing this to $n$ boxes... – BBischof Oct 28 '10 at 23:15
• In the case of a rectangular cuboid with $W \neq H \neq D$ (which isn't what was asked in the question, but I wanted to throw it out there anyway), the three closest points may not be adjacent to the $p$, but the closest two will be, and you can apply the above procedure to get one face of the cuboid. Then the other four vertices form the opposite face, and it's easy to reconstruct the rest from there. – Rahul Oct 28 '10 at 23:17