Re: [Algorithms] Acceleration Structures For Vertex Snapping

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

On 11/19/2010 2:15 PM, Oscar Forth wrote:
> O(1) implies hash lookup is direct array index ... surely best case
> lookup is O(n * log( n ))? Or care to explain where I am going wrong on
> my thinking? Ta

Vertex snapping: Take your snapping distance d
Imagine an infinite uniform grid with cell edge length e >= 2d.
Every vertex within d units of your query vertex must be either in the 
same cell or in one of the directly adjacent cells (that's 2^n cells to 
check where n is your dimension).
Hash on grid cell coordinates (x,y,z) to turn the theoretical infinite 
grid into a very practical hash-table :)

For vertex welding, the weld operation ensures that the number of points 
in each infinite grid cell is <= some constant C(n,e/d). Size the hash 
table according to the number of vertices and the expected number of 
items in a cell is also a small constant. That makes the whole thing 
expected O(1).

-Fabian