Find closest location not occupied by circles

Question

I have a limited set of "occupied" circular areas on a 2D-area ($x$ and $y$ axes). These circles are defined by a center point $(x_n,y_n)$, with $n=1,2,\ldots$ and a common fixed radius $r$. Those values are known.

For a game I’m making, I want to find the closest point to the user’s location $(x_u,y_u)$ that is not within the circles. I think this means I want to find the $x$ and $y$ such that

$$(x-x_u)^2+(y-y_u)^2$$

is minimized, while for each $n$,

$$(x-x_n)^2+(y-y_n)^2> r^2.$$

Note: In case the optimal solution differs from a fast one, I do not need to find the optimal solution every time, but a fast algorithm that gives me a reasonably good result. (Reasonably meaning that a user will not instantly react and see that it is wrong).

I guess this has been already solved somewhere but I could not find where. Pointers to question/answer are welcome.

P.S. Maybe making "guesses" on a spiral out from the user location could work, but I think there are much better solutions.

Update to clarify 1: All circles are occupied area. I want to find a location outside all circles.

Update 2: Sometimes the user location itself can be the solution. If outside of all circles.

Update 3: Circles can be anywhere, overlap etc.

Example image when user is inside circle(s). Then the task is to find the closest non-colored area near the star(the user). Note that intersections are marked also as I think they are relevant.

Update 4 More info based on a comment about optimization: The circles will stay and the user may move, when next calculation is done. When a spot is found another circle may be added there (based on user actions).

Answer 1

I think you can iterate over all arcs that don’t lie inside any circle or form the boundary of the area of union of all circles and for each arc find the minimum distance from that point where you’re standing. Exception would be when current position is the answer.

Answer 2

Find the squared distances $d_i^2$ from the user to each of the circle centers.

If all the differences $d_i^2 - r^2$ are nonnegative then the user is outside all the circles, so the user's position is the answer.

If the occupied circles are disjoint, at most one of those differences is negative and the user is in that circle. Then the answer is the point at distance $r$ on the line from that center to the user. (If the user is at the center of that circle any point on the circle will do.)

When the occupied circles can intersect then finding the answer when the user lies inside one (or more) of the circles is quite subtle - draw some pictures to see what might happen. Even if the user is in just one circle the other circles can affect the answer. The (new) figure in the question shows that.

I doubt that there's a good algorithm. I would start by quantifying the difficulty: how many occupied circles might there be? How good an answer do you need? How many distance calculations are you willing to make?

One possible strategy: pick $k$ directions. Step away from the user along each by (approximately) $d$ units until you reach a point outside all the circles (you can do that by incrementing coordinates). Use the closest point found. Experiment with different values of $k$ and $d$.

Another idea: keep a (long?) list of safe points. Remove points from that list each time you add an occupied circle. (The update will be faster but less precise if you throw out the points in the square circumscribed about the circle.)

Any ad hoc solution like these will require some experiments.

Answer 3

I am not saying that this is the answer but maybe.

1: If not inside a circle, the user location itself.

2: Check the closest circle and nearest distance to the edge of that circle. (If not in the exact middle when all points are suitable, and that is very unlikely i reality). If that location is free from other circles than that is the solution.

3: Start checking intersection points, between circles, inside out. Until one is found that is not inside another circle.

Answer 4

I needed to solve the exact same problem, and your diagram has given me the idea for what I think is the exact solution. This will work for varying radiuses, and can be simplified if all radiuses are equal, as in your case.

1. First a special case. If the point is outside of all circles, we have a trivial solution.
2. Find all the circles the point is inside. Calculate the closest point on their circumference (just move out from the original point along the radius).
3. Find all the intersection points between pairs of circles.
4. Combine the sets of points from steps 2 and 3, and filter these by finding the ones that are not covered by any other circle.
5. Pick the closest point from the remaining set. Done!

This seems to be O(n^3), so not terribly fast, but should be doable if your set is not too huge.

Answer 5

Just thoughts on the fly:

One way I came up with was to filter away some circles by boolean comparison, assuming multiplications take longer to compute (I almost never use square roots). This can be your first-stage filter, especially when the number of circles is huge.

Besides, I think, in your case, the next step could be finding out whether you are in a circle, among possible circle candidates.

Then, if you are in a particular circle (or else the solution has arrived), figure out what the current circle's relation to others is. Take the nearest (to circle's center) circle as your base circle. Again, we can use boolean comparison to do the first filtering (I think an approximate bound for circles of interest would be any circles within diameter, i.e. the circles of interest should be at least touching your base circle), and then do distance calculation to figure out more exact relations.

This brings me to an interesting observation: If we can prove that two circles' intersecting points (or a single point, since all circles not touching are excluded when filtering) do not live in a third circle, then we have a solution (on the other side by an infinitesimal delta). In other words, if we have points A and B as two circles intersections, and A is in a third circle while B is not, extending the vector from A to B by a small delta will be your solution (I think it is optimal under if you start doing this check from the nearest circle to your point, instead of base circle's center).

If both A and B are in a circle, then the arc AB is 'occupied', and we need to move on to, say clockwise go to the next circle. It may be better to start from a neighbor circle that is furthest to your base circle so that AB is smallest (some possibly simple math needs to be analytically derived to make the trade-off).

The next stage is, if all of your base circle's arc sections are occupied, i.e. all circumference points are in another circle, I think you'll need to do the check for the next nearest circle to your point.

I think at this stage some book-keeping will avoid double-computing.