задача: применить известные алгоритмы определения столкновений и реакции на них во флэше.

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

Авторы: Raigan Burns, Mare Sheppard
Перевод: Nox Noctis

1. краткий обзор
      1.1 определение столкновений в играх
      1.2 определение реакции на столкновение при помощи проецирования
      1.3 отскоки и трение

2. теорема о разделяющих осях (ТРО)
      2.1 ТРО для ограничивающего прямоугольника ("AABB")
      2.2 ТРО для окружностей
      2.3 ТРО для точек

3. быстро движущиеся объекты

4. выводы / исходник

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


1. Краткий обзор

Замечание: краткие сведения о базовых понятиях двумерной геометрии содержатся в приложении. Обратитесь к нему, если вы не помните, что такое вектор, как масштабировать, складывать и умножать вектора; пожалуй, это всё, что необходимо знать, для понимания исходного кода.

1.1 Определение столкновений в играх

Обычно определение столкновений (collision detection) в играх реализуется в два шага:
  1. определить, какие пары фигур необходимо проверить на столкновение (широкая фаза).
  2. определить, есть ли столкновение для каждой из пар, найденных в шаге 1 (узкая фаза).
В игре N шаг 1 реализован при помощи крупной сетки из квадратных ячеек; каждая фигура хранится в ячейке, которая содержит центр фигуры, и столкновения проверяются для всех фигур данной клетки или для всех фигур в 8 смежных клетках.

Подробнее эта система будет объяснена в других уроках; данный урок рассказывает о том, как шаг 2 реализован в N. Алгоритмы, использованные нами для шага 2, подходят для любой игры, в которой требуется быстрое определение столкновений, и в которой требуется определять не только факт столкновения, но и его характер/направление.
в начало

1.2 Определение реакции на столкновение при помощи проецирования

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

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

В принципе, этого может быть достаточно для некоторых типов объектов, но для физически реалистичных объектов хорошо бы задать более осмысленное поведение. Чтобы это организовать, нам потребуется больше информации, чем просто "a и b пересекаются". А конкретнее, наc интересует характер пересечения.

Проецирование — это один из физически реалистичных методов работы с пересекающимися ("взаимно проникающими") объектами. Основная идея в том, чтобы кратчайшим путем переместить объекты так, чтобы они перестали накладываться друг на друга. Обсчет результата столкновения в этом случае эквивалентен нахождению кратчайшего вектора перемещения V, при котором пересечение объектов прекратится.

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

Можно взглянуть на эти методы с точки зрения того, как они влияют на положение объекта в пространстве. В проекционном методе положение изменяется напрямую; в импульсном методе изменяется первая производная от координат (т. е. изменяются скорости), а в методе упругих сил изменяется вторая производная от координат (т. е. ускорения, вызванные упругими силами). Цель всех трех этих методов — переместить объекты в какое-то определенное положение.

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

Итак, от процедур, определяющих столкновения, нам нужен не просто результат в виде булева значения (столкнулись/не столкнулись), но также и вектор проекции. Вектор проекции может быть задан как единичный вектор, определяющий направление выхода объектов из пересечения, плюс скалярная величина — глубина проникновения.

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

1.3 Отскоки и трение

Мы придумали, как вывести объекты из столкновения — но хорошо бы еще изменить скорости столкнувшихся объектов так, чтобы смоделировать физически реалистичные отскоки и трение.

Физическая модель, использованная в N, довольно проста и не очень реалистична. Мы разработали также и модель с более "настоящими" отскоками и трением, но поняли, что играть с ней не настолько весело, как с простой.

Наш алгоритм реакции на столкновения состоит из следующих шагов:
  • найти вектор перемещения, необходимый для выведения объектов из столкновения (метод проецирования)
  • Разбить вектор скорости на две составляющие: параллельную поверхности столкновения и перпендикулярную ей
  • рассчитать отскок, используя перпендикулярную составляющую
  • рассчитать трение, используя параллельную составляющую
Пример 1: отскок частицы от горизонтальной поверхности.

Легенда:

красный регулятор изменяет силу трения.

синий регулятор изменяет силу отскока.

Комментарии:

Перетаскивайте красный и синий регуляторы, посмотрите, как изменяется результирующий вектор.

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

в начало

2. Теорема о разделяющих осях (ТРО)

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

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

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

И в этом основной плюс использования ТРО: в большинстве игр гораздо более вероятно, что проверяемые объекты не накладываются, и то, что мы можем сразу это определить, не производя много вычислений, существенно ускоряет работу алгоритма.
Пример 2: проекция прямоугольника на произвольную ось.

