Векторное произведение в вычислительной геометрии

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

Теория

Итак, пусть у нас есть два двухмерных вектора \vec{p_1} и \vec{p_2} с координатами (x_1, y_1) и (x_2, y_2) соответственно. Векторным произведением двух векторов p_1 x p_2 называется определитель матрицы:

\begin{vmatrix} x_1 & x_2 \\  y_1 & y_2  \end{vmatrix} = x_1 y_2 - x_2 y_1 = \vec{p_1} \times \vec{p_2}

В принципе, координаты векторов можно записывать не столбцами, а строками, так как в результате транспонирования определитель матрицы не меняется.

На практике этот определитель даёт очень полезную информацию о том, в какой полуплоскости находится вектор \vec{p_2} относительно вектора \vec{p_1}. Итак, если сделать параллельный перенос вектора \vec{p_2}, так, чтобы его начало совпадало с началом вектора \vec{p_1}, то возможно три случая:

  1. \vec{p_1} \times \vec{p_2} > 0, то вектор \vec{p_2} находится в направлении против часовой стрелки относительно вектора \vec{p_1}.
  2. \vec{p_1} \times \vec{p_2} = 0, то векторы \vec{p_1} и \vec{p_2} коллинеарны.
  3. \vec{p_1} \times \vec{p_2} < 0, то вектор \vec{p_2} находится в направлении по часовой стрелке относительно вектора \vec{p_1}.

Разбиение плоскости на полуплоскости по знаку векторного произведения относительно вектора \vec{p_1} показано на следующем рисунке:

Зоны знака векторного произведения относительно первого вектора

Ну и для наглядности – направления кратчайшего пути от первого до второго вектора при положительном и отрицательном векторном произведении:

Примеры знака результата векторного произведения

Немного практики

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

Пример использованияПервое очевидное, и довольно часто встречающееся применение – это определение, в какую сторону поворачивает отрезок, относительно предыдущего. Итак, пусть у нас есть два отрезка AB и BC, и нам надо определить в какой полуплоскости находится отрезок BC относительно прямой AB. Рассмотрим вектора AB и BC. Если (x_B - x_A) (y_C - y_B) - (x_C - x_B) (y_B - y_A) > 0, то отрезок BC поворачивает влево от отрезка AB. Если же меньше 0, то вправо. Если же 0 – отрезки находятся на одной прямой.

 

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

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

Возможно в будущем, я ещё напишу о чём-нибудь, где используется эта штука.

Метки: , ,
Google Bookmarks Digg Reddit del.icio.us Ma.gnolia Technorati Slashdot Yahoo My Web News2.ru БобрДобр.ru RUmarkz Ваау! Memori.ru rucity.com МоёМесто.ru Mister Wong

Напишите комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *