Найти все непересекающиеся области из графика связанных путей Безье

Question

У меня есть это: набор ребер, где ребро содержит:

• вектор связанных кривых Безье (геометрия)
• набор указателей на ребра neihboor на каждом конце

• указатели на две области, смежные с краем (ноль в начале)

  Класс Edge{векторные соседи [2]; Регион * регионы [2]; Геометрия БезьеПата; }

в плоскости нет пересекающихся ребер, я хочу найти все непересекающиеся области на плоскости, окруженные ребрами

пример:

Вы знаете алгоритм для этого?

Answer 1

Я предполагаю, что под "кривой Безье" вы подразумеваете "кубическую кривую Безье".

Параметрическое уравнение для кубической кривой Безье выглядит следующим образом.

B(U, t) = U * w(t)           (2x1 column vector)

U = [U1 U2 U3 U4]            (2x4 matrix)

       [    (1-t)^3      ]
w(t) = [3 * (1-t)^2 * t  ]   (4x1 column vector)
       [3 * (1-t)   * t^2]
       [              t^3]

Четыре столбца векторов U четыре последовательных точки на одной из ваших кубических кривых Безье.

Даны две кубические кривые Безье B(U, t) а также B(V, t), вы хотите определить, существуют ли какие-либо t0 а также t1 в [0,1] такой, что B(U, t0) = B(V, t1), Это ваши точки пересечения.

Чтобы решить это уравнение, вам нужно найти корни системы из двух многочленов 3-й степени с 2 переменными. Если вы посмотрите на все отчетливые t0 значения среди тех корней, которые скажут вам все точки пересечения для ваших кубических кривых Безье B(U, t) а также B(V, t),