Как сваривать вершины меша за линейное время

В процедурной генерации части геометрии удобно строить независимо, а затем сливать близкие вершины. Перебор всех пар требует квадратичного числа сравнений.

Пространственный хеш делит плоскость на ячейки. Для новой точки он проверяет её ячейку и восемь соседних; в 3D получается 27 проверок. При ослабленном правиле сварки сложность снижается до O(n).

Ячейки размером 2r и сдвиг сетки хранения на r сокращают поиск до четырёх обращений к словарю в 2D и восьми в 3D, но охватывают большую область. Хеш подходит для примерно равномерных точек; для библиотеки общего назначения kd-дерево безопаснее. В статье Mesh Welding with Spatial Hashing есть псевдокод и объяснение смещённой сетки.