有没有一种简单的方法来确定一个点是否在三角形内?是2D的,不是3D的。
当前回答
因为没有JS的答案, 顺时针和逆时针解决方案:
function triangleContains(ax, ay, bx, by, cx, cy, x, y) {
let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
return det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) >= 0 &&
det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) >= 0 &&
det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) >= 0
}
编辑:修正了两个拼写错误(关于符号和比较)。
https://jsfiddle.net/jniac/rctb3gfL/
function triangleContains(ax, ay, bx, by, cx, cy, x, y) { let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax) return det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) > 0 && det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) > 0 && det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) > 0 } let width = 500, height = 500 // clockwise let triangle1 = { A : { x: 10, y: -10 }, C : { x: 20, y: 100 }, B : { x: -90, y: 10 }, color: '#f00', } // counter clockwise let triangle2 = { A : { x: 20, y: -60 }, B : { x: 90, y: 20 }, C : { x: 20, y: 60 }, color: '#00f', } let scale = 2 let mouse = { x: 0, y: 0 } // DRAW > let wrapper = document.querySelector('div.wrapper') wrapper.onmousemove = ({ layerX:x, layerY:y }) => { x -= width / 2 y -= height / 2 x /= scale y /= scale mouse.x = x mouse.y = y drawInteractive() } function drawArrow(ctx, A, B) { let v = normalize(sub(B, A), 3) let I = center(A, B) let p p = add(I, rotate(v, 90), v) ctx.moveTo(p.x, p.y) ctx.lineTo(I.x, I .y) p = add(I, rotate(v, -90), v) ctx.lineTo(p.x, p.y) } function drawTriangle(ctx, { A, B, C, color }) { ctx.beginPath() ctx.moveTo(A.x, A.y) ctx.lineTo(B.x, B.y) ctx.lineTo(C.x, C.y) ctx.closePath() ctx.fillStyle = color + '6' ctx.strokeStyle = color ctx.fill() drawArrow(ctx, A, B) drawArrow(ctx, B, C) drawArrow(ctx, C, A) ctx.stroke() } function contains({ A, B, C }, P) { return triangleContains(A.x, A.y, B.x, B.y, C.x, C.y, P.x, P.y) } function resetCanvas(canvas) { canvas.width = width canvas.height = height let ctx = canvas.getContext('2d') ctx.resetTransform() ctx.clearRect(0, 0, width, height) ctx.setTransform(scale, 0, 0, scale, width/2, height/2) } function drawDots() { let canvas = document.querySelector('canvas#dots') let ctx = canvas.getContext('2d') resetCanvas(canvas) let count = 1000 for (let i = 0; i < count; i++) { let x = width * (Math.random() - .5) let y = width * (Math.random() - .5) ctx.beginPath() ctx.ellipse(x, y, 1, 1, 0, 0, 2 * Math.PI) if (contains(triangle1, { x, y })) { ctx.fillStyle = '#f00' } else if (contains(triangle2, { x, y })) { ctx.fillStyle = '#00f' } else { ctx.fillStyle = '#0003' } ctx.fill() } } function drawInteractive() { let canvas = document.querySelector('canvas#interactive') let ctx = canvas.getContext('2d') resetCanvas(canvas) ctx.beginPath() ctx.moveTo(0, -height/2) ctx.lineTo(0, height/2) ctx.moveTo(-width/2, 0) ctx.lineTo(width/2, 0) ctx.strokeStyle = '#0003' ctx.stroke() drawTriangle(ctx, triangle1) drawTriangle(ctx, triangle2) ctx.beginPath() ctx.ellipse(mouse.x, mouse.y, 4, 4, 0, 0, 2 * Math.PI) if (contains(triangle1, mouse)) { ctx.fillStyle = triangle1.color + 'a' ctx.fill() } else if (contains(triangle2, mouse)) { ctx.fillStyle = triangle2.color + 'a' ctx.fill() } else { ctx.strokeStyle = 'black' ctx.stroke() } } drawDots() drawInteractive() // trigo function add(...points) { let x = 0, y = 0 for (let point of points) { x += point.x y += point.y } return { x, y } } function center(...points) { let x = 0, y = 0 for (let point of points) { x += point.x y += point.y } x /= points.length y /= points.length return { x, y } } function sub(A, B) { let x = A.x - B.x let y = A.y - B.y return { x, y } } function normalize({ x, y }, length = 10) { let r = length / Math.sqrt(x * x + y * y) x *= r y *= r return { x, y } } function rotate({ x, y }, angle = 90) { let length = Math.sqrt(x * x + y * y) angle *= Math.PI / 180 angle += Math.atan2(y, x) x = length * Math.cos(angle) y = length * Math.sin(angle) return { x, y } } * { margin: 0; } html { font-family: monospace; } body { padding: 32px; } span.red { color: #f00; } span.blue { color: #00f; } canvas { position: absolute; border: solid 1px #ddd; } <p><span class="red">red triangle</span> is clockwise</p> <p><span class="blue">blue triangle</span> is couter clockwise</p> <br> <div class="wrapper"> <canvas id="dots"></canvas> <canvas id="interactive"></canvas> </div>
我在这里使用与上面描述的相同的方法:如果一个点分别位于AB, BC, CA的“同”边,则它在ABC内。
其他回答
一般来说,最简单(也是最优)的算法是检查由边创建的半平面的哪一边是点。
以下是关于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);
}
我要做的是预先计算三个面法线,
在三维中通过边向量和面法向量的叉乘得到。 通过简单地交换分量和负一个,
对于任意一条边的内/外都是边法线和点到点向量的点积,改变符号。重复其他两(或更多)面。
好处:
在同一个三角形上进行多点测试,很多都是预先计算好的。 早期拒签的常见情况是外分多内分。(如果点分布偏向一侧,可以先测试这一侧。)
求解如下方程组:
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*那么点是 在三角形里面。
两个解释替代方案的好网站是:
黑卒和沃尔夫勒姆
老实说,这就像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));