История изменений

1. Все исходные точки заключены внутри большого квадрата.

2. Разбиваем этот квадрат на 4 квадратика меньшего размера.

3. Каждый получившийся квадратик снова разбиваем на 4 равных части.

4. Рекурсивно повторяем разбиение плоскости и строим «квадродерево» (т.н. Quadtree). В листьях этого дерева сохраняем наборы наиболее близких друг ко другу точек, либо отдельные точки.

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

6. Если от найденного листочка подниматься обратно к «вершине» дерева, то в этих ветках будут точки, которые расположены все дальше и дальше от той, на которую мы «встали» на 5-м шаге.

Разбиение квадратной части плоскости в «квадродерево» сходно с разбиением кубической части пространства в разреженное воксельное октодерево - Sparse Voxel Octree (сокращенно S.V.O.), которое применяется в компьютерной графике.

google://Sparse Voxel Octree

1. Все исходные точки заключены внутри большого квадрата.

2. Разбиваем этот квадрат на 4 квадратика меньшего размера.

3. Каждый получившийся квадратик снова разбиваем на 4 равных части.

4. Рекурсивно повторяем разбиение плоскости и строим квадро-дерево (т.н. Quadtree). В листьях этого дерева сохраняем наборы наиболее близких друг ко другу точек, либо отдельные точки.

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

6. Если от найденного листочка подниматься обратно к «вершине» дерева, то в этих ветках будут точки, которые расположены все дальше и дальше от той, на которую мы «встали» на 5-м шаге.

Разбиение квадратной части плоскости в «квадро-дерево» сходно с разбиением кубической части пространства в разряженное воксельное окто-дерево - Sparse Voxel Octree (сокращенно S.V.O.), которое применяется в компьютерной графике.

google://Sparse Voxel Octree

1. Все исходные точки заключены внутри большого квадрата.

2. Разбиваем этот квадрат на 4 квадратика меньшего размера.

3. Каждый получившийся квадратик снова разбиваем на 4 равных части.

4. Рекурсивно повторяем разбиение плоскости и строим квадро-дерево (т.н. Quadtree). В листьях этого дерева сохраняем наборы наиболее близких друг ко другу точек, либо отдельные точки.

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

6. Если от найденного листочка подниматься обратно к «вершине» дерева, то в этих ветках будут точки, которые расположены все дальше и дальше от той, на которую мы «встали» на 5-м шаге.

Разбиение квадратной части плоскости в «квадро-дерево» сходно с разбиением кубической части пространства в разряженное воксельное окто-дерево - Sparsed Voxel Octree (сокращенно S.V.O.), которое применяется в компьютерной графике.

google://Sparsed Voxel Octree

1. Все исходные точки заключены внутри большого квадрата.

2. Разбиваем этот квадрат на 4 квадратика меньшего размера.

3. Каждый получившийся квадратик снова разбиваем на 4 равных части.

4. Рекурсивно повторяем разбиение плоскости и строим квадро-дерево (т.н. Quadtree). В листьях этого дерева сохраняем наборы наиболее близких друг ко другу точек, либо отдельные точки.

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

6. Если от найденого листочка подниматься к обратно «вершине» дерева, то в этих ветках будут точки, которые расположены все дальше и дальше от той, на которую мы «встали» на 5-м шаге.

Разбиение квадратной части плоскости в «квадро-дерево» сходно с разбиением кубической части пространства в разряженное воксельное окто-дерево - Sparsed Voxel Octree (сокращенно S.V.O.), которое применяется в компьютерной графике.

google://Sparsed Voxel Octree