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
    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?2012-05-11
  • 0
    Yes it's a convex hull. Point X is outside and not the part of convex. I just need solution that will work.2012-05-11
  • 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 Have you tested this approach?2012-05-11
  • 0
    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.2012-05-11
  • 0
    Projection should be on the whole plane $\pi$. It can occur inside or outside of triangle.2012-05-11
  • 0
    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.2012-05-11
  • 0
    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.2012-05-11
  • 0
    @jcubic I've added formula for computation of projection point $P$2012-05-11
  • 0
    your soltuion give me an idea about ortogonal projection of all points from convex hull into planes that lay on axis and then try to interpolate those points and then get the minimun length from the point to f(t) -> (R, R). I ask another question about 2d interpolation http://math.stackexchange.com/questions/144029/is-it-posible-to-interpolate-convex-hull-in-2d-space2012-05-11
  • 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
    This is a sledgehammer, the OP asks for distance between convex set and a $\it{point}$2012-05-11
  • 0
    True, but the algorithm provides mathematical insight into the problem even for just a point.2012-05-12