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

Question

Есть ли простой способ определить, находится ли точка внутри треугольника? Это 2D, а не 3D.

Answer 1

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

Answer 2

Другие функции в 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

Answer 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'). При этом будет реализован быстрый ограничивающий прямоугольный тест, но вам также придется сортировать по абсциссам.

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

((X - Xi) * (Y - Yj) > (X - Xi) * (Y - Yj)) == ((X - Xi) * (Y - Yk) > (X - Xi) * (Y - Yk))

Полное обсуждение комбинаций i, j, k (их шесть на основе результатов такого рода) выходит за рамки этого ответа и «оставлено читателю как упражнение»; для эффективности они должны быть жестко закодированы.

Если вы считаете, что это решение сложное, обратите внимание, что оно в основном включает в себя простые сравнения (некоторые из которых могут быть предварительно вычислены), плюс 6 вычитаний и 4 умножения в случае неудачи теста ограничивающего прямоугольника. Последнюю стоимость трудно превзойти, поскольку в худшем случае вы не можете избежать сравнения контрольной точки с двумя сторонами (ни один метод в других ответах не имеет более низкой стоимости, некоторые ухудшают ее, например, 15 вычитаний и 6 умножений, иногда делений). 1017 *

UPDATE: Быстрее с преобразованием сдвига

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

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

Затем рассмотрим преобразование "сдвиг", определяемое как X'= X - m Y, Y' = Y, где m - наклон DX/DY для самого высокого края. Это преобразование сделает эту сторону треугольника вертикальной. И поскольку вы знаете, на какой стороне средней горизонтали вы находитесь, достаточно проверить знак относительно одной стороны треугольника.

Предполагая, что вы предварительно вычислили наклон m, а также X' для вершин срезаемого треугольника и коэффициенты уравнений сторон как X = m Y + p, вам понадобится в худшем случае

• сравнение двух ординат для вертикальной классификации;
• опционально одно или два сравнения абсцисс для отклонения ограничительной рамки;
• вычисление X' = X - m Y;
• одно или два сравнения с абсциссами срезанного треугольника;
• один знак теста X >< m' Y + p' против соответствующей стороны срезанного треугольника.

Answer 4

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

Если линия, на которой лежит точка, является горизонтальной, используйте выше / ниже.

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

Веселее: три точки могут быть на прямой (ноль градусов), например (0,0) - (0,10) - (0,5). В алгоритме триангуляции «ухо» (0,10) должно быть отрезано, а сгенерированный «треугольник» является вырожденным случаем прямой линии.

Answer 5

Я просто хочу использовать простую векторную математику, чтобы объяснить решение барицентрических координат, которое дал Андреас, это будет гораздо легче понять.

1. Область A определяется как любой вектор, заданный s * v02 + t * v01, с условием s> = 0 и t> = 0. Если любая точка внутри треугольника v0, v1, v2, она должна находиться внутри области A .

2. Если дополнительно ограничить s, и t принадлежит [0, 1]. Мы получаем область B, которая содержит все векторы s * v02 + t * v01, с условием s, t принадлежит [0, 1]. Стоит отметить, что нижняя часть Зоны B является зеркалом Треугольника v0, v1, v2. Проблема возникает, если мы можем дать определенное условие s и t для дальнейшего исключения нижней части области B.

3. Предположим, мы даем значение 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].

Answer 6

Вот решение на 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")

Создание следующего рисунка:

Answer 7

        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])]

Answer 8

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

Самый простой рабочий код: `

#-*- 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)

`

Answer 9

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 direction, и результаты должны быть правильными после *v=1-*v; и *w=1-*w; для четырехугольника

Answer 10

Поскольку ответа 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.