Как разбить треугольник в прямоугольной области на N треугольников?

Question

[SergeySerge11]

Не могу найти ни одного алгоритма, вообще даже загуглить не могу, как это провернуть, а через 100 if не хочу делать, хотя сделал, но не нравится.
Всего больше 20 в третей степени комбинаций пересечение треугольников window прямоугольной области.

1. Треугольник внутри. 99% данных тут, а все остальное особые случаи, и с ними возня
   
2. Треугольник снаружи, есть вариант, что сама область внутри треугольника
   
3. Куча вариантов, одна или 2 или 3 стороны пересекают различные стороны прямоугольной области
   
4. Еще куча вариантов, с обработкой угловых областей прямоугольника, вот это самая сложная часть, все до легко, а вот тут сложная задача, угол квадрата внутри или нет, и там прям сотню проверок выползает
   

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


Всего там больше 20-30 что ли вариантов, как треугольник может пересечь прямоугольник, и в третей степени если для каждой вершины рассматривать, еще в 4 раза больше, если еще для каждой стороны, рассматривать, в общем код очень быстро растет в 5 сотен строк, а потом не знаешь где ошибку допустил.
Также непонятно, как делить треугольник, тоже миллион вариантов, наверняка есть более оптимальные способы размещения, например деление так, чтобы треугольники были вытянуты больше по горизонтали, чем по вертикали, так как их отрисовка горизонтальная.

Answer 1

[Rsa97]

Обычная задача клипинга в 2d-графике.
https://en.wikipedia.org/wiki/Sutherland%E2%80%93H...

Answer 2

[Wataru]

mayton2019 правильно вам сказал: сначала пересеките треугольник и ваш прямоугольник. А потом триангулируйте.

При пересечении у вас 2 выпуклых многоугольника. Алгоритм Сазерленда-Коэна тут немного перебор, ибо там один из многоугольников может быть не выпуклым. В вашем фиксированном случае скорее всего нет даже смысла заморачиваться с O(n log n) алгоритмом. Просто научитесь пересекать любые 2 отрезка. После чего пересеките каждую сторону треугольника с каждой стороной квадрата. Не надо считать за пересечение, если 2 отрезка параллельны и накладываются. Получите макимум 12 точек. К ним добавьте 3+4=7 вершины ваших многоугольников. Потом каждую точку проверьте на принадлежность обоим фигурам, и оставьте только те, которые лежат внутри или на границе. Потом постройте выпуклую оболочку из них (погуглите, эта-то задача вообще везде расписана).

Что касается триангуляции, то у вас там получится выпуклый многоугольник. Так что можно, например, провести все хорды из одной вершины. Если же вам нужна какая-то особо "хорошая" триангуляция, то гуглите "Триангуляция Делоне". Этот алгоритм не строит очень приплюснутых треугольников, где это возможно.

Answer 3

[mayton2019]

У тебя две задачи.

1) Первая - это пересечение треугольника и прямоугольника. Я не помню никаких
названий или реализаций этого алгоритма. Да. Сазерленд тебе будет полезен. Но он решает
только прямую и прямоугольник. Попробуй рассматривать треугольник - как многоугольник
и отрезай от него по одной стороне с 4 сторон.

2) Вторая называется - триангуляция. Она много где описана в инженерной графике. Книг
точно не помню но поищи. Шикин и Боресков. Эгрон. Павлидис. Они точно должны были
что-то писать про это.

Answer 4

[SergeySerge11]

Решил довольно 2 способами.
1. Рекурсивный алгоритм Отсеканием по граням, Top -> Right -> Bottom -> Left ->...
1. Запускаю функцию drawTriangle(a,b,c, Plane.Top); Начинаю обход с Верхнего разбиения.

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

//x0 y0 x1 y1 координаты точек прямоугольника. 
            byte b0 = (byte)((p0.X < x0 ? 8 : 0) | (p0.X > x1 ? 4 : 0) | (p0.Y < y0 ? 2 : 0) | (p0.Y > y1 ? 1 : 0));
            byte b1 = (byte)((p1.X < x0 ? 8 : 0) | (p1.X > x1 ? 4 : 0) | (p1.Y < y0 ? 2 : 0) | (p1.Y > y1 ? 1 : 0));
            byte b2 = (byte)((p2.X < x0 ? 8 : 0) | (p2.X > x1 ? 4 : 0) | (p2.Y < y0 ? 2 : 0) | (p2.Y > y1 ? 1 : 0));

3. По плоскости(линии) разрезания, перехожу к функции ее разрезания. Нахожу точки которые к ней относятся. Составляю из них маску.

//  например  для верхней, взять те где y меньше y0.  то есть чекаю 2 бит
      int _btop = ((b0 & 2) >>1 ) | ((b1&2) ) | ((b2&2)<<1);

4. В swith проверяю 8 комбинаций. (разрезаем треугольники, есть 2 типа разреза, на 2-1 и на 1-2 по сторонам)
- Комбинация равная 0b111 = 7 означает что все 3 точки за плоскостью, завершить функцию
-Комбинация 0b000 = 0 означает, что ни одной точки там нету, тогда повернуть по часовой стрелки, и перейти к 3.
- Комбинации 1,2,4 означают что одна точка за плоскостью, она локализована значениями 1,2,4. Тогда разрезать на 2 треугольника. Нахожу точки пересечения с данной линии разреза, решаю простое уравнение прямой по 2 точкам, от этой точки, к 2 внутренним точки (a,b)=>(Ab'), (a,c)=>(Ac' ). Нахожу значение функции на пересечении с линией разрезании. то есть подставляю в функцию, для Top Bottom, считаю по y от y0,y1...

public static float FunByX(float x,Vector2 p0, ,Vector2  p1){
    var dp = p1 - p0;
    return (dp.Y / dp.X) * (x - p0.X) + p0.Y;
} 
public static float FunByY(float y, ,Vector2 p0, ,Vector2  p1){}

Вызываю рекурсивно 2 функции drawTriangle для новых вершин {Ab',Ac',C}, {Ab',a,b} c следующей по часовой стрелки линии разрезания Top-> Right.
-Для комбинаций, 3,5,6 - 2 точки за линий разрезания. Делю на 1 треугольник, для точек a,b нахожу пересечение линий (a,c) (b,c) с линией разрезания Вызываю drawTriangle для точек {Ac', Bc', c} выхожу из функции.
Так же способ масштабируется для деления по выпуклому 4 угольнику.
Второй способ намного сложнее, куча if-ов что забываешь через минуту куда попал.