While I realise bitwise matching is quickest, three subtractions, three squares, an addition, an absolute and a less than is hardly that much slower (the minimum needed for a distance comparison) for a quadratic scaling operation like comparison. And you can easily save work here too. As a scientific programmer of many years, I've learned the hard way that it's sometimes too easy to get caught up trying to save CPU in the easy bits, when there's other much better places to save it.

And you should never, ever, ever rely on floating point bitwise matches. The moment you add, subtract, multiply or divide you will inevitably run into errors. This even applies if you quantise, as 1/16+1e-15 and 1/16-1e-15 are only 2e-15 apart, but appear in different quanta. Furthermore you need to choose an integer that is large enough to cover the whole range, which would have to be at least 32bytes to be safe (since 16 bytes at a 1/16 bucket gives a range of -2048 to 2048).

Pseudo-code for efficient matching of points

# Calculate tolerance squared
TOL2=TOL*TOL
# Precompute distance squared for every vertex P(i) - O(N)
for i from 1 to noPoints
P(i).r2=P(i).x*P(i).x+P(i).y*P(i).y+P(i).z*P(i).z
end
# Compare points - O(N^2)
for i from 1 to noPoints
for j from (i+1) to noPoints
# Check that points are close enough in the sphere - one abs, one <
if abs(P(i).r2-P(j).r2)<TOL2
# Now check their distance apart (squared) - 8 FLOPS, one <
if (P(i).r2+P(j).r2-2*(P(i).x*P(j).x+P(i).y*P(j).y+P(i).z*P(j).z))<TOL2
# Points are the same to TOL
SetPointsSame(i,j)
endif
endif
endfor
endfor

Edited 6 time(s). Last edit at 2013-03-10 11:49PM by Tim Gould.