**comp.graphics.algorithms**

## Subject: **Re: nearest neighbour of a point**

In article <1146317665.338373.110730@i40g2000cwc.googlegroups.com>,

"running.polygon@gmail.com"

> Even David Kinny mentioned this, but:

>

> I have gone through their approach, but the problem I think it has is

> that it filters out all points lying at some distance 'd' from the

> point under question along each of the axes. Now, it is very much

> possible to have the closest points having these co-ordinates(in

> 3-dimentions):

> A = {0.9, 0.1, 0.2}

> B = { 0.001, 0.1, 0.19}

>

> If we filter out points say even at a distance of 0.6 difference, then

> along the x-axis, the distance becomes 0.899, and the point is

> discarded from further consideration. This is what I gathered from my

> reading of the paper. I may be mistaken though. Please correct me if I

> am wrong.

>

> As an example, I took:

> >>> x=.9-.1

> >>> y=.1-.11

> >>> z=.2-.1

> >>>

> >>> x*x+y*y+z*z

> 0.65010000000000012

>

> >>> a=.6-.1

> >>> b=.7-.11

> >>> c=.5-.1

> >>> a*a+b*b+c*c

> 0.7581

>

> So, the 1st point(0.9,0.1,0.2) is closer to the point under

> question(0.1,0.11,0.1), than the 2nd one(0.6,0.7,0.5).

>

After reading this I still think I don't understand your particular

problem. But if you choose a distance d that gives you no points, you

just increase the distance and try again. You could probably do some

prior analysis to help guide you in choosing a good 'd' value. A kd

tree approach will always be successful in this sense, but I found it a

lot harder to code. You might want to check repositories like netlib

for canned kd code.

-- Lou Pecora (my views are my own) REMOVE THIS to email me.

Reply

View All Messages in

**comp.graphics.algorithms**

path:

nearest neighbour of a point =>Re: nearest neighbour of a point =>Re: nearest neighbour of a point =>

Replies:

Re: nearest neighbour of a point

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.