有没有一种简单的方法来确定一个点是否在三角形内?是2D的,不是3D的。
当前回答
If you know the co-ordinates of the three vertices and the co-ordinates of the specific point, then you can get the area of the complete triangle. Afterwards, calculate the area of the three triangle segments (one point being the point given and the other two being any two vertices of the triangle). Thus, you will get the area of the three triangle segments. If the sum of these areas are equal to the total area (that you got previously), then, the point should be inside the triangle. Otherwise, the point is not inside the triangle. This should work. If there are any issues, let me know. Thank you.
其他回答
下面是一个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")
制作以下图表:
一般来说,最简单(也是最优)的算法是检查由边创建的半平面的哪一边是点。
以下是关于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);
}
一个简单的方法是:
找出连接 分别指向三角形的三个点 顶点和夹角之和 这些向量。如果它们的和 角度是2*那么点是 在三角形里面。
两个解释替代方案的好网站是:
黑卒和沃尔夫勒姆
重心法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的边缘半平面版本一致,因为浮点舍入误差。
图片来源:我根据维基百科关于重心坐标的文章制作了上面的代码。
最简单的方法,适用于所有类型的三角形,就是确定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