有没有一种简单的方法来确定一个点是否在三角形内?是2D的,不是3D的。


当前回答

这是确定一个点是在三角形的内、外还是在三角形的臂上的最简单的概念。

用行列式确定三角形内的点:

最简单的工作代码:

#-*- coding: utf-8 -*-

import numpy as np

tri_points = [(1,1),(2,3),(3,1)]

def pisinTri(point,tri_points):
    Dx , Dy = point

    A,B,C = tri_points
    Ax, Ay = A
    Bx, By = B
    Cx, Cy = C

    M1 = np.array([ [Dx - Bx, Dy - By, 0],
                    [Ax - Bx, Ay - By, 0],
                    [1      , 1      , 1]
                  ])

    M2 = np.array([ [Dx - Ax, Dy - Ay, 0],
                    [Cx - Ax, Cy - Ay, 0],
                    [1      , 1      , 1]
                  ])

    M3 = np.array([ [Dx - Cx, Dy - Cy, 0],
                    [Bx - Cx, By - Cy, 0],
                    [1      , 1      , 1]
                  ])

    M1 = np.linalg.det(M1)
    M2 = np.linalg.det(M2)
    M3 = np.linalg.det(M3)
    print(M1,M2,M3)

    if(M1 == 0 or M2 == 0 or M3 ==0):
            print("Point: ",point," lies on the arms of Triangle")
    elif((M1 > 0 and M2 > 0 and M3 > 0)or(M1 < 0 and M2 < 0 and M3 < 0)):
            #if products is non 0 check if all of their sign is same
            print("Point: ",point," lies inside the Triangle")
    else:
            print("Point: ",point," lies outside the Triangle")

print("Vertices of Triangle: ",tri_points)
points = [(0,0),(1,1),(2,3),(3,1),(2,2),(4,4),(1,0),(0,4)]
for c in points:
    pisinTri(c,tri_points)

其他回答

我在JavaScript中改编的高性能代码(文章如下):

function pointInTriangle (p, p0, p1, p2) {
  return (((p1.y - p0.y) * (p.x - p0.x) - (p1.x - p0.x) * (p.y - p0.y)) | ((p2.y - p1.y) * (p.x - p1.x) - (p2.x - p1.x) * (p.y - p1.y)) | ((p0.y - p2.y) * (p.x - p2.x) - (p0.x - p2.x) * (p.y - p2.y))) >= 0;
}

pointInTriangle(p, p0, p1, p2) -用于逆时针方向的三角形 pointInTriangle(p, p0, p1, p2) -用于顺时针三角形

在jsFiddle(包括性能测试)中,在一个单独的函数中也有缠绕检查。或按下面的“运行代码片段”

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(); }); document.querySelector('#performance').addEventListener('click', _testPerformance); test(); function test() { var result = checkClockwise(triangle.a, triangle.b, triangle.c) ? pointInTriangle(point, triangle.a, triangle.c, triangle.b) : pointInTriangle(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 _testPerformance () { var px = [], py = [], p0x = [], p0y = [], p1x = [], p1y = [], p2x = [], p2y = [], p = [], p0 = [], p1 = [], p2 = []; for(var i = 0; i < 1000000; i++) { p[i] = {x: Math.random() * 100, y: Math.random() * 100}; p0[i] = {x: Math.random() * 100, y: Math.random() * 100}; p1[i] = {x: Math.random() * 100, y: Math.random() * 100}; p2[i] = {x: Math.random() * 100, y: Math.random() * 100}; } console.time('optimal: pointInTriangle'); for(var i = 0; i < 1000000; i++) { pointInTriangle(p[i], p0[i], p1[i], p2[i]); } console.timeEnd('optimal: pointInTriangle'); console.time('original: ptInTriangle'); for(var i = 0; i < 1000000; i++) { ptInTriangle(p[i], p0[i], p1[i], p2[i]); } console.timeEnd('original: ptInTriangle'); } function pointInTriangle (p, p0, p1, p2) { return (((p1.y - p0.y) * (p.x - p0.x) - (p1.x - p0.x) * (p.y - p0.y)) | ((p2.y - p1.y) * (p.x - p1.x) - (p2.x - p1.x) * (p.y - p1.y)) | ((p0.y - p2.y) * (p.x - p2.x) - (p0.x - p2.x) * (p.y - p2.y))) >= 0; } 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 render() { ctx.fillStyle = "#CCC"; ctx.fillRect(0, 0, 500, 500); drawTriangle(triangle.a, triangle.b, triangle.c); drawPoint(point); } 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 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() { return { 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) } }; } <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script> <button id="performance">Run performance test (open console)</button> <pre>Click: place the point. Double click: random triangle.</pre> <pre id="result"></pre> <canvas width="500" height="500"></canvas>

受此启发: http://www.phatcode.net/articles.php?id=459

一般来说,最简单(也是最优)的算法是检查由边创建的半平面的哪一边是点。

以下是关于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);
}

因为没有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是已知的,结果只是一些基本的比较和布尔运算。

我需要在“可控环境”中检查三角形中的点,当你绝对确定三角形是顺时针的时候。所以我拿了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;
}