有没有一种简单的方法来确定一个点是否在三角形内?是2D的,不是3D的。
当前回答
通过使用重心坐标的解析解(由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所指出的),可能会更好。
其他回答
一个简单的方法是:
找出连接 分别指向三角形的三个点 顶点和夹角之和 这些向量。如果它们的和 角度是2*那么点是 在三角形里面。
两个解释替代方案的好网站是:
黑卒和沃尔夫勒姆
我需要在“可控环境”中检查三角形中的点,当你绝对确定三角形是顺时针的时候。所以我拿了Perro Azul的jsfiddle,按照coproc的建议进行了修改。还去掉了多余的0.5和2乘法因为它们互相抵消了。
http://jsfiddle.net/dog_funtom/H7D7g/
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 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; } function checkClockwise(p0, p1, p2) { var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y); return A > 0; } 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() { while (true) { var result = { 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) } }; if (checkClockwise(result.a, result.b, result.c)) return result; } } <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>
以下是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;
}
老实说,这就像Simon P Steven的回答一样简单,但是用这种方法,你无法控制你是否想要包含三角形边缘上的点。
我的方法有点不同,但非常基本。考虑下面的三角形;
为了在三角形中有这个点我们必须满足三个条件
ACE角(绿色)应小于ACB角(红色) ECB角(蓝色)应小于ACB角(红色) 当点E和点C的x和y值应用于|AB|直线方程时,点E和点C的符号应该相同。
在此方法中,您可以完全控制单独包含或排除边缘上的点。所以你可以检查一个点是否在三角形中,例如,只包括|AC|边。
所以我的JavaScript解决方案是这样的;
function isInTriangle(t,p){ function isInBorder(a,b,c,p){ var m = (a.y - b.y) / (a.x - b.x); // calculate the slope return Math.sign(p.y - m*p.x + m*a.x - a.y) === Math.sign(c.y - m*c.x + m*a.x - a.y); } function findAngle(a,b,c){ // calculate the C angle from 3 points. var ca = Math.hypot(c.x-a.x, c.y-a.y), // ca edge length cb = Math.hypot(c.x-b.x, c.y-b.y), // cb edge length ab = Math.hypot(a.x-b.x, a.y-b.y); // ab edge length return Math.acos((ca*ca + cb*cb - ab*ab) / (2*ca*cb)); // return the C angle } var pas = t.slice(1) .map(tp => findAngle(p,tp,t[0])), // find the angle between (p,t[0]) with (t[1],t[0]) & (t[2],t[0]) ta = findAngle(t[1],t[2],t[0]); return pas[0] < ta && pas[1] < ta && isInBorder(t[1],t[2],t[0],p); } var triangle = [{x:3, y:4},{x:10, y:8},{x:6, y:10}], point1 = {x:3, y:9}, point2 = {x:7, y:9}; console.log(isInTriangle(triangle,point1)); console.log(isInTriangle(triangle,point2));
我在最后一次尝试谷歌和找到这个页面之前写了这段代码,所以我想我应该分享它。它基本上是Kisielewicz答案的优化版本。我也研究了重心法,但从维基百科的文章来看,我很难看出它是如何更有效的(我猜有一些更深层次的等价性)。不管怎样,这个算法的优点是不用除法;一个潜在的问题是边缘检测的行为取决于方向。
bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c)
{
int as_x = s.x - a.x;
int as_y = s.y - a.y;
bool s_ab = (b.x - a.x) * as_y - (b.y - a.y) * as_x > 0;
if ((c.x - a.x) * as_y - (c.y - a.y) * as_x > 0 == s_ab)
return false;
if ((c.x - b.x) * (s.y - b.y) - (c.y - b.y)*(s.x - b.x) > 0 != s_ab)
return false;
return true;
}
换句话说,思想是这样的:点s是在直线AB和直线AC的左边还是右边?如果是真的,它就不可能在里面。如果为假,则至少在“锥”内满足条件。现在,因为我们知道三角形(三角形)内的一个点必须与BC(以及CA)在AB的同一侧,我们检查它们是否不同。如果有,s就不可能在里面,否则s一定在里面。
计算中的一些关键字是线半平面和行列式(2x2叉乘)。也许一个更有教学意义的方法是将它看作是一个在AB、BC和CA的同一侧(左或右)的点。然而,上面的方法似乎更适合进行一些优化。
由andreasdr和Perro Azul发布的重心方法的c#版本。我添加了一个检查,当s和t有相反的符号(而且都不为零)时,放弃面积计算,因为潜在地避免三分之一的乘法成本似乎是合理的。
public static bool PointInTriangle(Point p, Point p0, Point p1, Point p2)
{
var s = (p0.X - p2.X) * (p.Y - p2.Y) - (p0.Y - p2.Y) * (p.X - p2.X);
var t = (p1.X - p0.X) * (p.Y - p0.Y) - (p1.Y - p0.Y) * (p.X - p0.X);
if ((s < 0) != (t < 0) && s != 0 && t != 0)
return false;
var d = (p2.X - p1.X) * (p.Y - p1.Y) - (p2.Y - p1.Y) * (p.X - p1.X);
return d == 0 || (d < 0) == (s + t <= 0);
}
2021年更新:这个版本正确处理任意一个缠绕方向(顺时针和逆时针)指定的三角形。请注意,对于恰好位于三角形边缘上的点,本页上的一些其他答案会给出不一致的结果,这取决于三角形三个点的排列顺序。这些点被认为是“在”三角形中,这段代码正确地返回true,而不管缠绕方向如何。