Finding nearest free position for a circle for any point [x,y] in a 2D space with circles

This isn't a complete answer, but you may be able to make it into one.

Suppose you've already placed circles of radii r1, r2, r3 ... rn with centres C1, C2, C3 ... Cn, and you're looking to place a new circle of radius rz, the new circle's centre will have to be outside all of a set of "enlarged" circles, centred at C1, C2, C3 ... Cn; with radii (r1+rz), (r2+rz), (r3+rz) ... (rn+rz). So if the cursor is at point P, then there are some cases to consider.

(1) If P is not in any of the enlarged circles, then the problem is solved.

(2) If P is in just one of the enlarged circles, then move outwards along a radius of that circle, until you either reach a point that's outside all of the enlarged circles, or until you reach another enlarged circle. The former case reduces to scenario (1); the latter reduces to scenario (2). Pick an arbitrary direction if P happens to be the centre of the circle.

(3) If P is in several of the circles, then find the directions from P to each centre of a circle that it's in. Find the pair of directions that have the widest interval between them, and bisect that angle, to work out which direction to head along. For example, if the directions to the centres of the circles are 30deg, 120deg and 330deg, then bisect the angle between 120deg and 330deg - then head in a direction of 225deg. Head in that direction until you reach the edge of a circle, then recalculate. Keep doing this until you get back to scenario (2).

The thing that I can't work out is what to do if you get stuck in scenario (3). Maybe only allow a certain number of steps, then exit. After all, it's possible that there's no suitable place to put the circle.


To calculate the distance between a point and a circle is with the center, considering your Circle class is like this one:

public class Circle{
    int x;
    int y;
    int radius;
}

public interface CircleHelper{
    public int distanceBetweenCircleAndPoint(Circle c, Point p);
    public int distanceBetweenTwoCircles(Circle c1, Circle c2);
}

First of all, I would think about using Quadtrees and check if there is any quad without surrounding circles

A quadtree

The quadtree deep can be selected considering the radius of the circles.

so if you have a point in one of the quads, you would look to its surrounding quads to check if there is any circle there and move from the point in the direction of empty quads.

I hope you understand my approach