Reputation: 7042
I'm working on a problem that essentially reduces down to the following:
Given:
(x,y)
points. There may be 0 points in the set.x
and y
values, where the minimum values are always non-negative.r
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
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
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.
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