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

Groups > comp.lang.python > #97950

Re: Nearest neighbours of points

Show all headers | View raw

On Sun, 25 Oct 2015 09:55:30 +0100, Christian Gollwitzer wrote:
> Am 25.10.15 um 00:44 schrieb Poul Riis:
>> 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.
>>
>
> Ah, that changes the game. But I'm still puzzled - is this first scipy 
> function fast enough? Because your second computation using teh nested 
> for loops in my tests gave exactly the same index. I'm not sure it is 
> guaranteed, but it seems that the pdist function uses the same ordering 
> as your code. In which case you can simply calculate i and j from the 
> index n.
>
> For instance, if you have i and j, you can compute n by the formula:
>
> print('The index computed: ', N*istore-istore-istore*(istore+1)/2+jstore-1)
>
> Now you are left with determining i and j from n. You need to find the 
> largest i such that the j from solving the above equation is not 
> negative. If you are lazy, and it is fast enough, you can compute this 
> value in a loop - it is O(n). Or you can try solvin it as a quadratic 
> inequation for i.

My algebra is a little rusty, but I think this boils down to

 i = floor(0.5*(2*N-3 - sqrt((2*N-3)**2 - 8*(n+1))))

Sorry I don't have time to test it right now.

-- 
To email me, substitute nowhere->runbox, invalid->com.

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