如何确定一个点是否在二维三角形中？

Question

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

Answer 1

通常,最简单(且非常优化)的算法是检查由点的边缘创建的半平面的哪一侧.

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

Answer 2

求解以下方程式:

p = p0 + (p1 - p0) * s + (p2 - p0) * t

p如果0 <= s <= 1和0 <= t <= 1,则该点位于三角形内部s + t <= 1.

s,t以及1 - s - t被称为重心坐标点的p.

Answer 3

我同意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);

只是评估s,t和1-s-t.p当且仅当它们都是正数时,该点在三角形内部.

编辑:请注意,该区域的上述表达式假定三角形节点编号是逆时针的.如果编号是顺时针方向,则此表达式将返回负区域(但具有正确的大小).然而,测试本身(s>0 && t>0 && 1-s-t>0)不依赖于编号的方向,因为1/(2*Area)如果三角形节点方向改变,则上面的表达式也乘以改变符号.

编辑2:对于一个更好的计算效率,参见coproc下面的注释(这使得如果三角形节点(顺时针或逆时针)的方向被预先已知的,除以点2*Area在表达式s和t可避免).在Andreas Brinck回答的评论中也可以看到Perro Azul的jsfiddle代码.

Answer 4

我在最后一次尝试谷歌并找到这个页面之前编写了这段代码,所以我想我会分享它.它基本上是Kisielewicz答案的优化版本.我也研究了Barycentric方法,但从维基百科的文章来看,我很难看到它是如何更有效的(我猜是有更深层次的等价).无论如何,这种算法的优点是不使用除法; 潜在的问题是边缘检测的行为取决于方向.

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;
}

用语言来说,这个想法是这样的:点AB和AC的左边或右边是点吗？如果是真的,它不能在里面.如果为假,则至少在符合条件的"锥体"内.既然我们知道三角形(三角形)内的一个点必须与BC的同一侧(以及CA),我们检查它们是否不同.如果他们这样做,s不可能在里面,否则s必须在里面.

计算中的一些关键字是线半平面和行列式(2x2交叉乘积).也许更为教学的方式可能是将其视为内部的一个点,如果它位于AB,BC和CA的每条线的同一侧(左侧或右侧).然而,上述方式似乎更适合某些优化.

Answer 5

由andreasdr和Perro Azul发布的C#版本的重心方法.需要注意的是面积计算可避免,如果s和t具有相反的信号.我通过非常彻底的单元测试验证了正确的行为.

public static bool PointInTriangle(Point p, Point p0, Point p1, Point 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 * (p2.X - p1.X) + p0.X * (p1.Y - p2.Y) + p1.X * p2.Y;

    return A < 0 ?
            (s <= 0 && s + t >= A) :
            (s >= 0 && s + t <= A);
}

_{[ 编辑 ]}
^{接受@Pierre的建议修改; 看评论}

Answer 6

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的边缘半平面版本一致.

图片来源:我从维基百科关于重心坐标的文章中做了上述代码.

Answer 7

这是 python 中的一个解决方案，该解决方案高效、有文档记录并且包含三个单元测试。它具有专业级的质量，可以按原样以模块的形式放入您的项目中。

import unittest

###############################################################################
def point_in_triangle(point, triangle):
    """Returns True if the point is inside the triangle
    and returns False if it falls outside.
    - The argument *point* is a tuple with two elements
    containing the X,Y coordinates respectively.
    - The argument *triangle* is a tuple with three elements each
    element consisting of a tuple of X,Y coordinates.

    It works like this:
    Walk clockwise or counterclockwise around the triangle
    and project the point onto the segment we are crossing
    by using the dot product.
    Finally, check that the vector created is on the same side
    for each of the triangle's segments.
    """
    # Unpack arguments
    x, y = point
    ax, ay = triangle[0]
    bx, by = triangle[1]
    cx, cy = triangle[2]
    # Segment A to B
    side_1 = (x - bx) * (ay - by) - (ax - bx) * (y - by)
    # Segment B to C
    side_2 = (x - cx) * (by - cy) - (bx - cx) * (y - cy)
    # Segment C to A
    side_3 = (x - ax) * (cy - ay) - (cx - ax) * (y - ay)
    # All the signs must be positive or all negative
    return (side_1 < 0.0) == (side_2 < 0.0) == (side_3 < 0.0)

###############################################################################
class TestPointInTriangle(unittest.TestCase):

    triangle = ((22 , 8),
                (12 , 55),
                (7 , 19))

    def test_inside(self):
        point = (15, 20)
        self.assertTrue(point_in_triangle(point, self.triangle))

    def test_outside(self):
        point = (1, 7)
        self.assertFalse(point_in_triangle(point, self.triangle))

    def test_border_case(self):
        """If the point is exactly on one of the triangle's edges,
        we consider it is inside."""
        point = (7, 19)
        self.assertTrue(point_in_triangle(point, self.triangle))

