Home Products Download Order Contacts


Subject: Re: Fast Way Of Calculating Nearest 3D Points

Adam Teasdale Hartshorne wrote:

> I have two sets of 3d points, X and Y. For every element in X, I need to
> find the closest (by euclidean distance) point from the set Y. I was
> wondering what options there are other than the obvious calculation,
> which is obviously quite slow when talking about massive sets of X and Y.

This differs from the other thread by only one detail: you have 3
dimensions, the other guy had upwards of 20, possibly up to 50.

In 3D, subdivision algorithms will work well. Regular 3D grids,
Octrees, or hash maps that work basically like grids or trees, will
all work quite nicely. This is a textbook case of the generic
algorithmic pattern "divide and conquer".

> Also what about if I was not talking about euclidean distance, but
> say a metric which is combination of that factored by say difference
> in normals of the points,

That would make it a more-than-3 dimensional problem. The more
dimensions there are, the smaller the advantage the conqueror can
expect from dividing the task.

> how would any previous suggests be
> affected by this slightly different metric.

Depends on *how* different the different metric is. Ultimately, all
such algorithms will have to end up doing exact distance calculations.
The more similar the metric's equivalent of a sphere is to the shape
of the cells you subdivided your input space into, the better it'll

Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.


View All Messages in comp.graphics.algorithms

Fast Way Of Calculating Nearest 3D Points =>


Copyright 2006 WatermarkFactory.com. All Rights Reserved.