有没有一种简单的方法来确定一个点是否在三角形内?是2D的，不是3D的。
当前回答
重心法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来检查)。
如果你要用同一个三角形测试不同的点，以重心为中心的版本是最快的。
重心版本在3个三角形点上是不对称的，所以它可能不如Kornel Kisielewicz的边缘半平面版本一致，因为浮点舍入误差。
图片来源:我根据维基百科关于重心坐标的文章制作了上面的代码。
其他回答
这是确定一个点是在三角形的内、外还是在三角形的臂上的最简单的概念。
用行列式确定三角形内的点:
最简单的工作代码:
#-*- 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)
重心法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来检查)。
如果你要用同一个三角形测试不同的点，以重心为中心的版本是最快的。
重心版本在3个三角形点上是不对称的，所以它可能不如Kornel Kisielewicz的边缘半平面版本一致，因为浮点舍入误差。
图片来源:我根据维基百科关于重心坐标的文章制作了上面的代码。
我同意Andreas Brinck的观点，重心坐标对于这项任务来说非常方便。注意，不需要每次都求解一个方程组:只需计算解析解。使用Andreas的符号，解是:
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);
只计算st和1-s-t。点p在三角形内当且仅当它们都是正的。
编辑:请注意，上面的区域表达式假设三角形节点编号是逆时针方向的。如果编号是顺时针的，这个表达式将返回一个负的面积(但大小正确)。然而，测试本身(s>0 && t>0 && 1-s-t>0)并不依赖于编号的方向，因为如果三角形节点的方向改变，上面乘以1/(2*Area)的表达式也会改变符号。
编辑2:为了获得更好的计算效率，请参阅下面的coproc注释(其中指出，如果三角形节点的方向(顺时针或逆时针)事先已知，则可以避免在s和t的表达式中除以2*Area)。在Andreas Brinck的回答下面的评论中也可以看到Perro Azul的jsfiddle-code。
下面是一个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")
制作以下图表:
如果你正在寻找速度，这里有一个方法可能会帮助你。
对三角形顶点的纵坐标进行排序。这最多需要三次比较。设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'对剪切三角形的相关边。
