Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Fabian G. <ry...@gm...>]

On 11/19/2010 3:18 PM, Mat Noguchi wrote:
> On a related note, is there a way to hash two points such that they map
> to the same value if they are within specified distance d of each other?
> Obviously you can hash down to their positions quantized to a cell of d,
> but if the two points happen to be in two different cells but less than
> d apart they hash to different values.

There isn't (except for the trivial case where your hash function maps 
everything into the same bucket). Look at the set of points

   H(v) := { x | h(x) = v }

where h is your hash function and v is some arbitrary hash bucket. H(v) 
is a set, and that set has a boundary. Pick a point on the boundary and 
there'll be "adjacent" points just outside the set (which by definition 
means they hash to a different cell).

-Fabian