How to find duplicate 3d points?

[oprah.chopra@gmail.com]

I have a large data file of upto 1 million x,y,z coordinates of
points. I want to identify which points are within 0.01 mm from each
other. I can compare the distance from each point to every other
point , but this takes 1 million * 1 million operations, or forever!

Any quick way to do it, perhaps by inserting just the integer portion
of the coordinates into an array, and checking if the integer has
already been defined before inserting a new point?

[Tim Henderson]

Re: How to find duplicate 3d points?

On Jun 11, 11:35 am, oprah.cho...@gm ail.com wrote:

I have a large data file of upto 1 million x,y,z coordinates of
points. I want to identify which points are within 0.01 mm from each
other. I can compare the distance from each point to every other
point , but this takes 1 million * 1 million operations, or forever!
>
Any quick way to do it, perhaps by inserting just the integer portion
of the coordinates into an array, and checking if the integer has
already been defined before inserting a new point?

what many people do when doing collision detection in 3d games in
instead of having one massive list of the vertices will break the
field into bounding boxes. in the 2d situation that would look like
this.

|----|----|----|----|
|. . | | .| |
|----|----|----|----|
|. |. | . |. |
|----|----|----|----|
| | . | . | |
|----|----|----|----|
| | | | . .|
|----|----|----|----|

That so instead of comparing all points against all other points
instead sort them into bounding cubes. that should make doing the
comparisons more reasonable. now the only sticky bit will be comparing
two vertices that are in two different boxes but so close to the edges
that they are under .01mm from each other. in this situation if a
point is less that .01mm from any edge of its bounding cube you must
compare it against the points in the adjacent cubes.

hope this helps a bit.

cheers
Tim Henderson

[Gary Herron]

Re: How to find duplicate 3d points?

oprah.chopra@gm ail.com wrote:

I have a large data file of upto 1 million x,y,z coordinates of
points. I want to identify which points are within 0.01 mm from each
other. I can compare the distance from each point to every other
point , but this takes 1 million * 1 million operations, or forever!
>
Any quick way to do it, perhaps by inserting just the integer portion
of the coordinates into an array, and checking if the integer has
already been defined before inserting a new point?
--

http://mail.python.org/mailman/listinfo/python-list

>

There is a whole field of Math/CS research on problems like this called
Computational Geometry. It provides many algorithms for many geometric
problems, including things like this.

In particular, to categorize a list of points and find the
NearestNeighbor , I'd suggest a KD-tree. I believe this would turn your
problem from O(N^2) to O(N log n) or so.

Happy google-ing and good luck.

Gary Herron