MAXimal

добавлено: 11 Jun 2008 10:14
редактировано: 24 Aug 2011 12:06

Нахождение уравнения прямой для отрезка

Задача — по заданным координатам конца отрезка построить прямую, проходящую через него.

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

Двумерный случай

Пусть дан отрезок $PQ$ , т.е. известны координаты его концов $P_x$ , $P_y$ , $Q_x$ , $Q_y$ .

Требуется построить уравнение прямой на плоскости, проходящей через этот отрезок, т.е. найти коэффициенты $A$ , $B$ , $C$ в уравнении прямой:

$A x + B y + C = 0.$

Заметим, что искомых троек $(A,B,C)$ , проходящих через заданный отрезок, бесконечно много: можно умножить все три коэффициента на произвольное ненулевое число и получить ту же самую прямую. Следовательно, наша задача — найти одну из таких троек.

Нетрудно убедиться (подстановкой этих выражений и координат точек $P$ и $Q$ в уравнение прямой), что подходит следующий набор коэффициентов:

$A = P_y - Q_y,$
$B = Q_x - P_x,$
$C = - A P_x - B P_y.$

Целочисленный случай

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

Однако есть и небольшой недостаток: для одной и той же прямой могут получаться разные тройки коэффициентов. Чтобы избежать этого, но не уходить от целочисленных коэффициентов, можно применить следующий приём, часто называемый нормированием. Найдём наибольший общий делитель чисел $|A|$ , $|B|$ , $|C|$ , поделим на него все три коэффициента, а затем произведём нормировку знака: если $A<0$ или $A=0, B<0$ , то умножим все три коэффициента на $-1$ . В итоге мы придём к тому, что для одинаковых прямых будут получаться одинаковые тройки коэффициентов, что позволит легко проверять прямые на равенство.

Вещественнозначный случай

При работе с вещественными числами следует всегда помнить о погрешностях.

Коэффициенты $A$ и $B$ получаются у нас порядка исходных координат, коэффициент $C$ — уже порядка квадрата от них. Это уже может быть достаточно большими числами, а, например, при пересечении прямых они станут ещё больше, что может привести к большим ошибкам округления уже при исходных координатах порядка $10^3$ .

Поэтому при работе с вещественными числами желательно производить так называемую нормировку прямой: а именно, делать коэффициенты такими, чтобы $A^2 + B^2 = 1$ . Для этого надо вычислить число $Z$ :

$Z = \sqrt{ A^2 + B^2 },$

и разделить все три коэффициента $A$ , $B$ , $C$ на него.

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

Наконец, упомянем о сравнении прямых — ведь после такой нормировки для одной и той же прямой могут получаться только две тройки коэффициентов: с точностью до умножения на $-1$ . Соответственно, если мы произведём дополнительную нормировку с учётом знака (если $A<-\varepsilon$ или $|A|<\varepsilon, B<-\varepsilon$ , то умножать на $-1$ ), то получающиеся коэффициенты будут уникальными.

Трёхмерный и многомерный случай

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

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

$p + v t, ~~~ t \in \cal{R}.$

Т.е. прямая — это все точки, которые можно получить из точки $p$ прибавлением вектора $v$ с произвольным коэффициентом.

Построение прямой в параметрическом виде по координатам концов отрезка — тривиально, мы просто берём один конец отрезка за точку $p$ , а вектор из первого до второго конца — за вектор $v$ .