Skip to main content

Removing neighbors in a point cloud

I have written a program to optimize a point cloud in dependency of their distances to each other. The code works very well for smaller number of points. For 1700 points it takes ca. 6 minutes. But I have 300000 points in the point cloud. The code is still running after almost 30 hours.

I am sure there is a pythonic way to optimze the code. But I do not know how can I reduce the calculation time and make the performance better. I have read alot about multithreding, chunk size etc. But I think there is no need for this size of dat. I think, I am using the memory in a very bad way. Am I right? Here is the code:

import pickle
import math
import itertools
import gc

def dist(p0, p1):
    return math.sqrt((p0[0] - p1[0])**2 + (p0[1] - p1[1])**2)

def join_pair(points, r):
    for p, q in itertools.combinations(points, 2):
        if dist(p, q) < r:
            points.remove(q)
            return True
    return False


if __name__ == "__main__":
    filename = 'points.txt'
    filename2 = 'points_modified.txt'
    mynumbers = []
    with open(filename) as f:
        for line in f:
            mynumbers.append([float(n) for n in line.strip().split(' ')])
        mynumbers = sorted(mynumbers, key=lambda tup: (tup[1], tup[0]))
    gc.collect()    
    while join_pair(mynumbers, 3.6):
        pass
    
    with open (filename2,"w")as fp2:
        for j in range(len(mynumbers)):
            fp2.write(' '.join(map(repr, mynumbers[j]))+'\n')


        

and the input data is like the following:

661234.58 5763766.03 72.63
661254.81 5763765.08 75.04
661244.86 5763764.14 74.99
661234.90 5763763.21 74.94
661225.13 5763762.29 74.89