Легенда:

красный регулятор изменяет направление оси проецирования.

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

толстая зелёная линия обозначает сумму проекций векторов полуширины прямоугольника на ту же ось.

Комментарии:

Перетаскивайте красный регулятор, обратите внимание, как меняются проекции.

Обратите внимание, длина толстой синей линии всегда ровно в два раза больше, чем длина толстой зелёной линии; поскольку длину зелёной линии рассчитать гораздо проще, мы можем использовать её, чтобы быстро получать длину всей проекции.

Если проекции фигур накладываются по всем возможным разделяющим осям, то они точно пересекаются; значит, произошло их столкновение, и мы должны найти вектор перемещения, который выведет объекты из столкновения.

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

Пример 3: использование ТРО для двух прямоугольников (AABB).

Легенда:

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

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

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

зелёной линией обозначено расстояние между центрами прямоугольников вдоль каждой из осей.

Комментарии:

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

Заметим, что величина наложения прямоугольников вдоль каждой из осей равна сумме длин красной и синей линии минус длина зелёной линии.
Итак, на данный момент мы в общих чертах разобрались с определением столкновений: для пары объектов мы проверяем каждую из их разделяющих осей, прекращая вычисления, если мы нашли ось, по которой проекции этих объектов не накладываются. Если же проекции объектов накладываются по всем разделяющим осям, мы находим минимальную величину наложения и направляем вектор перемещения вдоль найденной оси.
в начало

2.1 ТРО для ограничивающего прямоугольника ("AABB")

В 2D играх движущиеся объекты часто представляют в виде ограничивающих прямоугольников, стороны которых параллельны осям координат. Для краткости будем наызвать их "AABB", что расшифровывается как "axis-aligned bounding box". Прямоугольник AABB задается позицией p и парой векторов полуширины xw и yw которые определяют размеры прямоугольника вдоль осей координат.

Понятие "полуширина" похоже по смыслу на радиус, с той разницей, что полуширина задает размер в определенном направлении, а не по всем направлениям сразу.
Рис. 2: ограничивающий прямоугольник "AABB" и его вектора полуширины.

Ограничивающий прямоугольник "AABB" и его вектора полуширины
Потенциальные разделяющие оси прямоугольника AABB — x и y, поэтому для него пользоваться ТРО при определении столкновений особенно удобно. Естесственно, чем меньше других разделяющих осей у второй фигуры, с которой определяется столкновение, тем проще наша задача.

Треугольники

Использовать ТРО для прямоугольников AABB — легко, но как быть с фигурами, грани которых не параллельны осям координат?

В игре N мы использовали следующий подход: все треугольные фигуры были прямоугольными и две стороны треугольника обязательно были параллельны осям координат. Таким образом, при определении столкновения AABB и треугольника, единственной дополнительной разделяющей осью была ось, параллельная гипотенузе треугольника.

Пример 4: использование ТРО для AABB и прямоугольного треугольника.

Легенда:

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

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

красной и синей линиями обозначены размеры фигур вдоль каждой из осей.

Комментарии:

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

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

Круглые фигуры

Ну, что ж, теперь мы можем рассчитать столкновение AABB с любым выпуклым многоугольником, представив его в виде сочетания AABB и прямоугольных треугольников. Но что делать с круглыми фигурами?

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

Для того, чтобы в этом случае использовать ТРО, необходимо выбрать разделяющие оси, которые мы будем проверять для круглой фигуры. К счастью, ответ лежит на поверхности: если точка b — центр окружности, а точка p — ближайшая к центру окружности вершина AABB, то дополнительной разделяющей осью можно выбрать прямую, параллельную вектору от точки p к точке b.

Фигуры, составленные с "пустой" окружностью мы называем вогнутыми, а фигуры, составленные с "заполненной" окружностью — выпуклыми.

Пример 5: использование ТРО для AABB и выпуклой круглой фигуры.

Легенда:

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

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

красной и синей линиями обозначены размеры фигур вдоль каждой из разделяющих осей.

Комментарии:

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

Пример 6: использование ТРО для AABB и вогнутой круглой фигуры.

Легенда:

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

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

красной и синей линиями обозначены размеры фигур вдоль каждой из разделяющих осей.

Комментарии:

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

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

2.2 ТРО для окружностей

Для вычисления столкновений движущиеся 2D объекты также часто представляют в виде окружности.

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

