Триангуляция Полигона с "отверстием"

Программирование на Юнити.

Триангуляция Полигона с "отверстием"

Сообщение Roman777 13 май 2018, 19:08

Добрый день!
Интересуют алгоритмы триангуляции произвольного многоуголника (не самопересекающегося) с отверстиями (1-н и более) внутри. Без отверстий, триангулировать, вроде бы, получилось. А вот с ними как-то посложнее.
Пока думаю, что необходимо сводить такой "полигон" к полигонам без отверстий, тобишь разрезать его на отдельные кусочки через эти "дырки", так чтобы внутри каждого кусочка отверстий не было.

Наверняка кто-то уже работал с подобным вопросом, подскажите направление, плз)
Roman777
UNIт
 
Сообщения: 68
Зарегистрирован: 06 мар 2016, 12:09

Re: Триангуляция Полигона с "отверстием"

Сообщение jetyb 14 май 2018, 13:55

Каждый многоугольник и каждая дырка - не пересекающийся набор треугольников.

Сделайте сперва "вычитание" одного треугольника ABC из другого DEF: триангуляцию первого треугольника, ABC не пересекающуюся с вычитаемым треугольником DEF.
jetyb
Адепт
 
Сообщения: 1330
Зарегистрирован: 31 окт 2011, 17:21

Re: Триангуляция Полигона с "отверстием"

Сообщение Roman777 15 май 2018, 21:57

Думаю, что Ваше предложение должно рассматриваться при определённых случаях (алгоритмах) триангуляции произвольного полигона без отверстий, типа того же Делоне, я правильно понимаю? Я же пока выполнил триангуляцию с "ухообрезанием". В рамках данного алгоритма (ухообрезание) триангуляции, описанный Вами метод мне кажется недостижим...
Roman777
UNIт
 
Сообщения: 68
Зарегистрирован: 06 мар 2016, 12:09

Re: Триангуляция Полигона с "отверстием"

Сообщение IDoNotExist 16 май 2018, 08:20

Roman777 писал(а): Я же пока выполнил триангуляцию с "ухообрезанием".

Получается у тебя триангуляция идёт по последовательному набору точек (полилиния)? В чем проблема создать полилинию так, чтобы она обходила это отверстие и пересекалась с собой одним ребром?
Аватара пользователя
IDoNotExist
Адепт
 
Сообщения: 1169
Зарегистрирован: 23 мар 2011, 09:18
Skype: iamnoexist

Re: Триангуляция Полигона с "отверстием"

Сообщение Roman777 16 май 2018, 21:22

Получается у тебя триангуляция идёт по последовательному набору точек (полилиния)

В общем то да. И проблем нет. Просто сложности появляются, если этих отверстий несколько (много) на полигоне, поскольку такую диагональ уже может и не получиться провести непосредственно до этой полилинии без пересечения других отверстий. Собственно, поэтому думаю о похожем методе деления этого полигона на кусочки, которые будут отрезаться по 1 куску сквозь отверстие (надо только алгоритм продумать), чтобы получить несколько полигончиков уже без отверстий. Но тему создавал не потому что у меня появились конкретные проблемы, а просто хотел узнать ещё разные направления и способы решения данной задачи, чтобы определиться, куда стоит копать, а может быть и попробовать разное)
Roman777
UNIт
 
Сообщения: 68
Зарегистрирован: 06 мар 2016, 12:09

Re: Триангуляция Полигона с "отверстием"

Сообщение IDoNotExist 17 май 2018, 08:59

Алгоритмы булевого вырезания как вариант.
Аватара пользователя
IDoNotExist
Адепт
 
Сообщения: 1169
Зарегистрирован: 23 мар 2011, 09:18
Skype: iamnoexist


Вернуться в Скрипты

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3