Как определить, находится ли точка в 2D-треугольнике?
Есть ли простой способ определить, находится ли точка внутри треугольника? Это 2D, а не 3D.
25 ответов
В общем, самый простой (и довольно оптимальный) алгоритм проверяет, на какой стороне полуплоскости, созданной ребрами, находится точка.
Вот некоторая информация высокого качества в этой теме о GameDev, включая проблемы с производительностью.
А вот код, который поможет вам начать:
float sign (fPoint p1, fPoint p2, fPoint p3)
{
return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}
bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
float d1, d2, d3;
bool has_neg, has_pos;
d1 = sign(pt, v1, v2);
d2 = sign(pt, v2, v3);
d3 = sign(pt, v3, v1);
has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
return !(has_neg && has_pos);
}
Решите следующую систему уравнений:
p = p0 + (p1 - p0) * s + (p2 - p0) * t
Точка p находится внутри треугольника, если 0 <= s <= 1 а также 0 <= t <= 1 а также s + t <= 1,
s,t а также 1 - s - t называются барицентрическими координатами точки p,
Я согласен с Андреасом Бринком, барицентрические координаты очень удобны для этой задачи. Обратите внимание, что нет необходимости каждый раз решать систему уравнений: просто оцените аналитическое решение. Используя обозначение Андреаса, решение:
s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);
где Area является (подписанной) областью треугольника:
Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);
Просто оцени 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 в комментариях к ответу Андреаса Бринка.
Я написал этот код до последней попытки с Google и поиска этой страницы, поэтому я решил поделиться им. Это в основном оптимизированная версия ответа Киселевича. Я также изучил барицентрический метод, но, судя по статье в Википедии, мне трудно понять, как он более эффективен (полагаю, что существует более глубокая эквивалентность). В любом случае, этот алгоритм имеет то преимущество, что не использует деление; потенциальная проблема - поведение обнаружения края в зависимости от ориентации.
bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c)
{
int as_x = s.x-a.x;
int as_y = s.y-a.y;
bool s_ab = (b.x-a.x)*as_y-(b.y-a.y)*as_x > 0;
if((c.x-a.x)*as_y-(c.y-a.y)*as_x > 0 == s_ab) return false;
if((c.x-b.x)*(s.y-b.y)-(c.y-b.y)*(s.x-b.x) > 0 != s_ab) return false;
return true;
}
На словах идея такова: точка s слева или справа от обеих линий AB и AC? Если это правда, это не может быть внутри. Если ложь, то, по крайней мере, внутри "конусов", которые удовлетворяют условию. Теперь, когда мы знаем, что точка внутри треугольника (треугольника) должна находиться на той же стороне AB, что и BC (и также CA), мы проверяем, отличаются ли они. Если это так, то s не может быть внутри, иначе s должен быть внутри.
Некоторые ключевые слова в расчетах - это линейные полуплоскости и определитель (перекрестное произведение 2x2). Возможно, более педагогический способ - это думать о нем как о точке, находящейся внутри, если она находится с одной и той же стороны (слева или справа) от каждой из линий AB, BC и CA. Однако вышеприведенный способ лучше подходит для некоторой оптимизации.
C# версия барицентрического метода, опубликованная andreasdr и Perro Azul. Обратите внимание, что расчета площади можно избежать, если s а также t есть противоположные знаки. Я проверил правильное поведение с помощью довольно тщательного юнит-теста.
public static bool PointInTriangle(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))
return false;
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; смотреть комментарии
Java-версия барицентрического метода:
class Triangle {
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)
return false;
double b = y31 * dx + x13 * dy;
if (b < minD || b > maxD)
return false;
double c = det - a - b;
if (c < minD || c > maxD)
return false;
return true;
}
private final double x3, y3;
private final double y23, x32, y31, x13;
private final double det, minD, maxD;
}
Приведенный выше код будет точно работать с целыми числами, при условии отсутствия переполнений. Он также будет работать с треугольниками по часовой стрелке и против часовой стрелки. Он не будет работать с коллинеарными треугольниками (но вы можете проверить это, протестировав det==0).
Барицентрическая версия является самой быстрой, если вы собираетесь тестировать разные точки с одним и тем же треугольником.
Барицентрическая версия не является симметричной в трех точках треугольника, поэтому она, вероятно, будет менее последовательной, чем версия полуплоскости ребра Корнеля Киселевича, из-за ошибок округления с плавающей точкой.
Предоставлено: Я сделал приведенный выше код из статьи Википедии о барицентрических координатах.
Используя аналитическое решение для барицентрических координат (указано Андреасом Бринком) и:
- не распределяя умножение по скобкам
- избегая вычисления в несколько раз одних и тех же терминов, сохраняя их
- сокращение сравнений (на что указывают Копрок и Томас Эдинг)
можно минимизировать количество "дорогих" операций:
function ptInTriangle(p, p0, p1, p2) {
var dX = p.x-p2.x;
var dY = p.y-p2.y;
var dX21 = p2.x-p1.x;
var dY12 = p1.y-p2.y;
var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y);
var s = dY12*dX + dX21*dY;
var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY;
if (D<0) return s<=0 && t<=0 && s+t>=D;
return s>=0 && t>=0 && s+t<=D;
}
(код можно вставить в Perro Azul jsfiddle)
Ведущий к:
- переменная "напоминает": 30
- переменная память: 7
- дополнения: 4
- вычитаний: 8
- умножения: 6
- подразделения: нет
- сравнения: 4
Это очень хорошо сравнивается с решением Kornel Kisielewicz (25 повторений, 1 хранение, 15 вычитаний, 6 умножений, 5 сравнений) и может быть даже лучше, если требуется обнаружение по часовой стрелке / против часовой стрелки (которое занимает 6 повторений, 1 сложение, 2 вычитания, 2 умножения и 1 сравнение сами по себе, используя определитель аналитического решения, как указано в rhgb).
Простой способ состоит в том, чтобы:
найдите векторы, соединяющие точку с каждой из трех вершин треугольника, и суммируйте углы между этими векторами. Если сумма углов равна 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 negative
return (side_1 < 0.0) == (side_2 < 0.0) == (side_3 < 0.0)
###############################################################################
class TestPointInTriangle(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 import Polygon
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")
Производим следующую графику:
Так как нет ответа JS,
По часовой стрелке и против часовой стрелки решение:
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
}
РЕДАКТИРОВАТЬ: была опечатка для вычисления det (cy - ay вместо cx - ax), это исправлено.
https://jsfiddle.net/jniac/rctb3gfL/ 
Я использую здесь тот же метод, что и описанный выше: точка находится внутри ABC, если он находится соответственно на "той же" стороне каждой линии AB, BC, CA. 
Вот эффективная реализация Python:
def PointInsideTriangle2(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: return False
else: 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))
и пример вывода:
То, что я делаю, это пересчитать три норма лица,
в 3D - перекрестным произведением бокового вектора и нормального вектора лица.
в 2D, просто меняя компоненты и отрицая один,
тогда внутри / снаружи для любой одной стороны происходит, когда точечное произведение боковой нормали и вектора вершины в точку меняет знак. Повторите для других двух (или более) сторон.
Выгоды:
многое рассчитывается так, что отлично подходит для тестирования нескольких точек в одном и том же треугольнике.
раннее отклонение общего случая больше внешних, чем внутренних точек. (также, если распределение точек взвешено в одну сторону, можно сначала проверить эту сторону.)
Если вы знаете координаты трех вершин и координаты конкретной точки, то вы можете получить площадь полного треугольника. Затем вычислите площадь трех сегментов треугольника (одна точка - заданная точка, а две другие - любые две вершины треугольника). Таким образом, вы получите площадь трех треугольных сегментов. Если сумма этих областей равна общей площади (которую вы получили ранее), то точка должна быть внутри треугольника. В противном случае точка не находится внутри треугольника. Это должно работать. Если есть какие-либо вопросы, дайте мне знать. Спасибо.
Это простейшая концепция, чтобы определить, находится ли точка внутри или снаружи треугольника или на плече треугольника. Определение точки внутри триллера по определителям
Самый простой рабочий код: `
#-*- 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 == 0 or M2 == 0 or M3 ==0):
print("Point: ",point," lies on the arms of Triangle")
elif((M1 > 0 and M2 > 0 and M3 > 0)or(M1 < 0 and M2 < 0 and M3 < 0)):
#if products is non 0 check if all of their sign is same
print("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)
`
Если вы ищете скорость, вот процедура, которая может вам помочь.
Сортируйте вершины треугольника по их ординатам. Это займет в худшем случае три сравнения. Пусть 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'). При этом будет реализован быстрый ограничивающий прямоугольный тест, но вам также придется сортировать по абсциссам.
В конце концов вам нужно будет вычислить знак данной точки относительно двух сторон треугольника, которые разграничивают соответствующую плиту (верхнюю или нижнюю). Тест имеет вид:
((X - Xi) * (Y - Yj) > (X - Xi) * (Y - Yj)) == ((X - Xi) * (Y - Yk) > (X - Xi) * (Y - Yk))
Полное обсуждение 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, более быстрая, чем метод разработчика (по крайней мере для меня) и вдохновленная решением Седрика Дюфура:
def ptInTriang(p_test, p0, p1, p2):
dX = p_test[0] - p0[0]
dY = p_test[1] - p0[1]
dX20 = p2[0] - p0[0]
dY20 = p2[1] - p0[1]
dX10 = p1[0] - p0[0]
dY10 = p1[1] - p0[1]
s_p = (dY20*dX) - (dX20*dY)
t_p = (dX10*dY) - (dY10*dX)
D = (dX10*dY20) - (dY10*dX20)
if D > 0:
return ( (s_p >= 0) and (t_p >= 0) and (s_p + t_p) <= D )
else:
return ( (s_p <= 0) and (t_p <= 0) and (s_p + t_p) >= D )
Вы можете проверить это с:
X_size = 64
Y_size = 64
ax_x = np.arange(X_size).astype(np.float32)
ax_y = np.arange(Y_size).astype(np.float32)
coords=np.meshgrid(ax_x,ax_y)
points_unif = (coords[0].reshape(X_size*Y_size,),coords[1].reshape(X_size*Y_size,))
p_test = np.array([0 , 0])
p0 = np.array([22 , 8])
p1 = np.array([12 , 55])
p2 = np.array([7 , 19])
fig = plt.figure(dpi=300)
for i in range(0,X_size*Y_size):
p_test[0] = points_unif[0][i]
p_test[1] = points_unif[1][i]
if ptInTriang(p_test, p0, p1, p2):
plt.plot(p_test[0], p_test[1], '.g')
else:
plt.plot(p_test[0], p_test[1], '.r')
Построение занимает много времени, но эта сетка тестируется за 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
Я просто хочу использовать простую векторную математику, чтобы объяснить решение барицентрических координат, которое дал Андреас, это будет намного легче понять.
- Область 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-е) | v0v2 | / | v0v2 | = tp | v0v1 | / | v0v1 |
мы получаем 1 - s = tp, тогда 1 = s + tp. Если любое 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].
Честно говоря, это так же просто, как и ответ Саймона П. Стивена, однако при таком подходе у вас нет точного контроля, хотите ли вы, чтобы точки на краях треугольника были включены или нет.
Мой подход немного другой, но очень простой. Рассмотрим следующий треугольник;
Чтобы иметь точку в треугольнике, мы должны выполнить 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 slope
return Math.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 length
return Math.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));Существуют досадные граничные условия, когда точка находится точно на общем ребре двух соседних треугольников. Точка не может быть ни в обоих, ни в треугольниках. Вам нужен произвольный, но последовательный способ назначения точки. Например, нарисуйте горизонтальную линию через точку. Если линия пересекается с другой стороной треугольника справа, точка обрабатывается так, как если бы она находилась внутри треугольника. Если перекресток находится слева, точка находится снаружи.
Если линия, на которой лежит точка, является горизонтальной, используйте выше / ниже.
Если точка находится на общей вершине нескольких треугольников, используйте треугольник, центр которого точка образует наименьший угол.
Веселее: три точки могут быть на прямой (ноль градусов), например (0,0) - (0,10) - (0,5). В алгоритме триангуляции "ухо" (0,10) должно быть обрезано, а сгенерированный "треугольник" является вырожденным случаем прямой линии.
Предположительно высокопроизводительный код, который я адаптировал в JavaScript(статья ниже):
function pointInTriangle (p, p0, p1, p2) {
return (((p1.y - p0.y) * (p.x - p0.x) - (p1.x - p0.x) * (p.y - p0.y)) | ((p2.y - p1.y) * (p.x - p1.x) - (p2.x - p1.x) * (p.y - p1.y)) | ((p0.y - p2.y) * (p.x - p2.x) - (p0.x - p2.x) * (p.y - p2.y))) >= 0;
}
pointInTriangle (p, p0, p1, p2) - для треугольников против часовой стрелки
pointInTriangle (p, p0, p1, p2) - для треугольников по часовой стрелке
Посмотрите в jsFiddle (тест производительности включен), там также есть проверка обмоток в отдельной функции http://jsfiddle.net/z7x0udf7/3/
Вдохновленный этим: http://www.phatcode.net/articles.php?id=459
Самый простой способ, и он работает со всеми типами треугольников, это просто определить углы точек 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
Мне нужно было проверить треугольник в "контролируемой среде", когда вы абсолютно уверены, что треугольники будут по часовой стрелке. Итак, я взял jsfiddle Перро Азула и изменил его, как предложено coproc для таких случаев; также удалены избыточные 0,5 и 2 умножения, потому что они просто отменяют друг друга.
http://jsfiddle.net/dog_funtom/H7D7g/
Вот эквивалентный код C# для Unity:
public static bool IsPointInClockwiseTriangle(Vector2 p, Vector2 p0, Vector2 p1, Vector2 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)
return false;
var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
return (s + t) < A;
}
bool isInside( float x, float y, float x1, float y1, float x2, float y2, float x3, float y3 ) {
float l1 = (x-x1)*(y3-y1) - (x3-x1)*(y-y1),
l2 = (x-x2)*(y1-y2) - (x1-x2)*(y-y2),
l3 = (x-x3)*(y2-y3) - (x2-x3)*(y-y3);
return (l1>0 && l2>0 && l3>0) || (l1<0 && l2<0 && l3<0);
}
Это не может быть более эффективным, чем это! Каждая сторона треугольника может иметь независимое положение и ориентацию, следовательно, три вычисления: l1, l2 и l3, безусловно, необходимы, включая 2 умножения каждый. Как только l1, l2 и l3 станут известны, результатом будет лишь несколько базовых сравнений и логических операций.
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) return true;//is inside
else return false;//is outside
return 0;
}
почти идеальные декартовы координаты, преобразованные из барицентрических, экспортируются в двойные значения *v (x) и *w (y). Оба экспортных двойника должны иметь символ * в каждом случае, вероятно: *v и * w Код можно использовать и для другого треугольника четырехугольника. Настоящим подписанный записал только треугольник abc из четырехугольника abcd по часовой стрелке.
A---B
|..\\.o|
|....\\.|
D---C
точка o находится внутри треугольника ABC для тестирования со вторым треугольником, вызывая эту функцию в направлении CDA, и результаты должны быть правильными после *v=1-*v; а также *w=1-*w; для четырехугольника
one of the easiest ways to check if the area formed by the vertices of triangle
(x1,y1),(x2,y2),(x3,y3) is postive or not .
area can by calculated by the formula.
1/ 2 [x1(y2–y3) + x2 (y3–y1) + x3 (y1–y2)]
or python code can be written as:-
def triangleornot(p1,p2,p3):
return (1/ 2) [p1[0](p2[1]–p3[1]) + p2[0] (p3[1]–p1[1]) + p3[0] (p1[0]–p2[0])]