Для прямоугольников AABB минимальная проекция всегда будет лежать на одной из осей координат (поскольку стороны AABB параллельны осям по определению); для окружностей необходимо учитывать не только грани фигур, с которыми происходит столкновение, но и их вершины; например, набор потенциальных разделяющих осей при определении столкновения между окружностью и прямоугольником будет включать две оси, перпендикулярные сторонам прямоугольника и четыре оси, параллельные векторам, соединяющим каждую из вершин прямоугольника с центром окружности.

Пример 7: избыточное использование ТРО для окружности и прямоугольника.

Легенда:

красной и синей линиями обозначены размеры фигур вдоль каждой из разделяющих осей.

Комментарии:

Перетаскивайте круг, обратите внимание на изменения обозначений на разделяющих осях.

Обратите внимание, когда проекции фигур перекрываются по осям x и y, одна или несколько осей "окружность—>вершина прямоугольника" могут быть разделяющими.

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

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

Области Вороного

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

Пример 8: диаграмма Вороного для треугольника.

Легенда:

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

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

Комментарии:

Перетаскивайте синюю точку, обратите внимание на подсветку областей Вороного.

Каждая точка (в том числе синяя) из области, подсвеченной зелёным цветом, расположена ближе к выделенному фрагменту треугольника, чем к какому-либо другому его фрагменту.
Таким образом, если мы знаем, в какой из областей Вороного находится центр окружности, мы сразу знаем, какой из фрагментов многоугольника является ближайшим к окружности и знаем, какую из вершин многоугольника проверять на предмет столкновения.

Красота этого метода в том, что по результатам проверки наложения проекций на осях координат мы можем определить, в какой именно области Вороного находится окружность. Не нужно выполнять никаких дополнительных вычислений! Эта идея была впервые раскрыта Джеймсом Арво.

Пример 9: использование ТРО и областей Вороного для AABB и окружности.

Легенда:

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

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

красной и синей линиями обозначены размеры фигур вдоль каждой из разделяющих осей.

Комментарии:

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

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

Прочие фигуры

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

2.3 ТРО для точек

Мы можем использовать все идеи, описанные выше, и для определения столкновений точечных объектов с различными фигурами. Однако, обычно результаты такого подхода неудовлетворительны. И причина здесь не в какой-то ошибке наших процедур, а в самом методе определения столкновений через проецирование.

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

Например, вернемся к столкновению двух AABB; обратите внимание, кратчайший вектор проекции иногда "прыгает" от одной оси к другой, когда вы перемещаете объекты друг относительно друга. Это означает, что когда мы двигаем объект, например, справа налево, он может быть выведен из столкновения вверх или вниз, что будет выглядеть нелогично. И зависит это от того, насколько быстро двигаются объекты и насколько далеко они могут переместиться за один кадр. Может случиться, что объекты наложатся так, что наш метод проецирования определит кратчайшее перемещение не в том направлении, в котором объект должен оказаться согласно законами физики.

И это неизбежная проблема метода проецирования, которая появляется, если сталкивающиеся объекты могут перемещаться на большое растсояние за один кадр. Чем меньше объект и чем быстрее он двигается — тем вероятнее возникновение этой ошибки.

Однако, стоит помнить, что несмотря на указанную трудность для точечных объектов, определение самого факта столкновения проекционным методом всё же происходит корректно — мы можем использовать тот же код, что используем для определения столкновения AABB с другими фигурами, достаточно только задать ему нулевые размеры xw и yw и пропустить вычисление проекций.

В игре N для самонаводящейся ракеты используется процедура определения столкновений проекционным методом, как описано выше; мы также используем ТРО для точки, чтобы быстро определять, находится ли персонаж вблизи стены, чтобы разрешить/запретить взаимодействие с ней (прыжок или скольжение).
в начало

3. Быстро движущиеся объекты

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

Если же быстро движущиеся небольшие объекты в игре вам абсолютно неоходимы, существует два распространённых метода обработки их столкновений: проверка в протяженности (sweep test) и выборка положений (multisampling).

Проверки в протяженности

Вместо того, чтобы проверять пересечение самих фигур, создаются две новые фигуры путем растяжения исходных вдоль их траекторий; на пересечение проверяются эти растянутые фигуры. Эта идея подробно объясняется в статье Мигеля Гомеза (см. случаи столкновения окружность-окружность и AABB-AABB).

Выборка положений

Намного более простой алтернативой предыдущему методу является проверка пересечения фигур в нескольких промежуточных положениях в каждом кадре. Вместо того, чтобы проверять пересечение фигур только в их текущем положении, берется несколько положений фигур на их траекториях между предудыщим и текущим положениями. Эта техника и была использована для определения столкновений модели персонажа (ragdoll) с окружающими объектами.

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

