有没有一种简单的方法来确定一个点是否在三角形内?是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内。
其他回答
bool isInside( float x, float y, float x1, float y1, float x2, float y2, float x3, float y3 ) {
float l1 = (x-x1)*(y3-y1) - (x3-x1)*(y-y1),
l2 = (x-x2)*(y1-y2) - (x1-x2)*(y-y2),
l3 = (x-x3)*(y2-y3) - (x2-x3)*(y-y3);
return (l1>0 && l2>0 && l3>0) || (l1<0 && l2<0 && l3<0);
}
没有比这更有效率的了!三角形的每边都可以有独立的位置和方向,因此需要进行l1、l2和l3三个计算,每个计算需要进行2次乘法。一旦l1, l2和l3是已知的,结果只是一些基本的比较和布尔运算。
一般来说,最简单(也是最优)的算法是检查由边创建的半平面的哪一边是点。
以下是关于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);
}
我在最后一次尝试谷歌和找到这个页面之前写了这段代码,所以我想我应该分享它。它基本上是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的同一侧(左或右)的点。然而,上面的方法似乎更适合进行一些优化。
我同意Andreas Brinck的观点,重心坐标对于这项任务来说非常方便。注意,不需要每次都求解一个方程组:只需计算解析解。使用Andreas的符号,解是:
s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);
其中Area是三角形的(带符号的)面积:
Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);
只计算st和1-s-t。点p在三角形内当且仅当它们都是正的。
编辑:请注意,上面的区域表达式假设三角形节点编号是逆时针方向的。如果编号是顺时针的,这个表达式将返回一个负的面积(但大小正确)。然而,测试本身(s>0 && t>0 && 1-s-t>0)并不依赖于编号的方向,因为如果三角形节点的方向改变,上面乘以1/(2*Area)的表达式也会改变符号。
编辑2:为了获得更好的计算效率,请参阅下面的coproc注释(其中指出,如果三角形节点的方向(顺时针或逆时针)事先已知,则可以避免在s和t的表达式中除以2*Area)。在Andreas Brinck的回答下面的评论中也可以看到Perro Azul的jsfiddle-code。
因为没有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内。