有没有一种简单的方法来确定一个点是否在三角形内?是2D的,不是3D的。
当前回答
有一些恼人的边条件,即一个点恰好在两个相邻三角形的公共边上。这个点不可能在两个三角形中,也不可能不在两个三角形中。你需要一种任意但一致的方式来分配点。例如,画一条横线穿过这个点。如果这条直线与三角形的另一边在右侧相交,则该点被视为在三角形内。如果交点在左边,则该点在外面。
如果该点所在的直线是水平的,则使用above/below。
如果该点位于多个三角形的公共顶点上,则使用该点与中心点形成的角最小的三角形。
更有趣的是:三个点可以在一条直线上(零度),例如(0,0)-(0,10)-(0,5)。在三角剖分算法中,“耳朵”(0,10)必须被切掉,生成的“三角形”是直线的退化情况。
其他回答
求解如下方程组:
p = p0 + (p1 - p0) * s + (p2 - p0) * t
当0 <= s <= 1和0 <= t <= 1以及s + t <= 1时,点p在三角形内。
S,t和1 - S - t称为点p的重心坐标。
如果你正在寻找速度,这里有一个方法可能会帮助你。
对三角形顶点的纵坐标进行排序。这最多需要三次比较。设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'对剪切三角形的相关边。
我需要在“可控环境”中检查三角形中的点,当你绝对确定三角形是顺时针的时候。所以我拿了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点A点B点C点的角。如果任何一个角大于180.0度,那么它在外面,如果是180.0度,那么它在圆周上,如果acos欺骗了你,小于180.0度,那么它在里面。看一看理解http://math-physics-psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html
有一些恼人的边条件,即一个点恰好在两个相邻三角形的公共边上。这个点不可能在两个三角形中,也不可能不在两个三角形中。你需要一种任意但一致的方式来分配点。例如,画一条横线穿过这个点。如果这条直线与三角形的另一边在右侧相交,则该点被视为在三角形内。如果交点在左边,则该点在外面。
如果该点所在的直线是水平的,则使用above/below。
如果该点位于多个三角形的公共顶点上,则使用该点与中心点形成的角最小的三角形。
更有趣的是:三个点可以在一条直线上(零度),例如(0,0)-(0,10)-(0,5)。在三角剖分算法中,“耳朵”(0,10)必须被切掉,生成的“三角形”是直线的退化情况。