Обрезание двух двумерных треугольников

Question

Я знаю, что существуют эффективные алгоритмы отсечения полигонов (например, Maillot, Vatti, Greiner-Hormann). Однако эти алгоритмы работают для произвольных полигонов, и хотя они соответствуют моему случаю, мне кажется, что использование таких общих алгоритмов для простого случая, как мой, является излишним.

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

Q: Есть специализированный алгоритм отсечения двух 2D треугольников?

Answer 1

Для двух выпуклых форм традиционным подходом является только Sutherland Cohen, но с большим или меньшим количеством флагов.

E.g. в вашем случае:

• синий A находится за пределами красного AB, но внутри двух других красных краев; дайте ему код 100;
• синий B такой же; дайте ему код 100;
• синий C находится вне красного до н.э., но в двух других, так дайте ему код 010.

Начиная с:

• код не равен нулю, не включают в себя синий А в вывод;
• , глядя на крайний синий AB, двоичный И не равен нулю, поэтому не рассматривайте его для вывода;
• код для синего B отличен от нуля, не включает в вывод;
• коды B и C И до 0, поэтому XOR * их. Дает 110. Таким образом, найдите пересечения синего BC с краями красного AB и BC, добавьте их в список outpyt;
• код для синего C не равен нулю, не включает в вывод;
• коды для синих C и D снова указывают на пересечение с BC и AB, так что делайте это и добавляйте к выходу.

(* или OR их, мы установили, что они не разделяют ни одного бита общих, так что нет никакой разницы - я думаю, что XOR немного более описательным, говоря, что вы ищете различие)

Answer 2

Описаны два метода, эффективные для выпуклых многоугольников here - алгоритм Хойя и алгоритм О'Рурка.
(Я использовал O'Rourke один для выпуклых четырехугольников)

Answer 3

Просто подсказки для оптимизации.

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

Существует 9 таких треугольников, поэтому 9 областей и 9 знаков. Во всяком случае, три треугольника, построенные с той же вершиной (A), имеют области, которые суммируются с областью (B), и только 9 - 3 + 1 = 7 областей должны быть полностью вычислены.

Кроме того, точка пересечения между двумя ребрами вычисляется из двух областей, используя формулу типа t = S/(S - S '), где t - параметр вдоль ребра.

Таким образом, полностью развернутый алгоритм может быть записан как дерево решений глубины 9 (используя 9 подписанных областей), причем каждый лист (512 из них!) Генерирует последовательность вершин/пересечений. В худшем случае может быть 6 пересечений.