Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Сплит полигона. Ваше мнение господа... 26.07.05 19:25 Число просмотров: 2909
Автор: 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
|
- Сплит полигона. Ваше мнение господа... - void 26.07.05 19:25 [2909]
|
|
|
подробно о проекте
Анализ криптографических сетевых...
