如何确定一个点是否在二维三角形中?

这是确定一个点是在三角形的内、外还是在三角形的臂上的最简单的概念。

用行列式确定三角形内的点:

最简单的工作代码:

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

2018-08-08 14:10:14

如果你正在寻找速度，这里有一个方法可能会帮助你。

对三角形顶点的纵坐标进行排序。这最多需要三次比较。设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'或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'对剪切三角形的相关边。

2014-02-02 11:27:31

我需要在“可控环境”中检查三角形中的点，当你绝对确定三角形是顺时针的时候。所以我拿了Perro Azul的jsfiddle，按照coproc的建议进行了修改。还去掉了多余的0.5和2乘法因为它们互相抵消了。

http://jsfiddle.net/dog_funtom/H7D7g/

以下是Unity的等效c#代码:

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;
}

2014-04-20 18:36:43

python中的其他函数，比Developer的方法更快(至少对我来说)，并受到Cédric Dufour解决方案的启发:

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

2017-09-25 16:13:20

我在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://www.phatcode.net/articles.php?id=459

2016-05-13 23:34:09

最简单的方法，适用于所有类型的三角形，就是确定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

2016-08-18 18:21:56

如何确定一个点是否在二维三角形中?

推荐文章

最新文章

标签