разделить треугольники на перекрытие

Question

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

Как вычислить многоугольники (и, в свою очередь, тесселяцию их), которые получаются в результате вычитания второго треугольника (зеленого) из первого?

(Я использую Python и ищу объяснение и псевдокод подхода, который я могу использовать, а не рекомендации для непрозрачных библиотек. (В настоящее время я использую gluTess*(), чтобы выполнить тесселяцию полигонов, но было бы интересно объяснить, как сделать тесселяцию самостоятельно; моя насущная проблема - это действительно булева операция.) Будет интересно узнать и понять решениеМои треугольники всегда закручиваются против часовой стрелки, если это что-то меняет.)

Answer 1

Давайте пройдемся по некоторым сценариям ...

Случай 1 : треугольники не перекрываются (или касаются, но не перекрываются)

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

Если мы находимся в случае 1нам ничего не нужно делать.

Случай 2 : зеленый треугольник находится внутри красного треугольника.

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

Теперь для этого случая нарисуйте отрезок линии от каждой из зеленых вершин до каждой из красных вершин (всего 9 новых отрезков линии).Если какой-либо из этих новых отрезков линии пересекается с зеленым треугольником, удалите их (вы можете проверить это, используя метод пересечения отрезка с каждой из сторон зеленого треугольника).Теперь проверьте, не пересекаются ли какие-либо из оставшихся новых отрезков;если есть два, то устраните один и повторите тестирование, пока у вас не останется новых отрезков, пересекающихся друг с другом.

Случай 3 : зеленый треугольникперекрывает красный треугольник, где две стороны зеленого треугольника входят в красный треугольник и также выходят из красного треугольника.

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

Теперь для этого случая нарисуйте отрезок линии от каждой из точек пересечения (каждого места, где зеленая сторона пересекается с красной стороной) до каждой из красных вершин.Если какой-либо из этих отрезков в основном дублирует красные края, удалите их.Если какой-либо из этих новых отрезков линии пересекается с зеленым треугольником, удалите их (вы можете проверить это, используя метод пересечения отрезка с каждой из сторон зеленого треугольника).Теперь проверьте, не пересекаются ли какие-либо из оставшихся новых отрезков;если есть два, устраните один и повторите тестирование, пока у вас не останется новых отрезков, пересекающихся друг с другом.

Случай 4 : зеленый треугольникперекрывает красный треугольник, где две стороны зеленого треугольника входят в красный треугольник, но они не оставляют красный треугольник с другой стороны.

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

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

Случай 5 : зеленый треугольник перекрывает красный треугольник, где только одна сторона зеленого треугольника входит в красный треугольник и где эта же зеленая сторона выходитдругая сторона красного треугольника.

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

Теперь для этого случая нарисуйте отрезок линии от каждой из точек пересечения (каждое место, где зеленая сторона пересекается с красной стороной) до каждой из красных вершин. Если какой-либо из этих отрезков в основном дублирует красные края, удалите их. Если какой-либо из этих новых отрезков линии пересекается с зеленым треугольником, удалите их (вы можете проверить это, используя метод пересечения отрезка с каждой из сторон зеленого треугольника). Теперь проверьте, не пересекаются ли какие-либо из оставшихся новых отрезков; если есть два, то устраните один и повторите тестирование, пока у вас не останется новых отрезков, пересекающихся друг с другом.

И, надеюсь, на этом все готово!

Answer 2

Я уверен, что вы можете найти универсальные алгоритмы вычитания, отсечения и триангуляции многоугольника, которые можно применять, но поскольку вы ограничены треугольниками, применяются более простые методы.

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

resultSet := {}   // set of triangles
currentPoly := originalTriangle
for each edge E of secondTriangle:
    if E intersects currentPoly (*):
        Extend edge E to line L
        Split currentPoly by L into outerPoly and otherPoly (**)
        // outerPoly is on the side corresponding to the outside
        // of secondTriangle (right side if going CCW)
        resultSet += triangulatation of outerPoly (***)
        currentPoly := otherPoly
if resultSet is empty:
    resultSet := originalTriangle // no intersections

(*) Сегмент линии пересекает многоугольник, если сегмент пересекает любое из ребер многоугольника или если он полностью содержится в многоугольнике.Для этого алгоритма лучше всего рассматривать совпадающие линии как непересекающиеся (поскольку расщепление не произойдет).

(**) Алгоритм расщепления выпуклого многоугольника линией

result := [[],[]]   // two empty lists of points
intersectionCount = 0
for each point P in the polygon:
    // each point is added to one of the result polygons
    result[intersectionCount % 2] += P
    E := edge between P and the next point Q
    if E intersects L at R:
       // each intersection point is added to both result polygons
       if R is not equal to P:
           result[intersectionCount % 2] += R
       intersectionCount += 1
       if R is not equal to Q:
           result[intersectionCount % 2] += R

(***) externalPoly всегда будет треугольником или четырехугольником и, следовательно, тривиально для триангуляции.

Answer 3

Возможно, глупый подход, но уже поздно, и мой мозг перегружен после 10 часов работы:

1. Слияние всех треугольников в многоугольник (с возможными отверстиями).
2. Триангуляцияполигон.
3. Для каждого полученного треугольника проверьте, принадлежит ли он только к красному треугольнику.

Пример объединенного и триангулированного многоугольника:

Пример, когда один из треугольников полностью находится внутри другого:

При триангуляции хитрость заключается в том, чтобы повторно использовать любые точки из полностью заключенного треугольника.У вас также будет набор «жестких» линий (нарисованных сплошными), которые представляют сегменты сторон существующих треугольников и «мягких» линий (нарисованных пунктирной линией), которые вы должны определить с помощью триангуляции.

Я вполнеконечно, есть лучшие способы сделать это, но вы идете ...

Answer 4

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

Как только вы получите эти отличные фигуры (в приведенном выше примере, одну четырехстороннюю и одну трехстороннюю фигуру), вы удалите все фигуры, которые являются трехсторонними, из списка «необходимо вычислить» (так как это уже треугольники).

Далее, у вас должна остаться одна фигура или не фигуры (вы можете иметь только одну или две фигуры после наложения одного треугольника поверх другого), но на самом деле, если вы хотите более общий подход, вы можете применить это на все формы, которые вы оставили (после треугольников). Теперь выделите вершины каждой имеющейся фигуры и присвойте им порядок по часовой стрелке или против часовой стрелки. Начните с вершины 1, затем перейдите к вершине 1 + 2 и попытайтесь нарисовать линию, чтобы получить треугольник (проверьте наличие граничных задач, таких как рисование линии за пределами вашего исходного треугольника). Если вы столкнулись с проблемой границы, двигайтесь вверх и попробуйте следующую вершину, пытаясь нарисовать линию к вершине 1 + 3. Дело в том, что вы пропускаете самую смежную вершину и рисуете линию в вершине, которая находится сразу после этой, а затем пробуете все вершины за этим, пока не достигнете смежности снова. В этом случае вы строите треугольники по определению (так как они должны иметь 3 стороны, используя этот метод).

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

Вот (по общему признанию ужасный) анимированный GIF, который я сделал, чтобы показать метод: