How to find duplicate 3d points?

Tim Henderson tim.tadh at gmail.com
Wed Jun 11 17:47:53 CEST 2008


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



More information about the Python-list mailing list