'Given many circles and a point, how to find which circle contains that point

I recently came across a problem which is something like this

There are N disjoint (such that they do not touch or intersect) circles given by their center and radius, i.e. center = (x_i, y_i), radius = r_i. Then we have Q queries where a point (x, y) is given. For each query we need to find out the index i of the circle which contains that given point (-1 if no circle).
The constraints are roughly 1 <= N <= 10^5 and 1 <= Q <= 10^5. So a O(Q * log(N)) might be needed.

Apart from the straight-forward O(Q * N) solution the only better thing I can think of is keeping the leftmost and rightmost points of the circles as intervals in an array and then doing binary search to find out the intervals which contains the x-coordinate of the point, but more than one intervals may be overlapping and more than one circle may contain the point. So I'm not sure if that's going to work.

Any help would be highly appreciated. Thank you.

algorithmgeometrybinary-search


Solution 1:[1]

This can be solved as a nearest-neighbour query in N+1 dimensions.

Imagine a set of balls of a fixed radius in 3d, such that their intersection with the plane z=0 is exactly your set of circles. (The balls may intersect, it doesn't matter). Now a point that falls into a circle is necessarily closer to the centre of its corresponding ball than to centres of all other balls.

The nearest-neighbour problem is well studied. Space partitioning techniques work well with real life data, though worst-case performance is not so good.

Edit: since the query point in in the fixed plane z=0, the problem can be seen as a 2d nearest-neighbour problem with non-Euclidean distance function. The effective distance from a query point to the centre of a circle is

D = &sqrt;(d2+R2 - r2)

where d is the real distance, R is the ball radius (conmon for all balls) and r is the circle radius.

Another way to solve this is to build a power diagram of the set of circles. A power diagram is a plane subdivision. There are ways to efficiently answer queries of the form "which cell of a plane subdivision given point belongs to", for example, using Kirkpatrik's point location data structure.

The two approaches are similar, if not equivalent, because in the power diagram, the power of the point with respect to a circle is the square of D in the formula for distance (with R=0).

Solution 2:[2]

I know this is a quite old question but for the records.... You can solve it with matplotlib Circle

from matplotlib.patches import Circle as Cr
.................
self.my_mpl_circle = Cr(origin, radius)
......
def match_pos(self, coords):
    return self.my_mpl_circle.contains_point(coords)

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 marc_s
Solution 2 dummyhead

Related Questions