Как узнать принадлежит ли точка прямой

Вычислительная геометрия, или как я стал заниматься олимпиадным программированием. Часть 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 – точки лежат по разные стороны.
2. [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₁] < 0 => [P₁P₂, P₁M₂] * [P₁P₂, P₁M₁] < 0. Аналогично
[M₁M₂, M₁P₁] * [M₁M₂, M₁P₂] < 0. Вы наверно думаете, почему не меньше либо равно. А потому, что возможен следующий случай, при котором векторное произведение как раз и равно нулю, но отрезки не пересекаются:

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

Итак, для того чтобы отрезки имели общие точки необходимо и достаточно:
1. Концы отрезков лежат по разные стороны относительно другого отрезка.
2. Хотя бы один из концов одного отрезка принадлежит другому отрезку.

Задача №7

Расстояние от точки до прямой.

В предыдущей статье мы говорили о том, что геометрически косое произведение — это ориентированная площадь параллелограмма, поэтому S_P1P2M = 0,5*[P₁P₂, P₁M]. С другой стороны каждому школьнику известна формула для нахождения площади треугольника: половина основание на высоту.
S_P1P2M = 0,5*h*P₁P₂.
Приравнивая эти площади, находим

По модулю взяли потому, что первая площадь ориентированная.

Если же прямая задана уравнением ax + by + c = 0, то уравнение прямой проходящей через точку M перпендикулярной заданной прямой есть: a(y — y₀) – b(x — x₀) = 0. Теперь спокойно можно решить систему из полученных уравнений, найти их точку пересечения и вычислить расстояние от исходной точки до найденной: оно будет ровно ρ = (ax₀ + by₀ + c)/√(a 2 + b 2 ).

Задача №8

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

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

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

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

Задача №9

Расстояние от точки до отрезка.

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

Чтобы определить попадает ли перпендикуляр на отрезок нужно по аналогии с предыдущей задачей использовать скалярное произведение векторов. Если перпендикуляр не падает на отрезок, то либо угол MP₁P₂ либо угол MP₂P₁ будут тупыми. Поэтому по знаку скалярных произведений мы можем определить попадает ли перпендикуляр на отрезок или нет:
Если (P₁M, P₁P₂) < 0 или (P₂M, P₂P₁) < 0 то перпендикуляр не падает на отрезок.

Задача №10

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

Решение
Прямая и окружность может иметь нуль, одну или две точки пересечения. Давайте посмотрим на рисунки:

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

Задача №11

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

Решение
Возможные случаи расположения окружностей: пересекаются, касаются, не пересекаются.

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

Вспомним теперь, что такое сектор и сегмент.

Пересечение кругов состоит из двух сегментов O₁AB и O₂AB.

Казалось бы необходимо сложить площади этих сегментов и все. Однако, все не так просто. Необходимо еще определить всегда ли эти формулы верны. Оказывается, нет!

Рассмотрим случай, когда центр второго круга O₂ совпадает с точкой C. В этом случае d₂ = 0 и за значение α примем α = π. В этом случае имеем полукруг с площадью 1/2 πR₂ 2 .

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

Заключение

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

Лежит ли точка на прямой

Чтобы избавиться от деления, можно преобразовать уравнение:

Осталось сюда подставить точку (x3, y3).

Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.8.29.43607

Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.

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

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

Заключение

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

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

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

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

Проверка принадлежности точки прямой (Паскаль)

Пример. Составить программу для определения лежит ли точка (x3;y3), на прямой проходящей через точки (x1;y1),C(x2;y2) >

program z20;
uses crt;
var x1,x2,x3,y1,y2,y3 : real;
begin
clrscr;
write(‘x1=’);readln(x1);
write(‘y1=’);readln(y1);
write(‘x2=’);readln(x2);
write(‘y2=’);readln(y2);
write(‘x3=’);readln(x3);
write(‘y3=’);readln(y3);
if (x3-x1)*(y2-y1)-(y3-y1)*(x2-x1)=0
then write(‘лежит’)
else write(‘не лежит’);
readln;
end.

Урок из серии «Геометрические алгоритмы»

Здравствуйте, дорогой читатель!

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

Для реализации операций сравнения над вещественными данными напишем еще две функции: функцию EqPoint(), которая ,будет проверять, совпадают ли две точки на плоскости и функцию RealMoreEq() , которую будем использовать для проверки отношения «>=» (больше или равно). Причина ввода специальных функций нам уже известна.

Задача. Проверить, принадлежит ли точка отрезку.

