find closest point in 2d
Hello Falk,
I suggest jitter for that. You can first calculate distance(c^2=a^2
+b^2) of each point from your reference point, and then take the
index of cell with smallest difference:
Here's a question for people who know more about this than I do:
I wonder if it is possible/difficult to convert the 2-d representation to
a polar rep, and then "sweep out" from one of the points by increasing
radius and see which point gets encountered first. I've used the
distance-formula approach myself before, and I wonder if there is any
computational gain by a polar conversion.
helo brad,
i doubt that using polar representation would be any more effiecent
as you still have to get the distance-vector's length of *each* pair,
which in the case of polar-cordinates involves shifting/rotating to
make the first point the origin of a new coordinatesystem.
i'd suggest looking up quadtrees (2d) and kd-trees/octrees (3d) which
are methods AI/flock-people f.i. use to do neighbour-detection on
very large datasets. it's the divide and conquer approach, elimating
all the points that are not in one's immediate vincinity *before* any
actual distance measurements are being made.
/*j
> Here's a question for people who know more about this than I do:
>
> I wonder if it is possible/difficult to convert the 2-d
> representation to a polar rep, and then "sweep out" from one of the
> points by increasing radius and see which point gets encountered
> first. I've used the distance-formula approach myself before, and
> I wonder if there is any computational gain by a polar conversion.
On Sun, 28 Jan 2007, jasch wrote:
> helo brad,
>
> i doubt that using polar representation would be any more effiecent as you
> still have to get the distance-vector's length of *each* pair, which in the
> case of polar-cordinates involves shifting/rotating to make the first point
> the origin of a new coordinatesystem.
Thanks jasch -- that's what I suspected, and if I had used a few brain
cells to imagine the car-to-pol conversion it would have been clear. I'll
check out the other algorithms you mentioned. I figured there were much
snazzier ways to accomplish this somewhere.
tap.jit.proximity (part of the Tap Tools library) does exactly what
you're looking for.
http://www.maxobjects.com/?v=objects&id_objet=3867
http://www.electrotap.com/taptools/
MathieU
And here's a patch that should find two closest points in the set:
One good friend of mine noticed(yes, I'm a nerd, and talk about these
things at dinner sometimes) that we could save some processing if we
remove sqrt, since we don't need the actual distances.
This patch measures distance by creating 2d matrices from points a b
c d:
a b c d
a b c d
a b c d
a b c d
and second matrix by transposing previous:
a a a a
b b b b
c c c c
d d d d
then does (ax-bx)^2+(ay-by)^2 for whole matrix, giving out a matrix
with squared distances between all points.
After that comes the kludge: Sorting the matrix so that zero-distances
(usually "self-distances") come at first column, then cutting that
out with jit.submatrix. Now we can use jit.findbounds, in neatly
arranged matrix, to find cell coordinates with the minimum distance,
found by jit.3m...
best,
nesa