GEO Геометрия Структура данных
R-дерево
Также: R-tree · R*-дерево · R*-tree · STR · Sort-Tile-Recursive · пространственный индекс · spatial index · Guttman · Гуттман · best-first · поиск лучший — первым
Пространственный индекс для объектов с размером — отрезков, зданий, участков: каждый узел хранит прямоугольник, внутри которого лежит всё его поддерево, и запрос спускается только туда, где прямоугольник задевает окно. На береговой линии мира — окно карты, три способа построить дерево и расстояние от каждого из 45 тысяч городов до моря по поверхности Земли.
Карта на экране показывает кусок мира, и рисовать нужно только то, что в него попало. Береговая линия мира в масштабе 1:50 миллионов — 58 987 отрезков. Проверить каждый для каждого положения окна можно, но при каждом сдвиге карты это снова 58 987 проверок. R-дерево складывает соседние отрезки в группы по 16, вокруг каждой группы описывает прямоугольник, группы — снова в группы, и так до одного корня. Окно 10° × 5° над проливами между двумя морями задевает 499 отрезков, а дерево, чтобы их найти, проверяет 847 прямоугольников — остальное отбрасывается целыми ветвями.
Тонкие прямоугольники — узлы выбранного уровня, голубые — узлы, которые запрос открыл, красные — найденные отрезки. Переключите способ построения. Упакованное дерево и деревья, собранные вставкой по одному, находят в окне одно и то же, но выглядят совсем по-разному: у упаковки в пустом океане появляются листья-полосы на десятки градусов широты, у вставки вдоль берега листья жмутся к линии.
Идея
У отрезка, здания или участка есть размер, и одна точка его не описывает. Зато его всегда можно накрыть наименьшим прямоугольником со сторонами вдоль осей — по минимумам и максимумам координат. Проверить, пересекаются ли два таких прямоугольника, — четыре сравнения.
R-дерево похоже на B-дерево: все листья на одной глубине, в узле от m до M детей. Но вместо ключей узел хранит прямоугольник, внутри которого лежит всё его поддерево. Если окно не задевает прямоугольник узла, его не задевает ни один объект поддерева, и в узел не нужно спускаться.
Это и всё, что нужно для поиска по окну: обход от корня, который заходит только в узлы, задевающие окно. В отличие от k-d дерева, R-дерево не делит плоскость: прямоугольники соседних узлов могут перекрываться. Объект при этом лежит ровно в одном листе — его никогда не приходится резать или дублировать, — но запрос иногда спускается сразу в несколько ветвей, и гарантий худшего случая у дерева нет. Качество дерева — насколько малы и мало перекрыты прямоугольники узлов — решает всё.
Как строить
Вставка по одному (Антонин Гуттман, 1984). Новый объект спускается от корня в того ребёнка, чей прямоугольник от него раздуется меньше всего, а при равенстве — в меньший. В листе объект добавляется; если детей стало M + 1, узел делится надвое, и прямоугольники пересчитываются вверх. Деление — главная тонкость. Квадратичное разбиение Гуттмана выбирает два «семени» — пару, которая вместе оставила бы больше всего пустой площади, — и потом по одному раскладывает остальных: первым того, кому важнее всего, в какую группу идти, в ту группу, которую он раздувает меньше. Так строят дерево, когда объекты приходят по одному и дерево всё время должно работать.
Упаковка, если все объекты известны заранее. Способ STR (Sort-Tile-Recursive): отсортировать объекты по x центра, разрезать на √(n/M) полос по одинаковому числу объектов, внутри полосы отсортировать по y и брать по M подряд в лист. Потом то же с листьями — и так до корня. Это две сортировки на уровень, а узлы заполнены целиком.
Береговая линия показывает, что выбор не очевиден. Упаковка режет мир на полосы по числу отрезков, а не по ширине. Там, где берега густые, полоса узкая и листья маленькие. В океане полоса между 80° и 93° в. д. берёт и берег у 65° ю. ш., и острова у экватора, и лист растягивается на 72° широты. У всех листьев упакованного дерева вместе — 31 406 квадратных градусов, у дерева, собранного вставкой в порядке обхода берега, — 3767: соседние вершины ломаной и так лежат рядом. Вставка вперемешку — посередине, 20 680.
Но площадь листьев — ещё не скорость. На тысяче случайных окон 2° × 1° на берегах от 10° з. д. до 40° в. д. и от 50° до 72° с. ш. упакованное дерево открывает меньше всего узлов — 3,7, ведь в нём каждый узел полон, — а проверяет больше прямоугольников: 59 против 43 у вставки вдоль берега и 40 у вставки вперемешку. Узлы вставки заполнены на 60–70 %, их больше, но они теснее.
Код
Ближайший берег
Второй вопрос к пространственному индексу — что ближе всего к точке. Для каждого из 45 227 городов, где живёт от десяти тысяч человек, найдём ближайшую точку береговой линии — по поверхности Земли, а не на плоской карте. Точек берега 58 999, городов 45 227, и перебор — два с половиной миллиарда расстояний.
Поиск «лучший — первым» держит кучу, в которой лежат узлы и точки, каждый со своей оценкой — не больше, чем настоящее расстояние до всего, что внутри. Из кучи всегда достаётся самое близкое по оценке. Узел раскрывается, и в кучу идут его дети со своими оценками. Первая точка, вынутая из кучи, — ответ. Город, который дальше всех от моря по этой карте, — Карамай: 2422 километра до берега, и поиск измерил для него 287 расстояний до узлов и точек, а в среднем по всем городам — 132 вместо 58 999.
Пусть оценка узла не больше расстояния от запроса до любой точки его поддерева. Тогда точка, которую поиск «лучший — первым» достаёт из кучи первой, — ближайшая к запросу.
Пусть вынута точка p на расстоянии d. Куча отдаёт наименьшую оценку, значит, у всего, что в ней осталось, оценка не меньше d. Любая точка r, которую ещё не вынули, лежит в поддереве какого-то элемента кучи: изначально в куче корень, а раскрытый узел заменяется своими детьми, так что поддеревья элементов кучи покрывают всё нераскрытое. Расстояние до r не меньше оценки этого элемента, а та не меньше d. Значит, ни одна точка не ближе p.
Остаётся оценка. Прямоугольник узла задан в долготах и широтах, а расстояние меряется по большому кругу, и здесь нельзя взять ближайший угол: ближайшая к городу точка прямоугольника бывает в середине его стороны.
Пусть город в точке (λ, φ), прямоугольник — долготы [λ1, λ2] и широты [φ1, φ2]. Если λ внутри [λ1, λ2], ближайшая точка — на том же меридиане, и расстояние — |φ − φ*|, где φ* — φ, прижатая к [φ1, φ2]. Иначе ближайшая точка лежит на стороне с меньшей разностью долгот Δλ, и её широта — либо α, где tg α = sin φ / (cos φ · cos Δλ), если α попадает в [φ1, φ2], либо один из концов.
По сферической теореме косинусов угол d между городом и точкой (λ′, φ′) удовлетворяет cos d = sin φ sin φ′ + cos φ cos φ′ cos(λ′ − λ). Меньше d — больше косинус. При фиксированной φ′ множитель cos φ cos φ′ не отрицателен, поэтому косинус тем больше, чем меньше |λ′ − λ| (по кругу, от 0 до π). Если долгота города внутри прямоугольника, можно взять λ′ = λ, и тогда cos d = cos(φ′ − φ): ближе всего φ′, прижатая к [φ1, φ2]. Если снаружи, на отрезке долгот [λ1, λ2], не содержащем λ, разность по кругу меньше всего на одном из концов — и при каждой широте на одном и том же, ближнем.
На этой стороне Δλ постоянна, и cos d = sin φ · sin φ′ + cos φ cos Δλ · cos φ′ = A cos(φ′ − α), где A cos α = cos φ cos Δλ, A sin α = sin φ. Широты стороны занимают отрезок длиной не больше π внутри [−π/2, π/2], а A cos(φ′ − α) на таком отрезке растёт к α и убывает от неё. Поэтому максимум — в α, если она внутри, иначе на одном из концов. Это не просто оценка, а точное расстояние до прямоугольника, и тем более оно не больше расстояния до любой точки внутри.
Листинг берёт 6283 города от ста тысяч жителей, чтобы уложиться в секунду, и сверяет первый ответ с перебором всех точек берега. В сцене посчитаны все города; пять самых далёких от моря — города одной округи между 44° и 47° с. ш., от 2422 до 2394 километров. Ближайшая точка у них — то на заливе в устье северной реки, то на дельте южной, — расстояния до двух берегов почти равны. Расстояние меряется до вершин береговой линии, а не до отрезков между ними. Половина отрезков этой карты короче 7,6 километра, поэтому до самой линии бывает на несколько километров ближе, чем до ближайшей вершины.
Сколько это стоит
Запрос по окну стоит числа открытых узлов, умноженного на M, плюс число найденных объектов. Если окно маленькое, а прямоугольники узлов почти не перекрываются, открывается по узлу-другому на уровне — O(log n). Худший случай хуже: узлы, которые все задевают окно и ничего в нём не содержат, заставят открыть всё дерево. Гарантию — порядка √n + k чтений блоков на запрос — даёт приоритетное R-дерево (2004), но на практике обычно хватает упаковки или R*-дерева.
Просмотр всех отрезков растёт линейно, дерево — едва заметно: от 922 до 58 987 отрезков время на окна растёт в Go впятеро, в Python ещё меньше. На всей карте в Python дерево быстрее перебора почти в триста раз, в Go — в сорок с лишним: перебор простых сравнений в Go очень дешёв. Построение упаковкой — сортировки, O(n log n); вставка по одному дороже — спуск по дереву и квадратичное разбиение на каждые несколько вставок.
Где легко ошибиться
- Строгие неравенства. Прямоугольники, которые касаются, пересекаются; у отрезка вдоль меридиана прямоугольник нулевой ширины, у точки — нулевой площади. Со строгими сравнениями они не найдутся никогда.
- Расстояние на карте вместо расстояния на сфере. Градус долготы у полюса короче, чем у экватора, а через 180-й меридиан берег на другом краю карты на самом деле рядом. Оценка до прямоугольника должна считаться в той же метрике, что и ответ, иначе поиск «лучший — первым» вернёт не ближайшее.
- Ближайший угол прямоугольника как оценка. Это не нижняя оценка: ближайшая точка бывает в середине стороны, и узел с ответом достанется из кучи слишком поздно.
- Вставка без учёта порядка. Дерево, собранное вставкой, зависит от того, в каком порядке шли объекты. Если объекты можно упорядочить так, чтобы соседи шли подряд — вдоль линии, по кривой Гильберта, — дерево выходит заметно лучше.
- Удаление. Узел, в котором после удаления осталось меньше m детей, у Гуттмана распускается целиком, а его объекты вставляются заново. Просто оставить полупустой узел можно, но дерево деградирует.
Где работает
Базы данных. Пространственный индекс в PostGIS — R-дерево, построенное на обобщённом дереве поиска GiST; в SQLite есть модуль R*Tree, в MySQL и Oracle пространственные индексы тоже R-деревья. Запрос «объекты в этом прямоугольнике» сначала отбирает кандидатов по прямоугольникам из индекса, а уже потом проверяет точную геометрию.
Геометрические библиотеки. В GEOS и JTS, а через них в Shapely и во многих геоинформационных программах, есть STRtree — R-дерево, упакованное способом STR. Его строят один раз над всеми геометриями и спрашивают: что пересекается с этим, что ближе всего к этому.
Карты и игры. Отрисовка видимого, выбор объекта щелчком, поиск столкновений среди движущихся объектов — везде нужен ответ «что рядом с этим прямоугольником». Для движущихся объектов дерево приходится часто перестраивать, и там чаще берут сетку или дерево, которое легко подправлять.
История
Антонин Гуттман предложил R-дерево в 1984 году как индекс для систем автоматического проектирования и геоинформационных данных — и сразу с тремя способами деления узла: перебором, квадратичным и линейным. В 1990 году Норберт Бекман, Ханс-Петер Кригель, Ральф Шнайдер и Бернхард Зеегер описали R*-дерево: при выборе ребёнка и при делении оно учитывает не только площадь, но и перекрытие и периметр, а переполненный узел сначала пробует отдать часть объектов на повторную вставку. Ибрагим Камель и Христос Фалуцос в 1993–1994 годах упорядочили объекты по кривой Гильберта, а Скотт Лойтенеггер, Марио Лопес и Джеффри Эджингтон в 1997 году предложили упаковку STR. Поиск ближайшего «лучший — первым» по таким деревьям описали Гисли Хьяльтасон и Ханан Самет в 1995 году.
Задачи
Много окон над многими объектами — по одному запросу на каждое положение карты.
Что попало в окноДанные: Береговые линии: Natural Earth, общественное достояние Населённые пункты: GeoNames, CC BY 4.0