Point closest to combined geometric shapes (compound shape)

Question

I have a single point and a set of shapes. I need to know if the point is contained within the compound shape of those shapes. That is, where all of the shapes intersect.
But that is the easy part. If the point is outside the compound shape I need to find the position within that compound shape that is closest to the point.

These shapes can be of the type:

• square
• circle
• ring (circle with another circle cut out of the center)
• inverse circle (basically just the circular hole and a never ending fill outside that hole, or to the end of the canvas is there must be a limit to its size)
• part of circle (as in a pie chart)
• part of ring (as above but
• line

The example below has an inverted circle (the biggest circle with grey surrounding it), a ring (topleft) a square and a line. If we don't consider the line, then the orange part is the shape to constrain to. If the line is taken into account then the saturated orange part of the line is the shape to constrain to.

The black small dots represent the points that need to be constrained. The blue dots represent the desired result. (a 1, b 2 etc.) Point "f" has no corresponding constrained result, since it is already in the orange area. For the purpose of this example, only point "e" is constrained to the line, all others are constrained to the orange orange area.

If none of the shapes would intersect, then the point cannot be constrained. If the constraint would consist of two lines that cross eachother, then every point would be constrained to the same position (the exact position where the lines cross).

I have found methods that come close to this, but none that I can combine to produce the above functionality. Some similar questions that I found:

Points within a semi circle What algorithm can I use to determine points within a semi-circle?

Point closest to MovieClip Flash: Closest point to MovieClip

Closest point through Minkowski Sum (this will work if I can convert the compound shape to polygons) http://www.codezealot.org/archives/153

Select edge of polygon closest to point (similar to above) For a point in an irregular polygon, what is the most efficient way to select the edge closest to the point?

PS: I noticed that the orange area may actually come across as yellow on some screens. It's the colored area in any case.

Answer 1

This isn't much of an answer, but it's a bit too long to fit into a comment ...

It's tempting to think, and therefore to advise you, to find the nearest point in each of the shapes to the point of interest, and to find the nearest of those nearest points.

BUT

The area you are interested in is constructed by union, intersection and difference of other areas and there will, therefore, be no general relationship between the closest points of the original shapes and the closest point of the combined shape. If you understand what I mean. For example, while the closest point of A union B is the closest of the set {closest point of A, closest point of B}, the closest point of A intersection B is not a simple function of that same set; at least not for the general case.

I suggest, therefore, that you are going to have to compute the (complex) shape which represents the area of interest and use one of the algorithms you've already discovered to find the closest point to your point of interest.

I look forward to someone much better versed in computational geometry proving me wrong.

Answer 2

Let's call I the intersection of all the shapes, C the contour of I, p the point you want to constrain and r the result point. We have:

• If p is in I, then r = p
• If p is not in I, then r is in C. So r is the nearest point in C to p.

So I think what you should do is the following:

1. If p is inside of all the shapes, return p.
2. Compute the contour C of the intersection of all the shapes, it is defined by a list of parts (segments, arcs, ...).
3. Find the nearest point to p in every part of C (computed in 2.) and return the nearest point among them to p.

Answer 3

I've discussed this question at length with my brother, and together we came to conclude that any resulting point will always lie on either the point where two shapes intersect, or where a shape intersects with the line from that shape perpendicular to the original point.

In the case of a circular shape constraint, the perpendicular line equals the line to its center. In the case of a line shape constraint, the perpendicular line is (of course) the line perpendicular to itself. In the case of a rectangle, the perpendicular line is the line perpendicular to the closest edge. (And the same, theoretically, for complex polygon constraints.)

So a new approach (that I'll have to test still) will be to:

1. calculate all intersecting (with a shape constraint or with the perpendicular line from the original point to the shape constraint) points
2. keep only those that are valid: that lie within (comply with) all constraints
3. select the one closest to the original point

If this works, then one more optimization could be to determine first, which intersecting points are nearest and check if they are valid, and then work outward away from the original point until a valid one is found.

If this does not work, I will have another look at the polygon clipping method. For that approach I've come across this useful post:
Compute union of two arbitrary shapes
where clipping complex polygons is made much easier through http://code.google.com/p/gpcas/

The method holds true for all the cases (all points and their results) above, and also for a number of other scenarios that we tested (on paper).
I will try a live version tomorrow at work.