информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Spanning Tree Protocol: недокументированное применениеАтака на InternetГде водятся OGRы
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Блокировка российских аккаунтов... 
 Отзыв сертификатов ЦБ РФ, ПСБ,... 
 Памятка мирным людям во время информационной... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





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






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2022 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach