Efficiently find all points within a circle

Question

I am writing code that requires me to find all points within circle on certain parts of the screen hundreds of times per frame. I wrote a quadtree for this and have 1 method called query_circle that looks like this:

def query_circle(self, center, radius, lis=None):
    '''
    Uses given bounds of center and radius and
    creates AABB to search all quadtrees that intersect that region for
    the in that region
    '''
    bounds = [center[0] - radius, center[1] - radius, radius * 2, radius * 2]
    x1, y1 = (bounds[0], bounds[1])
    x2, y2 = (bounds[0] + bounds[2], bounds[1] + bounds[3])
    if lis == None:
        lis = []

    if self.nodes:
        if y1 <= self.center[1]:
            if x1 <= self.center[0]:
                self.nodes[0].query_circle(center, radius, lis)
            if x2 > self.center[0]:
                self.nodes[1].query_circle(center, radius, lis)
        if y2 > self.center[1]:
            if x1 <= self.center[0]:
                self.nodes[2].query_circle(center, radius, lis)
            if x2 > self.center[0]:
                self.nodes[3].query_circle(center, radius, lis)

    for point in self.points:
        if (point.x - center[0]) ** 2 + (point.y - center[1]) ** 2 <= radius**2:
            lis.append(point)
    return lis

What is happening is I create an AABB for the circle and then find all the QuadTrees that are intersecting with the AABB and using those QuadTrees to check if the points inside of them are within the circle. Unfortunately, the animation was running at less than 3 frames per second and the root cause was this method. I profiled the method and found this: As you can seet the last 4 lines of code where I check if the point is inside the circle and append it to a list are what are slowing down the method the most. Is there any technique I can use to considerably speed up that process?

Answer 1

About this algorithm:

You don't have to check whether every object is inside the circle. If a node square is completely inside or outside the circle, you can use all objects in it directly without distance check. If not, subdivide it until it can't be.In this way, the objects that need to be judged by distance are only a few objects near the ring. For example, the blue area in the figure does not need to be checked object by object:

---->

You can use the outer square of the circle to exclude the area completely outside the circle.(you have done so). And use the inscribed square of the circle to exclude the area completely inside the circle. Or you can use the circumcircle of the node square, and the target circle to judge, which will lead to somehow more accurate results. Or You can check that the node square is completely within or not within the target circle directly. I don't know which one is faster, it depends on your data characteristics.

This leads to an exponential performance boost when the map is very large and the target circle is also very large. Again, it depends on your data characteristics.

About code style:

As @Vaillancourt said in the comments, you are doing a lot of repeated calculations in the loop. Try putting them outside the loop or the function. Here are some of my suggested modifications:

1. query_circle should not be a member function, but a static utility function.
2. For each query, there is no need to repeatedly calculate the variables related to the target circle, use the closure to store them, create a method object and call it.
3. Use * to replace **2.
4. For each point, use AABB check first.

Disclaimer: I don't currently have a python environment and the (fake)code is untested:

def query_circle(center, radius):
    bounds = [center[0] - radius, center[1] - radius, radius * 2, radius * 2]
    x1, y1 = (bounds[0], bounds[1])
    x2, y2 = (bounds[0] + bounds[2], bounds[1] + bounds[3])
    r_square = radius*radius

    def query_circle_closure(node,lis):
        nCenter = node.center
        nNodes = node.nodes

        if nNodes:
            if y1 <= nCenter[1]:
                if x1 <= nCenter[0]:
                    query_circle_closure(nNodes[0], lis)
                if x2 > nCenter[0]:
                    query_circle_closure(nNodes[1], lis)
            if y2 > nCenter[1]:
                if x1 <= nCenter[0]:
                    query_circle_closure(nNodes[2], lis)
                if x2 > nCenter[0]:
                    query_circle_closure(nNodes[3], lis)
        else:
            for point in node.points:
                if x1<point.x<x2 and y1<point.y<y2:
                    if (point.x - center[0]) *(point.x - center[0]) + (point.y - center[1]) *(point.y - center[1]) <= r_square:
                        lis.append(point)
        return lis
    return query_circle_closure


lis = []
queryFunc = query_circle(center, radius)
queryFunc(your_root_node,lis)

Hope it helps.