finding valid points in 2d space with restrictions on arbitrary regions

I have a 2D double precision space with regions (arbitrarily defined, mostly circles) that are "not valid", so to say, and I'd like to get the nearest valid point, given a desired destination (that doesn't have to be valid). Now so far I've tried going from a case-by-case basis in avoiding those regions but when there are multiple constraints (like having to avoid 2-3 regions that are close/blended together) this approach doesn't work. I thought about some kind of search but discretizing the space would be another problem as these regions won't really comform with it.

I was hoping you guys c开发者_StackOverflow社区ould give me some advice on how to tackle a problem like this. A related but much simpler case would be this.

Thanks!

It's basically impossible, unless you can put some constraints on these invalid regions.

Consider an invalid region (or union of regions) in the form of a large irregular blob with a tiny pinhole of validity somewhere inside. And suppose your destination is inside the blob, near the pinhole, so that the desired point is actually in the pinhole. If the only way to examine this blob is with a yes/no method to test a point for validity, the only way to find the pinhole will be by exhaustive search, which will take forever.

If all of your invalid regions are disjoint, the problem is manageable. For a given point, if it is inside one of the regions, look for the closest point on the region boundary. This isn't necessarily trivial, but there should be lots of references - even on this site - for doing that, given various types of boundaries - straight lines, arcs, circles, splines, etc.

If the regions are not disjoint, you can combine them into regions that are. CGAL provides libraries for 2D booleans (specifically unions).