# How to calculate distance between point and object in 3d space

I have object in 3d space created from points $P_i(x, y, z)$ from which I can create triangles, and I need to calulate distance from point X to this object.

I try to take 3 points from smallest distance and calulate height of tetrahedron created from this 3 points and X, but this will be not the distance from the object.

So my question is how to calculate this distance.

-
There are several problems here. Is it true that object constructed from points $P_i$ is convex? Can you say something special about location of points $P_i$? Can you ensure that $X$ is not in convex hull of points $P_i$? How fast calculation should be? – Norbert May 11 '12 at 14:22
Yes it's a convex hull. Point X is outside and not the part of convex. I just need solution that will work. – jcubic May 11 '12 at 19:59

I don't know whether this is a correct solution. But I will make a try.

Let $P_1$, $P_2$, $P_3$ be three closest points to $X$. Consider plane $\pi$ containing $P_1$, $P_2$, $P_3$.

Let $P$ be the orthogonal projection of $X$ on $\pi$. If $P$ is inside triangle $P_1P_2P_3$ then the distance is $PX$, otherwise $\min(\mathrm{dist}(P_1,X),\mathrm{dist}(P_2,X),\mathrm{dist}(P_3,X))$. Here is a picture, for clarification

Well, how to determine that $P$ is inside $P_1P_2P_3$? Just check the equality  $$\mathrm{area}(P_1P_2P_3)= \mathrm{area}(PP_2P_3)+\mathrm{area}(P_1PP_3)+\mathrm{area}(P_1P_2P)$$

In order to determine projectoin $P$ you can use the following formula $$P=X+tN$$ where $$N=[P_3P_1,P_2P_1],\qquad t=\frac{\langle P_1-X,N\rangle}{\langle N,N\rangle}$$

-
@jcubic Have you tested this approach? – Norbert May 11 '12 at 21:00
I think this solution is the same as mine using height of tetrahedron, where P is inside triangle. I think that soltion need to take into consideration the curve of the convex. – jcubic May 11 '12 at 21:05
Projection should be on the whole plane $\pi$. It can occur inside or outside of triangle. – Norbert May 11 '12 at 21:07
I think that my solution is not the same as yours, because I consider two cases. If you want a can perform example where my solution works and yours doesn't. – Norbert May 11 '12 at 21:10
Yes now I see, My solution will be wrong when projection will be outside tirangle. Thanks for your solution, now I need to calulate it ousite projection. – jcubic May 11 '12 at 21:15

Use the GKJ algorithm.

A good online tutorial including pictures and code snippets is here:

http://entropyinteractive.com/2011/04/gjk-algorithm/

A good video explanation of the concept is here:

http://mollyrocket.com/849

The basic principle is that the spatial relationship between 2 convex objects can be studied by considering the properties of their minkowski difference.

-
This is a sledgehammer, the OP asks for distance between convex set and a $\it{point}$ – Norbert May 11 '12 at 21:55
True, but the algorithm provides mathematical insight into the problem even for just a point. – Nick Alger May 12 '12 at 0:10