Мне нужен пространственный индекс на языке C
Я работаю над форком gEDAи хочу избавиться от существующей простой тайловой системы 1в пользу реального пространственного индекса 2.
Алгоритма, который эффективно находит точек, недостаточно: мне нужно найти объекты с ненулевым экстентом.Подумайте об объектах, имеющих ограничивающие прямоугольники, которые в значительной степени отражают уровень детализации, который мне нужен в индексе. Учитывая прямоугольник поиска, мне нужно иметь возможность эффективно находить все объекты, ограничивающие прямоугольники которых находятся внутри или пересекают прямоугольник поиска.
Указатель не может быть доступен только для чтения: gschem — это программа для ввода схем, и весь ее смысл в перемещении объектов по схематическому представлению. Так что все будет меняться. Так что, хотя я могу позволить себе, чтобы вставка была немного дороже, чем поиск, она не может быть слишкомнамного дороже, а удаление также должно быть возможным и достаточно дешевым. Но самым важным требованием является асимптотическое поведение: поиск должен быть O(log n), если он не может быть O(1). Вставка/удаление предпочтительно должна быть O (log n), но O (n) будет в порядке. Я определенно не хочу ничего> O (n) (на действие; очевидно, O (n log n) ожидается для операции со всеми объектами).
Какие у меня есть варианты? Я не чувствую себя достаточно умным, чтобы оценивать различные варианты. В идеале должна быть какая-то библиотека C, которая будет делать все умные вещи за меня, но я механически реализую алгоритм, который я могу или не могу полностью понять, если понадобится. Кстати, gEDA использует glib, если это поможет сделать рекомендацию.
Сноски:
1Стандарт gEDA делит схематическую диаграмму на фиксированное количество (в настоящее время 100) «плиток», которые служат для ускорения поиска объектов в ограничивающем прямоугольнике.Этого, очевидно, достаточно, чтобы сделать большинство схем достаточно быстрыми для поиска, но то, как это делается, вызывает другие проблемы: слишком много функций требуют указателя на глобальный объект де-факто. Геометрия плиток также фиксирована: можно было бы полностью победить эту систему плиток, просто переместив (и, возможно, масштабируя) область, покрытую только одной плиткой.
2Правомерным ответом было бы сохранить элементы тайловой системы, но исправить ее недостатки:научить его охватывать все пространство и, при необходимости, делить его на части. Но я хотел бы, чтобы другие добавили свои пять копеек, прежде чем я самовольно решу, что это лучший способ.