Re: Acceleration Structures For Vertex Snapping

On Sat, Nov 20, 2010 at 12:18 AM, Mat Noguchi <[email protected]> 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

------------------------------------------------------------------------------
Beautiful is writing same markup. Internet Explorer 9 supports
standards for HTML5, CSS3, SVG 1.1,  ECMAScript5, and DOM L2 & L3.
Spend less time writing and  rewriting code and more time creating great
experiences on the web. Be a part of the beta today
http://p.sf.net/sfu/msIE9-sfdev2dev

_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list