Я написал полную статью о тесте точки в треугольнике. Он показывает методы, основанные на барицентрическом, параметрическом и точечном произведении. Затем речь идет о проблеме точности, возникающей, когда точка лежит ровно на одном ребре (с примерами). Наконец, он представляет совершенно новый метод, основанный на расстоянии от точки до края. totologic.blogspot.fr/2014/01/… Наслаждайтесь!
Стоит отметить, что любые методы, обсуждаемые здесь, применимы и в трехмерном пространстве. Им просто должно предшествовать преобразование координат (и соответствующая проекция точки на плоскость треугольника). Треугольник - это двумерный объект.
Обычно используется в 2D. Барицентрические координаты, как правило, сбивают людей с толку. Кроме того, учитывая координаты треугольника и точечный кординат, я не уверен в эффективности использования барицентриков.
Корнел Киселевич
7
@Kornel Барицентрическая версия более эффективна и в 2D. Ваше решение также имеет проблему, заключающуюся в том, что оно будет сообщать другой результат для точек точно по краям треугольника в зависимости от того, указан треугольник по часовой стрелке или против часовой стрелки.
Андреас Бринк
9
Для моих целей (причина, по которой я нашел этот сайт) оригинальный ответ, предложенный Корнелом Киселевичем, гораздо эффективнее. Я работаю с ЖК-дисплеем с координатами размера BYTE и очень типичным микропроцессором, в котором умножение целых чисел является очень быстрой инструкцией, а деление намного, намного медленнее. Числовые проблемы также намного меньше, из-за отсутствия деления! все расчеты точны. Спасибо, Рик
4
Таким образом, функция sign () сообщает, какая сторона полуплоскости (образованной линией между p2 и p3) p1?
Дэвид Дория
1
Обратите внимание, что если вы принимаете некоторый порядок вершин (скажем, против часовой стрелки), вам не нужно вычислять все эти детерминанты все время. На самом деле в лучшем случае достаточно одного определителя, чтобы обнаружить, что точка не находится внутри треугольника.
февраля
176
Решите следующую систему уравнений:
p = p0 + (p1 - p0) * s + (p2 - p0) * t
Точка pнаходится внутри треугольника, если 0 <= s <= 1и 0 <= t <= 1и s + t <= 1.
Это быстрее, чем проверка полуплоскости, но, возможно, немного сложнее понять, если вы новичок в барицентрических координатах.
Даниэль Риковски
8
С тривиальными выходами (не реализованными) в методе Корнеля, он может на самом деле гораздо эффективнее, чем ваш. Если вы на самом деле попытаетесь вычислить s и t, вы поймете, что я имею в виду.
85
Я хотел протестировать это, поэтому я сделал jsfiddle, опираясь на решение @andreasdr и комментарий coproc
urraka
5
Оптимизация: s + t <= 1подразумевается s <= 1и t <= 1если s >= 0и t >= 0.
Я согласен с Андреасом Бринком , барицентрические координаты очень удобны для этой задачи. Обратите внимание, что нет необходимости каждый раз решать систему уравнений: просто оцените аналитическое решение. Используя обозначение Андреаса , решение:
Просто оцени s, tи 1-s-t. Точка pнаходится внутри треугольника тогда и только тогда, когда все они положительны.
РЕДАКТИРОВАТЬ: Обратите внимание, что вышеприведенное выражение для области предполагает, что нумерация узлов треугольника против часовой стрелки. Если нумерация идет по часовой стрелке, это выражение вернет отрицательную область (но с правильной величиной). Однако сам тест ( s>0 && t>0 && 1-s-t>0) не зависит от направления нумерации, поскольку вышеприведенные выражения, умноженные на, 1/(2*Area)также меняют знак, если изменяется ориентация узла треугольника.
РЕДАКТИРОВАТЬ 2: Для еще большей вычислительной эффективности, см. Комментарий coproc ниже (который подчеркивает, что если заранее известна ориентация узлов треугольника (по часовой стрелке или против часовой стрелки), деление на 2*Areaв выражениях для sи tможет быть избегать). См. Также jsfiddle-код Perro Azul в комментариях к ответу Андреаса Бринка .
Да, я хочу сказать, что любая критика вашего метода, основанная на вычислительных затратах на решение системы уравнений, является необоснованной, так как это не нужно делать как часть алгоритма.
andreasdr
13
Эффективность может быть улучшена не путем деления 2*Area, то есть путем вычисления s´=2*|Area|*sи t´=2*|Area|*t(если ориентация точек - по часовой стрелке или против часовой стрелки - неизвестна, Areaконечно, необходимо проверить знак , но в противном случае это может быть даже не нужно вычислять), так как для проверки s>0достаточно проверить s´>0. И вместо проверки 1-s-t>0достаточно проверить s´+t´<2*|Area|.
Coproc
1
Я могу добавить , что , если p0->p1->p2это против часовой стрелки в декартовой (который, как правило , по часовой стрелке , в экранных координатах ), то Areaвычисляется с помощью этого метода будет положительным.
rhgb
1
@ user2600366 Когда вы путешествуете вдоль границы треугольника в направлении p0 -> p1 -> p2 -> p0 и т. д., вы будете иметь внутреннюю часть треугольника всегда справа или всегда слева. В первом случае нумерация идет по часовой стрелке, во втором - против часовой стрелки.
andreasdr
47
Я написал этот код до последней попытки с Google и поиска этой страницы, поэтому я решил поделиться им. Это в основном оптимизированная версия ответа Киселевича. Я также изучил барицентрический метод, но, судя по статье в Википедии, мне трудно понять, как он более эффективен (полагаю, что существует более глубокая эквивалентность). В любом случае, этот алгоритм имеет то преимущество, что не использует деление; потенциальная проблема заключается в поведении обнаружения края в зависимости от ориентации.
На словах идея заключается в следующем: находится ли точка s слева или справа от линий AB и AC? Если это правда, это не может быть внутри. Если ложно, это по крайней мере внутри "конусов", которые удовлетворяют условию. Теперь, когда мы знаем, что точка внутри треугольника (треугольника) должна находиться на той же стороне AB, что и BC (и также CA), мы проверяем, отличаются ли они. Если это так, то s не может быть внутри, иначе s должен быть внутри.
Некоторые ключевые слова в расчетах - это линейные полуплоскости и определитель (перекрестное произведение 2x2). Возможно, более педагогический способ - это думать о ней как о точке, находящейся внутри, если она находится с одной и той же стороны (слева или справа) от каждой из линий AB, BC и CA. Однако вышеприведенный способ лучше подходит для некоторой оптимизации.
Этот тест примерно на 140-180% быстрее, чем первый (спасибо вам обоим, кстати). Я запустил код здесь: paste.ubuntu.com/p/k5w7ywH4p8, используя движок nodejs v8 с отключенной оптимизацией, и получил следующие результаты:: w! Node -p - minimal test1: 114.852ms test2: 64.330ms test1: 115.650ms test2: 63.491ms test1: 117.671ms test2: 65.353ms test1: 119.146ms test2: 63.871ms test1: 118.271ms test1: 118.670ms test2: 63.352ms
surgemcgee
@surgemcgee почему вы запускаете его без оптимизации? Разве это не более удалено от реальности?
xuiqzy
@xuiqzy Ну, моя программа содержит два разных решения. Мне еще предстоит применить самый быстрый способ сделать это. Возможно, этот комментарий должен быть удален и заменен моими законченными работами на этот
счет
33
C # версия барицентрического метода, опубликованная andreasdr и Perro Azul. Обратите внимание, что расчета площади можно избежать, если sи tимеют противоположные знаки. Я проверил правильное поведение с помощью довольно тщательного юнит-теста.
publicstaticboolPointInTriangle(Point p,Point p0,Point p1,Point p2){var s = p0.Y * p2.X - p0.X * p2.Y +(p2.Y - p0.Y)* p.X +(p0.X - p2.X)* p.Y;var t = p0.X * p1.Y - p0.Y * p1.X +(p0.Y - p1.Y)* p.X +(p1.X - p0.X)* p.Y;if((s <0)!=(t <0))returnfalse;var A =-p1.Y * p2.X + p0.Y *(p2.X - p1.X)+ p0.X *(p1.Y - p2.Y)+ p1.X * p2.Y;return A <0?(s <=0&& s + t >= A):(s >=0&& s + t <= A);}
[ править ] принял предложенную модификацию @Pierre; см комментарии
Решение с конечным оператором if работает для треугольных точек по часовой стрелке и против часовой стрелки.
Люк Дюпен
@ LukeDupin Не уверен, что я понимаю ваш комментарий. Этот ответ работает, как отправлено для любого поставленного заказа 3 баллов.
Гленн
12
Java-версия барицентрического метода:
classTriangle{Triangle(double x1,double y1,double x2,double y2,double x3,double y3){this.x3 = x3;this.y3 = y3;
y23 = y2 - y3;
x32 = x3 - x2;
y31 = y3 - y1;
x13 = x1 - x3;
det = y23 * x13 - x32 * y31;
minD =Math.min(det,0);
maxD =Math.max(det,0);}boolean contains(double x,double y){double dx = x - x3;double dy = y - y3;double a = y23 * dx + x32 * dy;if(a < minD || a > maxD)returnfalse;double b = y31 * dx + x13 * dy;if(b < minD || b > maxD)returnfalse;double c = det - a - b;if(c < minD || c > maxD)returnfalse;returntrue;}privatefinaldouble x3, y3;privatefinaldouble y23, x32, y31, x13;privatefinaldouble det, minD, maxD;}
Приведенный выше код будет точно работать с целыми числами, при условии отсутствия переполнений. Он также будет работать с треугольниками по часовой стрелке и против часовой стрелки. Он не будет работать с коллинеарными треугольниками (но вы можете проверить это, протестировав det == 0).
Барицентрическая версия является самой быстрой, если вы собираетесь тестировать разные точки с одним и тем же треугольником.
Барицентрическая версия не является симметричной в 3 точках треугольника, поэтому она, вероятно, будет менее последовательной, чем версия полуплоскости ребра Корнеля Киселевича, из-за ошибок округления с плавающей точкой.
Предоставлено: я сделал приведенный выше код из статьи Википедии о барицентрических координатах.
Ницца ! Можно даже улучшить использование кортежей javax.vecmath Point3f / Point2f, чтобы лучше обрабатывать ввод данных.
Алекс Бирт
10
Простой способ состоит в том, чтобы:
найдите векторы, соединяющие точку с каждой из трех вершин треугольника, и суммируйте углы между этими векторами. Если сумма углов равна 2 * пи, то точка находится внутри треугольника.
Два хороших сайта, которые объясняют альтернативы:
Хм, этот метод не совсем эффективен и очень подвержен ошибкам в цифрах ...
Корнел Киселевич
Это совсем наоборот, это очень неэффективно :-) Это всего лишь один простой способ, который легко реализовать. Можете ли вы привести пример числовой ошибки, которую это может вызвать?
Саймон П Стивенс
Хотя мне кажется, что это лучший из всех ответов по этой теме, я думаю, что точки на краях треугольника рассчитаны для включения в треугольник, и у вас нет твердого контроля над этим.
Уменьшить
проверка, точно ли это 2pi, численно невозможна, учитывая иррациональность пи. Однако вам просто нужно проверить, составляют ли углы нечто большее, чем число пи.
<scriptsrc="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script><pre>Click: place the point.
Double click: random triangle.</pre><preid="result"></pre><canvaswidth="500"height="500"></canvas>
Это очень хорошо сравнивается с решением Kornel Kisielewicz (25 повторений, 1 память, 15 вычитаний, 6 умножений, 5 сравнений) и может быть даже лучше, если необходимо обнаружение по часовой стрелке / против часовой стрелки (которое занимает 6 повторений, 1 сложение, 2 вычитания , 2 умножения и 1 сравнение сами по себе, используя определитель аналитического решения, как указано в rhgb ).
Я только что проверил код как есть, и он не работает для меня (пример p -4.69317198, -6.99191951 p0 -7.05846786 0.596718192 p1 -6.8703599 -2.36565161 p2 -4.69317198, -6.99191951)
Джованни Фуншал,
@GiovanniFunchal Странно, ваш пример работает для меня как в jsfiddle (замените начальные определения «точка» и «треугольник»), так и в моей локальной реализации Python. Проблемы с числовой точностью (попробуйте удалить некоторые десятичные дроби)?
Седрик Дюфур
1
Вы, кажется, самый быстрый в моем тесте: jsfiddle.net/eyal/gxw3632c/27 . Разница между всеми методами довольно мала.
Эяль
Попробуйте треугольник (-1, -1), (1, -1), (0,1) и точку (0, -1). Возвращает false, когда должно возвращать true, потому что s (2) + t (2)> d (2). Кажется, что-то не так с математикой на краях треугольника, так как точка p находится прямо на границе между p0 и p1, и не просто преобразовать <в a <= или что-то в этом роде.
devnullicus
5
Что я делаю, это пересчитать три норма лица,
в 3D - перекрестным произведением бокового вектора и нормального вектора лица.
в 2D, просто меняя компоненты и отрицая один,
тогда внутри / снаружи для любой одной стороны это когда точечное произведение боковой нормали и вектора вершины в точку меняет знак. Повторите для других двух (или более) сторон.
Преимущества:
многое вычисляется заранее, что отлично подходит для тестирования нескольких точек в одном и том же треугольнике.
раннее отклонение общего случая больше внешних, чем внутренних точек. (также, если распределение точек взвешено в одну сторону, можно сначала проверить эту сторону.)
defPointInsideTriangle2(pt,tri):'''checks if point pt(2) is inside triangle tri(3x2). @Developer'''
a =1/(-tri[1,1]*tri[2,0]+tri[0,1]*(-tri[1,0]+tri[2,0])+ \
tri[0,0]*(tri[1,1]-tri[2,1])+tri[1,0]*tri[2,1])
s = a*(tri[2,0]*tri[0,1]-tri[0,0]*tri[2,1]+(tri[2,1]-tri[0,1])*pt[0]+ \
(tri[0,0]-tri[2,0])*pt[1])if s<0:returnFalseelse: t = a*(tri[0,0]*tri[1,1]-tri[1,0]*tri[0,1]+(tri[0,1]-tri[1,1])*pt[0]+ \
(tri[1,0]-tri[0,0])*pt[1])return((t>0)and(1-s-t>0))
Я не смог сделать эту работу, например, для точки в треугольнике [(0,0), (3,0), (3,4)], ни точек (1,1) или (0 , 0) положительный результат теста. Я попробовал с треугольными точками по часовой стрелке и против часовой стрелки.
ThorSummoner
3
Если вы ищете скорость, вот процедура, которая может вам помочь.
Сортируйте вершины треугольника по их ординатам. Это займет в худшем случае три сравнения. Пусть Y0, Y1, Y2 - три отсортированных значения. Проводя через них три горизонтали, вы делите плоскость на две полуплоскости и две плиты. Пусть Y будет ординатой точки запроса.
if Y < Y1
if Y <= Y0 -> the point lies in the upper half plane, outside the triangle; you are done
else Y > Y0 -> the point lies in the upper slab
else
if Y >= Y2 -> the point lies in the lower half plane, outside the triangle; you are done
else Y < Y2 -> the point lies in the lower slab
Стоит еще два сравнения. Как видите, быстрое отклонение достигается для точек за пределами «ограничительной плиты».
При желании вы можете поставить тест на абсциссы для быстрого отклонения слева и справа (X <= X0' or X >= X2' ). При этом будет реализован быстрый ограничивающий прямоугольный тест, но вам также придется сортировать по абсциссам.
В конце концов вам нужно будет вычислить знак данной точки относительно двух сторон треугольника, которые разграничивают соответствующую плиту (верхнюю или нижнюю). Тест имеет вид:
Полное обсуждение i, j, k комбинаций (их шесть на основе результатов такого рода) выходит за рамки этого ответа и «оставлено в качестве упражнения для читателя»; для эффективности они должны быть жестко закодированы.
Если вы считаете, что это решение сложное, обратите внимание, что оно в основном включает в себя простые сравнения (некоторые из которых могут быть предварительно вычислены), плюс 6 вычитаний и 4 умножения в случае неудачи теста ограничивающего прямоугольника. Последнюю стоимость трудно превзойти, так как в худшем случае вы не можете избежать сравнения контрольной точки с двумя сторонами (ни один метод в других ответах не имеет более низкой стоимости, некоторые ухудшают ее, например, 15 вычитаний и 6 умножений, иногда делений).
ОБНОВЛЕНИЕ: быстрее с преобразованием сдвига
Как объяснено выше, вы можете быстро найти точку внутри одной из четырех горизонтальных полос, разделенных тремя ординатами вершин, используя два сравнения.
При желании вы можете выполнить один или два дополнительных теста X, чтобы проверить внутреннюю границу ограничительной рамки (пунктирные линии).
Затем рассмотрим преобразование «сдвиг», определяемое как X'= X - m Y, Y' = Y, где m- наклон DX/DYдля самого высокого края. Это преобразование сделает эту сторону треугольника вертикальной. И поскольку вы знаете, на какой стороне средней горизонтали вы находитесь, достаточно проверить знак относительно одной стороны треугольника.
Предполагая, что вы предварительно вычислили наклон m, а также X'для вершин срезаемого треугольника и коэффициенты уравнений сторон, как X = m Y + pвам нужно в худшем случае
два ординатных сравнения для вертикальной классификации;
возможно одно или два сравнения абсцисс для отклонения ограничительной рамки;
расчет X' = X - m Y;
одно или два сравнения с абсциссами срезанного треугольника;
один знак теста X >< m' Y + p'против соответствующей стороны срезанного треугольника.
Если вы знаете координаты трех вершин и координаты конкретной точки, то вы можете получить площадь полного треугольника. Затем вычислите площадь трех сегментов треугольника (одна точка - заданная точка, а две другие - любые две вершины треугольника). Таким образом, вы получите площадь трех треугольных сегментов. Если сумма этих областей равна общей площади (которую вы получили ранее), то точка должна быть внутри треугольника. В противном случае точка не находится внутри треугольника. Это должно работать. Если есть какие-либо проблемы, дайте мне знать. Спасибо.
Построение занимает много времени, но эта сетка тестируется за 0,0195319652557 секунд против 0,0844349861145 секунд кода разработчика .
Наконец-то комментарий к коду:
# Using barycentric coordintes, any point inside can be described as:# X = p0.x * r + p1.x * s + p2.x * t# Y = p0.y * r + p1.y * s + p2.y * t# with:# r + s + t = 1 and 0 < r,s,t < 1# then: r = 1 - s - t# and then:# X = p0.x * (1 - s - t) + p1.x * s + p2.x * t# Y = p0.y * (1 - s - t) + p1.y * s + p2.y * t## X = p0.x + (p1.x-p0.x) * s + (p2.x-p0.x) * t# Y = p0.y + (p1.y-p0.y) * s + (p2.y-p0.y) * t## X - p0.x = (p1.x-p0.x) * s + (p2.x-p0.x) * t# Y - p0.y = (p1.y-p0.y) * s + (p2.y-p0.y) * t## we have to solve:## [ X - p0.x ] = [(p1.x-p0.x) (p2.x-p0.x)] * [ s ]# [ Y - p0.Y ] [(p1.y-p0.y) (p2.y-p0.y)] [ t ]## ---> b = A*x ; ---> x = A^-1 * b# # [ s ] = A^-1 * [ X - p0.x ]# [ t ] [ Y - p0.Y ]## A^-1 = 1/D * adj(A)## The adjugate of A:## adj(A) = [(p2.y-p0.y) -(p2.x-p0.x)]# [-(p1.y-p0.y) (p1.x-p0.x)]## The determinant of A:## D = (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x)## Then:## s_p = { (p2.y-p0.y)*(X - p0.x) - (p2.x-p0.x)*(Y - p0.Y) }# t_p = { (p1.x-p0.x)*(Y - p0.Y) - (p1.y-p0.y)*(X - p0.x) }## s = s_p / D# t = t_p / D## Recovering r:## r = 1 - (s_p + t_p)/D## Since we only want to know if it is insidem not the barycentric coordinate:## 0 < 1 - (s_p + t_p)/D < 1# 0 < (s_p + t_p)/D < 1# 0 < (s_p + t_p) < D## The condition is:# if D > 0:# s_p > 0 and t_p > 0 and (s_p + t_p) < D# else:# s_p < 0 and t_p < 0 and (s_p + t_p) > D## s_p = { dY20*dX - dX20*dY }# t_p = { dX10*dY - dY10*dX }# D = dX10*dY20 - dY10*dX20
function triangleContains(ax, ay, bx, by, cx, cy, x, y){let det =(bx - ax)*(cy - ay)-(by - ay)*(cx - ax)return det *((bx - ax)*(y - ay)-(by - ay)*(x - ax))>0&&
det *((cx - bx)*(y - by)-(cy - by)*(x - bx))>0&&
det *((ax - cx)*(y - cy)-(ay - cy)*(x - cx))>0}let width =500, height =500// clockwiselet triangle1 ={
A :{ x:10, y:-10},
C :{ x:20, y:100},
B :{ x:-90, y:10},
color:'#f00',}// counter clockwiselet triangle2 ={
A :{ x:20, y:-60},
B :{ x:90, y:20},
C :{ x:20, y:60},
color:'#00f',}let scale =2let mouse ={ x:0, y:0}// DRAW >let wrapper = document.querySelector('div.wrapper')
wrapper.onmousemove =({ layerX:x, layerY:y })=>{
x -= width /2
y -= height /2
x /= scale
y /= scale
mouse.x = x
mouse.y = y
drawInteractive()}function drawArrow(ctx, A, B){let v = normalize(sub(B, A),3)let I = center(A, B)let p
p = add(I, rotate(v,90), v)
ctx.moveTo(p.x, p.y)
ctx.lineTo(I.x, I .y)
p = add(I, rotate(v,-90), v)
ctx.lineTo(p.x, p.y)}function drawTriangle(ctx,{ A, B, C, color }){
ctx.beginPath()
ctx.moveTo(A.x, A.y)
ctx.lineTo(B.x, B.y)
ctx.lineTo(C.x, C.y)
ctx.closePath()
ctx.fillStyle = color +'6'
ctx.strokeStyle = color
ctx.fill()
drawArrow(ctx, A, B)
drawArrow(ctx, B, C)
drawArrow(ctx, C, A)
ctx.stroke()}function contains({ A, B, C }, P){return triangleContains(A.x, A.y, B.x, B.y, C.x, C.y, P.x, P.y)}function resetCanvas(canvas){
canvas.width = width
canvas.height = height
let ctx = canvas.getContext('2d')
ctx.resetTransform()
ctx.clearRect(0,0, width, height)
ctx.setTransform(scale,0,0, scale, width/2, height/2)}function drawDots(){let canvas = document.querySelector('canvas#dots')let ctx = canvas.getContext('2d')
resetCanvas(canvas)let count =1000for(let i =0; i < count; i++){let x = width *(Math.random()-.5)let y = width *(Math.random()-.5)
ctx.beginPath()
ctx.ellipse(x, y,1,1,0,0,2*Math.PI)if(contains(triangle1,{ x, y })){
ctx.fillStyle ='#f00'}elseif(contains(triangle2,{ x, y })){
ctx.fillStyle ='#00f'}else{
ctx.fillStyle ='#0003'}
ctx.fill()}}function drawInteractive(){let canvas = document.querySelector('canvas#interactive')let ctx = canvas.getContext('2d')
resetCanvas(canvas)
ctx.beginPath()
ctx.moveTo(0,-height/2)
ctx.lineTo(0, height/2)
ctx.moveTo(-width/2,0)
ctx.lineTo(width/2,0)
ctx.strokeStyle ='#0003'
ctx.stroke()
drawTriangle(ctx, triangle1)
drawTriangle(ctx, triangle2)
ctx.beginPath()
ctx.ellipse(mouse.x, mouse.y,4,4,0,0,2*Math.PI)if(contains(triangle1, mouse)){
ctx.fillStyle = triangle1.color +'a'
ctx.fill()}elseif(contains(triangle2, mouse)){
ctx.fillStyle = triangle2.color +'a'
ctx.fill()}else{
ctx.strokeStyle ='black'
ctx.stroke()}}
drawDots()
drawInteractive()// trigofunction add(...points){let x =0, y =0for(let point of points){
x += point.x
y += point.y
}return{ x, y }}function center(...points){let x =0, y =0for(let point of points){
x += point.x
y += point.y
}
x /= points.length
y /= points.length
return{ x, y }}function sub(A, B){let x = A.x - B.x
let y = A.y - B.y
return{ x, y }}function normalize({ x, y }, length =10){let r = length /Math.sqrt(x * x + y * y)
x *= r
y *= r
return{ x, y }}function rotate({ x, y }, angle =90){let length =Math.sqrt(x * x + y * y)
angle *=Math.PI /180
angle +=Math.atan2(y, x)
x = length *Math.cos(angle)
y = length *Math.sin(angle)return{ x, y }}
*{margin:0;}
html {font-family: monospace;}
body {padding:32px;}
span.red {color:#f00;}
span.blue {color:#00f;}
canvas {position: absolute;border: solid 1px#ddd;}
<p><spanclass="red">red triangle</span> is clockwise</p><p><spanclass="blue">blue triangle</span> is couter clockwise</p><br><divclass="wrapper"><canvasid="dots"></canvas><canvasid="interactive"></canvas></div>
Я использую здесь тот же метод, который описан выше: точка находится внутри ABC, если она находится соответственно на «той же» стороне каждой линии AB, BC, CA.
я видел ваш ответ Python, мы используем тот же метод, если я использую еще одну строку ( let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)), это определить порядок намотки треугольника, поэтому метод будет работать с треугольниками CW и CCW (см. jsFiddle).
Джозеф Мердриньяк
1
хм, я сделал ошибку, я написал: let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)вместо того, let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)чтобы это исправить, спасибо за сообщение
Джозеф Мердриньяк
2
Я просто хочу использовать простую векторную математику, чтобы объяснить решение барицентрических координат, которое дал Андреас, это будет намного легче понять.
Область A определяется как любой вектор, заданный s * v02 + t * v01, с условием s> = 0 и t> = 0. Если любая точка внутри треугольника v0, v1, v2, она должна находиться внутри области A.
Если дополнительно ограничить s, то t принадлежит [0, 1]. Мы получаем область B, которая содержит все векторы s * v02 + t * v01, с условием s, t принадлежит [0, 1]. Стоит отметить, что нижняя часть Зоны B является зеркалом Треугольника v0, v1, v2. Проблема возникает, если мы можем дать определенные условия s и t для дальнейшего исключения нижней части области B.
Предположим, мы даем значение s, и t меняется в [0, 1]. На следующем рисунке точка p находится на краю v1v2. Все векторы s * v02 + t * v01, которые расположены вдоль штриховой линии простой векторной суммой. В v1v2 и точке пересечения штриховой линии p имеем:
мы получаем 1 - s = tp, тогда 1 = s + tp. Если любое t> tp, 1 <s + t где находится на двойной штриховой линии, вектор находится за пределами треугольника, то любое t <= tp, 1> = s + t где находится на одной штриховой линии, вектор внутри треугольника.
Тогда, если мы задали s в [0, 1], соответствующему t должно соответствовать 1> = s + t для вектора внутри треугольника.
Итак, в итоге мы получаем v = s * v02 + t * v01, v находится внутри треугольника с условием s, t, s + t принадлежит [0, 1]. Затем переведите в точку, мы имеем
p - p0 = s * (p1 - p0) + t * (p2 - p0), с s, t, s + t в [0, 1]
что аналогично решению Андреаса для решения системы уравнений p = p0 + s * (p1 - p0) + t * (p2 - p0), где s, t, s + t принадлежат [0, 1].
Вы можете просто сказать, что вы используете локальную рамку, определенную тремя вершинами, так что стороны становятся s = 0, t = 0 и s + t = 1. Аффинное преобразование координат является хорошо известной операцией линейной алгебры.
Ив Дауст
2
Вот решение в Python, которое является эффективным, документированным и содержит три юнит-теста. Это профессиональное качество, готовое для использования в вашем проекте в виде модуля, как есть.
import unittest
###############################################################################def point_in_triangle(point, triangle):"""Returns True if the point is inside the triangle
and returns False if it falls outside.
- The argument *point* is a tuple with two elements
containing the X,Y coordinates respectively.
- The argument *triangle* is a tuple with three elements each
element consisting of a tuple of X,Y coordinates.
It works like this:
Walk clockwise or counterclockwise around the triangle
and project the point onto the segment we are crossing
by using the dot product.
Finally, check that the vector created is on the same side
for each of the triangle's segments.
"""# Unpack arguments
x, y = point
ax, ay = triangle[0]
bx, by = triangle[1]
cx, cy = triangle[2]# Segment A to B
side_1 =(x - bx)*(ay - by)-(ax - bx)*(y - by)# Segment B to C
side_2 =(x - cx)*(by - cy)-(bx - cx)*(y - cy)# Segment C to A
side_3 =(x - ax)*(cy - ay)-(cx - ax)*(y - ay)# All the signs must be positive or all negativereturn(side_1 <0.0)==(side_2 <0.0)==(side_3 <0.0)###############################################################################classTestPointInTriangle(unittest.TestCase):
triangle =((22,8),(12,55),(7,19))def test_inside(self):
point =(15,20)
self.assertTrue(point_in_triangle(point, self.triangle))def test_outside(self):
point =(1,7)
self.assertFalse(point_in_triangle(point, self.triangle))def test_border_case(self):"""If the point is exactly on one of the triangle's edges,
we consider it is inside."""
point =(7,19)
self.assertTrue(point_in_triangle(point, self.triangle))###############################################################################if __name__ =="__main__":
suite = unittest.defaultTestLoader.loadTestsFromTestCase(TestPointInTriangle)
unittest.TextTestRunner().run(suite)
Существует дополнительный необязательный графический тест для алгоритма выше, чтобы подтвердить его правильность:
import random
from matplotlib import pyplot
from triangle_test import point_in_triangle
################################################################################ The area #
size_x =64
size_y =64# The triangle #
triangle =((22,8),(12,55),(7,19))# Number of random points #
count_points =10000# Prepare the figure #
figure = pyplot.figure()
axes = figure.add_subplot(111, aspect='equal')
axes.set_title("Test the 'point_in_triangle' function")
axes.set_xlim(0, size_x)
axes.set_ylim(0, size_y)# Plot the triangle #from matplotlib.patches importPolygon
axes.add_patch(Polygon(triangle, linewidth=1, edgecolor='k', facecolor='none'))# Plot the points #for i in range(count_points):
x = random.uniform(0, size_x)
y = random.uniform(0, size_y)if point_in_triangle((x,y), triangle): pyplot.plot(x, y,'.g')else: pyplot.plot(x, y,'.b')# Save it #
figure.savefig("point_in_triangle.pdf")
Существуют досадные граничные условия, когда точка находится точно на общем ребре двух соседних треугольников. Точка не может быть ни в обоих, ни в одном из треугольников. Вам нужен произвольный, но последовательный способ назначения точки. Например, нарисуйте горизонтальную линию через точку. Если линия пересекается с другой стороной треугольника справа, точка обрабатывается так, как если бы она находилась внутри треугольника. Если пересечение слева, точка находится снаружи.
Если линия, на которой лежит точка, является горизонтальной, используйте выше / ниже.
Если точка находится на общей вершине нескольких треугольников, используйте треугольник, центр которого точка образует наименьший угол.
Веселее: три точки могут быть на прямой (ноль градусов), например (0,0) - (0,10) - (0,5). В алгоритме триангуляции «ухо» (0,10) должно быть обрезано, а сгенерированный «треугольник» является вырожденным случаем прямой линии.
Это простейшая концепция, чтобы определить, находится ли точка внутри или снаружи треугольника или на плече треугольника.
Определение точки находится внутри треугольника по определителям:
Самый простой рабочий код:
#-*- coding: utf-8 -*-import numpy as np
tri_points =[(1,1),(2,3),(3,1)]def pisinTri(point,tri_points):Dx,Dy= point
A,B,C = tri_points
Ax,Ay= A
Bx,By= B
Cx,Cy= C
M1 = np.array([[Dx-Bx,Dy-By,0],[Ax-Bx,Ay-By,0],[1,1,1]])
M2 = np.array([[Dx-Ax,Dy-Ay,0],[Cx-Ax,Cy-Ay,0],[1,1,1]])
M3 = np.array([[Dx-Cx,Dy-Cy,0],[Bx-Cx,By-Cy,0],[1,1,1]])
M1 = np.linalg.det(M1)
M2 = np.linalg.det(M2)
M3 = np.linalg.det(M3)print(M1,M2,M3)if(M1 ==0or M2 ==0or M3 ==0):print("Point: ",point," lies on the arms of Triangle")elif((M1 >0and M2 >0and M3 >0)or(M1 <0and M2 <0and M3 <0)):#if products is non 0 check if all of their sign is sameprint("Point: ",point," lies inside the Triangle")else:print("Point: ",point," lies outside the Triangle")print("Vertices of Triangle: ",tri_points)
points =[(0,0),(1,1),(2,3),(3,1),(2,2),(4,4),(1,0),(0,4)]for c in points:
pisinTri(c,tri_points)
Самый простой способ, и он работает со всеми типами треугольников, это просто определить углы точек P, A, B, C точек. Если любой из углов больше 180.0 градусов, то он снаружи, если 180.0, то он на окружности, а если acos изменяет вам и меньше 180.0, то он внутри. Посмотрите на понимание http: // math- Physics -psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html
Честно говоря, это так же просто, как ответ Саймона П Стивена однако при таком подходе у вас нет точного контроля, хотите ли вы, чтобы точки на краях треугольника были включены или нет.
Мой подход немного другой, но очень простой. Рассмотрим следующий треугольник;
Чтобы иметь точку в треугольнике, мы должны выполнить 3 условия
Угол ACE (зеленый) должен быть меньше угла ACB (красный)
Угол ECB (синий) должен быть меньше угла ACB (красный)
Точка E и точка C должны иметь один и тот же знак, когда их значения x и y применяются к уравнению | AB | линия.
В этом методе у вас есть полный контроль, чтобы включить или исключить точку по краям индивидуально. Таким образом, вы можете проверить, находится ли точка в треугольнике, включая только | AC | край например.
Так что мое решение в JavaScript будет следующим;
function isInTriangle(t,p){function isInBorder(a,b,c,p){var m =(a.y - b.y)/(a.x - b.x);// calculate the slopereturnMath.sign(p.y - m*p.x + m*a.x - a.y)===Math.sign(c.y - m*c.x + m*a.x - a.y);}function findAngle(a,b,c){// calculate the C angle from 3 points.var ca =Math.hypot(c.x-a.x, c.y-a.y),// ca edge length
cb =Math.hypot(c.x-b.x, c.y-b.y),// cb edge length
ab =Math.hypot(a.x-b.x, a.y-b.y);// ab edge lengthreturnMath.acos((ca*ca + cb*cb - ab*ab)/(2*ca*cb));// return the C angle}var pas = t.slice(1).map(tp => findAngle(p,tp,t[0])),// find the angle between (p,t[0]) with (t[1],t[0]) & (t[2],t[0])
ta = findAngle(t[1],t[2],t[0]);return pas[0]< ta && pas[1]< ta && isInBorder(t[1],t[2],t[0],p);}var triangle =[{x:3, y:4},{x:10, y:8},{x:6, y:10}],
point1 ={x:3, y:9},
point2 ={x:7, y:9};
console.log(isInTriangle(triangle,point1));
console.log(isInTriangle(triangle,point2));
Это не может быть более эффективным, чем это! Каждая сторона треугольника может иметь независимую позицию и ориентацию, следовательно, три вычисления: l1, l2 и l3, безусловно, необходимы, включая 2 умножения каждый. Как только l1, l2 и l3 станут известны, результатом будет лишь несколько базовых сравнений и логических операций.
<scriptsrc="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script><buttonid="performance">Run performance test (open console)</button><pre>Click: place the point.
Double click: random triangle.</pre><preid="result"></pre><canvaswidth="500"height="500"></canvas>
bool point2Dtriangle(double e,double f,double a,double b,double c,double g,double h,double i,double v,double w){/* inputs: e=point.x, f=point.y
a=triangle.Ax, b=triangle.Bx, c=triangle.Cx
g=triangle.Ay, h=triangle.By, i=triangle.Cy */
v =1-(f *(b - c)+ h *(c - e)+ i *(e - b))/(g *(b - c)+ h *(c - a)+ i *(a - b));
w =(f *(a - b)+ g *(b - e)+ h *(e - a))/(g *(b - c)+ h *(c - a)+ i *(a - b));if(*v >-0.0&&*v <1.0000001&&*w >-0.0&&*w <*v)returntrue;//is insideelsereturnfalse;//is outsidereturn0;}
почти идеальные декартовы координаты, преобразованные из барицентрических, экспортируются в двойные числа * v (x) и * w (y). Оба экспортных двойника должны иметь символ * в каждом случае, вероятно: * v и * w Код можно использовать и для другого треугольника четырехугольника. Настоящим подписанный записал только треугольник abc из четырехугольника abcd по часовой стрелке
A---B
|..\\.o|
|....\\.|
D---C
точка o находится внутри треугольника ABC для тестирования со вторым треугольником, вызывая эту функцию в направлении CDA, и результаты должны быть правильными после *v=1-*v;и *w=1-*w;для четырехугольника
Мне нужна была проверка треугольника в «контролируемой среде», когда вы абсолютно уверены, что треугольники будут по часовой стрелке. Итак, я взял jsfiddle Перро Азула и изменил его, как предложено coproc для таких случаев; также удалены избыточные 0,5 и 2 умножения, потому что они просто отменяют друг друга.
<scriptsrc="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script><pre>Click: place the point.
Double click: random triangle.</pre><preid="result"></pre><canvaswidth="500"height="500"></canvas>
Ответы:
В общем, самый простой (и довольно оптимальный) алгоритм проверяет, на какой стороне полуплоскости, созданной ребрами, находится точка.
Вот некоторая качественная информация в этой теме о GameDev , включая проблемы с производительностью.
А вот код, который поможет вам начать:
источник
Решите следующую систему уравнений:
Точка
p
находится внутри треугольника, если0 <= s <= 1
и0 <= t <= 1
иs + t <= 1
.s
,t
И1 - s - t
называются барицентрические координаты точкиp
.источник
s + t <= 1
подразумеваетсяs <= 1
иt <= 1
еслиs >= 0
иt >= 0
.Я согласен с Андреасом Бринком , барицентрические координаты очень удобны для этой задачи. Обратите внимание, что нет необходимости каждый раз решать систему уравнений: просто оцените аналитическое решение. Используя обозначение Андреаса , решение:
где
Area
находится (подписанная) площадь треугольника:Просто оцени
s
,t
и1-s-t
. Точкаp
находится внутри треугольника тогда и только тогда, когда все они положительны.РЕДАКТИРОВАТЬ: Обратите внимание, что вышеприведенное выражение для области предполагает, что нумерация узлов треугольника против часовой стрелки. Если нумерация идет по часовой стрелке, это выражение вернет отрицательную область (но с правильной величиной). Однако сам тест (
s>0 && t>0 && 1-s-t>0
) не зависит от направления нумерации, поскольку вышеприведенные выражения, умноженные на,1/(2*Area)
также меняют знак, если изменяется ориентация узла треугольника.РЕДАКТИРОВАТЬ 2: Для еще большей вычислительной эффективности, см. Комментарий coproc ниже (который подчеркивает, что если заранее известна ориентация узлов треугольника (по часовой стрелке или против часовой стрелки), деление на
2*Area
в выражениях дляs
иt
может быть избегать). См. Также jsfiddle-код Perro Azul в комментариях к ответу Андреаса Бринка .источник
2*Area
, то есть путем вычисленияs´=2*|Area|*s
иt´=2*|Area|*t
(если ориентация точек - по часовой стрелке или против часовой стрелки - неизвестна,Area
конечно, необходимо проверить знак , но в противном случае это может быть даже не нужно вычислять), так как для проверкиs>0
достаточно проверитьs´>0
. И вместо проверки1-s-t>0
достаточно проверитьs´+t´<2*|Area|
.p0->p1->p2
это против часовой стрелки в декартовой (который, как правило , по часовой стрелке , в экранных координатах ), тоArea
вычисляется с помощью этого метода будет положительным.Я написал этот код до последней попытки с Google и поиска этой страницы, поэтому я решил поделиться им. Это в основном оптимизированная версия ответа Киселевича. Я также изучил барицентрический метод, но, судя по статье в Википедии, мне трудно понять, как он более эффективен (полагаю, что существует более глубокая эквивалентность). В любом случае, этот алгоритм имеет то преимущество, что не использует деление; потенциальная проблема заключается в поведении обнаружения края в зависимости от ориентации.
На словах идея заключается в следующем: находится ли точка s слева или справа от линий AB и AC? Если это правда, это не может быть внутри. Если ложно, это по крайней мере внутри "конусов", которые удовлетворяют условию. Теперь, когда мы знаем, что точка внутри треугольника (треугольника) должна находиться на той же стороне AB, что и BC (и также CA), мы проверяем, отличаются ли они. Если это так, то s не может быть внутри, иначе s должен быть внутри.
Некоторые ключевые слова в расчетах - это линейные полуплоскости и определитель (перекрестное произведение 2x2). Возможно, более педагогический способ - это думать о ней как о точке, находящейся внутри, если она находится с одной и той же стороны (слева или справа) от каждой из линий AB, BC и CA. Однако вышеприведенный способ лучше подходит для некоторой оптимизации.
источник
C # версия барицентрического метода, опубликованная andreasdr и Perro Azul. Обратите внимание, что расчета площади можно избежать, если
s
иt
имеют противоположные знаки. Я проверил правильное поведение с помощью довольно тщательного юнит-теста.[ править ]
принял предложенную модификацию @Pierre; см комментарии
источник
Java-версия барицентрического метода:
Приведенный выше код будет точно работать с целыми числами, при условии отсутствия переполнений. Он также будет работать с треугольниками по часовой стрелке и против часовой стрелки. Он не будет работать с коллинеарными треугольниками (но вы можете проверить это, протестировав det == 0).
Барицентрическая версия является самой быстрой, если вы собираетесь тестировать разные точки с одним и тем же треугольником.
Барицентрическая версия не является симметричной в 3 точках треугольника, поэтому она, вероятно, будет менее последовательной, чем версия полуплоскости ребра Корнеля Киселевича, из-за ошибок округления с плавающей точкой.
Предоставлено: я сделал приведенный выше код из статьи Википедии о барицентрических координатах.
источник
Простой способ состоит в том, чтобы:
Два хороших сайта, которые объясняют альтернативы:
черная пешка и вольфрам
источник
Используя аналитическое решение для барицентрических координат (указал Андреас Бринк ) и:
Можно минимизировать количество «дорогостоящих» операций:
Код можно вставить в Perro Azul jsfiddle или попробовать, нажав «Выполнить фрагмент кода» ниже.
Ведущий к:
Это очень хорошо сравнивается с решением Kornel Kisielewicz (25 повторений, 1 память, 15 вычитаний, 6 умножений, 5 сравнений) и может быть даже лучше, если необходимо обнаружение по часовой стрелке / против часовой стрелки (которое занимает 6 повторений, 1 сложение, 2 вычитания , 2 умножения и 1 сравнение сами по себе, используя определитель аналитического решения, как указано в rhgb ).
источник
Что я делаю, это пересчитать три норма лица,
в 3D - перекрестным произведением бокового вектора и нормального вектора лица.
в 2D, просто меняя компоненты и отрицая один,
тогда внутри / снаружи для любой одной стороны это когда точечное произведение боковой нормали и вектора вершины в точку меняет знак. Повторите для других двух (или более) сторон.
Преимущества:
многое вычисляется заранее, что отлично подходит для тестирования нескольких точек в одном и том же треугольнике.
раннее отклонение общего случая больше внешних, чем внутренних точек. (также, если распределение точек взвешено в одну сторону, можно сначала проверить эту сторону.)
источник
Вот эффективная реализация Python :
и пример вывода:
источник
Если вы ищете скорость, вот процедура, которая может вам помочь.
Сортируйте вершины треугольника по их ординатам. Это займет в худшем случае три сравнения. Пусть Y0, Y1, Y2 - три отсортированных значения. Проводя через них три горизонтали, вы делите плоскость на две полуплоскости и две плиты. Пусть Y будет ординатой точки запроса.
Стоит еще два сравнения. Как видите, быстрое отклонение достигается для точек за пределами «ограничительной плиты».
При желании вы можете поставить тест на абсциссы для быстрого отклонения слева и справа (
X <= X0' or X >= X2'
). При этом будет реализован быстрый ограничивающий прямоугольный тест, но вам также придется сортировать по абсциссам.В конце концов вам нужно будет вычислить знак данной точки относительно двух сторон треугольника, которые разграничивают соответствующую плиту (верхнюю или нижнюю). Тест имеет вид:
Полное обсуждение
i, j, k
комбинаций (их шесть на основе результатов такого рода) выходит за рамки этого ответа и «оставлено в качестве упражнения для читателя»; для эффективности они должны быть жестко закодированы.Если вы считаете, что это решение сложное, обратите внимание, что оно в основном включает в себя простые сравнения (некоторые из которых могут быть предварительно вычислены), плюс 6 вычитаний и 4 умножения в случае неудачи теста ограничивающего прямоугольника. Последнюю стоимость трудно превзойти, так как в худшем случае вы не можете избежать сравнения контрольной точки с двумя сторонами (ни один метод в других ответах не имеет более низкой стоимости, некоторые ухудшают ее, например, 15 вычитаний и 6 умножений, иногда делений).
ОБНОВЛЕНИЕ: быстрее с преобразованием сдвига
Как объяснено выше, вы можете быстро найти точку внутри одной из четырех горизонтальных полос, разделенных тремя ординатами вершин, используя два сравнения.
При желании вы можете выполнить один или два дополнительных теста X, чтобы проверить внутреннюю границу ограничительной рамки (пунктирные линии).
Затем рассмотрим преобразование «сдвиг», определяемое как
X'= X - m Y, Y' = Y
, гдеm
- наклонDX/DY
для самого высокого края. Это преобразование сделает эту сторону треугольника вертикальной. И поскольку вы знаете, на какой стороне средней горизонтали вы находитесь, достаточно проверить знак относительно одной стороны треугольника.Предполагая, что вы предварительно вычислили наклон
m
, а такжеX'
для вершин срезаемого треугольника и коэффициенты уравнений сторон, какX = m Y + p
вам нужно в худшем случаеX' = X - m Y
;X >< m' Y + p'
против соответствующей стороны срезанного треугольника.источник
Если вы знаете координаты трех вершин и координаты конкретной точки, то вы можете получить площадь полного треугольника. Затем вычислите площадь трех сегментов треугольника (одна точка - заданная точка, а две другие - любые две вершины треугольника). Таким образом, вы получите площадь трех треугольных сегментов. Если сумма этих областей равна общей площади (которую вы получили ранее), то точка должна быть внутри треугольника. В противном случае точка не находится внутри треугольника. Это должно работать. Если есть какие-либо проблемы, дайте мне знать. Спасибо.
источник
Другая функция в Python , более быстрая, чем метод разработчика (по крайней мере для меня) и вдохновленная решением Седрика Дюфура :
Вы можете проверить это с:
Построение занимает много времени, но эта сетка тестируется за 0,0195319652557 секунд против 0,0844349861145 секунд кода разработчика .
Наконец-то комментарий к коду:
источник
ptInTriang([11,45],[45, 45],[45, 45] ,[44, 45])
и вернёмсяtrue
хотя и неверноПоскольку нет ответа JS, по
часовой стрелке и против часовой стрелки:
РЕДАКТИРОВАТЬ: была опечатка для вычисления det (
cy - ay
вместоcx - ax
), это исправлено.https://jsfiddle.net/jniac/rctb3gfL/
Я использую здесь тот же метод, который описан выше: точка находится внутри ABC, если она находится соответственно на «той же» стороне каждой линии AB, BC, CA.
источник
let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)
), это определить порядок намотки треугольника, поэтому метод будет работать с треугольниками CW и CCW (см. jsFiddle).let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)
вместо того,let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
чтобы это исправить, спасибо за сообщениеЯ просто хочу использовать простую векторную математику, чтобы объяснить решение барицентрических координат, которое дал Андреас, это будет намного легче понять.
(1-е) | v0v2 | / | v0v2 | = tp | v0v1 | / | v0v1 |
мы получаем 1 - s = tp, тогда 1 = s + tp. Если любое t> tp, 1 <s + t где находится на двойной штриховой линии, вектор находится за пределами треугольника, то любое t <= tp, 1> = s + t где находится на одной штриховой линии, вектор внутри треугольника.
Тогда, если мы задали s в [0, 1], соответствующему t должно соответствовать 1> = s + t для вектора внутри треугольника.
Итак, в итоге мы получаем v = s * v02 + t * v01, v находится внутри треугольника с условием s, t, s + t принадлежит [0, 1]. Затем переведите в точку, мы имеем
p - p0 = s * (p1 - p0) + t * (p2 - p0), с s, t, s + t в [0, 1]
что аналогично решению Андреаса для решения системы уравнений p = p0 + s * (p1 - p0) + t * (p2 - p0), где s, t, s + t принадлежат [0, 1].
источник
Вот решение в Python, которое является эффективным, документированным и содержит три юнит-теста. Это профессиональное качество, готовое для использования в вашем проекте в виде модуля, как есть.
Существует дополнительный необязательный графический тест для алгоритма выше, чтобы подтвердить его правильность:
Производим следующую графику:
источник
Существуют досадные граничные условия, когда точка находится точно на общем ребре двух соседних треугольников. Точка не может быть ни в обоих, ни в одном из треугольников. Вам нужен произвольный, но последовательный способ назначения точки. Например, нарисуйте горизонтальную линию через точку. Если линия пересекается с другой стороной треугольника справа, точка обрабатывается так, как если бы она находилась внутри треугольника. Если пересечение слева, точка находится снаружи.
Если линия, на которой лежит точка, является горизонтальной, используйте выше / ниже.
Если точка находится на общей вершине нескольких треугольников, используйте треугольник, центр которого точка образует наименьший угол.
Веселее: три точки могут быть на прямой (ноль градусов), например (0,0) - (0,10) - (0,5). В алгоритме триангуляции «ухо» (0,10) должно быть обрезано, а сгенерированный «треугольник» является вырожденным случаем прямой линии.
источник
Это простейшая концепция, чтобы определить, находится ли точка внутри или снаружи треугольника или на плече треугольника.
Определение точки находится внутри треугольника по определителям:
Самый простой рабочий код:
источник
Самый простой способ, и он работает со всеми типами треугольников, это просто определить углы точек P, A, B, C точек. Если любой из углов больше 180.0 градусов, то он снаружи, если 180.0, то он на окружности, а если acos изменяет вам и меньше 180.0, то он внутри. Посмотрите на понимание http: // math- Physics -psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html
источник
Честно говоря, это так же просто, как ответ Саймона П Стивена однако при таком подходе у вас нет точного контроля, хотите ли вы, чтобы точки на краях треугольника были включены или нет.
Мой подход немного другой, но очень простой. Рассмотрим следующий треугольник;
Чтобы иметь точку в треугольнике, мы должны выполнить 3 условия
В этом методе у вас есть полный контроль, чтобы включить или исключить точку по краям индивидуально. Таким образом, вы можете проверить, находится ли точка в треугольнике, включая только | AC | край например.
Так что мое решение в JavaScript будет следующим;
источник
Это не может быть более эффективным, чем это! Каждая сторона треугольника может иметь независимую позицию и ориентацию, следовательно, три вычисления: l1, l2 и l3, безусловно, необходимы, включая 2 умножения каждый. Как только l1, l2 и l3 станут известны, результатом будет лишь несколько базовых сравнений и логических операций.
источник
Предположительно высокопроизводительный код, который я адаптировал в JavaScript (статья ниже):
pointInTriangle(p, p0, p1, p2)
- для треугольников против часовой стрелкиpointInTriangle(p, p0, p1, p2)
- для треугольников по часовой стрелкеПосмотрите в jsFiddle (тест производительности включен), есть также проверка обмотки в отдельной функции. Или нажмите «Выполнить фрагмент кода» ниже
Вдохновленный этим: http://www.phatcode.net/articles.php?id=459
источник
почти идеальные декартовы координаты, преобразованные из барицентрических, экспортируются в двойные числа * v (x) и * w (y). Оба экспортных двойника должны иметь символ * в каждом случае, вероятно: * v и * w Код можно использовать и для другого треугольника четырехугольника. Настоящим подписанный записал только треугольник abc из четырехугольника abcd по часовой стрелке
точка o находится внутри треугольника ABC для тестирования со вторым треугольником, вызывая эту функцию в направлении CDA, и результаты должны быть правильными после
*v=1-*v;
и*w=1-*w;
для четырехугольникаисточник
Мне нужна была проверка треугольника в «контролируемой среде», когда вы абсолютно уверены, что треугольники будут по часовой стрелке. Итак, я взял jsfiddle Перро Азула и изменил его, как предложено coproc для таких случаев; также удалены избыточные 0,5 и 2 умножения, потому что они просто отменяют друг друга.
http://jsfiddle.net/dog_funtom/H7D7g/
Вот эквивалентный код C # для Unity:
источник
Один из самых простых способов проверить, положительна ли область, образованная вершинами треугольника (x1, y1), (x2, y2), (x3, y3).
Площадь можно рассчитать по формуле:
или код Python может быть записан как:
источник