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

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

Как проверить, принадлежит ли точка треугольнику
Пожалуйста, помогите найти ошибку: Sub xy() Dim x1, y1, x2, y2, x3, y3 As Single x1 =.

Проверить, принадлежит ли точка M(x,y) треугольнику с заданными вершинами
помогите плиз две задачки решить: Проверить, принадлежит ли точка M(x,y) треугольнику с.

Проверить принадлежит ли точка плоскости с координатами (x,y) треугольнику с заданными вершинами
Даны два вещественных числа x,y. Если точка плоскости с координатами (x,y) принадлежит треугольнику.

Принадлежит ли точка треугольнику
дан три угольник ABC с координатами вершин A(xa,ya), B(xb,yb), C(xc,yc), Пользователь водит.

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

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

Решение

Добавлено через 13 минут
вот ещо одно решения етой задачи

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

С другой стороны, задача-то простая. Не элементарная, но достаточно простая. Somebody уже показал, что все решается без особого выпендрежа. Ну, и нафиг оно, усложнение!

Решение

Господа. Должен заметить, что код первого решения вроде как неверен. Я не знаю, проверял ли ПроСтоСанек свое решение, но он в цикле явно «гадит» мимо массива (из-за ++i вместо i++)
Выкладываю код моего решения, которое проверено и работает (косметические изменения плюс исправленая ошибка, для тех, кто обожает копипасту с форумов =) ).

При обнаружении в программе цикла for первым выполняется инициализирующее_выражение, в котором обычно устанавливается счетчик цикла. Это происходит только один раз перед запуском цикла. Затем анализируется условное_выражение, которое также называется условием прекращения цикла. Пока оно равно true, цикл не прекращается.

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

Решение. Точка лежит внутри треугольника, если она расположена правее прямой x, выше прямой y и ниже прямой x+y=2. Таким образом, принадлежность точки с координатами (x,y) нашему треугольнику определяется истинностью логического выражения

Поэтому наше решение будет содержать ровно один условный оператор:

module ПроверкаРасположенияТочки;
const НУЛЬ = 0;
var X,Y : Real;
begin
read(X,Y);
writeLn (‘Точка с координатами (‘,X, ‘, ‘, Y, ‘) ‘);
if (X > НУЛЬ) & (Y > НУЛЬ )& (X + Y НУЛЬ )&(Y $» BORDER=0 height=33 width=19 align=CENTER> НУЛЬ ) &(X+Y 2)) и (X = НУЛЬ) or (Y = НУЛЬ) or (X+Y $» BORDER=0 height=33 width=19 align=CENTER> = 2).

Поэтому печать ответа можно записать чуть короче:

module ПроверкаРасположенияТочки2;
const НУЛЬ = 0;
var X,Y : Real;
begin
read(X,Y);
writeln (‘Точка с координатами (‘,X, ‘, ‘, Y, ‘) ‘);
if (X = 2)
then write (‘ не ‘)
end;
writeln (‘ принадлежит треугольнику.’)
end ПроверкаРасположенияТочки2.

Источник

Русские Блоги

Как определить, находится ли точка внутри треугольника

Основная мысль

Как показано на рисунке, точка P находится внутри треугольника ABC, о чем можно судить по следующим трем условиям:

Если три вышеуказанных условия выполняются одновременно, точка P находится внутри треугольника ABC.

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

Определите, на какой стороне линии находится точка

где, Угол вектора, Вектор, и с Все они вертикальны, а направление соответствует правилу правой спирали, как показано на рисунке ниже:

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

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

Реализация алгоритма

Обратите внимание, что прочитать все сразу непросто, но легче понять, является ли это координатой Z после перекрестного умножения вектора AB и вектора AC.

Затем соответственно вычислите, какая сторона P находится на AB, CA, BC:

Наконец, определите, находятся ли они на одной стороне:

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

Источник

Определите, лежит ли заданная точка внутри заданного треугольника

У меня проходит 95%. Что не так?

Входные данные
Первые 3 строки содержат координаты вершин треугольника (в каждой строке по 2 целых числа, разделенных пробелом). Четвертая строка содержит координаты точки, в таком же формате. Все числа – целые, по модулю не превосходящие 10000. Гарантируется, что вершины треугольника не лежат на одной прямой.
Выходные данные
Единственная строка содержит слово «In», если точка лежит внутри треугольника, «On», если точка лежит на границе треугольника (вершине либо стороне), или «Out», если она лежит вне него.

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

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

Лежит ли точка М(xm;ym) внутри треугольника, заданного координатами своих вершин
Лежит ли точка М(xm;ym) внутри треугольника, заданного координатами своих вершин A(xa;ya).

Определить лежит ли точка внутри треугольника
Треугольник и точка (№102) В декартовой системе координат на плоскости заданы координаты вершин.

Решение

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

Условие a == 0 на самом деле означает, что точка лежит на прямой, содержащей соответствующую сторону A. Точка может лежать на прямой, содержащей сторону A, далеко за пределами треугольника. При этом a будет равно 0. Поэтому ваше

это неправильно. Правильнее будет

Добавлено через 5 минут
Извините, был неправ. Увидел в вашем коде, что четвертую точку вы вводите в начало массива.
Вы правильно вычисляете площади, а дальше действуйте по описанной мной логике.

Источник