Выявление слишком частого и ошибочного геопространственного алгоритма
Моя первоначальная презентация
Я представил то, что я придумал - Легенда буфера в прошлый день ГИС в моей альма-матер, Шербрукском университете. Вы можете найти мою презентацию на youtube. Я устранил все алгоритмические сложности, написав прямую статью, в которой излагались мои основные идеи.
Главный вывод:
Только не используйте буфер. Самый эффективный способ сделать алгоритм неэффективным - использовать неправильную структуру данных. Буфер почти никогда не бывает подходящим инструментом для работы.
Давайте начнем разбираться с последствиями некоторых распространенных заблуждений об использовании буфера.
Что такое буфер?
Буфер, скорее всего, первая операция, с которой вы познакомились, если вы следовали любому курсу ГИС. Буфер принимает входную геометрию и определенное расстояние и выводит новую геометрию. Входная геометрия может быть любого типа, будь то точка, линия или многоугольник.
Буфер (точка, расстояние) → Многоугольник
Обычно буфер используется для поиска геометрических фигур, близких к нашей входной геометрии. Применяем пересечение, используя сгенерированный буфер. Геометрии, выбранные пересечением, должны попадать в наш буфер.
Алгоритм буферного пересечения работает с предположением, что наш буфер представляет собой идеальный круг. Такое предположение ошибочно.
Ошибка нет. 1: буфер - это не круг
Если буфер представляет собой круг, то мы могли бы использовать радиус, чтобы найти все геометрические формы внутри него.
Однако буфер - это не круг, это многоугольник. Многоугольник состоит из вершин, тех точек, которые определяют его границу. Например, возьмите это определение многоугольника с помощью хорошо знакомого текста:
ПОЛИГОН ((30 10, 40 40, 20 40, 10 20, 30 10))
Вершины - это координаты, разделенные запятыми. Чтобы многоугольник стал кругом, нам понадобится бесконечное количество вершин. Бесконечное количество вершин потребует бесконечного количества памяти. Увеличьте изображение буферного многоугольника, и вы увидите его края. Итак, буфер - это не идеальный круг, но что это в любом случае влечет за собой?
Ошибка нет. 2: Исключение некоторых геометрических фигур в пределах буферного расстояния
Наш алгоритм пересечения буфера исключит некоторые геометрические формы. Только вершины будут иметь максимальное расстояние от входной геометрии. Все остальные геометрии, попадающие на границу воображаемого круга, исключаются из алгоритма.
Некоторые буферные алгоритмы пытаются аппроксимировать круг более точно, чем другие. Например, алгоритм GDAL в QGIS сгенерирует намного больше вершин, чем алгоритм по умолчанию, используемый QGIS. Решает ли увеличение числа вершин проблему с исключенной геометрией? Нет. Буфер по-прежнему представляет собой лишь приблизительную форму круга.
Ошибка нет. 3. Стоимость путешествия (почти) никогда не равна расстоянию полета птицы.
Мои друзья приехали навестить нашу самую популярную скалолазную гору недалеко от Квебека: Камураску. Камураска находится на южном берегу реки Святого Лаврентия и полностью затопляется в выходные и праздничные дни. Мои друзья искали дешевое жилье в Интернете, места для кемпинга почти иссякли. Они нашли интересную сделку и забронировали ее на месте. Приехав, они поняли, что их многое не так удобно. Мотель, хоть и находился в 30 км от Камураски, был в 3 часах езды. Расстояние до высоты птичьего полета ограничивало результаты поиска на веб-сайте, таким образом, включая результаты поиска на противоположном берегу реки.
Мои друзья, бронирующие отель, - это единственный случай, когда все пошло не так. Тысячи пользователей могли испытать такой же неудачный опыт. Я видел слишком много производственных веб-сайтов, совершающих ту же ошибку. Мы должны добиться большего успеха. Мы, как разработчики, несем ответственность за предоставление нашим клиентам отличного опыта.
Существуют лучшие альтернативы буферу
Конечно, использование буфера, вероятно, даст вам результат, похожий на тот, который вы ожидали… в большинстве случаев. Это только вопрос времени, когда вы попадете в крайний случай, когда последствия ошибки будут важны. Вот несколько общих примеров, иллюстрирующих некоторые альтернативы буферам.
Решение для поиска геометрических фигур на расстоянии
Чтобы найти наиболее близкие геометрические формы, выбросьте буферное пересечение в мусорную корзину. Есть простая и правильная альтернатива:
- Рассчитайте расстояние между исходной геометрией и другими геометриями
- Выбирайте только те, на которых расстояние меньше желаемого.
Решение для лучшего представления на расстоянии
Расстояние полета птицы редко представляет собой реальную стоимость наших сценариев использования. Вы (почти) никогда не будете путешествовать по прямой, чтобы добраться из пункта A в пункт B, даже если вы летите. Скорее всего, вас интересует стоимость поездки из пункта А в пункт Б. В большинстве случаев лучше будет время в пути или другие расходы.
Графы - это классическая структура данных, в которой разные узлы соединены ребрами (также называемыми дугами). Когда эти дуги имеют стоимость, называемую весами, граф является взвешенным графом. Мы можем использовать взвешенные графики для расчета времени в пути. Фактически, графики могут представлять уличную сеть. Весом уличной сети может быть расстояние или, скорее, время, необходимое для достижения следующего узла. Затем мы можем рассчитать кратчайший путь, чтобы определить стоимость проезда из одного или даже в несколько пунктов назначения.
Когда нам следует использовать буфер?
Устраняя неправильные использования, я нашел только два оправданных применения буфера:
- Вы хотите отобразить область вокруг заданной геометрии
- Вы хотите выполнить какую-то пространственную операцию, для которой абсолютно необходим буфер
Во всех случаях единственно оправданные варианты использования должны использоваться только для демонстрации. Использование буфера для алгоритмических целей, скорее всего, вернет неверные результаты.
Когда не следует использовать буфер?
Если это еще не было ясно, вы почти всегда должны найти альтернативу использованию буфера. Выбирайтесь и исправляйте наши неработающие реализации поиска по геометрии.
Я призываю вас упомянуть еще один способ законного использования буфера. Я все еще пытаюсь понять, как это стало таким заметным. Пожалуйста, свяжитесь с нами, если у вас есть историческая справка о том, как буфер был введен и популяризирован.
