Nearest point on concave surface from point

Question

Given the union of convex objects and the point p inside this union, how to find the nearest point on the (concave) surface of the union of p ?

Why can I easily find the closest point on the surface of one convex object, this is the union of several that give me problems.

EDIT: I'm sorry, I was referring to a union of objects, not an intersection :( I apologize to everyone who answered.

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

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

Answer 1

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

Answer 2

I think you will have to calculate the closest points on the surface of all individual objects (gives you n points), and then check each point if it is inside all other objects (so that it is part of the intersection surface), and find the closest to p .

This algorithm uses the fact that a point is on the intersection surface of n convex objects if it is on the surface of one of these objects and inside all other objects (the intersection surface consists of small pieces of surfaces of intersecting objects ...)

Answer 3

I don’t know the tool and data structure that you are working on, but, for example, in Matlab, when you intersect n polygons, the result is a new intersection polygon, and if you can easily find the nearest point on the surface of one convex object, then if the polygon The intersection is concave, you can triangulate to get your convex objects.

Answer 4

(for Union version)

Each concave joining point is at the intersection of the border of your two objects. Thus, you can simply calculate all such intersection points, check if they are on the border of your union, and select the one closest to p.

You need more than this, as in the following situation (combining two rectangles)

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

The result you want is not a border crossing point, and it is not the closest point to p for each rectangle separately. I am not sure how to handle this.