Есть статический набор точек. Как построить вокруг них сбалансированный сабж с помощью Z-order curve? В википедии ( https://en.wikipedia.org/wiki/Z-order_(curve) ) нифига не ясно, например:
Once the points are in sorted order, two properties make it easy to build a quadtree: The first is that the points contained in a square of the quadtree form a contiguous interval in the sorted order.
Ну нифига не ясно, что это может значить. Или мы произвольный прямоугольник берем, и все точки внутри выстраиваем в Z-order, но это не будет значить, что этот непрерывный интервал совпадет с каким-либо непрерывным интервалом в отсортированных исходных данных; или берем точки, z-order которых лежит в некотором интервале, и строим вокруг них минимальное покрытие прямоугольником, но тогда ничто не мешает прямоугольникам, отвечающим двум непересекающимся интервалам, пересекаться, что как-то противоречит идее этих деревьев
И в финале:
For each adjacent pair of points, the derived square is computed and its side length determined. For each derived square, the interval containing it is bounded by the first larger square to the right and to the left in sorted order.[2] Each such interval corresponds to a square in the quadtree. The result of this is a compressed quadtree, where only nodes containing input points or two or more children are present. A non-compressed quadtree can be built by restoring the missing nodes, if desired.
Derived square - это у них минимальное покрытие прямоугольником
Набор слов какой-то. Не ясно, что такое «смежные точки». Самые близкие друг к другу, или те которые идут подряд, отсортированные по этому z-order'у? Далее, построение этого дерева подразумевает некую рекурсию, я не знаю. Где она?
В общем я ничего не понял и реквестирую нормальный алгоритм.
