POV-Ray : Newsgroups : povray.advanced-users : looking for algorithm Server Time
25 Nov 2024 10:01:56 EST (-0500)
  looking for algorithm (Message 1 to 3 of 3)  
From: ABX
Subject: looking for algorithm
Date: 27 Feb 2003 04:20:06
Message: <pikr5vscbk91svplsusq395uho7o6qb00u@4ax.com>
I'm looking for effective algorithm or at least possible english term to name it
for google. I have array A with set of points. I have array B with other set of
points. For each point from array A I need nearest point in array B. The
question is what structure and additional data I should use for array B to make
this finding fastest. The structure should be aplicable for any not sorted set
of points in array A.

ABX


Post a reply to this message

From: ABX
Subject: Re: looking for algorithm
Date: 27 Feb 2003 04:45:22
Message: <qdnr5vgi3ni9rn3ulrg5g5c9s7e4h6hdvv@4ax.com>
On Thu, 27 Feb 2003 10:19:16 +0100, ABX <abx### [at] abxartpl> wrote:
> I'm looking for effective algorithm or at least possible english term to name it
> for google.

I found it myself: http://www.google.com/search?q=Nearest+Neighbor+Search

ABX


Post a reply to this message

From: Alex Falappa
Subject: Re: looking for algorithm
Date: 27 Feb 2003 05:14:46
Message: <3e5de516@news.povray.org>
ABX wrote:
> I'm looking for effective algorithm or at least possible english term
> to name it for google. I have array A with set of points. I have
> array B with other set of points. For each point from array A I need
> nearest point in array B. The question is what structure and
> additional data I should use for array B to make this finding
> fastest. The structure should be aplicable for any not sorted set of
> points in array A.
>
> ABX

IMHO I would llok for a spatial subdivision structure in which store points
from B array and then perform nearest finding queries using each point in A
array. I would firstly look at:
http://www.cs.umd.edu/~brabec/quadtree/index.html
where you will find several spatial subdivision data structures (and some
useful algorithms operating with them) explained with graphical demos
implemented as java applets.
Then you can go deeper making a google search for:
octree (or the 2D variant quad-tree)
kd-tree
bsp-tree

--
Alessandro Falappa
web: http://www.falappa.net/alessandro


Post a reply to this message

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.