Когда точка лежит внутри треугольника (5 видео)

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

Дано: у нас есть треугольник, нам известны только координаты его вершин. У нас есть точка, нам известны её координаты.

Что нужно узнать: нужно установить принадлежность точки треугольнику.

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

Содержание

Метод сравнения площадей
Метод относительности
Всё относительно!
Векторный метод
Как определить лежит ли точка внутри треугольника или снаружи.
Точка в треугольнике
Векторное произведение ( z — координата )
Точка внутри треугольника. Описание алгоритма.
Когда точка лежит внутри треугольника
💡 Видео

Видео:Где находится точка в треугольнике заданном координатами вершин, внутри или вне треугольника.Скачать

Метод сравнения площадей

В данном методе сначала находятся площади 3-х треугольников, которые образует данная точка с каждой стороной треугольника. В нашем случае(рис. 1) это треугольники ABP, BCP, CAP и их площади s1, s2, s3 соответственно.

Затем находится площадь самого треугольника ABC.

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

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

Простейшая реализация алгоритма:

Атрибуты функции: aAx, aAy, aBx, aBy, aCx, aCy — координаты точек A, B, C треугольника; aPx, aPy — координаты точки, принадлежность которой надо определить.

Видео:Геометрия Точка М лежит внутри равнобедренного треугольника АВС с основанием АС на расстоянии 6 смСкачать

Метод относительности

Данный метод заключается в следующем. Сначала выбирается ориентация движения по вершинам треугольника(по часовой или против часовой стрелке). Я выбираю по часовой. На рисунке 2 выбранная ориентация движения(по часовой) показана стрелками. По данной ориентации проходим все стороны треугольника, рассматривая их как прямые, и рассчитываем по какую сторону от текущей прямой лежит наша точка. Не трудно догадаться, что если точка для всех прямых, при нашей ориентации, лежит с правой стороны, то значит точка принадлежит треугольнику, а если хоть для какой-то прямой она лежит с левой стороны, то значит условие принадлежности не выполняется.

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

Видео:Алгоритмы. Попадание точки в треугольникСкачать

Всё относительно!

Тут надо кое что пояснить, весьма не маловажное, что может сыграть роль в оптимизации и выборе алгоритма. Обратите внимание, что в приведённом коде есть закомментированные блоки кода с комментариями «для строгой ориентации», в то время как рабочий код универсален — он предназначен для любой ориентации. Т.е. представленный код определит принадлежность точки для любого заданного треугольника. В моей тестирующей программе треугольники как раз таки строятся по random()-у координат вершин, а ориентация идёт по вершинам(A>B>C>A). Для рисунка 2 — это по часовой стрелки, но для рисунка 3 — это против часовой.

Так вот, в случае рисунка 3 точка должна лежать по левую сторону векторов, чтобы принадлежать треугольнику.

Вот тут и получается важный момент! Если вы уверены, что в вашем проекте все треугольники будут ориентированы по часовой стрелке(а т.е. вершина C будет всегда правее вектора AB), то вам можно закомментировать блок универсального решения и раскомментировать блок «для строгой ориентации по часовой» и данный алгоритм упрощается аж на 3 логических операции!

Видео:№525. Расстояние от точки М, лежащей внутри треугольника ABC, до прямой АВ равно 6 см, а до прямойСкачать

Векторный метод

Третий метод который я освещаю для меня самый интересный.

Идея его применения зарождается если взглянуть на треугольник как на половинку параллелограмма…

Данный метод я сначала проверил на бумаге. После всех оптимизаций формул, как всё сошлось, я реализовал его в коде, где он показал себя вполне успешным и результативным. Аж эффективнее 2-х предыдущих методов :]

1) одну вершину треугольника помещаем в координаты (0;0);

2) две стороны, выходящие из этой вершины, представляем как вектора.

Таким образом из всего этого появляется система простых условий нахождения точки P между векторами b и c.(рис. 4)

Рис. 4.

Видео:№54. Точка В не лежит в плоскости треугольника ADC, точки М, N и Р — середины отрезков ВА, ВССкачать

Как определить лежит ли точка внутри треугольника или снаружи.

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

Этот калькулятор определит где находится заданная точка внутри 2-мерного треугольника или вовне. Калькулятор использует простой алгоритм, основанный на свойствах векторного произведения. Описание этого алгоритма можно найти сразу за калькулятором.

Точка в треугольнике

Векторное произведение ( z — координата )

