Главная > Математика > Геометрическое моделирование
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4.8. Определение точек пересечения линий

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

Пересечение двухмерных прямых линий.

Точка пересечения двухмерных прямых линий может быть найдена аналитически. Пусть даны двухмерные прямые

(4.8.1)

Прямые имеют точку пересечения, если их направляющие векторы не коллинеарны. Через обозначим единичные нормали к прямым . Если касательный вектор кривой имеет координаты x и у, то ортогональный ему вектор имеет координаты , где На рис. 4.8.1 показаны прямые (4.8.1) и (4.8.2), нормали к ним и точка пересечения . Из рисунка видно, что, например, параметр второй прямой для точки пересечения может быть найден как отношение проекции вектора на нормаль первой прямой к проекции вектора на ту же нормаль.

Рис. 4.8.1. Пересечение прямых

Аналогично найдем параметры точки пересечения для первой прямой:

Радиус-вектор точки пересечения найдем, подставив в (4.8.1) или (4.8.2) соответствующий параметр,

(4.8.5)

Пересечение двухмерных отрезков прямых.

Аналитически можно найти точку пересечения отрезков прямых. Пусть даны два отрезка прямых

построенных по точкам . Параметры их точки пересечения найдем из векторного уравнения

которое представляет собой систему двух скалярных уравнений

Если , то по формуле Крамера параметры точки пересечения равны

Отрезки пересекаются, если в противном случае пересекаются продолжения отрезков.

Частные случаи.

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

Общий случай пересечения двухмерных кривых.

Пусть требуется найти все точки пересечения двух двухмерных кривых, радиус-векторы которых описываются функциями . Для каждой точки пересечения должно удовлетворяться векторное уравнение

(4.8.6)

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

(4.8.7)

Неизвестными являются параметры кривых . Система уравнений в общем случае является нелинейной и решается итерационными методами. Точек пересечения может быть несколько и от того, с какого приближения параметров начнется итерационный процесс решения, зависит, к какой точке сойдется решение. Итерационный процесс определения параметров точки пересечения закончим, когда на очередной итерации не только параметры кривых удовлетворят заданным условиям, но и координаты точек удовлетворят заданным условиям точности. Процесс уточнения решения закончим, когда выполнятся неравенства . Это связано с тем, что координаты двухмерных кривых сами служат параметрами поверхностей. Для нахождения нулевого приближения каждой точки пересечения будем двигаться с вычисляемыми по формуле (4.2.3) шагами по кривым, в каждом сочетании точек строить касательные линии (4.8.1) и (4.8.2) к кривым и определять параметры точки их пересечения.

Для этого в (4.8.1) и (4.8.2) подставим значения: — точки на кривых, — производные кривых в этих точках. Параметры касательных прямых в точке их пересечения определим по формулам (4.8.3) и (4.8.4). Вблизи точки пересечения параметры приблизительно соответствуют приращениям параметров кривых, поэтому величины

(4.8.8)

могут быть приняты в качестве нулевого приближения при решении системы уравнений (4.8.6), если удовлетворяются условия

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

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

Полученные решения необходимо проверить на совпадение. Решения будем считать одинаковыми, если выполняются одновременно неравенства: , где Величину мы рассмотрим в конце главы.

Если заданные кривые имеют точку касания, то уравнения системы (4.8.7) являются линейно зависимыми и на некоторой итерации определитель системы станет недопустимо малым или равным нулю, и мы не сможем найти точку касания. В этом случае вместо векторного уравнения (4.8.6) можно решать систему скалярных уравнений

(4.8.9)

определитель которой не равен нулю в точке касания. Но системе (4.8.9) удовлетворяют не только точки касания, а еще и точки, в которых касательные прямые параллельны друг другу и ортогональны вектору, соединяющему точки, в которых построены касательные прямые. Поэтому после решения системы уравнений (4.8.9) следует проверить тот факт, что полученные точки являются точками касания.

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

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

(4.8.10)

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

Общий случай пересечения пространственных кривых.

С помощью системы уравнений (4.8.9) можно найти точки пересечения или касания пространственных кривых Системе уравнений

(4.8.11)

удовлетворяют точки пересечения пространственных кривых, точки касания пространственных кривых, а также точки, в которых касательные к кривым прямые ортогональны вектору, соединяющему точки построения касательных прямых. Система уравнений (4.8.11) получена из системы уравнений (4.8.9) путем замены в ней двухмерных кривых на трехмерные кривые После решения системы уравнений (4.8.11) следует проверить полученные точки на близость по формуле (4.8.10). Проверкой коллинеарности производных радиус-векторов кривых можно выделить среди полученных точек точки касания. Метод определения близости найденных точек с помощью радиуса погрешности (4.8.10) инвариантен по отношению к геометрическим размерам объектов и к единицам измерения координатной системы.

<< Предыдущий параграф Следующий параграф >>
Оглавление