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


当前回答

bool point2Dtriangle(double e,double f, double a,double b,double c, double g,double h,double i, double v, double w){
    /* inputs: e=point.x, f=point.y
               a=triangle.Ax, b=triangle.Bx, c=triangle.Cx 
               g=triangle.Ay, h=triangle.By, i=triangle.Cy */
    v = 1 - (f * (b - c) + h * (c - e) + i * (e - b)) / (g * (b - c) + h * (c - a) + i * (a - b));
    w = (f * (a - b) + g * (b - e) + h * (e - a)) / (g * (b - c) + h * (c - a) + i * (a - b));
    if (*v > -0.0 && *v < 1.0000001 && *w > -0.0 && *w < *v) return true;//is inside
    else return false;//is outside
    return 0;
} 

从质心转换而来的几乎完美的笛卡尔坐标 在*v (x)和*w (y)双精度内导出。 在每种情况下,两个导出双精度对象前面都应该有一个*字符,可能是*v和*w 代码也可以用于四边形的另一个三角形。 特此签名只写三角形abc从顺时针abcd的四边形。

A---B
|..\\.o|  
|....\\.| 
D---C 

o点在ABC三角形内 对于带有第二个三角形的测试,将此函数称为CDA方向,*v=1-*v后的结果应正确;* w = 1 - * w;为了四合院

其他回答

由andreasdr和Perro Azul发布的重心方法的c#版本。我添加了一个检查,当s和t有相反的符号(而且都不为零)时,放弃面积计算,因为潜在地避免三分之一的乘法成本似乎是合理的。

public static bool PointInTriangle(Point p, Point p0, Point p1, Point p2)
{
    var s = (p0.X - p2.X) * (p.Y - p2.Y) - (p0.Y - p2.Y) * (p.X - p2.X);
    var t = (p1.X - p0.X) * (p.Y - p0.Y) - (p1.Y - p0.Y) * (p.X - p0.X);

    if ((s < 0) != (t < 0) && s != 0 && t != 0)
        return false;

    var d = (p2.X - p1.X) * (p.Y - p1.Y) - (p2.Y - p1.Y) * (p.X - p1.X);
    return d == 0 || (d < 0) == (s + t <= 0);
}

2021年更新:这个版本正确处理任意一个缠绕方向(顺时针和逆时针)指定的三角形。请注意,对于恰好位于三角形边缘上的点,本页上的一些其他答案会给出不一致的结果,这取决于三角形三个点的排列顺序。这些点被认为是“在”三角形中,这段代码正确地返回true,而不管缠绕方向如何。

我在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

下面是一个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")

制作以下图表:

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.

下面是一个高效的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))

和一个示例输出: