Как проверить что точка лежит внутри треугольника
Как проверить что точка лежит внутри треугольника
Есть плоскость О. Есть двухмерная декартова система координат XY, лежащая на этой плоскости.
Есть треугольник АВС. Нам известны его вершины: А(x;y) В(x;y) С(x;y). Есть точка p.
Требуется определить, находится ли точка внутри треугольника.
Есть такое решение (оно мне кажется слишком громоздким):
проводим прямые через АВ, ВС, СА и определяем (с помощью уравнения прямой), с какой стороны в каждом случае лежит точка (сверху — снизу, слева — справа). Путем перебора всех трех сторон можно определить попадание, но тут много подводных камней. Например надо определять ориентацию треугольника относительно осей координат.
Неужели нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу.
 | От: | Anpek |
| Дата: | 01.08.06 10:46 | |
| Оценка: |
 | От: | Smal |
| Дата: | 01.08.06 10:51 | |
| Оценка: |
Здравствуйте, Anpek, Вы писали:
A>Проводишь любой луч из этой точки — если луч пересечет стороны нечетное количество раз — то внутри, иначе — снаружи
Хреново работает, если луч прошел через вершину
Пусть ABC — треугольник, R — точка.
Тогда [AB, AR], [BС, BR], [CA, CR] должны быть одного знака.
 | От: | Сергей |
| Дата: | 01.08.06 10:59 | |
| Оценка: |
Здравствуйте, Logic Bomb, Вы писали:
LB>Неужели нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу.
Площадь треугольника — половина векторного произведения двух его сторон, взятая по модулю. Эта формула легко записывается через координаты вершин треугольника.
Если нужно проверять еше и попадание на границу, то нужно проверять ABDSquare, BCDSquare, CADSquare на равенство нулю.
 | От: | FoolS.Top |
| Дата: | 01.08.06 11:04 | |
| Оценка: |
Здравствуйте, Logic Bomb, Вы писали:
LB>Есть плоскость О. Есть двухмерная декартова система координат XY, лежащая на этой плоскости.
LB>Есть треугольник АВС. Нам известны его вершины: А(x;y) В(x;y) С(x;y). Есть точка p.
LB>Требуется определить, находится ли точка внутри треугольника.
LB>Есть такое решение (оно мне кажется слишком громоздким):
LB>проводим прямые через АВ, ВС, СА и определяем (с помощью уравнения прямой), с какой стороны в каждом случае лежит точка (сверху — снизу, слева — справа). Путем перебора всех трех сторон можно определить попадание, но тут много подводных камней. Например надо определять ориентацию треугольника относительно осей координат.
LB>Неужели нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу.
 | От: | Logic Bomb |
| Дата: | 01.08.06 11:17 | |
| Оценка: |
 | От: | twisted_mind |
| Дата: | 01.08.06 11:19 | |
| Оценка: |
Здравствуйте, Logic Bomb, Вы писали:
LB>Есть плоскость О. Есть двухмерная декартова система координат XY, лежащая на этой плоскости.
LB>Есть треугольник АВС. Нам известны его вершины: А(x;y) В(x;y) С(x;y). Есть точка p.
LB>Требуется определить, находится ли точка внутри треугольника.
LB>Есть такое решение (оно мне кажется слишком громоздким):
LB>проводим прямые через АВ, ВС, СА и определяем (с помощью уравнения прямой), с какой стороны в каждом случае лежит точка (сверху — снизу, слева — справа). Путем перебора всех трех сторон можно определить попадание, но тут много подводных камней. Например надо определять ориентацию треугольника относительно осей координат.
LB>Неужели нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу.
Можно и из векторной алгебры. Достаточно посмотреть знаки следующих смешанных произведений векторов:
AB*AP, BC*BP, CA*CP. Их знаки соответствуют знакам синуса угла между векторами (с учетом направления поворота). Т.е. по сути надо чтобы относительно каждой стороны точка была всегда либо справа, либо слева в зависимости от обхода. В любом случае достаточно, чтобы у всех произведений знак совпадал. Преимущество в том, что здесь не требуется деление или корень.
 | От: | sch |
| Дата: | 01.08.06 14:37 | |
| Оценка: |
Я, как правило делаю, следующим образом.
Пусть дана точка P и три вершины треугольника A, B, C.
Я считаю координаты точки относительно системы координат, образованной
векторами AB, AC с началом в точке A.
u = ((P — A) & AB) / |AB| ^ 2,
v = ((P — A) & AC) / |AC| ^ 2.
Если u 1 || v 1, то точка не лежит внутри
треугольника.
Если это условие не соблюдается, то повторяю тест уже в системе
координат (B, BA, BC).
P.S. & == скалярное произведение.
Logic Bomb wrote:
> Есть плоскость О. Есть двухмерная декартова система координат XY, лежащая на этой плоскости.
> Есть треугольник АВС. Нам известны его вершины: А(x;y) В(x;y) С(x;y). Есть точка p.
> Требуется определить, находится ли точка внутри треугольника.
> Есть такое решение (оно мне кажется слишком громоздким):
> проводим прямые через АВ, ВС, СА и определяем (с помощью уравнения прямой), с какой стороны в каждом случае лежит точка (сверху — снизу, слева — справа). Путем перебора всех трех сторон можно определить попадание, но тут много подводных камней. Например надо определять ориентацию треугольника относительно осей координат.
>
> Неужели нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу.
| | От: | sch |
| Дата: | 01.08.06 14:40 | |
| Оценка: |
Сответственно, если тестов выполняется много и координаты треугольника
постоянны,
то можно предвычислить выражения типа AB / |AB| ^ 2.
sch wrote:
> Я, как правило делаю, следующим образом.
| | От: | Smal |
| Дата: | 01.08.06 14:49 | |
| Оценка: |
Здравствуйте, sch, Вы писали:
sch>Я, как правило делаю, следующим образом.
sch>Пусть дана точка P и три вершины треугольника A, B, C.
sch>Я считаю координаты точки относительно системы координат, образованной
sch>векторами AB, AC с началом в точке A.
sch>u = ((P — A) & AB) / |AB| ^ 2,
sch>v = ((P — A) & AC) / |AC| ^ 2.
sch>Если u 1 || v 1, то точка не лежит внутри
sch>треугольника.
А не проще ли проверять
В этом случае не нужно проверять для оставшихся 2-х систем.
 | От: | McSeem2 | http://www.antigrain.com |
| Дата: | 02.08.06 03:25 | ||
| Оценка: |
Здравствуйте, Logic Bomb, Вы писали:
LB>Неужли нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу.
Это и есть самый простой способ. И самый эффективный, не требующий делений. Есть такое понятие как cross product, вычисляется для трех точек на плоскости. Если cross products всех трех сторон по отношению к искомой точке имеют одинаковый знак, то точка внутри, оначе — снаружи.
| | От: | sch |
| Дата: | 02.08.06 06:56 | |
| Оценка: |
Проще.
Но я почему-то до этой простой мысли так и не дошел 
 | От: | Аноним |
| Дата: | 02.08.06 07:18 | |
| Оценка: |
| | От: | Logic Bomb |
| Дата: | 02.08.06 07:26 | |
| Оценка: |
Здравствуйте, McSeem2, Вы писали:
предыдущий пост — мой!
| | От: | Smal |
| Дата: | 02.08.06 08:33 | |
| Оценка: |
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, McSeem2, Вы писали:
MS>>Здравствуйте, Logic Bomb, Вы писали:
LB>>>Неужли нет алгоритма проще? Что-то из векторной алгебры вертится в голове но не могу перенести на бумагу.
MS>>Это и есть самый простой способ. И самый эффективный, не требующий делений.
А>А как-же запись уравнеия прямой? Ведь деление там как раз присутствует. Мне способ с вычислением площадей показался проще. Еще про луч понравилось. Хотя вы помогли мне посмотреть на мой способ под другим углом — пропала необходимость выяснять ориентацию треугольника. Очевидные преимущества у этого способа есть и для более сложных фигур. Количество вычислений растет в прямой пропорции с количеством сторон (речь естественно идет только о фигурах без внутренних углов)
Странно %).
Cross product — это векторное умножение.
Способ уже два раза предлагался. И тем не менее пользуется популярностью %)
| | От: | McSeem2 | http://www.antigrain.com |
| Дата: | 02.08.06 14:44 | ||
| Оценка: |
Здравствуйте, Аноним, Вы писали:
А>А как-же запись уравнеия прямой? Ведь деление там как раз присутствует. Мне способ с вычислением площадей показался проще. Еще про луч понравилось. Хотя вы помогли мне посмотреть на мой способ под другим углом — пропала необходимость выяснять ориентацию треугольника. Очевидные преимущества у этого способа есть и для более сложных фигур. Количество вычислений растет в прямой пропорции с количеством сторон (речь естественно идет только о фигурах без внутренних углов)
Способ так же работет для любого выпуклого полигона. Для произвольного полигона — вкуривать Eric Haines, Point In Polygon Strategies.
Для определения CW/CCW достаточно вычислить Cross Product для трех точек треугольника. Если меньше нуля, значит CCW, в предаоложениии, что ось Y направлена вверх.
 | От: | ministr |
| Дата: | 06.08.06 04:13 | |
| Оценка: |
Здравствуйте, Logic Bomb, Вы писали:
LB>Неужели нет алгоритма проще?
Есть проще, только он помоему самый быстрый.
Ну вот твой алгоритм, на мой взгляд достаточно быстрый :
0.находим для каждой стороны каноническое уравнение Ax+By+C=0 (!рассмотреть случай параллельности осям координат);
Если не параллельны:
1.проверяем на принадлежность сторонам:
пусть (x1,y1) (x2,y2) Ax+By+C=0 — проверяемая сторона, тогда:
2.ну тогда проверяем три аналогичных условия для каждой стороны:
пусть (x1,y1) (x2,y2) Ax+By+C=0 — проверяемая сторона, тогда:
В принципе просто 2- проверяем чтоб точка противоположная стороне лежала в тойже полуплоскости и исходной точкой
проверять на параллельность осям координат просто — из равенства нулю разности иксов или игриков концов стороны, сразу заполняем uslX. и еще — очевидно что если две стороны параллельны осям, то третья — нет (типа оптимизации 
| | От: | ministr |
| Дата: | 06.08.06 05:16 | |
| Оценка: |
Здравствуйте, McSeem2, Вы писали:
MS>Здравствуйте, Аноним, Вы писали:
MS>
Фишка в том,что это определение полуплоскости относительно прямой заданной уравнением:
(x-x2) = (y-y2)
(x2-x1) (y2-y1)
как я пологаю cross_product получен умножением этого уравнения на (x2-x1)*(y2-y1), но умножать мы имеем право только если это не ноль! дело в том,что каноническое уравнение это совсем не уравнение, а пропорция, поэтому мы имеем право рисовать дробь, а вот если его рассмастривать как уравнение необходимо проверять на ноль, который может получиться если сторона параллельна какой-нибудь оси координат,вот опять никуда не делись.
Еще — я не согласен с проверкой на отношение к нулю этого выражения 
, в этом случае нужно проверять на принадлежность стороне данной точки(те равенство нулю и принадлежность к промежутку. ), и лучше еще сравнивать результаты не между собой, а с этим выражением для противоположной вершины в случае с прямоугольными треугольниками, хотя, думаю, это лишне — лучше вместо ‘. Re[5]: проверка на попадание точки в треугольник
| | От: | twisted_mind |
| Дата: | 06.08.06 10:13 | |
| Оценка: |
Здравствуйте, ministr, Вы писали:
M>Здравствуйте, McSeem2, Вы писали:
M>Фишка в том,что это определение полуплоскости относительно прямой заданной уравнением:
M> (x-x2) = (y-y2)
M>(x2-x1) (y2-y1)
M>как я пологаю cross_product получен умножением этого уравнения на (x2-x1)*(y2-y1), но умножать мы имеем право только если это не ноль! дело в том,что каноническое уравнение это совсем не уравнение, а пропорция, поэтому мы имеем право рисовать дробь, а вот если его рассмастривать как уравнение необходимо проверять на ноль, который может получиться если сторона параллельна какой-нибудь оси координат,вот опять никуда не делись.
cross_product — это обычное смешанное произведение векторов: здесь, которое никак не зависит от ориентации векторов относительно осей, а зависит только от их длин и ориентации относительно друг друга.
M>Еще — я не согласен с проверкой на отношение к нулю этого выражения , в этом случае нужно проверять на принадлежность стороне данной точки(те равенство нулю и принадлежность к промежутку. ), и лучше еще сравнивать результаты не между собой, а с этим выражением для противоположной вершины в случае с прямоугольными треугольниками, хотя, думаю, это лишне — лучше вместо ‘.
Равенство нулю говорит о том, что точка лежит на прямой, проходящей через сторону. Если точка должна лежать строго внутри треугольника, то в случае равенства нулю хотя бы одного из произведений можно сразу говорить, что не лежит внутри. Поэтому все произведения должны быть > 0 или все = 0 или все Re[6]: проверка на попадание точки в треугольник
Как проверить принадлежит ли точка треугольнику?
Как проверить, принадлежит ли точка треугольнику
Пожалуйста, помогите найти ошибку: 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)