Danidin9, спасибо! Я наивно надеялся, что подобное только для административных границ применяется и прочей “чепухи”. Что ж, будем допиливать
Тут еще может понадобиться определять, какому из outer’ов принадлежит inner. Ох.
Если я не ошибаюсь, то для определения принадлежности точки мультиполигону теоретически даже деление на inner и outer не нужно.
Нечётное кол-во пересечений луча уходящего в бесконечность - принадлежит. Чётное - не принадлежит.
Но это если мультиполигон нарисован правильно и при корректной обработке пересечений по node.
С какой это стати?
http://wiki.openstreetmap.org/wiki/Multipolygon
Это вполне допустимый вариант, который называется Island within a hole
VikDD:Да.
Например: Площадь - газон - памятник.Это уже разные мультиполигоны должны быть.
Отнюдь.
Это называется Two disjunct outer rings
От себя еще напомню, что при сортировке путей для полигона может потребоваться “обратить” путь.
Sergey Astakhov: Shasoft:А может быть дырка в дырке?
Это считается ошибкой. Там вообще всякого рода ошибок туева хуча может быть. Именно поэтому мультиполигоны так часто ломаются.
С какой это стати?
http://wiki.openstreetmap.org/wiki/Multipolygon
Это вполне допустимый вариант, который называется Island within a hole
Читайте внимательнее. Там outer внутри inner а не inner внутри inner про которые шла речь.
VikDD:Например: Площадь - газон - памятник.
Это уже разные мультиполигоны должны быть.
Отнюдь.
Это называется Two disjunct outer rings
Давайте вы, прежде чем влезать в чужой разговор, разберётесь сначала о чём там идёт речь.
Если я не ошибаюсь, то для определения принадлежности точки мультиполигону теоретически даже деление на inner и outer не нужно.
Нечётное кол-во пересечений луча уходящего в бесконечность - принадлежит. Чётное - не принадлежит.
Но это если мультиполигон нарисован правильно и при корректной обработке пересечений по node.
Мне вообще нужно получить из отношения мультиполигон, чтобы потом с ним проводить уже операции попал/не попал объект полигон.
После обдумывания алгоритм получается простой:
- Создаем пустой мультиполигон
- Добавляем в мультиполигон все полигоны, которые outer
- Вычитаем из полученного полигона все полигоны, которые inner
Единственная проблема получается с островами в дырках. Так как эти острова пропадут. Остальное вроде правильно должно отработать.
Если нужно получить gis-овский мультиполигон, который является коллекцией простых полигонов с дырками, то
самый простой алгоритм мне кажется таким:
- Собираем коллекцию полигонов на базе outer-колец.
- Проходим по всем inner-кольцам, добавляя их дырками в те полигоны outer, внутри которых они находятся.
- Объединяем полученные полигоны в единый мультиполигон.
Острова в дырках при этом должны получиться автоматом.
Читайте внимательнее. Там outer внутри inner а не inner внутри inner про которые шла речь.
Если читать внимательнее, то было “дырка в дырке”.
Совершенно очевидно, что если в outer дырка должна быть inner, то в inner дырка - outer.
Т.е. речь может идти исключительно о проследовательности outer-inner-outer.
И, кстати, глубина этой последовательности ничем не ограничена: outer-inner-outer-inner-outer…
Мне вообще нужно получить из отношения мультиполигон, чтобы потом с ним проводить уже операции попал/не попал объект полигон.
После обдумывания алгоритм получается простой:
- Создаем пустой мультиполигон
- Добавляем в мультиполигон все полигоны, которые outer
- Вычитаем из полученного полигона все полигоны, которые inner
Единственная проблема получается с островами в дырках. Так как эти острова пропадут. Остальное вроде правильно должно отработать.
- Создаем пустой мультиполигон.
- Добавляем в мультиполигон все полигоны, которые outer с соответствующим признаком.
- Добавляем в мультиполигон все полигоны, которые inner с соответствующим признаком.
При определении вхождения пользуемся правилом:
- если количество вхождений точки в outer полигоны на 1 больше количества вхождений в полигоны inner, точка внутри мультиполигона,
- если количество вхождений точки в outer полигоны равно количеству вхождений в полигоны inner, точка вне мультиполигона,
- любой другой случай - ошибка.
Если нужно получить gis-овский мультиполигон, который является коллекцией простых полигонов с дырками, то
самый простой алгоритм мне кажется таким:
- Собираем коллекцию полигонов на базе outer-колец.
- Проходим по всем inner-кольцам, добавляя их дырками в те полигоны outer, внутри которых они находятся.
- Объединяем полученные полигоны в единый мультиполигон.
Острова в дырках при этом должны получиться автоматом.
Автоматом не получится.
Результат существенным образом будет зависеть от того, как мы определим:
- полигон,
- outer-кольцо,
- inner-кольцо,
- мультиполигон,
- процедуру “добавления дырками в полигоны”,
- процедуру объединения мультиполигонов.