Can you sort based on position? Then you only need to compare adjacent elements ... If the step size you take is small, you could only sort once every few steps and compare the adjacent few droplets, merging as necessary.
import numpy as np
def merge(p1,p2):
#somehow merge particles. With real particles, mass might matter too,
#but my particles only have position :-)
return (p1+p2)/2 #average location of particles.
def merge_particles(particles,merge_dist_squared):
#Merge particles in 1 pass through the list
#This will always work if the particles are sorted in order
#It will fail if the particles aren't sorted well enough.
i=1
output=[]
prev=particles[0] #location of previous (first) particle
while i<(len(particles)):
dist_vec=(particles[i]-prev)
dist_squared=np.dot(dist_vec,dist_vec)
if dist_squared > merge_dist_squared: #particle isn't close enough to merge
output.append(prev)
prev=particles[i]
else: #particle is close enough to merge
prev=merge(prev,particles[i])
i+=1
output.append(prev) #Have to make sure we add the last particle.
return output
#create N particles:
N=1000
particles=[np.random.random(3) for x in xrange(N)]
particles.sort(key=tuple) #sort particles based on position.
particles=merge_particles(particles,0.1**2)
print len(particles)