Пусть точки — начальная и конечные точки отрезка. — произвольная точка на плоскости.

Вектор с началом в точке и концом в точке будет иметь координаты (x2-x1, y2-y1).

Если P(x, y) – произвольная точка, то координаты вектора равны: (x-x1, y – y1).

Точка Р будет принадлежать отрезку если:

1. Векторы в и коллинеарны (равно нулю их векторное произведение):
   , т.е. (x-x1)(y2-y1)-(y-y1)(x2-x1) = 0
2. Абсцисса точки P удовлетворяет условию: или . Иначе точка будет находиться на прямой левее или правее отрезка.

Результаты выполнения программы.

Введите координаты точек: x1, y1, x2, y2, x,y
0.5 1 2.5 2.8 1.203 1.633
Да.

Результаты тестирования в программе GeoGebra:

Сегодня мы написали функцию AtOtres() , которая проверяет принадлежность произвольной точки отрезку, заданному своими координатами.

Ввели еще две функции: EqPoint() и RealMoreEq() для реализации операций сравнения над вещественными данными. Первая проверяет, совпадают ли две точки на плоскости, вторая — используется для проверки отношения «>=».

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

На этом я с вами прощаюсь. До встречи на следующем уроке.

Вступление

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

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

Задача №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π.

Заключение

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

Как узнать, что точка принадлежит прямой. Как определить, лежат ли точки на одной прямой

Как узнать, что точка принадлежит прямой. Как определить, лежат ли точки на одной прямой

Если вам даны две точки, то вы можете смело заявить, что они лежат на одной прямой, так как через любые две точки можно провести прямую. Но как же выяснить, лежат ли все точки на прямой, если точек три, четыре или больше? Доказать принадлежность точек одной прямой можно несколькими способами.

• Как определить, лежат ли точки на одной прямой
• Как найти точку на прямой
• Как провести прямую через две точки

• Точки, заданные координатами.

Если вам даны точки с координатами (х1, у1, z1), (х2, у2, z2), (х3, у3, z3), найдите уравнение прямой, используя координаты любых двух точек, например, первой и второй. Для этого подставьте соответствующие значения в уравнение прямой: (х-х1)/(х2-х1)=(у-у1)/(у2-у1)=(z-z1)/(z2-z1). Если один из знаменателей равен нулю, просто приравняйте к нулю числитель.

Найти уравнение прямой, зная две точки с координатами (х1, у1), (х2, у2), еще проще. Для этого подставьте значения в формулу (х-х1)/(х2-х1)=(у-у1)/(у2-у1).

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

Проверьте принадлежность всех точек прямой, проверив равенство тангенсов углов наклона соединяющих их отрезков. Для этого проверьте, будет ли верным равенство (х2-х1)/(х3-х1)=(у2-у1)/(у3-у1)=(z2-z1)/(z3-z1). Если один из знаменателей равен нулю, то для принадлежности всех точек одной прямой должно выполняться условие х2-х1=х3-х1, у2-у1=у3-у1, z2-z1=z3-z1.

Еще один способ проверить принадлежность трех точек прямой – посчитайте площадь треугольника, который они образуют. Если все точки лежат на прямой, то его площадь будет равна нулю. Подставьте значения координат в формулу: S=1/2((х1-х3)(у2-у3)-(х2-х3)(у1-у3)). Если после всех вычислений вы получили ноль — значит, три точки лежат на одной прямой.

Чтобы найти решение задачи графическим способом, постройте координатные плоскости и найдите точки по указанным координатам. Затем проведите прямую через две из них и продолжите до третьей точки, посмотрите, пройдет ли она через нее. Учтите, этот способ подходит только для точек, заданных на плоскости с координатами (х, у), если же точка задана в пространстве и имеет координаты (х, у, z), то такой способ неприменим.

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

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

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

Итак, пусть нам даны две точкии. Наша прямая проходит через две эти точки, давайте получим уравнение этой прямой. Уравнение пучка прямых, проходящих через точку с координатамиимеет вид:

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

и подставим в уравнение (1):

Преобразовывая уравнение (3) получим:

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

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

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

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

Из подобия треугольниковинаходим:

Из рисунка видно, что:

Таким образом, получаем уравнение прямой по двум точкам:

Задача

Составим уравнение прямой, проходящей через две точкии.

Как доказать, что точки лежат на одной прямой без координат. Лежат ли 3 точки на прямой. Как определить, лежат ли точки на одной прямой

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

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

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

