1632
правки
Изменения
м
rollbackEdits.php mass rollback
Наряду с линейными комбинациями векторов рассматривают аффинные комбинации точек аффинного пространства <math>A</math>:
<math>\sum \lambda_i a_i</math>, где <math>\lambda_i \in \mathbb{R}, a_i \in A</math>.
По определению считают <math>\sum \lambda_i a_i = b + \sum \lambda_i \overrightarrow{(a_i - b)}, b \in A, \sum \lambda_i = 1</math> (можно показать, что только в {{Лемма|statement=В случае равенства единице суммы коэффициентов результат не зависит от выбора точки <mathtex>b</tex>.|proof=Рассмотрим точку <tex>b + \overrightarrow{l}</tex>, тогда <tex>\sum \lambda_i a_i = b + \overrightarrow{l} +\sum \lambda_i \overrightarrow{(a_i - (b+l))} = b+\sum \lambda_i \overrightarrow{(a_i - b)} + \overrightarrow{l} - \sum \lambda_i \overrightarrow{l} = </mathtex><tex>b +\sum \lambda_i \overrightarrow{(a_i - b)}+ \overrightarrow{l}(1 - \sum \lambda_i) = b +\sum \lambda_i \overrightarrow{(a_i - b).}</tex> }}
Также рассматривают понятие аффинной независимости точек (например, три точки на одной прямой аффинно зависимы).
Рассмотрим кососимметричную линейную форму от N N-мерных векторов, т.е. функцию <math>f: X \rightarrow \mathbb{R}</math>, обладающую свойством
<math>f(\hdotsx_1, xx_2, \hdots, yx_{n-1}, \hdotsx_n) = -f(\hdotsx_n, yx_{n - 1}, \hdots, xx_2, \hdotsx_1)</math>.
Из курса линейной алгебры известно, что любые две такие формы отличаются друг от друга только на некоторый множитель.
and orientation(b0, b1, a0) != orientation(b0, b1, a1)
В случае, если обе ориентации в одной из строк равны нулю, отрезки лежат на одной прямой, и в этом случае пересечение можно проверить способом, аналогичным пересечению отрезков на действительной прямой(считаем, что точки сравниваются лексикографически):
between(x, a0, a1) = (a0 <= x <= a1)
do_intersect = between(b0, a0, a1) || between(b1, a0, a1) || between(a0, b0, b1) || between(a1, b0, b1)
Если предикат вычисления ориентации был абсолютно точным, то таким же будет описанный алгоритм.
== Ссылки ==
