Как нарезать простой многоугольник с линией

Question

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

Основные выпуклые случаи, всегда приводящие к двум подполигонам, просты, но как бы я справился со сложной вогнутой формой? Возьмите, например, многоугольник в форме буквы «Е». Вертикальный срез может дать 4 полигона. Как я могу определить, какие вершины составляют каждый из этих подполигонов?

Определение многоугольника: у меня есть два варианта здесь. Мой многоугольник может быть упорядоченным списком вершин или массивом треугольников. Я бы предпочел решение, которое использует массив треугольников. Должно быть довольно легко пройти через каждый треугольник и отрезать его с линией, если они пересекаются. Но тогда я понятия не имею, как сгруппировать эти треугольники в получающиеся подполигоны.

Псевдокод или даже общий совет - это хорошо; реализация C # идеальна.

Answer 1

У меня есть этот алгоритм в моей библиотеке PolyK .Вот демо .Если вы понимаете Javascript, я уверен, что будет легко переписать его на ваш язык программирования.

Answer 2

Некоторое время назад я дал этот ответ на несколько иной вопрос.

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

Основная идея состоит в том, чтобы рассматривать ребра всех треугольников как направленные векторы, а затем отбрасывать равные, но противоположные ребра.

В вашем случае у вас будет группа треугольников, представляющих исходныйформа.Вы бы нарезали отдельные треугольники с линией.Затем вы могли бы объединить треугольники в фигуры, используя метод, описанный выше, с условием, что нарезанные края не будут отменены.

В ответе, указанном выше, есть подробности и рисунки.Но суммировать шаги можно было бы следующим образом:

1. Выполнить разбиение треугольника

2. Для каждого полученного треугольника добавьте три направленные ребра в набор.Чтобы определить порядок по часовой стрелке, посмотрите ответы на этот вопрос .

3. Просмотрите набор ребер, удалив пары ребер, которые равны, но противоположны (если только ониявляются краями среза)

4. Выберите ребро в наборе, затем найдите ребро, хвост которого совпадает с головкой первого ребра.Затем повторите для этого края, пока не дойдете до начального края.Удалите каждое ребро из набора ребер, когда вы доберетесь до него.Всякий раз, когда вы добираетесь до начального ребра, у вас есть замкнутый цикл, представляющий один из результирующих полигонов.

5. Выполняйте шаг 4, пока не останется ребер.

Все это соответствует вашему желанию начать с триангуляции вашего многоугольника.Но, как отметил один из комментаторов к вашему первоначальному вопросу, вы можете рассмотреть альтернативы, указанные в Создание новых многоугольников из отрезанного многоугольника (2D) .