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 - radius, center - radius, radius * 2, radius * 2] x1, y1 = (bounds, bounds) x2, y2 = (bounds + bounds, bounds + bounds) if lis == None: lis =  if self.nodes: if y1 <= self.center: if x1 <= self.center: self.nodes.query_circle(center, radius, lis) if x2 > self.center: self.nodes.query_circle(center, radius, lis) if y2 > self.center: if x1 <= self.center: self.nodes.query_circle(center, radius, lis) if x2 > self.center: self.nodes.query_circle(center, radius, lis) for point in self.points: if (point.x - center) ** 2 + (point.y - center) ** 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?