Безье

Ответ 1

Я нашел следующую публикацию лучшей информацией о Безье Clipping:

Т. W. Sederberg, BYU, Примечания к курсу по автоматизированному геометрическому дизайну

Глава 7, в которой говорится о пересечении кривых, доступна в Интернете. В нем описываются 4 разных подхода к поиску пересечений и подробно описывается Безье:

http://www.tsplines.com/technology/edu/CurveIntersection.pdf

Ответ 2

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

Вы можете переписать кривые Безье как набор из двух бивариантных кубических уравнений, таких как:

• Δx = ax₁ * t₁ ^ 3 + bx₁ * t₁ ^ 2 + cx₁ * t₁ + dx₁ - ax₂ * t₂ ^ 3 - bx₂ * t₂ ^ 2 - cx₂ * t₂ - dx₂
• Δy = ay₁ * t₁ ^ 3 + by₁ * t₁ ^ 2 + cy₁ * t₁ + dy₁ - ay₂ * t₂ ^ 3 - by₂ * t₂ ^ 2 - cy₂ * t₂ - dy₂

Очевидно, кривые пересекаются для значений (t₁, t₂), где Δx = Δy = 0. К сожалению, это осложняется тем, что трудно найти корни в двух измерениях, а приближенные подходы имеют тенденцию (как другой писатель сказал) взорвать.

Но если вы используете целые числа или рациональные числа для своих контрольных точек, то вы можете использовать базы Groebner, чтобы переписать ваши двучленные полиномы порядка-3 в (возможно, порядок-9-так-ваши-девять-возможные-пересечения) monovariate полином. После этого вам просто нужно найти свои корни (например, t₂) в одном измерении и включить свои результаты обратно в одно из ваших исходных уравнений, чтобы найти другое измерение.

У Burchburger есть непрофессиональное введение в базы Groebner под названием " Gröbner Bases: Краткое введение для системных теоретиков", что было очень полезно для меня. Погугли это. Другим документом, который был полезен, был назван " Быстрый, точный сглаживание кубического пути Безье и кривые смещения" TF Hain, который имеет множество уравнений полезности для кривых Безье, в том числе, как найти коэффициенты полинома для уравнений x и y.

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

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

Если вы хотите, чтобы какой-то готовый код в Haskell обнаружил перекрестки, дайте мне знать.

Ответ 3

Я написал код, чтобы сделать это долго, давным-давно. В проекте я работал над определенными 2D-объектами, используя кусочные границы Безье, которые были созданы как пути PostScipt.

Подход, который я использовал, был:

Пусть кривые p, q, определяются контрольными точками Безье. Они пересекаются?

Вычислить ограничивающие поля контрольных точек. Если они не перекрываются, то две кривые не пересекаются. Иначе:

p.x(t), p.y(t), q.x(u), q.y(u) - кубические полиномы на 0 <= t, u <= 1.0. Квадрат расстояния (p.x - q.x) ** 2 + (p.y - q.y) ** 2 является многочленом на (t, u). Используйте Newton-Raphson, чтобы попытаться решить это для нуля. Отбросить любые решения вне 0 <= t, u <= 1.0

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

Если N-R не сходится на решении, разделим одну кривую (скажем, p) на две кривые pa, pb при t = 0,5. Это легко, просто вычисляя средние точки, как показывает связанная статья. Затем рекурсивно проверяем (q, pa) и (q, pb) для пересечений. (Заметим, что в следующем слое рекурсии q стал p, так что p и q поочередно расщепляются на каждом слое рекурсии.)

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

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

Когда вы найдете пересечение, вы не закончите, потому что кубические кривые могут иметь несколько пересечений. Таким образом, вам нужно разбить каждую кривую на пересекающейся точке и рекурсивно проверить наличие большего количества взаимосвязей между (pa, qa), (pa, qb), (pb, qa), (pb, qb).

Ответ 4

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

http://www.andrew.cmu.edu/user/sowen/abstracts/Se306.html

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.6669

http://www.dm.unibo.it/~casciola/html/research_rr.html

Я рекомендую методы интервалов, потому что, как вы описываете, вам не нужно делиться на многоугольники, и вы можете получить гарантированные результаты, а также определить свою произвольную точность для набора результатов. Для получения дополнительной информации об интервальном рендеринге вы также можете обратиться к http://www.sunfishstudio.com