Nearest point on concave surface from point

Question

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).

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).

Answer 1

I guess you'll have to calculate the closest points on the surface all single objects (gives you n points), then check for each point, if its inside all other objects (so its part of the surface of the intersection), and than find the closest one to p.

This algorithm uses the fact, that a point is on the surface of the intersections of n convex objects, if it's on the surface of one of these objects and inside all other objects (the surface of the intersection is made of little pieces of surfaces of the intersected objects...)

Answer 2

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.

Answer 3

I don't know the tool and data structure you're working on, but for example in matlab when you intersect n polygons the result is a new polygon of intersection, and if you can easily find the closest point on the surface of a single convex object, then if the intersection polygon is concave you can triangulate for getting your convex objects.

Answer 4

(for the Union version)

Every concave point of the union is at the intersection of the boundary of two of your objects. So you can just compute all such intersection points, test if they are on the boundary of your union, and pick the closest to p.

You need more than that, though, as in the following situation (union of 2 rectangles)

+--------------------+
|                    |
+--------------------+
|         p          |
|                    |
|                    |
|                    |
|                    |
+--------------------+

The result you want is not a boundary intersection point, and it isn't the closest point to p for either rectangle individually. I'm not sure how to handle that case.