###############################################################################
if __name__ == "__main__":
    suite = unittest.defaultTestLoader.loadTestsFromTestCase(TestPointInTriangle)
    unittest.TextTestRunner().run(suite)

上述算法还有一个额外的可选图形测试来确认其有效性：

import random
from matplotlib import pyplot
from triangle_test import point_in_triangle

###############################################################################
# The area #
size_x = 64
size_y = 64

# The triangle #
triangle = ((22 , 8),
            (12 , 55),
            (7 , 19))

# Number of random points #
count_points = 10000

# Prepare the figure #
figure = pyplot.figure()
axes = figure.add_subplot(111, aspect='equal')
axes.set_title("Test the 'point_in_triangle' function")
axes.set_xlim(0, size_x)
axes.set_ylim(0, size_y)

# Plot the triangle #
from matplotlib.patches import Polygon
axes.add_patch(Polygon(triangle, linewidth=1, edgecolor='k', facecolor='none'))

# Plot the points #
for i in range(count_points):
    x = random.uniform(0, size_x)
    y = random.uniform(0, size_y)
    if point_in_triangle((x,y), triangle): pyplot.plot(x, y, '.g')
    else:                                  pyplot.plot(x, y, '.b')

# Save it #
figure.savefig("point_in_triangle.pdf")

生成以下图形：

Answer 8

一个简单的方法是:

找到将点连接到三角形的三个顶点中的每个顶点的向量,并对这些向量之间的角度求和.如果角度之和为2*pi,则该点在三角形内.

解释替代品的两个好网站是:

blackpawn和wolfram

Answer 9

由于没有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 内。

Answer 10

通过使用重心坐标的解析解(Andreas Brinck指出)和:

• 不在括号内分配乘法
• 通过存储它们来避免计算几次相同的术语
• 减少比较(正如coproc和Thomas Eding所指出的那样)

一个可以最小化"costy"操作的数量:

function ptInTriangle(p, p0, p1, p2) {
    var dX = p.x-p2.x;
    var dY = p.y-p2.y;
    var dX21 = p2.x-p1.x;
    var dY12 = p1.y-p2.y;
    var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y);
    var s = dY12*dX + dX21*dY;
    var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY;
    if (D<0) return s<=0 && t<=0 && s+t>=D;
    return s>=0 && t>=0 && s+t<=D;
}

(代码可以粘贴在Perro Azul jsfiddle中)

导致:

• 变量"召回":30
• 变量存储:7
• 补充:4
• 减法:8
• 乘法:6
• 分裂:没有
• 比较:4

这与Kornel Kisielewicz解决方案(25次召回,1次存储,15次减法,6次乘法,5次比较)相当,如果需要顺时针/逆时针检测,可能会更好(需要6次召回,1次添加,2次减法) ,如rhgb所指出的,使用解析解决方案决定因素,本身进行2次乘法和1次比较.

Answer 11

我做的是预先计算三个法线法线,

• 通过侧向量和面法向量的交叉乘积在3D中.

• 在2D中通过简单地交换组件和否定一个,

然后任何一方的内/外是当侧法线和点到点矢量的点积时,改变符号.重复其他两个(或更多)方面.

优点:

• 对于在同一个三角形上进行多点测试,预计算得很多.

• 早期拒绝常见案例比内部点更多.(如果点数分布加权到一边,可以先测试那边.)

Answer 12

这是一个高效的Python实现：

def PointInsideTriangle2(pt,tri):
    '''checks if point pt(2) is inside triangle tri(3x2). @Developer'''
    a = 1/(-tri[1,1]*tri[2,0]+tri[0,1]*(-tri[1,0]+tri[2,0])+ \
        tri[0,0]*(tri[1,1]-tri[2,1])+tri[1,0]*tri[2,1])
    s = a*(tri[2,0]*tri[0,1]-tri[0,0]*tri[2,1]+(tri[2,1]-tri[0,1])*pt[0]+ \
        (tri[0,0]-tri[2,0])*pt[1])
    if s<0: return False
    else: t = a*(tri[0,0]*tri[1,1]-tri[1,0]*tri[0,1]+(tri[0,1]-tri[1,1])*pt[0]+ \
              (tri[1,0]-tri[0,0])*pt[1])
    return ((t>0) and (1-s-t>0))

和一个示例输出：

Answer 13

如果你知道三个顶点的坐标和特定点的坐标，那么你就可以得到完整三角形的面积。然后，计算三个三角形线段的面积（一个点是给定的点，另外两个点是三角形的任意两个顶点）。这样，您就可以得到三个三角形线段的面积。如果这些面积的总和等于总面积（您之前得到的），那么该点应该在三角形内部。否则，该点不在三角形内。这应该有效。如果有任何问题，请告诉我。谢谢。