Принадлежит ли точка системе уравнений

Вычислительная геометрия, или как я стал заниматься олимпиадным программированием. Часть 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

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

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

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

Как же определить падает ли перпендикуляр на луч или нет? Если перпендикуляр не падает на луч, то угол MP₁P₂ – тупой иначе острый (прямой). Поэтому по знаку скалярного произведения векторов мы можем определить попадает ли перпендикуляр на луч или нет:
1. (P₁M, P₁P₂) 2 .

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

Заключение

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

Уравнения прямой в пространстве — это уравнения двух пересекающихся плоскостей

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

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

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

Уравнения двух плоскостей, задающих прямую линию в пространстве

Пусть даны две плоскости, которые не совпадают между собой и пересекаются. Обозначим их как плоскость α и плоскость β . Разместим их в прямоугольной системе координат O х у z трехмерного пространства.

Как мы помним, любую плоскость в прямоугольной системе координат задает общее уравнение плоскости вида A x + B y + C z + D = 0 . Будем считать, что плоскости α соотвествует уравнение A 1 x + B 1 y + C 1 z + D 1 = 0 , а плоскости β уравнение A 2 x + B 2 y + C 2 z + D 2 = 0 . В этом случае нормальные вектора плоскостей α и β n 1 → = ( A 1 , B 1 , C 1 ) и n 2 → = ( A 2 , B 2 , C 2 ) не коллинеарны, так как плоскости не совпадают между собой и е размещаются параллельно друг другу. Запишем это условие следующим образом:

n 1 → ≠ λ · n 2 → ⇔ A 1 , B 1 , C 1 ≠ λ · A 2 , λ · B 2 , λ · C 2 , λ ∈ R

Чтобы освежить в памяти материал по теме «Параллельность плоскостей», смотрите соответствующий раздел нашего сайта.

Линию пересечения плоскостей обозначим буквой a . Т.е. a = α ∩ β . Эта прямая представляет собой множество точек, которые являются общими для обеих плоскостей α и β . Это значит, что все точки прямой линии a удовлетворяют обоим уравнениям плоскости A 1 x + B 1 y + C 1 z + D 1 = 0 и A 2 x + B 2 y + C 2 z + D 2 = 0 . Фактически, они являются частным решением системы уравнений A 1 x + B 1 y + C 1 z + D 1 = 0 A 2 x + B 2 y + C 2 z + D 2 = 0 .

Общее решение системы линейных уравнений A 1 x + B 1 y + C 1 z + D 1 = 0 A 2 x + B 2 y + C 2 z + D 2 = 0 определяет координаты всех точек линии, по которой происходит пересечение двух плоскостей α и β . Это значит, что с его помощью мы можем определить положение прямой в прямоугольной системе координат O x y z .

Рассмотрим описанную теорию еще раз, теперь уже на конкретном примере.

Прямая O x – это прямая, по которой пересекаются координатные плоскости O x y и O x z . Зададим плоскость O x y уравнением z = 0 , а плоскость O x z уравнением у = 0 . Такой подход мы подробно разобрали в разделе «Неполное общее уравнение плоскости», так что, в случае затруднений, можно обратиться к этому материалу повторно. В этом случае координатная прямая O x определяется в трехмерной системе координат системой из двух уравнений вида y = 0 z = 0 .

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

Рассмотрим задачу. Пусть в трехмерном пространстве задана прямоугольная система координат O х у z . Линия, по которой пересекаются две плоскости a , задана системой уравнений A 1 x + B 1 y + C 1 z + D 1 = 0 A 2 x + B 2 y + C 2 z + D 2 = 0 . Дана точка трехмерного пространства M 0 x 0 , y 0 , z 0 .

Давайте определим, принадлежит ли точка M 0 x 0 , y 0 , z 0 заданной прямой линии a .