Это сделаем лишь для того, чтобы не решать поставленную задачу в общем виде, а чтобы дать ответ на вопрос лежат ли 3 именно эти точки с этими координатами на одной прямой. Сформулируем задачу: Необходимо проверить лежат ли точки A(-2;1), Б(0;3), В (5;-7) на одной прямой.

Решим поставленную задачу

Как известно, через любые две точки можно провести прямую, причем единственную. Вот и проведем мысленно эту прямую. Допустим, прямую АБ. Значит, решение нашей задачи свелось к тому, что нужно проверить: принадлежит ли точка В прямой АБ. Если окажется, что точка В принадлежит прямой АБ, то все точки из условия будут лежать на одной прямой. Если мы выясним, что точка В не принадлежит прямой АБ, то можно будет утверждать, что точки А, Б и В на одной прямой не лежат. Составим уравнение прямой АБ как уравнение прямой проходящей через две точки:

После преобразования получим:

x-y=-3 — это уравнение прямой АБ

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

Как видим, не получили верное числовое равенство. Значит в этом случае точки А, Б, В не лежат на одной прямой.

Пример, когда 3 точки лежат на одной прямой можно легко подобрать для этой задачи. Всего лишь точка В должна иметь координаты (0;3) или (-7;-4)

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

• Точки, заданные координатами.

Инструкция

1. Если вам даны точки с координатами (х1, у1, z1), (х2, у2, z2), (х3, у3, z3), обнаружьте уравнение прямой , применяя координаты всяких 2-х точек, скажем, первой и 2-й. Для этого подставьте соответствующие значения в уравнение прямой : (х-х1)/(х2-х1)=(у-у1)/(у2-у1)=(z-z1)/(z2-z1). Если один из знаменателей равен нулю, примитивно приравняйте к нулю числитель.

2. Обнаружить уравнение прямой , зная две точки с координатами (х1, у1), (х2, у2), еще проще. Для этого подставьте значения в формулу (х-х1)/(х2-х1)=(у-у1)/(у2-у1).

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

4. Проверьте принадлежность всех точек прямой , проверив равенство тангенсов углов наклона соединяющих их отрезков. Для этого проверьте, будет ли правильным равенство (х2-х1)/(х3-х1)=(у2-у1)/(у3-у1)=(z2-z1)/(z3-z1). Если один из знаменателей равен нулю, то для принадлежности всех точек одной прямой должно выполняться условие х2-х1=х3-х1, у2-у1=у3-у1, z2-z1=z3-z1.

5. Еще один метод проверить принадлежность 3 точек прямой – посчитайте площадь треугольника, тот, что они образуют. Если все точки лежат на прямой , то его площадь будет равна нулю. Подставьте значения координат в формулу: S=1/2((х1-х3)(у2-у3)-(х2-х3)(у1-у3)). Если позже всех вычислений вы получили нуль – значит, три точки лежат на одной прямой .

6. Дабы обнаружить решение задачи графическим методом, постройте координатные плоскости и обнаружьте точки по указанным координатам. После этого проведите прямую через две из них и продолжите до третьей точки , посмотрите, пройдет ли она через нее. Учтите, данный метод подходит только для точек, заданных на плоскости с координатами (х, у), если же точка задана в пространстве и имеет координаты (х, у, z), то такой метод неприменим.

Как показать, что точка лежит на прямой. Как определить лежит ли точка на прямой

Урок из серии « Геометрические алгоритмы »

Здравствуйте, дорогой читатель!

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

Для реализации операций сравнения над вещественными данными напишем еще две функции: функцию EqPoint(), которая ,будет проверять, совпадают ли две точки на плоскости и функцию RealMoreEq() , которую будем использовать для проверки отношения «>=» (больше или равно). Причина ввода специальных функций нам уже известна.

Задача. Проверить, принадлежит ли точка отрезку .

Пусть точки— начальная и конечные точки отрезка.— произвольная точка на плоскости.

Вектор с началом в точкеи концом в точкебудет иметь координаты (x2-x1, y2-y1).

Если P(x, y) – произвольная точка, то координаты вектораравны: (x-x1, y – y1).

Точка Р будет принадлежать отрезку если:

1. Векторы виколлинеарны (равно нулю их векторное произведение):
   , т.е. (x-x1)(y2-y1)-(y-y1)(x2-x1) = 0
2. Абсцисса точки P удовлетворяет условию:или. Иначе точка будет находиться на прямой левее или правее отрезка.

Результаты выполнения программы.

Введите координаты точек: x1, y1, x2, y2, x,y
0.5 1 2.5 2.8 1.203 1.633
Да.

