Совпадение housenumbers на зданиях (частный случай точки в многоугольнике-тест)

Question

Задача с примером

Я работаю с геоданных (страна размера) от OpenStreetMap. Здания часто являются многоугольниками без комнатных колодцев, и одна точка с номером номера помещается в многоугольник здания. Здания могут иметь несколько многоквартирных домов.

Я хочу, чтобы соответствовать многоквартирным домам для многоугольников зданий.

Простое решение

Foreach номер дома выполнить точка в многоугольнике-тест с каждым строительно-многоугольник.

Проблема

Путь слишком медленно для около 50000000 зданий и 10000000 адресных точек.

Идея

Сложение и индекс для строительства-полигонов для ускорения поиска окружающего полигона для каждой точки номера дома.

Вопрос

Какой индекс или стратегии вы рекомендовали бы для этого многоугольника-структуру? Полигоны никогда не перекрываются, и площадь рассеянно покрыта.

---

этот вопрос дублируется gis.stackexchange.com. Было предложено поставить вопрос там.

Answer 1

Поскольку у вас есть хорошо сформированные полигоны для тестирования, я бы использовал пространственный хеш с проверкой AABB, а затем, наконец, полный тест точки в полигоне. Надеемся, что в этот момент вы будете усреднять три или менее теста типа «точка-в-полигон» на адрес.

• Перерыв в области, в которой ваши данные завершены, в простую сетку, где сетка представляет собой небольшую крайнюю (от 2 до 4) от среднего размера здания. (Может быть, 100-200 метров?)
• Вычислить ограничиваемую осью ограничительную рамку каждого многоугольника, добавить ее (с ее ограничивающей рамкой) в каждую ячейку сетки, с которой пересекает ограничивающий прямоугольник. (Это довольно просто, чтобы выяснить, где рамка с выравниванием по оси пересекается с ячейками сетки, выровненными по регулярной оси. Я бы не сохранил сетку в простом двумерном массиве - я бы использовал хеш-таблицу, которая отображает координаты целочисленной сетки 2D, например (1023, 301), к списку полигонов)
• Затем пройдите через все ваши адреса. Посмотрите в своей хэш-таблице, в какой ячейке находится эта точка. Пройдите через все полигоны в этой ячейке, и если точка находится в пределах рамки, выровненной по оси любого полигона, выполните полный тест «точка в полигоне».

Это имеет ряд преимуществ:

• Структура данных не являются простым - не фантазии библиотек нужно (кроме обработки полигонов). С C++ ваша библиотека многоугольников и пространство имен std могут быть реализованы менее чем за час.
• Пространственная структура не является иерархической - когда вы просматриваете точки, вам нужно сделать только один поиск O (1) в хеш-таблице.

И, конечно же, обычный недостаток сеток как пространственная структура:

• Не обрабатывать дико различные размерные многоугольники особенно хорошо. Тем не менее, я надеюсь, что с тех пор, как вы используете данные карты, размеры почти всегда находятся на порядок и, вероятно, намного меньше.

Предполагая, что вы в конечном итоге с N максимальных многоугольников в каждой из сетки, и каждый многоугольник имеет P точки и у вас есть B здания и A адреса, вы смотрите на O(B*P + N*A). Поскольку B и P, вероятно, относительно малы, особенно в среднем, вы можете подумать об этом O(B + N) - довольно линейно.