Для того, чтобы получить ответ на вопрос задачи, подставим координаты точки М 0 в каждое из двух уравнений плоскости. Если в результате подстановки оба уравнения превратятся в верные равенства A 1 x 0 + B 1 y 0 + C 1 z 0 + D 1 = 0 и A 2 x 0 + B 2 y 0 + C 2 z 0 + D 2 = 0 , то точка М 0 принадлежит каждой из плоскостей и принадлежит заданной линии. Если хотя бы одно из равенств A 1 x 0 + B 1 y 0 + C 1 z 0 + D 1 = 0 и A 2 x 0 + B 2 y 0 + C 2 z 0 + D 2 = 0 окажется неверным, то точка М 0 не принадлежит прямой линии.

Рассмотрим решение примера

Прямая линия задана в пространстве уравнениями двух пересекающихся плоскостей вида 2 x + 3 y + 1 = 0 x — 2 y + z — 3 = 0 . Определите, принадлежат ли точки M 0 ( 1 , — 1 , 0 ) и N 0 ( 0 , — 1 3 , 1 ) прямой линии пересечения плоскостей.

Решение

Начнем с точки М 0 _. Подставим ее координаты в оба уравнения системы 2 · 1 + 3 · ( — 1 ) + 1 = 0 1 — 2 · ( — 1 ) + 0 — 3 = 0 ⇔ 0 = 0 0 = 0 .

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

Подставим в оба уравнения плоскости координаты точки N 0 ( 0 , — 1 3 , 1 ) . Получаем 2 · 0 + 3 · — 1 3 + 1 = 0 0 — 2 · — 1 3 + 1 — 3 = 0 ⇔ 0 = 0 — 1 1 3 = 0 .

Как вы видите, второе уравнение системы превратилось в неверное равенство. Это значит, что точка N 0 не принадлежит заданной прямой.

Ответ: точка М 0 принадлежит прямой линии, а точка N 0 не принадлежит.

Теперь предлагаем вам алгоритм нахождения координат некоторой точки, принадлежащей прямой линии, если прямая в пространстве в прямоугольной системе координат O x y z определяется уравнениями пересекающихся плоскостей A 1 x + B 1 y + C 1 z + D 1 = 0 A 2 x + B 2 y + C 2 z + D 2 = 0 .

Количество решений системы из двух линейных уравнений с темя неизвестными A 1 x + B 1 y + C 1 z + D 1 = 0 A 2 x + B 2 y + C 2 z + D 2 = 0 бесконечно. Любое из этих решений может стать решением задачи.

Пусть в трехмерном пространстве задана прямая линия уравнениями двух пересекающихся плоскостей вида x + 3 z + 7 = 0 2 x + 3 y + 3 z + 2 = 0 . Найдите координаты любой из точек этой прямой.

Решение

Перепишем систему уравнений x + 3 z + 7 = 0 2 x + 3 y + 3 z + 2 = 0 ⇔ x + 0 y + 3 z = — 7 2 x + 3 y + 3 z = — 2 .

Возьмем отличный от нуля минор второго порядка в качестве базисного минора основной матрицы системы 1 0 2 3 = 3 ≠ 0 . Это значит, что z – это свободная неизвестная переменная.

Перенесем слагаемые, содержащие свободную неизвестную переменную z в правые части уравнений:

x + 0 y + 3 z = — 7 2 x + 3 y + 3 z = — 2 ⇔ x + 0 y = — 7 — 3 z 2 x + 3 y = — 2 — 3 z

Введем произвольное действительное число λ и примем, что z = λ .

Тогда x + 0 y = — 7 — 3 z 2 x + 3 y = — 2 — 3 z ⇔ x + 0 y = — 7 — 3 λ 2 x + 3 y = — 2 — 3 λ .

Для решения полученной системы уравнений применим метод Крамера:

∆ = 1 0 2 3 = 1 · 3 — 0 · 1 = 2 ∆ x = — 7 — 3 λ 0 — — 3 λ 3 = — 7 — 3 λ · 3 — 0 · ( — 2 — 3 λ ) = 21 — 9 λ ⇒ x = ∆ x ∆ = — 7 — 3 λ ∆ y = 1 — 7 — 3 λ 2 — 2 — 3 λ = 1 · — 2 — 3 λ — — 7 — 3 λ · = 12 + 3 λ ⇒ y = ∆ y ∆ = 4 + λ

