list - Using enumerate in nested loops [Python]

Question

I have a list points of triples containing (x, y, z) where x is the x-coordinate, y is the y-coordinate and z is a magnitude. Now I want to check if any point in the list is within a certain radius to the other points in the list. If so the point in the radius has to be deleted. Therefore I made the following code.

radius = 20
for _, current_point in enumerate(points):
    # get the x and y coordinate of the current point
    current_x, current_y = current_point[0], current_point[1]
    for _, elem in enumerate(points):
        # check if the second point is within the radius of the first point
        if (elem[0] - current_x)**2 + (elem[1] - current_y)**2 < radius**2:
            # remove the point if its within the radius
            points.remove(elem)

When I run this the list still contains points which are within the radius of another point. Is there some property of enumerate that I'm missing here?

question from:https://stackoverflow.com/questions/65880856/using-enumerate-in-nested-loops-python

Answer 1

You can iteratively build a new list containing points satisfying the condition.

radius = 20
spread_points = []
for point in points:
    # get the x and y coordinate of the current point
    current_x, current_y = point[0], point[1]
    for sp in spread_points:
        # check if the second point is within the radius of the first point
        if (sp[0] - current_x)**2 + (sp[1] - current_y)**2 < radius**2:
            break
    else:
        spread_points.append(point)

For a more efficient algorithm, perhaps you can use https://en.wikipedia.org/wiki/Quadtree.

Or to just speed this up, you can use numpy arrays to speed up the one point to many points distance computation.