Сплит полигона

[vg]

Требуется разбить 2D полигон (проекция невыпуклого 3D полигона без «дыр») пересекающей проекцией полилинии (возможно самопересекающейся). Такая задача актуальна, например, в ГИС приложениях.

Адаптация известных простых алгоритмов отсечения (clipping), например, Sutherland-Hodgman (SH) не подходит из-за сложности задачи. Общий алгоритм Weiler-Atherton (WA) для выполнения булевых операций над полигонами (пересечение, объединение, разность) хорош, но представляется достаточно тяжеловесным для данной задачи. Кроме того, общий алгоритм WA решает задачу о двух полигонах. Его непосредственное использование затруднительно.

Ниже предлагается достаточно ясный алгоритм, который значительно легче в программировании, чем WA. Идея проста... Выберем первое пересечение полигона полилинией, и постоим два полигона – левый (SSL) и правый (SSR). Рекурсивно применим эту же операцию для левого и правого полигонов. Будем повторять рекурсию до тех пор, пока полигон делится. Если полигон не может быть разделён ( не имеет пересечения с полилинией), то рекурсия прекращается, а “неделимый” полигон сохраняется в массиве результатов расчётов.

Просьба высказаться о предлагаемом алгоритме; возможно указать, что данный алгоритм уже предлагался (я не мог найти такой информации); возможно также предложить, как это можно улучшить; возможно предложить другой эффективный алгоритм.

Пусть:

SUBJECT – полигон с вершинами SUBJECT, который необходимо разделить полилинией.
SPLITTER – полилиния с вершинами SPLITTER, которая пересекает полигон SUBJECT.
RESULT – массив результатов (элемент RESULT является массивом вершин результирующих полигонов)

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 к левым и правым полигонам.


Преимущество данного алгоритма в простоте. Это позволяет создавать весьма надёжный и гибкий в модификации код. Алгоритм проверен на различных задачах ГИС. Работает устойчиво для любых полилиний, включая, самопересекающиеся, содержащие «кольца», сегменты, совпадающие с гранями полигонов, точки «касания» и другие вырожденные случаи, в том числе обусловленные ошибками пользовательского ввода координат полилинии.

[oblom]

s kem eto ti seichas razgovarivaesh?

[vg]

Для особо одарённых

... Просьба высказаться о предлагаемом алгоритме; возможно указать, что данный алгоритм уже предлагался (я не мог найти такой информации); возможно также предложить, как это можно улучшить; возможно предложить другой эффективный алгоритм.

[oblom]

ti iavno pereocenivaesh nashu publicu

[vg]

ti iavno pereocenivaesh nashu publicu

Здесь есть ребята, которые программируют ГИС задачи. Наверняка есть, кто занимается графикой, играми. Не часто, но движки пишут и сами. Сам видел одну САПР-контору, где графические движки писаны руками (отказался поощрять это безобразие). Математика здесь - основа для операций заливок, скрытия невидимых линий и т.д. Это очень общие алгоритмы обеспечения компьютерной графики. Публика здесь и в штатах в коледжах это учит. Сам видел их учебные материалы.

[Димас]

"Мне ваши стихи про кефир очень понравились". Шматрица (Гоблин)

Скажи VG, я что-то не догнал, алгоритм уже реализован и отлично работает? Почему тогда интересно мнение других?
Я лично очень заинтересован в таком алгоритме. Если он действительно хорошо работает, завтра брошусь писать.
Мне вот еще в голову идея пришла - а нет ли таких функций в DirextX (или типа в Direct3D). По идеи похожие задачи должны там часто считаться. А еще высока вероятность, что эта функция будет использовать аппаратные возможности 3D ускорителя, т.е. скорость должна быть бы бешенная. А скорость мне потребуется, так как обсчитывать надо миллилны полилиний.

[aissp]

Вроде написано что главное преимущество в , блин, простоте. Поетому чего ты не догоняешь на понятно. Впрочем тебе гораздо лучше, я вот и условие с трудом... Как представил себе 3-d полигон разбитый на части полилинией (нет соврал проекцией еейной) поплохело мне... и не представил я его. Пойду выпью йаду