4. Выводы / исходник

Надеемся, этот материал дал вам общее представление о том, каким образом можно организовать определение столкновений и реакцию на них в 2D. Мы уверены, что наше решение — не самое оптимальное или элегантное, но мы довели его реализацию до такого уровня, когда оно практически не дает сбоев.

Разумеется, можно расширить представленную методику в различных направлениях. Например, можно работать с произвольными фигурами, представляя их в виде набора примитивов, который будет рассчитываться динамически. На самом деле, всё что нужно, чтобы адаптировать нашу методику для любых произвольных фигур — это уметь определять их вектора полуширины при проекции на произвольную ось. Однако, если скорость работы алгоритма очень критична (как в ActionScript, например), приходится ограничиваться теми фигурами, для которых эти вектора могут быть рассчитаны заранее или легко получены динамически.

Исходник

[ посмотреть ] [ исходник ]

Приложение содержит часть исходного кода игры N, которая относится к материалу этого урока.

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


Как с нами связаться

Если у вас есть замечания или дополнения к этому уроку, напишите нам по адресу tutorials@harveycartel.org

УБЕДИТЕЛЬНАЯ ПРОСЬБА, не писать нам письма с вопросами об исходном коде — с этим вам придётся разобраться самостоятельно.

На нашем форуме есть специальный раздел об уроках.

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

+. Примечания, ссылки по теме

Ниже приводятся ссылки на весьма полезные материалы на английском языке, но половина из приведенных в оригинале ссылок уже не дейстувует. Если вы знаете, где можно найти аналогичные материалы на русском языке — напишите мне. - прим. перев.


в начало

+. Базовая геометрия

Нормирование

Нормирование вектора — это сокращение его длины до 1. Такие вектора обычно называют единичными. Они часто используются для того, чтобы задавать направления.

Чтобы нормировать вектор v, достаточно разделить обе его компоненты на его длину:
len_v = Math.sqrt(v.x*v.x + v.y*v.y);
v.x /= len_v;
v.y /= len_v; 
Получившийся единичный вектор часто называют "нормой вектора".

Заметим, что при нормировании вектора неплохо бы добавить проверку на то, что его длина не равна нулюю. Иначе вы рискуете получить ошибку деленияы на ноль.

Скалярное умножение векторов

Скалярное произведение векторов вычисляется следующим образом:
dp = a.x*b.x + a.y*b.y; 
Результатом умножения является скалярная величина (обычное число).

Проекция

Формула проецирования вектора a на вектор b:
proj.x = ( dp / (b.x*b.x + b.y*b.y) ) * b.x;
proj.y = ( dp / (b.x*b.x + b.y*b.y) ) * b.y;
где dp = (a.x*b.x + a.y*b.y); (скалярное произведение вектора a на вектора b).

Заметьте, результатом проецирования является вектор; выражение в скобках (b.x*b.x + b.y*b.y) — это квадрат длины вектора b.

Если вектор b — единичный, то есть, (b.x*b.x + b.y*b.y) = 1, то формулы проецирования можно сократить:
proj.x = dp*b.x;
proj.y = dp*b.y; 
Пример 10: проецирование вектора.

Легенда:

зелёный вектор является результатом проецирования вектора p1->p0 на линию, проходящую через p1 и p2.

Комментарии:

Перетаскивайте точки p0, p1, и p2, обратите внимание, как изменяется зелёный вектор.

Cкалярное произведение c перпендикулярным вектором

Еще одно полезное понятие в геометрии на плоскости — нормали (не путать с нормализацией!).

Нормалью вектора является вектор, лежащий на перпендикулярной к исходному вектору прямой и имеющий ту же длину.

Любой вектор на поскости имеет две нормали: правую и левую. Как следует из их названия, эти вектора отличаются направлением: правая нормаль лежит в правой относительно исходного вектора полуплоскости, а левая нормаль — в левой.

Правой нормалью произвольного вектора a является вектор rn:
rn.x = -a.y;
rn.y = a.x; 
а левой нормалью — вектор ln:
ln.x = a.y;
ln.y = -a.x; 
Обратите внимание, ln = -rn.

Cкалярным перпендикулярным произведением (perproduct) векторов a и b является скалярное произведение вектора a на правую нормаль вектора b.
Рис. 3: вектор c его правой нормалью и левой нормалью.

Вектор c его правой и левой нормалями


Metanet Software Inc. Metanet Software Inc.
Raigan Burns, Mare Sheppard


в начало
назад к списку уроков N