2

I am trying to remove some items inside an array based on the distance from each other.

I have 104 items in an array with tuples:

points = [(910, 28), (914, 29), (919, 30), (915, 32), (766, 73), (777, 75), (768, 80), (1227, 117), (1224, 119), (1228, 120), (1224, 121), (1228, 122), (1221, 124), (1218, 126), (486, 147), (482, 150), (474, 153), (905, 182), (908, 184), (904, 186), (901, 187), (913, 188), (909, 190), (903, 193), (187, 213), (186, 214), (189, 215), (611, 262), (617, 264), (619, 265), (610, 268), (1231, 272), (1228, 274), (1228, 276), (1232, 278), (1223, 282), (486, 306), (477, 309), (463, 312), (470, 313), (486, 315), (473, 319), (764, 376), (773, 379), (770, 383), (795, 386), (778, 390), (631, 412), (626, 414), (624, 416), (626, 418), (1218, 434), (1217, 435), (1218, 436), (1219, 437), (1220, 438), (1222, 439), (1225, 440), (1226, 442), (480, 460), (478, 463), (1071, 466), (1062, 468), (1067, 469), (1072, 470), (339, 485), (343, 487), (345, 489), (346, 490), (350, 492), (343, 495), (352, 497), (930, 505), (929, 508), (929, 513), (199, 535), (197, 537), (203, 539), (201, 542), (771, 547), (774, 547), (773, 548), (772, 549), (776, 549), (776, 550), (629, 576), (628, 579), (631, 580), (625, 583), (1237, 586), (1218, 590), (1226, 593), (1223, 595), (1227, 599), (639, 732), (643, 733), (643, 734), (204, 875), (209, 877), (210, 879), (210, 880), (210, 882), (210, 884), (204, 887)]

and my code is as follows:

print len(points)
w = 152
h = 157
for pt in points:
    for fpt in points:
        if pt == fpt:
            continue
        else:
            distX = abs(pt[0] - fpt[0])
            distY = abs(pt[1] - fpt[1])
            dist = distX + distY
            if distX < w / 2 and distY < h / 2:
                points.remove(fpt)

print len(points)

When I run it, it removes lots of items and it leaves me with only 33, but it is not correct. If I run it again it leaves me the correct number which is 22.

I am sure that I did something wrong, can anyone help me locate and correct my mistake?

bkbilly
  • 193
  • 1
  • 15
  • 2
    http://stackoverflow.com/questions/10665591/how-to-remove-list-elements-in-a-for-loop-in-python – Delgan Jun 29 '15 at 08:56
  • 1
    Are you sure the points remaining should be 22? According to current logic, seems like all the points are to be removed? – Anand S Kumar Jun 29 '15 at 09:13
  • The logic is that I want from a cluster of points to get only one of them. I don't care which one so that it will be easier... – bkbilly Jun 29 '15 at 09:21

1 Answers1

2

Removing list items in place while iterating the list is not good practice. For instance, 

if points has only 3 elements [a, b, c], 
a is adjacent to b, 
b is adjacent to c, 
but a is not adjacent to c, 
Correct result is [a] after the algorithm runs. But with your algorithm,
after the first iteration, b is removed; points = [a, c]
c can never be removed, since a and c are not adjacent.

What you are looking for is a Union-find-set, here is a implementation: http://code.activestate.com/recipes/215912-union-find-data-structure/

And here is a more naive implementation of Union-Find, for your reference: A set union find algorithm

Community
  • 1
  • 1
NeoWang
  • 17,361
  • 24
  • 78
  • 126
  • 1
    I knew that it wasn't a good idea to remove items while iterating, but I didn't know any other solution... I just thought of storring all close items to a double list and then pick one of them. If it works i'll tell you! Thanks for clarifying what I did wrong! – bkbilly Jun 29 '15 at 10:38