как доказать что векторы пересекаются

Вычислительная геометрия, или как я стал заниматься олимпиадным программированием. Часть 2

Вступление

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

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

Задача №1

Определить взаимное расположении точки и прямой: лежит выше прямой, на прямой, под прямой.

Решение
Понятно, что если прямая задана своим уравнением ax + by + c = 0, то тут и решать нечего. Достаточно подставить координаты точки в уравнение прямой и проверить чему оно равно. Если больше нуля, то точка находится в верхней полуплоскости, если равна нулю, то точка находится на прямой и если меньше нуля, то точка находится в нижней полуплоскости. Интереснее случай, когда прямая задана, задана координатами двух точек назовем их P₁(x₁, y₁), P₂(x₂, y₂). В этом случае можно спокойно найти коэффициенты a, b и c и применить предыдущее рассуждение. Но надо сначала подумать, оно нам надо? Конечно, нет! Как я говорил косое произведения — это просто жемчужина вычислительной геометрии. Давайте применим его. Известно, что косое произведение двух векторов положительно, если поворот от первого вектора ко второму идет против часовой стрелки, равно нулю, если векторы коллинеарны и отрицательно, если поворот идет по часовой стрелки. Поэтому нам достаточно посчитать косое произведение векторов P₁P₂ и P₁M и по его знаку сделать вывод.

Задача №2

Определить принадлежит ли точка лучу.

Решение
Давайте вспомним, что такое луч: луч — это прямая, ограниченная точкой с одной стороны, а с другой стороны бесконечная. То есть луч задается некоторой начальной точкой и любой точкой лежащей на нем. Пусть точка P₁(x₁, y₁) — начало луча, а P₂(x₂, y₂) — любая точка принадлежащая лучу. Понятно, что если точка принадлежит лучу, то она принадлежит и прямой проходящей через эти точки, но не наоборот. Поэтому принадлежность прямой является необходимым, но не достаточным условием для принадлежности лучу. Поэтому от проверки косового произведения нам никуда не деться. Для достаточного условия нужно вычислить еще и скалярное произведение тех же векторов. Если оно меньше нуля, то точка не принадлежит лучу, если же оно не отрицательно, то точка лежит на луче. Почему так? Давайте посмотрим на рисунок.

Итак, для того чтобы точка M(x, y) лежала на луче с начальной точкой P₁(x₁, y₁), где P₂(x₂, y₂) лежит на луче необходимо и достаточно выполнения двух условий:
1. [P₁P₂, P₁M] = 0 – косое произведение (точка лежит на прямой)
2. (P₁P₂, P₁M) ≥ 0 – скалярное произведение (точка лежит на луче)

Задача №3

Определить принадлежит ли точка отрезку.

Решение
Пусть точки P₁(x₁, y₁), P₂(x₂, y₂) концы заданного отрезка. Опять-таки необходимым условием принадлежности точки отрезку является ее принадлежность прямой проходящей через P₁, P₂. Далее нам нужно определить лежит ли точка между точками P₁ и P₂, для этого нам на помощь приходит скалярное произведение векторов только на этот раз других: (MP₁, MP₂). Если оно меньше либо равно нуля, то точка лежит на отрезке, иначе вне отрезка. Почему так? Посмотрим на рисунок.

Итак, для того чтобы точка M(x, y) лежала на отрезке с концами P₁(x₁, y₁), P₂(x₂, y₂) необходимо и достаточно выполнения условий:
1. [P₁P₂, P₁M] = 0 – косое произведение (точка лежит на прямой)
2. (MP₁,MP₂) ≤ 0 – скалярное произведение (точка лежит между P₁ и P₂)

Задача №4

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

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

Если точки находятся по разные стороны относительно прямой, то косые произведения имеют разные знаки, а значит их произведение отрицательно. Если же точки лежат по одну сторону относительно прямой, то знаки косых произведений совпадают, значит, их произведение положительно.
Итак:
1. [P₁P₂, P₁M₁] * [P₁P₂, P₁M₂] 0 – точки лежат по одну сторону.
3. [P₁P₂, P₁M₁] * [P₁P₂, P₁M₂] = 0 – одна (или две) из точек лежит на прямой.

Кстати, задача об определении наличия точки пересечения у прямой и отрезка решается точно также. Точнее, это и есть эта же задача: отрезок и прямая пересекаются, когда концы отрезка находятся по разные стороны относительно прямой или когда концы отрезка лежат на прямой, то есть необходимо потребовать [P₁P₂, P₁M₁] * [P₁P₂, P₁M₂] ≤ 0.

Задача №5

Определить пересекаются ли две прямые.

Решение
Будем считать, что прямые не совпадают. Понятно, что прямые не пересекаются, только если они параллельны. Поэтому, найдя условие параллельности, мы можем, определить пересекаются ли прямые.
Допустим прямые заданы своими уравнениями a₁x + b₁y + c₁ = 0 и a₂x + b₂y + c₂ = 0. Тогда условие параллельности прямых заключается в том, что a₁b₂ — a₂b₁ = 0.
Если же прямые заданы точками P₁(x₁, y₁), P₂(x₂, y₂), M₁(x₃, y₃), M₂(x₄, y₄), то условие их параллельности заключается в проверки косого произведения векторов P₁P₂ и M₁M₂: если оно равно нулю, то прямые параллельны.

В общем, то когда прямые заданы своими уравнениями мы тоже проверяем косое произведение векторов (-b₁, a₁), (-b₂, a₂) которые называются направляющими векторами.

