Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Niklas F. <ni...@fr...>]

On Sat, Nov 20, 2010 at 12:18 AM, Mat Noguchi <mat...@bu...> 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.
>

No. If any points within distance e should hash to the same value then p and
p + e should hash to the same value. But p + e and p + 2e should also hash
to the same value. By extension p and p + ne should hash to the same value.
You can only do that if all points hash to the same value.

But what you can do (that sometimes is interesting) is find two hash
functions h & g such that if |p - q| < e then either h(p) == h(q) or g(p) ==
g(q).

For 1-dimensional floats you could for instance use:

h(x) = floor(x / 2e)
g(x) = floor(x / 2e + 0.5)

// Niklas