Общее решение системы уравнений x + 3 z + 7 = 0 2 x + 3 y + 3 z + 2 = 0 будет иметь вид x = — 7 — 3 λ y = 4 + λ z = λ , где λ ∈ R .

Для получения частного решения системы уравнений, которое даст нам искомые координаты точки, принадлежащей заданной прямой, нам необходимо взять конкретное значение параметра λ . Если λ = 0 , то x = — 7 — 3 · 0 y = 4 + 0 z = 0 ⇔ x = — 7 y = 4 z = 0 .

Это позволяет нам получить координаты искомой точки — 7 , 4 , 0 .

Проверим верность найденных координат точки методом подстановки их в исходные уравнения двух пересекающихся плоскостей — 7 + 3 · 0 + 7 = 0 2 · ( — 7 ) + 3 · 4 + 3 · 0 + 2 = 0 ⇔ 0 = 0 0 = 0 .

Ответ: — 7 , 4 , 0

Направляющий вектор прямой, по которой пересекаются две плоскости

Давайте рассмотрим, как определить координаты направляющего вектора прямой, которая задана уравнениями двух пересекающихся плоскостей A 1 x + B 1 y + C 1 z + D 1 = 0 и A 2 x + B 2 y + C 2 z + D 2 = 0 . В прямоугольной системе координат 0хуz направляющий вектор прямой неотделим от прямой линии.

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

Плоскости α и β пересекаются по линии a . Направляющий вектор a → прямой линии a расположен перпендикулярно по отношению к нормальному вектору n 1 → = ( A 1 , B 1 , C 1 ) плоскости A 1 x + B 1 y + C 1 z + D 1 = 0 и нормальному вектору n 2 → = ( A 2 , B 2 , C 2 ) плоскости A 2 x + B 2 y + C 2 z + D 2 = 0 .

Направляющий вектор прямой a представляет собой векторное произведение векторов n → 1 = ( A 1 , B 1 , C 1 ) и n 2 → = A 2 , B 2 , C 2 .

a → = n → 1 × n 2 → = i → j → k → A 1 B 1 C 1 A 2 B 2 C 2

Зададим множество всех направляющих векторов прямой как λ · a → = λ · n 1 → × n 2 → , где λ — это параметр, который может принимать любые действительные значения, отличные от нуля.

Пусть прямая в пространстве в прямоугольной системе координат O х у z задана уравнениями двух пересекающихся плоскостей x + 2 y — 3 z — 2 = 0 x — z + 4 = 0 . Найдем координаты любого направляющего вектора этой прямой.

Решение

Плоскости x + 2 y — 3 z — 2 = 0 и x — z + 4 = 0 имеют нормальные векторы n 1 → = 1 , 2 , — 3 и n 2 → = 1 , 0 , — 1 . Примем за направляющий вектор прямой линии, являющейся пересечением двух заданных плоскостей, векторное произведение нормальных векторов:

a → = n → 1 × n 2 → = i → j → k → 1 2 — 3 1 0 — 1 = i → · 2 · ( — 1 ) + j → · ( — 3 ) · 1 + k → · 1 · 0 — — k → · 2 · 1 — j → · 1 · ( — 1 ) — i → · ( — 3 ) · 0 = — 2 · i → — 2 j → — 2 k →

Запишем ответ в координатной форме a → = — 2 , — 2 , — 2 . Тем, кто не помнит, как это делается, рекомендуем обратиться к теме «Координаты вектора в прямоугольной системе координат».

Ответ: a → = — 2 , — 2 , — 2

Переход к параметрическим и каноническим уравнениям прямой в пространстве

Для решения ряда задач проще использовать параметрические уравнения прямой в пространстве вида x = x 1 + a x · λ y = y 1 + a y · λ z = z 1 + a z · λ или канонические уравнения прямой в пространстве вида x = x 1 + a x · λ y = y 1 + a y · λ z = z 1 + a z · λ . В этих уравнениях a x , a y , a z — координаты направляющего вектора прямой, x 1 , y 1 , z 1 — координаты некоторой точки прямой, а λ — параметр, принимающий произвольные действительные значения.

