Re: Acceleration Structures For Vertex Snapping

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

------------------------------------------------------------------------------
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