有没有一种简单的方法来确定一个点是否在三角形内?是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.
其他回答
由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,而不管缠绕方向如何。
我在最后一次尝试谷歌和找到这个页面之前写了这段代码,所以我想我应该分享它。它基本上是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的同一侧(左或右)的点。然而,上面的方法似乎更适合进行一些优化。
我需要在“可控环境”中检查三角形中的点,当你绝对确定三角形是顺时针的时候。所以我拿了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;
}
求解如下方程组:
p = p0 + (p1 - p0) * s + (p2 - p0) * t
当0 <= s <= 1和0 <= t <= 1以及s + t <= 1时,点p在三角形内。
S,t和1 - S - t称为点p的重心坐标。
最简单的方法,适用于所有类型的三角形,就是确定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