How to find duplicate 3d points?

[Tim Henderson]

On Jun 11, 11:35 am, oprah.cho... at gmail.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