Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
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
2  
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 Narain Oct 28 '10 at 23:17
@Rahul, yes you are correct, nice adaption for a slightly harder case. – BBischof Oct 28 '10 at 23:23
Thanks BBischof! – Steve H Oct 30 '10 at 0:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.