有没有一种简单的方法来确定一个点是否在三角形内?是2D的,不是3D的。
当前回答
求解如下方程组:
p = p0 + (p1 - p0) * s + (p2 - p0) * t
当0 <= s <= 1和0 <= t <= 1以及s + t <= 1时,点p在三角形内。
S,t和1 - S - t称为点p的重心坐标。
其他回答
一个简单的方法是:
找出连接 分别指向三角形的三个点 顶点和夹角之和 这些向量。如果它们的和 角度是2*那么点是 在三角形里面。
两个解释替代方案的好网站是:
黑卒和沃尔夫勒姆
其中一个最简单的方法来检查是否由三角形的顶点组成的面积 (x1,y1) (x2,y2) (x3,y3)是否为正。
面积可由公式计算:
1/2 [x1(y2–y3) + x2(y3–y1) + x3(y1–y2)]
或者python代码可以写成:
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])]
我只是想用一些简单的向量数学来解释安德里亚斯给出的重心坐标解,它会更容易理解。
区域A定义为s * v02 + t * v01给出的任意向量,条件s >= 0, t >= 0。如果三角形v0 v1 v2内的任意一点,它一定在区域A内。
如果进一步限制s, t属于[0,1]。得到包含s * v02 + t * v01的所有向量的区域B,条件s, t属于[0,1]。值得注意的是,区域B的下部是三角形v0, v1, v2的镜像。问题来了,我们是否可以给定一定的s和t条件,来进一步排除区域B的低部分。
假设我们给出一个值s, t在[0,1]内变化。在下图中,点p位于v1v2的边缘。s * v02 + t * v01的所有向量沿着虚线通过简单向量和得到。在v1v2和虚线交点p处,我们有:
(1-S)|V0v2|/ |v0v2|= tp|v0v1|/ |v0v1|
得到1 - s = tp,然后1 = s + tp。如果任意t > tp,即1 < s + t where在双虚线上,则该向量在三角形外,任意t <= tp,即1 >= s + t where在单虚线上,则该向量在三角形内。
如果我们给出[0,1]中的任意s,对应的t必须满足1 >= s + t,对于三角形内的向量。
最后我们得到v = s * v02 +t * v01, v在三角形内,条件s, t, s+t属于[0,1]。然后翻译到点,我们有
P - p0 = s * (p1 - p0) + t * (p2 - p0), and s, t, s + t in [0,1]
和Andreas解方程组的解是一样的 P = p0 + s * (p1 - p0) + t * (p2 - p0),带s, t, s + t属于[0,1]。
通过使用重心坐标的解析解(由Andreas Brinck指出)和:
不是把乘法分布在括号里的项上 通过存储相同的项来避免多次计算 还原比较(如coproc和Thomas Eding所指出的)
可以最小化“昂贵”操作的数量:
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中,或者通过点击下面的“运行代码片段”来尝试
var ctx = $("canvas")[0].getContext("2d"); var W = 500; var H = 500; var point = { x: W / 2, y: H / 2 }; var triangle = randomTriangle(); $("canvas").click(function(evt) { point.x = evt.pageX - $(this).offset().left; point.y = evt.pageY - $(this).offset().top; test(); }); $("canvas").dblclick(function(evt) { triangle = randomTriangle(); test(); }); test(); function test() { var result = ptInTriangle(point, triangle.a, triangle.b, triangle.c); var info = "point = (" + point.x + "," + point.y + ")\n"; info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n"; info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n"; info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n"; info += "result = " + (result ? "true" : "false"); $("#result").text(info); render(); } function ptInTriangle(p, p0, p1, p2) { var A = 1/2 * (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y); var sign = A < 0 ? -1 : 1; var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y) * sign; var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y) * sign; return s > 0 && t > 0 && (s + t) < 2 * A * sign; } function render() { ctx.fillStyle = "#CCC"; ctx.fillRect(0, 0, 500, 500); drawTriangle(triangle.a, triangle.b, triangle.c); drawPoint(point); } function drawTriangle(p0, p1, p2) { ctx.fillStyle = "#999"; ctx.beginPath(); ctx.moveTo(p0.x, p0.y); ctx.lineTo(p1.x, p1.y); ctx.lineTo(p2.x, p2.y); ctx.closePath(); ctx.fill(); ctx.fillStyle = "#000"; ctx.font = "12px monospace"; ctx.fillText("1", p0.x, p0.y); ctx.fillText("2", p1.x, p1.y); ctx.fillText("3", p2.x, p2.y); } function drawPoint(p) { ctx.fillStyle = "#F00"; ctx.beginPath(); ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI); ctx.fill(); } function rand(min, max) { return Math.floor(Math.random() * (max - min + 1)) + min; } function randomTriangle() { return { a: { x: rand(0, W), y: rand(0, H) }, b: { x: rand(0, W), y: rand(0, H) }, c: { x: rand(0, W), y: rand(0, H) } }; } <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script> <pre>Click: place the point. Double click: random triangle.</pre> <pre id="result"></pre> <canvas width="500" height="500"></canvas>
导致:
变量“召回”:30 可变存储:7 补充:4 减法:8 乘法:6 部门:没有 比较:4
这与Kornel Kisielewicz解决方案(25次召回,1次存储,15次减法,6次乘法,5次比较)相比非常好,如果需要顺时针/逆时针检测(它本身需要6次召回,1次加法,2次减法,2次乘法和1次比较,使用解析解行列式,如rhgb所指出的),可能会更好。
这是确定一个点是在三角形的内、外还是在三角形的臂上的最简单的概念。
用行列式确定三角形内的点:
最简单的工作代码:
#-*- 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)