有没有一种简单的方法来确定一个点是否在三角形内?是2D的，不是3D的。
当前回答
其中一个最简单的方法来检查是否由三角形的顶点组成的面积 (x1,y1) (x2,y2) (x3,y3)是否为正。
面积可由公式计算:
1/2 [x1（y2–y3） + x2（y3–y1） + x3（y1–y2）]
或者python代码可以写成:
def triangleornot(p1,p2,p3):
return (1/ 2) [p1[0](p2[1]–p3[1]) + p2[0] (p3[1]–p1[1]) + p3[0] (p1[0]–p2[0])]
其他回答
一般来说，最简单(也是最优)的算法是检查由边创建的半平面的哪一边是点。
以下是关于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);
}
一个简单的方法是:
找出连接 分别指向三角形的三个点 顶点和夹角之和 这些向量。如果它们的和 角度是2*那么点是 在三角形里面。
两个解释替代方案的好网站是:
黑卒和沃尔夫勒姆
重心法Java版:
class Triangle {
Triangle(double x1, double y1, double x2, double y2, double x3,
double y3) {
this.x3 = x3;
this.y3 = y3;
y23 = y2 - y3;
x32 = x3 - x2;
y31 = y3 - y1;
x13 = x1 - x3;
det = y23 * x13 - x32 * y31;
minD = Math.min(det, 0);
maxD = Math.max(det, 0);
}
boolean contains(double x, double y) {
double dx = x - x3;
double dy = y - y3;
double a = y23 * dx + x32 * dy;
if (a < minD || a > maxD)
return false;
double b = y31 * dx + x13 * dy;
if (b < minD || b > maxD)
return false;
double c = det - a - b;
if (c < minD || c > maxD)
return false;
return true;
}
private final double x3, y3;
private final double y23, x32, y31, x13;
private final double det, minD, maxD;
}
上面的代码可以准确地处理整数，假设没有溢出。它也适用于顺时针和逆时针三角形。它不适用于共线三角形(但您可以通过测试det==0来检查)。
如果你要用同一个三角形测试不同的点，以重心为中心的版本是最快的。
重心版本在3个三角形点上是不对称的，所以它可能不如Kornel Kisielewicz的边缘半平面版本一致，因为浮点舍入误差。
图片来源:我根据维基百科关于重心坐标的文章制作了上面的代码。
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是已知的，结果只是一些基本的比较和布尔运算。
因为没有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内。