От уравнения прямой вида A 1 x + B 1 y + C 1 z + D 1 = 0 A 2 x + B 2 y + C 2 z + D 2 = 0 можно перейти к каноническим и параметрическим уравнениям прямой линии в пространстве. Для записи канонических и параметрических уравнений прямой нам понадобятся навыки нахождения координат некоторой точки прямой, а также координат некоторого направляющего вектора прямой, заданной уравнениями двух пересекающихся плоскостей.

Рассмотрим написанное выше на примере.

Зададим прямую линию в трехмерной системе координат уравнениями двух пересекающихся плоскостей 2 x + y — z — 1 = 0 x + 3 y — 2 z = 0 . Напишем канонические и параметрические уравнения этой прямой.

Решение

Найдем координаты направляющего вектора прямой, который является векторным произведением нормальных векторов n 1 → = 2 , 1 , — 1 плоскости 2 x + y — z — 1 = 0 и n 2 → = ( 1 , 3 , — 2 ) плоскости x + 3 y — 2 z = 0 :

a → = n 1 → × n 2 → = i → j → k → 2 1 — 1 1 3 — 2 = i → · 1 · ( — 2 ) + j → · ( — 1 ) · 1 + k → · 2 · 3 — — k → · 1 · 1 — j → · 2 · ( — 2 ) — i → · ( — 1 ) · 3 = i → + 3 · j → + 5 · k →

Координаты направляющего вектора прямой a → = ( 1 , 2 , 5 ) .

Следующим шагом является определение координат некоторой точки заданной прямой линии, которыми является одно из решений системы уравнений: 2 x + y — z — 1 = 0 x + 3 y — 2 z = 0 ⇔ 2 x + y — z = 1 x + 3 y — 2 z = 0 .

Возьмем в качестве минорной матрицы системы определитель 2 1 1 3 = 2 · 3 — 1 · 1 = 5 , который отличен от нуля. В этом случае переменная z является свободной. Перенесем слагаемые с ней в правые части каждого уравнения и придаем переменной произвольное значение λ :

2 x + y — z = 1 x + 3 y — 2 z = 0 ⇔ 2 x + y = 1 + z x + 3 y = 2 z ⇔ 2 x + y = 1 + λ x + 3 y = 2 λ , λ ∈ R

Применяем для решения полученной системы уравнений метод Крамера:

∆ = 2 1 1 3 = 2 · 3 — 1 · 1 = 5 ∆ x = 1 + λ 1 2 λ 3 = ( 1 + λ ) · 3 — 1 · 2 λ = 3 + λ ⇒ x = ∆ x ∆ = 3 + λ 5 = 3 5 + 1 5 · λ ∆ y = 2 1 + λ 1 2 λ = 2 · 2 λ — ( 1 + λ ) · 1 = — 1 + 3 λ ⇒ y = ∆ y ∆ = — 1 + 3 λ 5 = — 1 5 + 3 5 · λ

Получаем: 2 x + y — z — 1 = 0 x + 3 y — 2 z = 0 ⇔ x = 3 5 + 1 5 y = — 1 5 + 3 5 z = λ

Примем λ = 2 для того, чтобы получить координаты точки прямой линии: x 1 = 3 5 + 1 5 · 2 y 1 = — 1 5 + 3 5 · 2 z 1 = 2 ⇔ x 1 = 1 y 1 = 1 z 1 = 2 . Теперь мы имеем достаточно данных для того, чтобы записать канонические и параметрические уравнения данной прямой в пространстве: x — x 1 a x = y — y 1 a y = z — z 1 a z ⇔ x — 1 1 = y — 1 3 = z — 2 5 x = x 1 + a x · λ y = y 1 + a y · λ z = z 1 + a z · λ ⇔ x = 1 + 1 · λ y = 1 + 3 · λ z = 2 + 5 · λ ⇔ x = 1 + λ y = 1 + 3 · λ z = 2 + 5 · λ

Ответ: x — 1 1 = y — 1 3 = z — 2 5 и x = 1 + λ y = 1 + 3 · λ z = 2 + 5 · λ

