Take the 2-minute tour ×
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.

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.

share|improve this question
    
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? –  no identity 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

2 Answers 2

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

enter image description here

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} $$

share|improve this answer
    
@jcubic Have you tested this approach? –  no identity 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. –  no identity 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. –  no identity 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.

share|improve this answer
    
This is a sledgehammer, the OP asks for distance between convex set and a $\it{point}$ –  no identity 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

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.