**comp.graphics.algorithms**

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

Adam Teasdale Hartshorne

> 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

work.

--

Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)

Even if all the snow were burnt, ashes would remain.

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Fast Way Of Calculating Nearest 3D Points =>

Replies:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.