Данная задача имеет еще один способ решения.

Нахождение координат некоторой точки прямой проводится при решении системы уравнений A 1 x + B 1 y + C 1 z + D 1 = 0 A 2 x + B 2 y + C 2 z + D 2 = 0 .

В общем случае ее решения можно записать в виде искомых параметрических уравнений прямой в пространстве x = x 1 + a x · λ y = y 1 + a y · λ z = z 1 + a z · λ .

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

x = x 1 + a x · λ y = y 1 + a y · λ z = z 1 + a z · λ ⇔ λ = x — x 1 a x λ = y — y 1 a y λ = z — z 1 a z ⇔ x — x 1 a x = y — y 1 a y = z — z 1 a z

Применим данный способ к решению задачи.

Зададим положение прямой линии уравнениями двух пересекающихся плоскостей 2 x + y — z — 1 = 0 x + 3 y — 2 z = 0 . Напишем параметрическое и каноническое уравнения для этой прямой линии.

Решение

Решение системы из двух уравнений с тремя неизвестными проводится аналогично тому, как мы делали это в предыдущем примере. Получаем: 2 x + y — z — 1 = 0 x + 3 y — 2 z = 0 ⇔ x = 3 5 + 1 5 · λ y = — 1 5 + 3 5 · λ z = λ .

Это параметрические уравнения прямой в пространстве.

Канонические уравнения получаем следующим образом: x = 3 5 + 1 5 · λ y = — 1 5 + 3 5 · λ z = λ ⇔ λ = x — 3 5 1 5 λ = y + 1 5 3 5 λ = z 1 ⇔ x — 3 5 1 5 = y + 1 5 3 5 = z 1

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

Ответ: x — 3 5 1 5 = y + 1 5 3 5 = z 1 и x = 3 5 + 1 5 · λ y = — 1 5 + 3 5 · λ z = λ

Принадлежность точки отрезку. Почему не работает классика?

IP76 > Векторная графика > Принадлежность точки отрезку. Почему не работает классика?

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

Причины и постановка задачи

Запросы «как найти принадлежность точки отрезку» уводят на страницу «Пересечение прямых, угол и координаты пересечения», где есть пункт «Принадлежность точки отрезку». В нем рассматривается факт принадлежности точки отрезку, уже после того, как мы определили точку пересечения прямых. То есть точка уже принадлежит прямым, и это абсолютно точно. Осталось только определиться, точка в отрезке между двумя точками отрезка, либо где-то на прямой мимо них.

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

Есть отрезок, заданный точками P1(x1,y1) и P2 (x2,y2) . Необходимо определить, принадлежит ли точка P(x,y) этому отрезку.

Классическое уравнение

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

Для совместимости с Delphi 7 введем тип вещественной точки:

Почему бы не сделать сразу TPointF вместо типа TxPoint? Просто у меня гора старых исходников, где используется этот тип, а никакого TPointF не было ни в помине, ни в планах. Delphi 7 казалась вершиной инженерной мысли на тот момент.

В предложение uses дописываем следующее (ради TPointF, и чтобы компилятор XE не доставал хинтами):

Почему именно XE5? Если честно, нет возможности проверить, не ставить же ради этого всю линейку дельфей. Но в XE5 вещественная точка точно есть, а в Delphi 7 ее точно нет. Вот этим и объясняется выбор версии компилятора в директиве. Одни говорят, что TPointF появился в XE2, другие — аж в Delphi 2010. Короче, с таким директивным условием будет работать везде и точка.

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

SameValue — сравнивает два вещественных числа с учетом погрешности Epsilon. Находится в модуле Math, который надо подключить в предложении uses секции implementation.

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

Рис.1. Курсор точно на линии, но не определяет, что точка принадлежит отрезку

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

Расширенная классика

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

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

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

Выведем в интерфейс значения dx = (p2.x-p1.x), dy = (p2.y-p1.y) и т.д. Плюс результат работы функции (p.x-p1.x)*(p2.y-p1.y) — (p.y-p1.y)*(p2.x-p1.x). И убедимся, что при самых казалось бы максимально возможных приближениях к отрезку, результат ошеломляет своей двух- или трехзначной непохожестью на ноль.