Задача №6

Определить пересекаются ли два отрезка.

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

Итак, нам нужно проверить, чтобы концы каждого из отрезков лежали по разные стороны относительного концов другого отрезка. Пользуемся косым произведением векторов. Посмотрите на первый рисунок: [P₁P₂, P₁M₂] > 0, [P₁P₂, P₁M₁] [P₁P₂, P₁M₂] * [P₁P₂, P₁M₁] 2 + b 2 ).

Задача №8

Расстояние от точки до луча.

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

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

Теперь рассмотрим случай, когда центр второго круга O₂ находится между точками O₁ и C. В этом случае получим отрицательное значение величины d₂. Использование отрицательного значения d₂ приводит к отрицательному значению α. В этом случае необходимо для правильного ответа прибавить к α 2π.

Заключение

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

Источник

Как доказать что векторы пересекаются

Сформулируем ряд базовых определений.

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

то есть модуль вектора равен корню квадратному из суммы квадратов его координат.

Обозначим углы между вектором и осями координат через α, β, γ соответственно. Косинусы этих углов называются для вектора направляющими, и для них выполняется соотношение: Верность данного равенства можно показать с помощью свойства проекции вектора на ось, которое будет рассмотрено в нижеследующем пункте 4.

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

1. Сложение двух векторов производится покоординатно, то есть если

Геометрически два вектора складываются по двум правилам:

а) правило треугольника – результирующий вектор суммы двух векторов соединяет начало первого из них с концом второго при условии, что начало второго совпадает с концом первого вектора; для суммы векторов – результирующий вектор суммы соединяет начало первого из них с концом последнего вектора-слагаемого при условии, что начало последующего слагаемого совпадает с концом предыдущего;

б) правило параллелограмма (для двух векторов) – параллелограмм строится на векторах-слагаемых как на сторонах, приведенных к одному началу; диагональ параллелограмма исходящая из их общего начала, является суммой векторов.

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

При λ>0 – вектор сонаправлен ; λ противоположно направлен ; | λ|> 1 – длина вектора увеличивается в λ раз; | λ| 1 – длина вектора уменьшается в λ раз.

4. Пусть в пространстве задана направленная прямая (ось l ), вектор задан координатами конца и начала. Обозначим проекции точек A и B на ось l соответственно через A ’ и B ’.

Рассмотрим некоторые основные свойства проекций:

1) проекция вектора на ось l равна произведению модуля вектора на косинус угла между вектором и осью, то есть ;

2.) проекция вектора на ось положительна (отрицательна), если вектор образует с осью острый (тупой) угол, и равна нулю, если этот угол – прямой;

3) проекция суммы нескольких векторов на одну и ту же ось равна сумме проекций на эту ось.

Сформулируем определения и теоремы о произведениях векторов, представляющих нелинейные операции над векторами.

5. Скалярным произведением векторов и называется число (скаляр), равное произведению длин этих векторов на косинус угла φ между ними, то есть

Теорема 2.2. Необходимым и достаточным условием перпендикулярности двух векторов является равенство нулю их скалярного произведения

Следствие. Попарные скалярные произведения единичных орт равны нулю, то есть

Отсюда следует условие перпендикулярности ненулевых векторов и :

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

Решение. Вычислим модули векторов и их скалярное произведение по теореме (2.3):

Пример 2.10. Затраты сырьевых и материальных ресурсов, используемых на производство одной тонны творога, заданы в таблице 2.2 (руб.).

Какова общая цена этих ресурсов, затрачиваемых на изготовление одной тонны творога?

Примечание. Действия с векторами, осуществленные в примере 2.10, можно выполнить на персональном компьютере. Для нахождения скалярного произведения векторов в MS Excel используют функцию СУММПРОИЗВ( ), где в качестве аргументов указываются адреса диапазонов элементов матриц, сумму произведений которых необходимо найти. В MathCAD скалярное произведение двух векторов выполняется при помощи соответствующего оператора панели инструментов Matrix

Решение. Находим вектор перемещения, вычитая из координат его конца координаты начала

Угол φ между и находим по формуле (2.29), то есть

– перпендикулярен векторам и ;

– векторы образуют правую тройку (рис. 2.15).

Примечание. Определитель (2.25) раскладывается по свойству 7 определителей

Следствие 1. Необходимым и достаточным условием коллинеарности двух векторов является пропорциональность их соответствующих координат

Следствие 2. Векторные произведения единичных орт равны

Следствие 3. Векторный квадрат любого вектора равен нулю

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

— перпендикулярен плоскости, проходящей через точки O , A , B ;

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

Решение. Найдем векторное произведение заданных векторов по формуле (2.32).

Теорема 2.6. Необходимым и достаточным условием компланарности трех векторов является равенство нулю их смешанного произведения

Теорема 2.7. Если три вектора заданы своими координатами, то их смешанное произведение представляет собой определитель третьего порядка, составленный из координат векторов- сомножителей соответственно, то есть

Объем треугольной пирамиды, построенной на этих же векторах, равен

Решение. Найдем координаты векторов

По формуле (2.36) объем пирамиды, построенной на векторах равен (единиц объема)

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

получим выражение вектора через остальные векторы

Линейно независимыми называют векторы, если равенство (2.37) выполняется только тогда, когда все

Базисом n – мерного пространства E_n называют любую совокупность линейно независимых векторов n – мерного пространства.

Произвольный вектор n – мерного пространства можно представить в виде линейной комбинации векторов базиса таким образом:

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

Источник