[Димас]

Вроде написано что главное преимущество в , блин, простоте. Поетому чего ты не догоняешь на понятно. Впрочем тебе гораздо лучше, я вот и условие с трудом... Как представил себе 3-d полигон разбитый на части полилинией (нет соврал проекцией еейной) поплохело мне... и не представил я его. Пойду выпью йаду

Не догоняю - алгоритм классно работает или есть изъяны?
У меня чуть проще задача - найти пересечение между полигоном и другим полигоном или полилинией.

[aissp]

Попробуй тут

http://geos.refractions.net/

[vg]

Вроде написано что главное преимущество в , блин, простоте. Поетому чего ты не догоняешь на понятно. Впрочем тебе гораздо лучше, я вот и условие с трудом... Как представил себе 3-d полигон разбитый на части полилинией (нет соврал проекцией еейной) поплохело мне... и не представил я его. Пойду выпью йаду

Не догоняю - алгоритм классно работает или есть изъяны?
У меня чуть проще задача - найти пересечение между полигоном и другим полигоном или полилинией.

Алгоритм работает хорошо, пля любых 2D фигур, включая невыпуклые многоугольники, вырожденные случаи пересечения ("касания" рерба или вершины, "совпадение" в ребром и т.д.). Меня просто сильно удивило, что я не увидел схожего. Кажется, я внятно написал в начале топика, что я хочу.

Если тебе нужно быстро решить задачу - рекомендую взять известные имплементации (в интернет есть куча исходников С/C++)
алгоритма Вейлера. Тогда не придётся программировать. Или можешь имплементировать то, что я вверху написал (придется тебе программировать).

[Димас]

Если тебе нужно быстро решить задачу - рекомендую взять известные имплементации (в интернет есть куча исходников С/C++)
алгоритма Вейлера. Тогда не придётся программировать. Или можешь имплементировать то, что я вверху написал (придется тебе программировать).

Спасибо за ответ!
Мне на C# надо, поэтому возьму твой алгоритм и вперед.

[vg]

Если тебе нужно быстро решить задачу - рекомендую взять известные имплементации (в интернет есть куча исходников С/C++)
алгоритма Вейлера. Тогда не придётся программировать. Или можешь имплементировать то, что я вверху написал (придется тебе программировать).

Спасибо за ответ!
Мне на C# надо, поэтому возьму твой алгоритм и вперед.

Вот и хорошо. Могу прислать войд чек твоей компании.

[Димас]

Если тебе нужно быстро решить задачу - рекомендую взять известные имплементации (в интернет есть куча исходников С/C++)
алгоритма Вейлера. Тогда не придётся программировать. Или можешь имплементировать то, что я вверху написал (придется тебе программировать).

Спасибо за ответ!
Мне на C# надо, поэтому возьму твой алгоритм и вперед.

Вот и хорошо. Могу прислать войд чек твоей компании.

Э-э. Наверное сначала в инете посмотрю классические алгоритмы.

[vg]

Если тебе нужно быстро решить задачу - рекомендую взять известные имплементации (в интернет есть куча исходников С/C++)
алгоритма Вейлера. Тогда не придётся программировать. Или можешь имплементировать то, что я вверху написал (придется тебе программировать).

Спасибо за ответ!
Мне на C# надо, поэтому возьму твой алгоритм и вперед.

Вот и хорошо. Могу прислать войд чек твоей компании.

Э-э. Наверное сначала в инете посмотрю классические алгоритмы.

Да ты не обращай внимания на мои шутки по поводу чека. Пользуйся наздоровье.
А классиков надо посмотреть в любом случае. Хотя бы для того, чтобы знать терминологию, области применения, ограничения.
Ну а послу уж, самое классное, конечно, если найдёшь готовую подходящую имплементацию на C#, пусть и "неэффективную" и ограниченную. Ибо тратить время на такую ерунду всегда не хочется.