CODEWITHSUNDEEP
algorithmgeometry
Mshnik
Mshnik

Reputation: 7042

Find circle of given radius that contains no points

I'm working on a problem that essentially reduces down to the following:

Given:

Determine if it is possible to place a circle of radius r anywhere on the plane such that the circle is in-bounds and does not contain any of the points, and if so return that location.

Intersections are allowed - points from the set can intersect the circle, but they can't be contained by the circle. The circle can tangentially touch the min and max x and y values, but can't go out of bounds.

The result would be a (x,y) point where the center of the circle would go, or some dummy result (i.e. (-1,-1))/failure if there is no such location. If there are multiple valid solutions, returning any is fine.

Any ideas on an algorithm to solve for such a location? I'll end up implementing in java, but I can work with psuedocode.

Upvotes: 1

Views: 285

Answers (2)

n. m. could be an AI
n. m. could be an AI

Reputation: 120239

Build a Delaunay triangulation of your pointset. For each point, perform the following procedure.

Draw a circle of radius 2r around your point. If all the neighbouring points are inside the circle, this point is bad, continue to the next one.

If not, consider all the triangles with this vertex. They form some convex polygon. Trim it if necessary to the borders of your region (it will still be complex). Now you need to find a circle of radius r that is inside of this polygon and does not contain the current point. This is a simple geometric exercise (draw a circle of radius r tangent to each pair of neighbouring edges; if any such circle does not contain any point from the pointset, you are done).

You can accelerate this in various ways (e.g. if a circumscribed circle for any triangle is entirely inside your rectangle, and the radius is r or greater, you are done).

Upvotes: 0

square1001
square1001

Reputation: 1464

Answer

I'll tell the solution for the case n >= 2, if n is the number of points.

You can find two circles that goes through chosen 2 points.

Circles that goes through 2 points

If the circle is in a range and it contains exactly zero points, you can output the circle.

So, you can choose pair of points (p[i], p[j]) and check for all circles.

If you don't know the solution of get two circles, please read this.
Circle of given radius through two points

You can implementate like this:

for i = 0 to n-1
    for j = 0 to n-1
        if dist(p[i], p[j]) <= 2 * r
            circle c1, c2 = circle that goes through p[i] and p[j]
            bool f1 = true
            for k = 0 to n-1
                if p[k] is in c1 -> f1 = false
            if f1 is true -> return center of c1
            bool f2 = true
            for k = 0 to n-1
                if p[k] is in c2 -> f2 = false
            if f2 is true -> return center of c2

If you can't find, you can use Monte Carlo Algorithm.
If you can't find in randomly chosen thousands of points, I think "cannot find" is ok.

Upvotes: 0

Related Questions