Видео:Baltic Way - 2021. Problem #11.Скачать

Точка внутри треугольника. Описание алгоритма.

Векторное произведение векторов a и b, заданного декартовыми координатами в пространстве для 3-х мерного правого ортонормального базиса можно выразить так:
[1].
Векторное произведение обладает свойством антикоммутативности:

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

Попарное векторное произведение векторов-сторон треугольника и вектора из вершины в точку

Для того чтобы определить лежит ли точка P внутри треугольника ABC мы вычислим 3 векторных произведения: ABxAP, BCxBP and CAxCP. Так как наш треугольник и точка в 2-мерном пространстве на плоскости, третья координата z для трехмерного пространства равна нулю. Согласно формуле [1] мы можем не вычислять координаты x и y для векторного произведения, если координата z векторов-множителей равна нулю — координаты x и y результата в этом случае всегда равны нулю (результирующий псевдо-вектор перпендикулярен плоскости треугольника). Знак результата произведения для оставшейся координаты (z) зависит от относительного положения умножаемых векторов. Если первый вектор (в нашем случае это сторона треугольника) находится правее второго вектора (вектор из вершины в точку P), то координата z результата будет положительна, если первый вектор будет левее второго — отрицательна, и в противном случае, если оба вектора идут в одном и том же направлении, результат будет равен нулю.
Получив результаты по трем векторным произведениям, нам остается их проанализировать, чтобы понять лежит ли точка внутри треугольника:
Если мы имеем и положительные и отрицательные результаты, точка лежит вне треугольника, если результаты только положительные или только отрицательные, точка — внутри.
Таблица далее иллюстрирует все возможные варианты результатов векторного произведения:

Видео:✓ Три способа решить планиметрию из ОММО-2019 | Борис ТрушинСкачать

Когда точка лежит внутри треугольника

Задача. Даны координаты трех точек (A),(B),(C). Точки расположены так, что образуют треугольник. Дана еще одна точка (D). Необходимо проверить лежит ли эта точка внутри треугольника (triangle ABC). Написать код программы на #С++.

Решение. Сразу заметим, что здесь будет предложено решение, которое нельзя назвать наилучшим. Это — быстрое решение, но имеет целый ряд недостатков. Классическая идея для решения состоит в том, что если точка (D) лежит внутри треугольника (triangle ABC), то получаются три треугольника, содержащихся внутри данного и сумма их площадей должна равняться площади данного треугольника. Т.е. должно выполняться равенство: [S_=S_+S_+S_] А теперь поясним проблему. Вам придется сравнивать значения двух действительных чисел — площадь данного треугольника и сумму площадей трех внутренних треугольников. А, как известно, это можно сделать только с определенной точностью. На практике рассматривают разность этих площадей по модулю и сравнивают с маленьким числом, задающим точность сравнения. А это плохо.

Для решения задачи воспользуемся другой идеей:

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

Запишем уравнение прямой, проходящей, например, через точки A и B. Получим: [left( x — x_A right) left( y_B — y_A right) — left( y — y_A right) left( x_B — x_A right) = 0]. Уравнение записано в такой форме, чтобы не приходилось выполнять деление и переживать о нуле в знаменателе.

Теперь для любой точки (left( x;y right)) мы можем вычислить левую часть приведенного равенства. Для точек, лежащих на прямой мы должны получать ноль. В тоже время прямая разобьёт плоскость на две полуплоскости. Точки лежащие в одной полуплоскости будут давать положительные значения. А точки из другой полуплоскости — отрицательные.

Мы готовы проверить первое условие — принадлежит ли точка D (left( x_d,y_d right)) той же полуплоскости, что и точка C (left( x_c,y_c right)) относительно прямой (left( AB right)) ? Для этого подставим обе точки в левую часть приведенного выше уравнения прямой и убедимся, что получены значения одного и того же знака. А если одна из точек даст точно ноль? Это означает, что точка лежит на прямой. По условию задачи это может быть только точка D. Тогда она принадлежит треугольнику независимо от знака выражения, вычисленного для точки C.

Приведем код простенькой программы на С++. Вам надо ввести координаты трех вершин треугольника на плоскости, а затем координат точки, принадлежность которой треугольнику проверяется. Вот код программы. Проверить работу программы онлайн можно на нашем компиляторе здесь. Скопируйте код программы (ctrl+c) и вставьте (ctrl+v) в компилятор вместо программы по умолчанию.