Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!zaphod.mps.ohio-state.edu!caen!zeus.engin.umich.edu!pong
From: pong@caen.engin.umich.edu (Bryan John Jalowitz)
Newsgroups: comp.graphics
Subject: Re: Finding nearest point
Message-ID: <1991Feb14.181028.7851@engin.umich.edu>
Date: 14 Feb 91 18:10:28 GMT
References: <kadie.666468082@herodotus.cs.uiuc.edu>
Sender: news@engin.umich.edu (CAEN Netnews)
Organization: University of Michigan Engineering, Ann Arbor
Lines: 34

In article <kadie.666468082@herodotus.cs.uiuc.edu> kadie@cs.uiuc.edu (Carl M. Kadie) writes:
>Given a set of 3-D data points, {<x,y,z>}, and
>a point p1, <x1,y1,z1>, is there a fast way to find which
>point in the set is nearest to p1?
>
>I've tried to think of ways to sort the set, but search is
>linear (and often a little slower).
>

This is the best way I've come up with yet.

First sort the set of 3-D data points on x, then y, then z.
Make the best initial guess you can given the information available to you.
With no additional information you can do the following:
   find the closest match in x.
   for that value of x find the closest match in y.
   for that value of x and y find the closest match in z.
   (It's not always a great guess, but it's a place to start.)
Calculate the error from that guess to your point p1.
   The exact error is the Euclidian distance.
   A faster way at the expense of a little accuracy is described in
   Graphics Gems by Glassner (see the FAQ) in the article "A Fast
   Approximation to 3D Euclidian Distance".
From this point traverse both up and down your 3D set keeping track of
the point with the minimum error.
Stop when the error in x exceeds the minimum error found.


>--
>Carl Kadie -- kadie@cs.uiuc.edu -- University of Illinois at Urbana-Champaign


Tony Whipple
Tony_Whipple@um.cc.umich.edu