Каков наилучший алгоритм обрезки пути безье

Question

Я знаю два общих алгоритма Грейнера-Хормана и Ватти. Они работают с полигонами. Я хочу реализовать логические операции по путям безье. Я хочу расширить эти алгоритмы для работы с путями безье. Но это численная проблема. Каков наилучший способ обрезки пути безье? (и какова наилучшая модификация алгоритма Грейнера-Хормана для произвольных многоугольников (с самопересечениями))

Answer 1

Предлагаемый алгоритм.

1. использовать четыре контрольные точки для определения многоугольника, охватывающего кривую Безье.

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

3. если многоугольник перекрывается, разделите две кривой безье в два, используя одну итерацию casteljau. Остановите рекурсию, если размер кривой безье слишком мал относительно требуемой точности. В противном случае резюме рекурсивно с шагом 2.

В процессе деления кривой Безье, отслеживать, где вы (значение Т), чтобы можно было легко определить 4 управления точку подрезанной кривой Безье.

Обратите внимание, что в какой-то момент кривая Безье может быть аппроксимирована прямой. В этом случае совпадение теста и расщепления будет быстрее.

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