Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Сплит полигона. Ваше мнение господа... 26.07.05 19:25
Автор: void <Grebnev Valery> Статус: Elderman
|
Требуется разбить 2D полигон (проекция невыпуклого 3D полигона без «дыр») пересекающей проекцией полилинии (возможно самопересекающейся). Такая задача актуальна, например, в ГИС приложениях.
Адаптация известных простых алгоритмов отсечения (clipping), например, Sutherland-Hodgman (SH) не подходит из-за сложности задачи. Общий алгоритм Weiler-Atherton (WA) для выполнения булевых операций над полигонами (пересечение, объединение, разность) хорош, но представляется достаточно тяжеловесным для данной задачи. Кроме того, общий алгоритм WA решает задачу о двух полигонах. Его непосредственное использование затруднительно.
Ниже предлагается достаточно ясный алгоритм, который значительно легче в программировании, чем WA. Идея проста... Выберем первое пересечение полигона полилинией, и постоим два полигона – левый (SSL) и правый (SSR). Рекурсивно применим эту же операцию для левого и правого полигонов. Будем повторять рекурсию до тех пор, пока полигон делится. Если полигон не может быть разделён ( не имеет пересечения с полилинией), то рекурсия прекращается, а “неделимый” полигон сохраняется в массиве результатов расчётов.
Просьба высказаться о предлагаемом алгоритме; возможно указать, что данный алгоритм уже предлагался (я не мог найти такой информации); возможно также предложить, как это можно улучшить; возможно предложить другой эффективный алгоритм.
Пусть:
SUBJECT – полигон с вершинами SUBJECT[i], который необходимо разделить полилинией.
SPLITTER – полилиния с вершинами SPLITTER[i], которая пересекает полигон SUBJECT.
RESULT – массив результатов (элемент RESULT[i] является массивом вершин результирующих полигонов)
1) Получить массив INTERSECTION[] точек переечения SUBJECT & SPLITTER (точки пересечения получают, «как есть», без анализа «касаний» и других вырожденных случаев, когда, например, вершина или ребро SUBJECT инцидентна или совпадает со стороной SPLITTER).
2) Добавить точки пересечения в массивы SUBJECT[] и SPLITTER[] (аналогично тому, как это делают в WA; однако, здесь достаточно иметь только векторы (массивы) вершин, а не их двусвязанные списки, как в большинстве известных реализаций WA).
3) Анализирвать и нумеровать вершины пересечений. Как и в алгоритме WA, нумерация заключается в именовании вершины в качестве входящей (E - entering), или исходящей (L - leaving). При анализе вершин используются следующие интуитивные представления и эвристические утверждения (как и в других алгоритмах, например, Liang-Barsky):
3.1) Каждой входящей E-вершине должна соответствовать исходящая L-вершина. При нарушении этого условия E/L вершина отбрасывается (не считается пересечением).
3.2) Если SPLITTER пересекает SUBJECT, и при этом отсекает непустой левый полигон SSL (являющийся непустым подмножеством исходного полигона), и непустой правый полигон SSR, то найдётся, как минимум одно пересечение с E и L вершинами.
3.3) Если SSL или SSR пусто, то пересечение вырождено (например, сегменты полилинии совпадают с ребром полигона), а E и L вершины отбрасываются. Эти вершины удаляются как из массива SUBJECT[], так и SPLITTER[]. Фактического удаления вершин не происходит. Для этих вершин снимается флаг «пересечение».
3.4) Eсли SSL и SSR не пусто, то найдётся первое пересечение, которое делит SUBJECT на SSL и SSR (остальные пересечения не нужны для построения SSL и SSR, и отбрасываются). Для постороения SLL и SSR необходимо только первое пересечение полилинией SPLITTER полигона SUBJECT.
4) Если пересечение отсутствует ( SSL или SSR пусто ) добавить SUBJECT в массив результатов RESULT[].
5) Если пересечение не пусто, постороить SSL и SSR, как в WA.
6) Рекурсивно применять шаги 1-6 к левым и правым полигонам.
Преимущество данного алгоритма в простоте. Это позволяет создавать весьма надёжный и гибкий в модификации код. Алгоритм проверен на различных задачах ГИС. Работает устойчиво для любых полилиний, включая, самопересекающиеся, содержащие «кольца», сегменты, совпадающие с гранями полигонов, точки «касания» и другие вырожденные случаи, в том числе обусловленные ошибками пользовательского ввода координат полилинии.
ПС. Если админ слуйчайно заглянет... Подремонтируйте, пожалуйста, мой профиль. Я уже несколько лет не могу получать уведомления об ответах в форум. Мой майл - vg_123 at mail dot ru
|
|
Не совсем понятно, что именно надо, в каком виде и/или для... 29.07.05 11:01
Автор: leo <Леонид Юрьев> Статус: Elderman
|
Не совсем понятно, что именно надо, в каком виде и/или для чего. Разбить полигон полилинией на множество полигонов - это достаточно абстрактно. Для этого можно посоветовать только "полный" универсальный алгоритм. Но зная конечную цель (например - заливки разным цветом), можно посоветовать оптимальное решение, которое не будет делать ничего лишнего.
P.S.
Если можешь постить - значить помнишь (знаешь) пароль. Если знаешь пароль - можешь отредактировать свой профайл сам.
|
| |
Уточнение 29.07.05 15:27
Автор: void <Grebnev Valery> Статус: Elderman
|
> Не совсем понятно, что именно надо, в каком виде и/или для
> чего. Разбить полигон полилинией на множество полигонов -
> это достаточно абстрактно. Для этого можно посоветовать
> только "полный" универсальный алгоритм. Но зная конечную
> цель (например - заливки разным цветом), можно посоветовать
> оптимальное решение, которое не будет делать ничего
> лишнего.
>
> P.S.
> Если можешь постить - значить помнишь (знаешь) пароль. Если
> знаешь пароль - можешь отредактировать свой профайл сам.
>>Для этого можно посоветовать
> >только "полный" универсальный алгоритм.
Спасибо за мнение. Наиболее универсальный - WA (см. выше). Я постил, что:
1) он представляется слишком тяжёлым для этой задачи.
2) его нельзя применить непосредственно, поскольку WA решает задачу о булевых операциях наддвумя_полигонами
3) другого универсального алгоритма я не нашёл. В этом тоже и был поинт моего постинга.
Уточнение по задаче:
Полигоны (как исходный, так и генерируемые сплитом) имеют векторное представление. Кроме пространственной информации для каждого полигона храниться атрибутивная информация, например, в простейшем случае идентификатор базы RDBMS. Веторная информация о полигонах сохраняется и восстанавливается из файлов при работе приложений.
Задача состоит в том, чтобы разбить исходный полигон с меткой ID на n-"подполигонов" с метками ID1,..., IDn.
ПС. Спасибо за реакцию.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
