Думаю, что эта идея "витает в воздухе", но пока на форуме не нашел (возможно, просто трудно придумать правильный ключ поиска
Хочется, чтобы mapedit поддерживал полный набор операций булевой алгебры множеств на площадных объектах. Одно из естественных решений - реализовать теоретико-множественную разность полигонов, т.е. уметь по полигонам A и B строить полигон "A\B", содержащий точки из A, не лежащие в B. Результат можно записывать в A. Пока что в mapedit эта операция реализована только для специального случая, когда B строго содержится в A ("Join objects").
Набросок возможного алгоритма:
Примем за основу, что закрашенные области определяются так: точки, находящиеся "далеко", не закрашены, а при пересечении границы полигона состояние закрашенности меняется на противоположное (ведь в Гарминах все так и делается?). Тогда, зная вершины каждого из полигонов A и B и точки их самопересечения, можно считать каждый полигон объединением нескольких обычных многоугольников. Далее из каждого многоугольника, входящего в A, вычитаем все многоугольники, входящие в B (что, наверно, несложно).
Кстати, сама по себе возможность разбиения самопересекающегося полигона на многоугольники может быть полезной. Дополнительно можно предусмотреть операцию "чистки границ" по принципу: если удаление границы не изменяет множество внутренних точек полигона, то выполнить это удаление. Например, когда граница заходит внутрь и возвращается обратно своим следом. Или два многоугольника, соединенные длинной перемычкой: делаем разбиение и чистку границ - получаем просто два отдельных многоугольника.
Ну и не составит труда автоматизировать эти операции для однотипных объектов ("вычесть все болота из всех лесов").
Вот такие у меня мечты. А все из-за несовершенства гарминовского векторного формата, не поддерживающего слои ("одно над другим").
Мечта про Mapedit
Правила форума
Для предотврашения спама первые сообщения вновь зарегистрированных пользователей проходят ручную премодерацию.
Для предотврашения спама первые сообщения вновь зарегистрированных пользователей проходят ручную премодерацию.
|
||
Re: Мечта про Mapedit
> Набросок возможного алгоритма Есть достаточно популярный обзор подобных алгоритмов: http://www.csd.tsu.ru/library/Publicati ... pdf <br>
О, даже по-русски!
Спасибо за ссылку. Надо будет изучить на досуге. А потом, когда времени побольше станет, может, и программу писать...
Re: О, даже по-русски!
Ещё вот тут кое-что было: <A HREF="http://algolist.manual.ru/maths/geom/in ... br>Местами с кодом.
Re: Мечта про Mapedit
: Дополнительно можно предусмотреть операцию "чистки границ" по принципу: если удаление границы не изменяет множество внутренних точек полигона, то выполнить это удаление. Например, когда граница заходит внутрь и возвращается обратно своим следом.
Но-но, полегче! Острова потопишь.
Но-но, полегче! Острова потопишь.
|
||
Re: О, даже по-русски!
Удачный алгоритм описан в следующей статье: http://www.inf.tsu.ru/library/Publicati ... 0.pdf а пример с кодом - www.inf.tsu.ru/library/DiplomaWorks/Com ... br> При этом в первой работе учитывают погрешности дискретизации координат точек пересечения отрезков, чего нет в других алгоритмах, а во второй - рассматривается применение линейно-узлового алгоритма к криволинейным полигонам, о чём тоже пока приходится мечтать :)
Острова топить не хочу...
Просто, например, хотелось бы, чтобы при отсекании чего-нибудь с краю карты граница отсеченного полигона не содержала лишнего участка края. Впрочем, может быть, это и не обязательно. Главное - болота из лесов научиться вырезать
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 68 гостей