Как разные ГИС-системы определяют интерьер полигона?

11

Мне интересно понять, как реальные ГИС-системы и их данные кодируют полигоны.

В частности, как они решают неоднозначность интерьера многоугольника на сфере?

Фон: в 2D тривиально выбрать сторону границы, которая имеет конечную площадь, поскольку 2D-плоскость бесконечна. Однако сфера конечна, поэтому невозможно узнать, какая сторона находится внутри, не делая дополнительных предположений.

Возможные подходы, о которых я знаю:

  1. Правило правой руки : внешние границы всегда задаются по часовой стрелке, а отверстия - против часовой стрелки. (Конечно, есть и правило левой руки).
  2. Наименьшая площадь : для любого заданного кольца всегда выбирайте сторону с наименьшей площадью. Я не уверен, как бы вы указали полигон большого радиуса действия: возможно, пустое внешнее кольцо с отверстиями?
  3. Прямоугольная : просто рассмотрим равноугольную проекцию на бесконечную 2D-плоскость. Тем не менее, это предполагает, что функции анемеридиана прерваны, в противном случае потребуется возврат к одному из двух методов, описанных выше.

Мои личные предпочтения - это первый подход, но мне интересно понять, распространено ли это в стандартных ГИС-системах.

Джейсон Дэвис
источник

Ответы:

3

Основные ГИС-системы и их методы для устранения неоднозначности:

  • ESRI : правило правой ноги.
  • ArcGIS : правило правой ноги.
  • SQL Server 2012 : правило левой ноги. До SQL Server 2012 полигоны большего размера, чем полусфера, могли выдавать ошибку.

GeoJSON не указывает порядок.

Джейсон Дэвис
источник
1
В пересмотренной спецификации GeoJSON ( tools.ietf.org/html/rfc7946 ) указано, что «Кольца многоугольника ДОЛЖНЫ следовать правому правилу ориентации (внешние кольца против часовой стрелки, внутренние кольца по часовой стрелке)».
Perrygeo
1

Если я правильно понимаю ваш вопрос, вы хотите знать, как ГИС выполняет тест в сферическом многоугольнике. Вот алгоритм, который я нашел на geospatialmethods.org :

  1. Соедините точку с известной внешней точкой большой дугой окружности.
  2. Для каждой большой дуги окружности, которая является стороной теста сферического многоугольника, если она пересекает дугу, построенную на шаге № 1, и подсчитывает количество пересечений.
  3. Если общее количество пересечений нечетное, данная точка находится внутри сферического многоугольника. если общее количество пересечений является четным, то точка находится вне сферического многоугольника.

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

Этот вопрос также подробно обсуждается в документе JPA НАСА об алгоритмах для многоугольников на сфере . Это на странице 11. Есть, конечно, некоторые оптимизации:

Во-первых, по возможности избегайте дорогостоящих вычислений сферической тригонометрии, сравнивая пробный луч с предварительно вычисленной ограничительной рамкой, прежде чем смотреть на какие-либо ребра многоугольника. Если тестовый луч пересекает ограничивающий прямоугольник, Q проверяется по каждой из вершин многоугольника. Нет смысла проверять, находится ли Q на краю в этой точке, потому что это будет выявлено, когда будут выполнены тесты на пересечение, а остальные ребра могут быть пропущены в это время.

Я думаю, вы найдете бумагу наиболее интересной :)

RK
источник
Похоже, это отвечает на другой вопрос. Несамопересекающиеся замкнутые ломаные делят сферу на две связанные компоненты. ФП спрашивает, как ГИС определяет - или как ей сообщают - какой из этих компонентов следует рассматривать "внутри", а какой "снаружи"? Веб-сайт, который вы цитируете, обсуждает эту проблему под заголовком «Угадай внешнюю точку», подчеркивая, что он просто угадывает, какой компонент должен быть внутри.
whuber
Ох ... Драт. Неправильно понял его вопрос. Я связал это со сферической версией точки в тесте многоугольника. Буду пересматривать его, как только найду ответ.
РК
Что ж, я ценю ссылки, которые вы нашли, поэтому я надеюсь, что вам удастся включить их в свой исправленный ответ :-).
whuber
Я надеюсь на это тоже. Или, может быть, я просто задам вопрос и сам отвечу на него ;-) Было бы стыдно тратить их.
РК
1
Спасибо за подробный ответ! К сожалению, как указывает @whuber, это не отвечает на мой конкретный вопрос. :) Я обрисовал возможные подходы к устранению неоднозначности внутренней части многоугольника, но мне интересно знать, какие подходы применяют в реальной ГИС-программе.
Джейсон Дэвис