有没有一种简单的方法来确定一个点是否在三角形内?是2D的，不是3D的。
当前回答
我只是想用一些简单的向量数学来解释安德里亚斯给出的重心坐标解，它会更容易理解。
区域A定义为s * v02 + t * v01给出的任意向量，条件s >= 0, t >= 0。如果三角形v0 v1 v2内的任意一点，它一定在区域A内。
如果进一步限制s, t属于[0,1]。得到包含s * v02 + t * v01的所有向量的区域B，条件s, t属于[0,1]。值得注意的是，区域B的下部是三角形v0, v1, v2的镜像。问题来了，我们是否可以给定一定的s和t条件，来进一步排除区域B的低部分。
假设我们给出一个值s, t在[0,1]内变化。在下图中，点p位于v1v2的边缘。s * v02 + t * v01的所有向量沿着虚线通过简单向量和得到。在v1v2和虚线交点p处，我们有:
（1-S）|V0v2|/ |v0v2|= tp|v0v1|/ |v0v1|
得到1 - s = tp，然后1 = s + tp。如果任意t > tp，即1 < s + t where在双虚线上，则该向量在三角形外，任意t <= tp，即1 >= s + t where在单虚线上，则该向量在三角形内。
如果我们给出[0,1]中的任意s，对应的t必须满足1 >= s + t，对于三角形内的向量。
最后我们得到v = s * v02 +t * v01, v在三角形内，条件s, t, s+t属于[0,1]。然后翻译到点，我们有
P - p0 = s * (p1 - p0) + t * (p2 - p0)， and s, t, s + t in [0,1]
和Andreas解方程组的解是一样的 P = p0 + s * (p1 - p0) + t * (p2 - p0)，带s, t, s + t属于[0,1]。
其他回答
我在最后一次尝试谷歌和找到这个页面之前写了这段代码，所以我想我应该分享它。它基本上是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的同一侧(左或右)的点。然而，上面的方法似乎更适合进行一些优化。
求解如下方程组:
p = p0 + (p1 - p0) * s + (p2 - p0) * t
当0 <= s <= 1和0 <= t <= 1以及s + t <= 1时，点p在三角形内。
S,t和1 - S - t称为点p的重心坐标。
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.
我同意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内。
