3
$\begingroup$

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.

  • 0
    If you need a code here is snippet in C that calculate distance to triangle http://iquilezles.org/www/articles/triangledistance/triangledistance.htm2017-09-07

2 Answers 2

3

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

  • 0
    @jcubic This is a bad idea. As far as I understand your approch, it will not work well.2012-05-11
2

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.

  • 0
    True, but the algorithm provides mathematical insight into the problem even for just a point.2012-05-12