On Jun 11, 11:35 am, [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list