qweqweqe123123

Пересечение кривых

Мы уже показали, что для реализации булевских операций необходимо уметь рассчитывать точки пересечения кривых. Точку пересечения приходится также определять для отсечения части кривой другой кривой. В этом разделе мы кратко изложим основные сведения об алгоритмах поиска точек пересечения кривых, заданных параметрическими уравнениями. Описанный метод может использоваться для расчетов с произвольными кривыми следующих типов: эрмитовы кривые, кривые Безье, В-сплайн и NURBS. Методы расчета точек пересечения для кривых, заданных не параметрически, а также для кривых с уравнениями разных типов (параметрическими и непараметрическими) излагаются в работе Хоффманна [69].

Предположим, что пересекающиеся кривые заданы уравнениями Р(u) и Q(v). Значение параметра, соответствующее точкам пересечения, задается уравнением

Пересечение кривых

Обратите внимание, что уравнение (6.70) распадается на три скалярных уравнения с двумя неизвестными. Выберем какие-либо две компоненты векторов, например х и y:

Пересечение кривых

Решим уравнения (6.71) и (6.72) относительно и и v и воспользуемся оставшимся скалярным уравнением (компонентой z уравнения (6.70)), чтобы проверить полученные значения u и v. Системы нелинейных уравнений обычно решаются численными методами, такими как метод Ньютона—Рафсона [39]. Последний требует вычисления производных Рx, Qx, Ру, Qy, для чего нам потребуются выведенные в разделах 6.4.1, 6.5.3 и 6.6.2 формулы дифференцирования уравнений кривых.

Решая уравнения (6.71) и (6.72) любым численным методом, мы можем столкнуться со следующими проблемами.

□   Итерации могут разойтись, если начальные приближения и и о окажутся слишком далеки от настоящих решений.

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

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

□   Если в некоторых местах расстояние между кривыми очень мало, координаты этих участков могут быть возвращены в качестве точек пересечения (в зависимости от внутренней погрешности алгоритма).

Первая и вторая проблемы решаются последовательным заданием начальных приближений, близких к реальным точкам пересечения. Для кривых Безье и В- сплайнов начальные приближения могут быть получены путем аппроксимации кривых отрезками. В приложении Ж мы показали, что аппроксимация кривой Безье или В-сплайна отрезками получается путем последовательного деления такой кривой. Третья проблема обычно возникает при расчете точек пересечения простых кривых, например отрезков или дуг окружностей. Например, мы можем попытаться найти численным методом точку пересечения двух дуг, лежащих на одной и той же окружности, преобразовав уравнение каждой из них к уравнению NURBS. Вспомните, что это преобразование часто выполняется для того, чтобы одна программа могла работать с кривыми любых типов. Численный метод не может обнаружить перекрытие, поэтому он возвратит неопределенное количество точек пересечения, зависящее от начального приближения. Следовательно, проверять возможность перекрытия следует до вызова численного метода. Эта проверка может осуществляться путем сравнения характерных параметров кривых, например центров и радиусов дуг, перед преобразованием их к форме NURBS. Четвертую проблему в большинстве случаев можно решить, правда не полностью, аккуратной настройкой точности численного метода.

Рассмотрим теперь более простой метод определения точки пересечения, который применим в том случае, если одна из кривых является прямой. Предположим, что Р(u) — уравнение прямой, a Q(v) — уравнение кривой. Если прямая проходит через точки, положение которых задается векторами Р0 и Р1, то ее уравнение может быть записано следующим образом:

Пересечение кривых

Параметры и и v в точке пересечения должны, таким образом, удовлетворять уравнению

Пересечение кривых

Умножим левую и правую части уравнения (6.74) скалярно на Р0х Р1:1

Пересечение кривых

Нелинейное уравнение (6.75) может быть решено относительно v численным методом. Однако здесь нас подстерегают те же проблемы, что и раньше.

 


1 Уравнение получается таким, потому что скалярное произведение Р0 или P1 на равно нулю.

Смотрите также