Path: csiph.com!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Peter Pearson Newsgroups: comp.lang.python Subject: Re: Nearest neighbours of points Date: 25 Oct 2015 17:01:43 GMT Lines: 32 Message-ID: References: <81947104-f6dd-48b3-ba7b-f03b0c5b6f39@googlegroups.com> <2be81eec-e7dc-4c83-a578-f8c15eb4c1dc@googlegroups.com> X-Trace: individual.net 6Stgzo22AxoKYQEmLctoqwPmtYoGedeGNs8jJt0OrQuE6V1CqG Cancel-Lock: sha1:LDa4fYrJVrKI/fL5lLaRQl9HGEc= User-Agent: slrn/pre1.0.0-18 (Linux) Xref: csiph.com comp.lang.python:97950 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.