Полигон из отношения

Danidin9, спасибо! Я наивно надеялся, что подобное только для административных границ применяется и прочей “чепухи”. Что ж, будем допиливать :slight_smile:
Тут еще может понадобиться определять, какому из outer’ов принадлежит inner. Ох.

Если я не ошибаюсь, то для определения принадлежности точки мультиполигону теоретически даже деление на inner и outer не нужно.
Нечётное кол-во пересечений луча уходящего в бесконечность - принадлежит. Чётное - не принадлежит.
Но это если мультиполигон нарисован правильно и при корректной обработке пересечений по node.

Угу, а чтобы не изобретать велосипед - можно использовать boost::geometry::within

С какой это стати?
http://wiki.openstreetmap.org/wiki/Multipolygon
Это вполне допустимый вариант, который называется Island within a hole

Отнюдь.
Это называется Two disjunct outer rings

От себя еще напомню, что при сортировке путей для полигона может потребоваться “обратить” путь.

Читайте внимательнее. Там outer внутри inner а не inner внутри inner про которые шла речь.

Давайте вы, прежде чем влезать в чужой разговор, разберётесь сначала о чём там идёт речь.

Мне вообще нужно получить из отношения мультиполигон, чтобы потом с ним проводить уже операции попал/не попал объект полигон.

После обдумывания алгоритм получается простой:

  1. Создаем пустой мультиполигон
  2. Добавляем в мультиполигон все полигоны, которые outer
  3. Вычитаем из полученного полигона все полигоны, которые inner

Единственная проблема получается с островами в дырках. Так как эти острова пропадут. Остальное вроде правильно должно отработать.

Если нужно получить gis-овский мультиполигон, который является коллекцией простых полигонов с дырками, то
самый простой алгоритм мне кажется таким:

  1. Собираем коллекцию полигонов на базе outer-колец.
  2. Проходим по всем inner-кольцам, добавляя их дырками в те полигоны outer, внутри которых они находятся.
  3. Объединяем полученные полигоны в единый мультиполигон.

Острова в дырках при этом должны получиться автоматом.

Если читать внимательнее, то было “дырка в дырке”.
Совершенно очевидно, что если в outer дырка должна быть inner, то в inner дырка - outer.
Т.е. речь может идти исключительно о проследовательности outer-inner-outer.
И, кстати, глубина этой последовательности ничем не ограничена: outer-inner-outer-inner-outer…

  1. Создаем пустой мультиполигон.
  2. Добавляем в мультиполигон все полигоны, которые outer с соответствующим признаком.
  3. Добавляем в мультиполигон все полигоны, которые inner с соответствующим признаком.

При определении вхождения пользуемся правилом:

  • если количество вхождений точки в outer полигоны на 1 больше количества вхождений в полигоны inner, точка внутри мультиполигона,
  • если количество вхождений точки в outer полигоны равно количеству вхождений в полигоны inner, точка вне мультиполигона,
  • любой другой случай - ошибка.

Автоматом не получится.
Результат существенным образом будет зависеть от того, как мы определим:

  • полигон,
  • outer-кольцо,
  • inner-кольцо,
  • мультиполигон,
  • процедуру “добавления дырками в полигоны”,
  • процедуру объединения мультиполигонов.