Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Nearest point on concave surface from point

Given a union of convex objects and a point p inside this union, how does one find the closest point on the (concave) surface of the union from p?

For what it's worth I can easily find the closest point on the surface of a single convex object, it's the union of several that's giving me problems.

EDIT: I'm terribly sorry, I meant the union of the objects and not the intersection :( Apologies to everyone who answered.

EDIT2: Here's a small image describing the situation courtesy AakashM, a is the closest point on the surface of A from O, b is the closest point on the surface of B from O and x is the point I'm actually looking for (O == p).

alt text

My objects are not polygonal objects but lines with radius (I think the term capsule is sometimes used for this but I don't know if this term is universally accepted).

like image 842
Andreas Brinck Avatar asked Jan 18 '10 14:01

Andreas Brinck


1 Answers

There may be a more efficient way, but the naive approach would be to simply find the closest point to p on each surface, then select the one with the smallest distance. Since p is inside the mutual intersection of all of the objects, this point is guaranteed to be on the intersection surface.

like image 165
ezod Avatar answered Oct 17 '22 15:10

ezod