Точка пересечения сплайна и линии

Question

Я пытаюсь найти способ рассчитать пересечение между b-сплайном и прямой линией. Пока что Google не особо помог.

Answer 1

Самый эффективный алгоритм, о котором я когда-либо слышал, называется отсечкой Безье.

Вот глава книги о пересечении кривых и сплайнов (pdf).

Answer 2

Чисто математический подход:

• Преобразуйте сплайн и линию так, чтобы линия лежала на оси X.
• Рассчитать точки на сплайне, где Y = 0 (зависит от порядка сплайна).
• Преобразуйте эти точки обратно в исходную систему коринат.

Если вы идете по этому пути, я могу выработать необходимые формулы.

Answer 3

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