Я пишу реализацию R-Tree на основе оригинальной статьи Гутмана. Я думал об использовании R-Tree для программы, которую я пишу, которая включает в себя множество прямоугольников на экране, которые можно перемещать / масштабировать с помощью мыши.
Я хочу эффективно выбирать только прямоугольники, которые находятся в определенном прямоугольнике, и рисовать их (вместо того, чтобы перебирать потенциально более 100 элементов и проверять, пересекаются ли границы). Проблема, которую я обнаружил после прочтения статьи Гутмана, заключается в том, что z-порядок нельзя поддерживать для 2D-объектов.
Например, если я переместлю объект, он будет удален, а затем снова вставлен. Когда он вставлен заново, узел, в который он вставлен, не сможет отслеживать правильный порядок. Большинство реализаций R-Tree, которые я видел, используют массив и просто находят пустую позицию. Повторная вставка фактически уничтожит любое позиционирование в z-порядке.
Поэтому, когда я рисую все прямоугольники, которые пересекаются с прямоугольником, порядок их возврата не обязательно является правильным.
Я ошибаюсь в этом предположении? Я думал, что вместо использования массива я мог бы использовать дерево AVL или красно-черное дерево и использовать Comparer, который сравнивается по z-index для вставки в дерево. Таким образом, z-порядок всегда поддерживается (и это самый важный фактор).
Я также думал о сортировке, когда они вернутся, но я думаю, это может быть дороже.