Given a random point and a cube, how can I determine the distance from that point to the furthest possible point on the cube

3deuclidean-geometrygeometry

Given a random point in space ( $\vec{p}$ ), I am trying to figure out how to calculate the distance to the furthest point on an axis-aligned cube/cuboid from that other point. This cube is defined by two corners which we will call $\vec{c_{l}}$ and $\vec{c_{h}}$. It is guaranteed that $\vec{c_l}$ is the corner on the cube with the lowest values for each of its axes and $\vec{c_h}$ is the corner on the cube with the highest values for each of its axes.

For what it's worth, I've figured out (I think) how to calculate the closest point on the cube to $\vec{p}$. The equation I've figured out for that is: $$min(max(\vec{p}, \vec{c_l}), \vec{c_h})$$ Despite figuring this out, I cannot figure out how to calculate the furthest point (or the distance to it, which is my ultimate goal).

To help illustrate what I am trying to do, here is a diagram I rendered. The red sphere is the closest point on the cube to $\vec{p}$.

the image

Best Answer

Let the cube be defined by

$$x_1<x<x_3, \ \ \ \ y_1<y<y_3, \ \ \ \ z_1<z<z_3.$$

Let $M (x,y,z)$ be the coordinates of the given point.

The farthest point in the cube is necessarily a vertex.

First solution : compute the 8 distances to the 8 vertices $(x_i,y_j,z_k)$ and choose the vertex realizing the maximum.
Second solution (with much less computation) :

Let $$x_2=(x_1+x_3)/2, \ \ y_2=(y_1+y_3)/2, \ \ z_2=(z_1+z_3)/2$$

Algorithm : Just test the signs of ($(x-x_2),(y-y_2),(z-z_2)$).

Indeed, to each combination of signs $(-,-,-), (-,-,+), \cdots (+,+,+))$ is associated a precise vertex (an association that has to be computed beforehand, resulting in a simple "hash table").

Related Solutions

[Math] Minimal distance to a cube in 2D and 3D from a point lying outside

For an axis aligned cube, there are nice tricks. Consider, for example, the axis aligned cube with corners $(\pm 1,\pm 1,\pm 1)$ (after a scaling and a shift, everything reduces to this case).

For a point $(x,y,z)$:

If $|x|\leq 1$, $|y|\leq 1$ and $|z|>1$, then the distance is $|z|-1$ (the face is closest).
If $|x|\leq 1$, $|y|>1$, and $|z|>1$, then the distance is $\sqrt{(|y|-1)^2+(|z|-1)^2}$ (the edge is closest).
If $|x|>1$, $|y|>1$, and $|z|>1$, then the distance is $\sqrt{(|x|-1)^2+(|y|-1)^2+(|z|-1)^2}$ (the vertex is closest).

All other cases are similar. To visualize what is going on, draw a square, but extend the edges into (infinite) lines. This breaks up the space outside the box into $8$ regions, all points in each region are closest to the same edge or point. Now, doing the same thing in three dimensions results in $26$ regions and you need to figure out which region you're in.

Pseudocode:

 if |x|<=1
 {
      if |y|<=1
           d=|z|-1
      else
      {
           if |z|<=1
                 d=|y|-1
           else
                 d=sqrt((|y|-1)^2+(|z|-1)^2)
      }
 }
 else
 {
      if |y|<=1
      {
           if |z|<=1
                d=|x|-1
           else
                d=sqrt((|x|-1)^2+(|z|-1)^2)
      }
      else
           if |z|<=1
                d=sqrt((|x|-1)^2+(|y|-1)^2)
           else
                d=sqrt((|x|-1)^2+(|y|-1)^2+(|z|-1)^2)
      }
 }

Also as @YvesDaoust mentions in the comments, this can be rewritten as $$ \sqrt{\max\{0,|x|-1\}^2+\max\{0,|y|-1\}^2+\max\{0,|z|-1\}^2} $$ although, after unpacking the maximums, you get, essentially, the series of inequalities above.

Find shortest distance from triangle to point in 2D space

You find the equations of the 3 lines that make the triangle: $$m = \frac {y_2-y_1} {x_2-x_1} \\ y - y_1 = m(x-x_1)$$ Then you can simplify, and use this formula to find distance between $(-4,7)$ and each line, for a line of equation $ax+by+c=0$: $$\operatorname{distance}= \frac {ax+by+c} {\sqrt {a^2 + b^2}}$$

Best Answer

Related Solutions

[Math] Minimal distance to a cube in 2D and 3D from a point lying outside

Find shortest distance from triangle to point in 2D space

Related Question