информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыSpanning Tree Protocol: недокументированное применениеВсе любят мед
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Microsoft предупредила о двух незакрытых... 
 Перевод Firefox на DNS over HTTPS 
 Microsoft закрыла серьёзную уязвимость,... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Уточнение 29.07.05 15:27  Число просмотров: 2543
Автор: void <Grebnev Valery> Статус: Elderman
<"чистая" ссылка>
> Не совсем понятно, что именно надо, в каком виде и/или для
> чего. Разбить полигон полилинией на множество полигонов -
> это достаточно абстрактно. Для этого можно посоветовать
> только "полный" универсальный алгоритм. Но зная конечную
> цель (например - заливки разным цветом), можно посоветовать
> оптимальное решение, которое не будет делать ничего
> лишнего.
>
> P.S.
> Если можешь постить - значить помнишь (знаешь) пароль. Если
> знаешь пароль - можешь отредактировать свой профайл сам.

>>Для этого можно посоветовать
> >только "полный" универсальный алгоритм.

Спасибо за мнение. Наиболее универсальный - WA (см. выше). Я постил, что:
1) он представляется слишком тяжёлым для этой задачи.
2) его нельзя применить непосредственно, поскольку WA решает задачу о булевых операциях наддвумя_полигонами
3) другого универсального алгоритма я не нашёл. В этом тоже и был поинт моего постинга.

Уточнение по задаче:
Полигоны (как исходный, так и генерируемые сплитом) имеют векторное представление. Кроме пространственной информации для каждого полигона храниться атрибутивная информация, например, в простейшем случае идентификатор базы RDBMS. Веторная информация о полигонах сохраняется и восстанавливается из файлов при работе приложений.
Задача состоит в том, чтобы разбить исходный полигон с меткой ID на n-"подполигонов" с метками ID1,..., IDn.

ПС. Спасибо за реакцию.
<theory>
Сплит полигона. Ваше мнение господа... 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.

ПС. Спасибо за реакцию.
1






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


  Copyright © 2001-2020 Dmitry Leonov   Page build time: 1 s   Design: Vadim Derkach