Рис.2. Теперь определяет конечные точки, но между ними по-прежнему работает так себе…

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

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

Функция применима в точных расчетах, но не в векторном редакторе.

Модификация уравнения

Очевидно, надо вычислять как-то иначе. Например вычислять Y по имеющейся координате X и сравнивать с имеющейся координатой Y. Если разница меньше заданного Epsilon — точка принадлежит отрезку. Выразим Y из используемого уравнения прямой. Итак, дано:

Выразим Y:

И напишем еще одну функцию, в которой учтем ситуацию, когда (X₂-X₁) может быть равно нулю. Это ситуация вертикальной (или почти вертикальной) прямой.

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

Рис.3. Все здорово определяет с учетом погрешности Epsilon=12 pix

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

На рисунке 3 расчетная точка и ее координаты выделена коричневым цветом.

Однако, все равно есть нюанс. Если линия сильно вертикальна, то есть расстояние (X₂-X₁) невелико, попадать в линию все равно трудно.

Рис.3.1. На почти вертикальной линии функция снова капризничает

Связано с тем, что при уменьшении делителя, коим разность по X выступает в нашем случае, сильно вырастает результат, и чем расстояние (X₂-X₁) меньше, тем труднее попасть в Epsilon.

Итоговая функция

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

Давайте проверять, что больше (X₂-X₁) или (Y₂-Y₁), и в зависимости от результата, будем высчитывать либо Y, либо X. Формулу для X не привожу, он очевидна.

Почему такая большая функция получилась?

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

Можно сократить, не считать конечные точки, не анализировать «вертикальность» и «горизонтальность». Можно взять за настоящую ту точку, которую анализируем и не считать «истинную». Код в этом случае сильно сократиться. Поэтому лучше иметь полный комплект, из которого можно удалить «лишнее» на ваш взгляд.

Зачем нужны такие ощутимо большие проверки на вертикальность и горизонтальность. Ну, во-первых мы освобождаем от условий последний блок вычислений, во-вторых, если убрать, скажем, проверку на dy, погрешность станет в два раза меньше. Потому что отработает это условие: Abs(p1.Y-p.Y) + Abs(p2.Y-p.Y). Имея идеальную горизонтальную линию, подведя курсор на Epsilon допустимый интервал, мы получим в итоге Epsilon + Epsilon = 2 * Epsilon и условие конечно не сработает. Сработает, если подведем на расстояние в два раза меньшее Epsilon.

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

Классика всегда в моде или Математика — царица наук

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

Рис.5. Результат применения рассчитанной точки для первой функции

На рисунке 5 добавлен результат функции f(x,y)=(x-x₁) * (y₂-y₁) — (y-y₁) * (x₂-x₁) для рассчитанной точки на отрезке. Он равен, как и следовало ожидать, нулю. А также результат вызова первой функции, которая использует это уравнение и возвращает 3, если точка принадлежит отрезку. Что мы воочию и видим.

1)Поэтому в графике надо избегать типов TPoint, даже если это вызывает необходимость постоянно их округлять для функций GDI.

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

Скачать

Друзья, спасибо за внимание!

Надеюсь, материал был полезен.

Не пропустите новых интересных штуковин, подписывайтесь на телегу. )))

Если есть вопросы, с удовольствием отвечу.

Исходники и исполняемый файл для GDI и Delphi 7. Проверен в XE 7, XE 10.

Исходники (Delphi 7, XE7, XE10) 11 Кб

Исполняемый файл (zip) 213 Кб

Как подключить GDI+ в Delphi 7 и без проблем скомпилировать в XE 7, XE 10 читаем в этой статье. Там же забираем исходники.

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

За концы отрезка можно таскать. Если попали на отрезок, т.е. видна коричневая точка, можно таскать весь отрезок.

Исходники намеренно выложены в D7 варианте.

При компиляции в XE10 следует снять галочку с Enable High-DPI