Результаты тестирования в программе GeoGebra:

Сегодня мы написали функцию AtOtres() , которая проверяет принадлежность произвольной точки отрезку, заданному своими координатами.

Ввели еще две функции: EqPoint() и RealMoreEq() для реализации операций сравнения над вещественными данными. Первая проверяет, совпадают ли две точки на плоскости, вторая — используется для проверки отношения «>=».

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

На этом я с вами прощаюсь. До встречи на следующем уроке.

Ответ

Проверено экспертом

Точка лежит на прямой, если её координаты удовлетворяют уравнению прямой, т.е. при их подстановке вместо неизвестных (х и у) получается верное числовое равенство.

а(-5;3)
-5-4*3+7=0 ?
-5-12+7≠0
-10≠0 => точка А не принадлежит прямой

в(9;4)
9-4*4+7=0 ?
9-16+7=0
0=0 => В лежит на прямой, заданной уравнением х-4у+7=0

Как в canvas определить лежит ли точка на прямой. Уточню — прямая толстая, то есть по сути это наклонный прямоугольник.

Пробовал по формуле взятой из этого вопроса и с небольшой погрешностью.

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

Подскажите пожалуйста алгоритм.

1 ответ 1

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

Лежит ли точка на прямой онлайн. Точка внутри треугольника

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

Известны координаты вершин треугольника и известный координаты точки. Нужно установить принадлежность точки треугольнику.
Существует несколько способов определения. лежит-ли точка внутри треугольника или снаружи:
1. Метод сравнения площадей — по формуле Герона находятся площади 3-х треугольников которые образует точка с каждой стороной треугольника, далее находится площадь самого треугольника и сравнивается с суммой 3ех предыдущих треугольников, если суммы равны то значит точка принадлежит треугольнику.
2. Метод относительности — выбирается ориентация движения по вершинам треугольника, например по часовой стрелке. По данной ориентации проходим все стороны треугольника, рассматривая их как прямые, и рассчитываем по какую сторону от текущей прямой лежит наша точка. Если точка для всех прямых, лежит с правой стороны, то значит точка принадлежит треугольнику, если хоть для какой-то прямой она лежит с левой стороны, то значит условие принадлежности не выполняется.
3. Метод геометрического луча — из точки пускается луч по какой-либо оси в каком-либо направлении. Вычисляется количество пересечений со сторонами, если кол-во нечётное, то значит точка лежит внутри многоугольника.

Если точка лежит на прямой, то можно сказать, что она принадлежит этой прямой. Точка и прямая

Точка и прямая являются основными геометрическими фигурами на плоскости.

Определение точки и прямой в геометрии не вводят, эти понятия рассматриваются на интуитивно-понятийном уровне.

Точки обозначают прописными (заглавными, большими) латинскими буквами: A, B, C, D, …

Прямые обозначают одной строчной (маленькой) латинской буквой, например,

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

О точках, которые лежат на прямой, говорят, что они принадлежат этой прямой. Принадлежность отмечают знаком ∈. О точках вне прямой говорят, что они не принадлежат этой прямой. Знак «не принадлежит» — ∉.

Например, точка B принадлежит прямой a (пишут: B∈a),

точка F не принадлежит прямой a, (пишут: F∉a).

Основные свойства принадлежности точек и прямых на плоскости:

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

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

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

— эту прямую можно назвать MK или MN или NK.

Две прямые могут пересекаться и не пересекаться. Если прямые не пересекаются, они не имеют общих точек. Если прямые пересекаются, они имеют одну общую точку. Знак пересечения — ∩ .

Например, прямые a и b пересекаются в точке O

Прямые c и d также пересекающиеся, хотя на рисунке нет их точки пересечения.

Прямые m и n не имеют общих точек.

Проверить лежит ли точка м на прямой. Как проверить, что точки не лежат на одной прямой

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

• — карандаш;
• — линейка;
• — ручка;
• — тетрадь;
• — калькулятор.

Проверить принадлежность точки той либо иной прямой довольно просто. Используйте для этого уравнение прямой. Итак, предположим, что прямая проходит через точки А(x1,y1) и В(x2,y2). Дана точка К(x,y): нужно проверить ее принадлежность прямой. Уравнение линии по двум точкам имеет следующий вид: (x — x1) * (y2 — y1) — (x2 — x1) * (y — y1) = 0.

Подставьте значение координат точки К в уравнение. Если (x — x1) * (y2 — y1) — (x2 — x1) * (y — y1) окажется больше нуля, то точка К расположена правее или ниже прямой, проведенной по точкам А и В.

