Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #97938

Re: Nearest neighbours of points

Show all headers | View raw

A program that does what I want can be found below.
However, I want to know if there is a faster way because I have many moving points and the two nearest neighbours must be identified a lot of times.

Poul Riis



import math
import numpy as np
import scipy
from scipy.spatial.distance import pdist

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

pts=[]
for i in range(-1,2):
    for j in range(-1,2):
        for k in range(-1,2):
            pts.append((i+np.random.random()/10,j+np.random.random()/10,k+np.random.random()/10))
for i in range(0,len(pts)):
    print(i,pts[i])

#The minimum distance is easily found
distances=scipy.spatial.distance.pdist(pts)
distmin=min(distances)
n=np.argmin(distances)
for i in range(0,len(distances)):
    print(i,distances[i])
print('The minimum distance is: ',distmin,' which has number ',n)


#But that doesn't tell which two points it was...
n=-1
for i in range(0,27):
    for j in range(i+1,27):
        n=n+1
        dist=calc_dist(pts[i],pts[j])
        if n==0:
            distold=dist
        else:
            if dist <distold:
                distold=dist
                istore=i
                jstore=j
                neighbour=n
print('The two closest points are: ')
print(pts[istore])
print('and')
print(pts[jstore])
print('They have the numbers ',istore,' and ',jstore)
print('Their distance is ',calc_dist(pts[istore],pts[jstore]))
print('The index with the minimum value of the distance array is ',neighbour)

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Nearest neighbours of points Poul Riis <priisdk@gmail.com> - 2015-10-24 13:05 -0700
  Re: Nearest neighbours of points Christian Gollwitzer <auriocus@gmx.de> - 2015-10-24 22:45 +0200
  Re: Nearest neighbours of points Poul Riis <priisdk@gmail.com> - 2015-10-24 15:44 -0700
    Re: Nearest neighbours of points Christian Gollwitzer <auriocus@gmx.de> - 2015-10-25 09:55 +0100
      Re: Nearest neighbours of points Poul Riis <priisdk@gmail.com> - 2015-10-25 05:00 -0700
      Re: Nearest neighbours of points Peter Pearson <pkpearson@nowhere.invalid> - 2015-10-25 17:01 +0000
    Re: Nearest neighbours of points Bartc <bc@freeuk.com> - 2015-10-25 12:36 +0000
  Re: Nearest neighbours of points Fabien <fabien.maussion@gmail.com> - 2015-10-26 03:25 +0100
  Re: Nearest neighbours of points Tom P <werotizy@freent.dd> - 2015-10-31 22:28 +0100
    Re: Nearest neighbours of points Terry Reedy <tjreedy@udel.edu> - 2015-10-31 23:00 -0400

csiph-web