В том случае, если (x — x1) * (y2 — y1) — (x2 — x1) * (y — y1) будет меньше нуля, точка К располагается выше или левее линии. Другими словами, только в том случае, если уравнение вида (x — x1) * (y2 — y1) — (x2 — x1) * (y — y1) = 0 справедливо, точки А, В и К будут расположены на одной прямой.

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

Рассмотрите второй вариант определения принадлежности точки примой: на этот раз нужно проверить принадлежит ли точка С(x,y) отрезку с концевыми точками В(x1,y1) и А(x2,y2), который является частью прямой z.

Точки рассматриваемого отрезка опишите уравнением pOB+(1-p)OА=z, при условии, что 0≤p≤1. ОВ и ОА являются векторами. Если есть такое число p, которое больше или равно 0, но меньше или равно 1, то pOB+(1-p)OА=С, а значит, точка С будет лежать на отрезке АВ. В противном случае, данная точка не будет принадлежать этому отрезку.

Распишите равенство pOB+(1-p)OА=С покоординатно: px1+(1-p)x2=x и py1+(1-p)y2=y.

Найдите из первого уравнения число р и подставьте его значение во второе равенство. Если равенство будет соответствовать условиям 0≤p≤1, то точка С принадлежит отрезку АВ.

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

Убедитесь в правильности расчетов!

Чтобы найти k — угловой коэффициент прямой, нужно (y2 — y1)/(x2 — x1).

Точка принадлежит прямой обозначение. Точки, Прямые и Отрезки — Определения и Свойства

Вспомним определения точки и прямой:

Точка — это фигура в геометрии, не имеющая никаких
измеримых характеристик, кроме координат.

Прямая — это фигура в геометрии, которая не
имеет ни начала, ни конца.

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

На рисунке 1 изображены прямая c и точки A , B , D , E . Точки А и B
лежат на прямой c , а точки D и E не лежат. Прямая с проходит через
точки A и B, но не проходит через точки С и D . Также заметим, что через
точки A и В нельзя провести другую прямую, не совпадающую с прямой c .

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

Если две прямые имеют общую точку, то можно сказать,
что они пересекаются. На рисунке 2 прямые a и b
пересекаются в общей точке C , а прямые e и f не
пересекаются, так как не имеют общей точки. Две прямые
не могут иметь двух и более общих точек, так как через две
и более точек проходит только одна прямая.

Две прямые имеют только одну общую точку,
либо не имеют общих точек.

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

Часть прямой ограниченная двумя точками называется отрезком . Точки,
ограничивающие отрезок, называются концами отрезка . Отрезок имеет
начало и конец. Пример отрезка на рисунке 4.

Как доказать, что точка лежит на прямой. Теорема Чевы

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

Рис. 1. Пример чевианы

Соответственно, биссектриса, высота и медиана – чевианы. Как вы помните, и высоты, и медианы, и биссектрисы в треугольнике пересекаются в одной точке (см. рисунок 2).

Рис. 2. Пересечение некоторых чевиан в одной точке

Теорема Чевы. Чевианы,ипересекаются в одной точке тогда и только тогда, когда(см. рисунок 3).

Рис. 3. Пересечение чевиан

1) Докажем сперва, что если чевианы пересекаются в одной точке, то выполняется соотношение.

Пусть чевианы,итреугольникапересекаются в точке(см. рисунок 3).

Рассмотрим треугольникии(см. рисунок 4).

Рис. 4. Треугольникии

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

Рис. 5. Высоты рассматриваемых треугольников совпадают

Аналогично можно выписать еще два соотношения:;.

Перемножая эти три равенства получаем:

Рассмотрим левую часть данного равенства. Запишем её иначе. Треугольникииимеют равные углы (вертикальные, при вершине– см. рисунок 6). Значит, их площади относятся как произведения длин сторон, заключающих этот угол.

Рис. 6. Треугольники с равными углами

То есть:. Аналогично можно выписать еще два соотношения:;. Перемножая эти равенства, получаем:.

Что и требовалось доказать.

2) Теперь докажем, что если соотношениевыполнено, то три чевианы пересекаются в одной точке.

Воспользуемся методом от противного. Пусть это не так и– точка пересеченияи, ане проходит через эту точку. Проведем чевианучерез точкии(см. рисунок 7).

Рис. 7. Иллюстрация к доказательству теоремы Чевы

Тогда для чевиан,и выполняется условие теоремы Чевы, которое мы уже доказали:.

Но с другой стороны известно, что

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