如何在二维整数坐标系中测试一个点是否在凸多边形内部？

Question

如何在二维整数坐标系中测试一个点是否在凸多边形内部？

geometrypolygonhittest

28

这个多边形是由Vector2I对象列表（二维整数坐标）给出的。如何测试给定的点是否在其内部？我在网上找到的所有实现都不能处理一些微不足道的反例。似乎很难编写正确的实现。语言无关紧要，因为我会自己移植。

- usr

一条注释。如果这是一个面试问题，你应该得到一个O(log n)的解决方案，因为凸多边形是一个特殊情况。使用二分查找以及ufukgun答案中提供的思路。 - Yin Zhu

5

这里的回答出乎意料地糟糕。Eric Haines的这篇文章介绍了许多处理此类问题的方法，并提供了一些知名文献的参考。 - bobobobo

可能是[点在多边形内的问题，也称为命中测试]的重复。 (https://dev59.com/p3VC5IYBdhLWcg3wrDJd) - bobobobo

9个回答

14

如果多边形是凸的，在C#中以下实现了“test if always on same side”方法，并且至多以O（多边形点数n）运行：

public static bool IsInConvexPolygon(Point testPoint, List<Point> polygon)
{
    //Check if a triangle or higher n-gon
    Debug.Assert(polygon.Length >= 3);

    //n>2 Keep track of cross product sign changes
    var pos = 0;
    var neg = 0;

    for (var i = 0; i < polygon.Count; i++)
    {
        //If point is in the polygon
        if (polygon[i] == testPoint)
            return true;

        //Form a segment between the i'th point
        var x1 = polygon[i].X;
        var y1 = polygon[i].Y;

        //And the i+1'th, or if i is the last, with the first point
        var i2 = (i+1)%polygon.Count;

        var x2 = polygon[i2].X;
        var y2 = polygon[i2].Y;

        var x = testPoint.X;
        var y = testPoint.Y;

        //Compute the cross product
        var d = (x - x1)*(y2 - y1) - (y - y1)*(x2 - x1);

        if (d > 0) pos++;
        if (d < 0) neg++;

        //If the sign changes, then point is outside
        if (pos > 0 && neg > 0)
            return false;
    }

    //If no change in direction, then on same side of all segments, and thus inside
    return true;
}

- Justas

1

如果列表的长度小于3，您应该直接失败（甚至断言）而不是尝试继续。这是多边形测试，而不是测试点是否等于另一个点或点是否在一条线上。处理这些情况是让您在稍后遇到巨大头痛的好方法，因为您期望的结果与实际结果不同，而没有告诉您哪里出了问题。此外，该方法名称并不意味着它很好地涵盖了这些情况。 - Gurgadurgen

非常有帮助！如果有人需要的话，我已经修改并移植了那段代码到另一个答案：https://dev59.com/NG435IYBdhLWcg3w0Trc#48941131 或许有人会觉得我的版本更清晰易懂。 - Emmanuel Touzery

1

非常有帮助！我刚刚在我的自制游戏开发中测试了这个函数：一个针对Amiga计算机的点击式冒险游戏。它可以直接使用，转换为C89，编译并在老旧的68000上运行。谢谢！（C版本在此处：https://github.com/ResistanceVault/rpage/blob/master/rpage/utils.c#L119） - Astrofra

14

射线投射或绕组方法是解决此问题最常见的方法。有关详细信息，请参见维基百科文章。

此外，查看此页面以获取C语言的良好文档化解决方案。

- e.James

对于整数坐标，wrf的代码片段将足够使用。 - Eric

1

这是最常见的...但如果您已经知道多边形是凸的，就像这种情况一样，Fortran应该更快！ - Wagner Patriota

2

@e-James，C语言解决方案的链接似乎已经失效。 - Yonatan Simson

4

在openCV中，pointPolygonTest函数用于“确定点是否在轮廓内部、外部或边缘上”：

http://docs.opencv.org/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html?highlight=pointpolygontest#pointpolygontest

- RawMean

OpenCV是一个非常庞大的库。你真的不想仅仅为了这个而使用它。 - Christopher Barber

3

fortran的答案对我几乎有用，但是我发现我必须将多边形转换，以便测试的点与原点相同。这是我编写的JavaScript使其正常工作:

function Vec2(x, y) {
  return [x, y]
}
Vec2.nsub = function (v1, v2) {
  return Vec2(v1[0]-v2[0], v1[1]-v2[1])
}
// aka the "scalar cross product"
Vec2.perpdot = function (v1, v2) {
  return v1[0]*v2[1] - v1[1]*v2[0]
}

// Determine if a point is inside a polygon.
//
// point     - A Vec2 (2-element Array).
// polyVerts - Array of Vec2's (2-element Arrays). The vertices that make
//             up the polygon, in clockwise order around the polygon.
//
function coordsAreInside(point, polyVerts) {
  var i, len, v1, v2, edge, x
  // First translate the polygon so that `point` is the origin. Then, for each
  // edge, get the angle between two vectors: 1) the edge vector and 2) the
  // vector of the first vertex of the edge. If all of the angles are the same
  // sign (which is negative since they will be counter-clockwise) then the
  // point is inside the polygon; otherwise, the point is outside.
  for (i = 0, len = polyVerts.length; i < len; i++) {
    v1 = Vec2.nsub(polyVerts[i], point)
    v2 = Vec2.nsub(polyVerts[i+1 > len-1 ? 0 : i+1], point)
    edge = Vec2.nsub(v1, v2)
    // Note that we could also do this by using the normal + dot product
    x = Vec2.perpdot(edge, v1)
    // If the point lies directly on an edge then count it as in the polygon
    if (x < 0) { return false }
  }
  return true
}

- Elliot Winkler

2

您需要检查待测试的点与凸多边形的所有线段之间的方向关系是否一致。如果是，则该点在凸多边形内部。为了对每个线段执行此操作，请检查线段向量AB和点向量AP的行列式是否保持其符号不变。如果行列式为零，则该点位于线段上。

要在C#代码中实现这一点，

public bool IsPointInConvexPolygon(...)
{
    Point pointToTest = new Point(...);
    Point pointA = new Point(...);
    //....

    var polygon = new List<Point> { pointA, pointB, pointC, pointD ... };
    double prevPosition = 0;
    // assuming polygon is convex.
    for (var i = 0; i < polygon.Count; i++)
    {
        var startPointSegment = polygon[i];
        // end point is first point if the start point is the last point in the list
        // (closing the polygon)
        var endPointSegment = polygon[i < polygon.Count - 1 ? i + 1 : 0];
        if (pointToTest.HasEqualCoordValues(startPointSegment) ||
              pointToTest.HasEqualCoordValues(endPointSegment))
            return true;

        var position = GetPositionRelativeToSegment(pointToTest, startPointSegment, endPointSegment);
        if (position == 0) // point position is zero so we are on the segment, we're on the polygon.
            return true;

        // after we checked the test point's position relative to the first segment, the position of the point 
        // relative to all other segments must be the same as the first position. If not it means the point 
        // is not inside the convex polygon.
        if (i > 0 && prevPosition != position)
            return false;

        prevPosition = position;
    }
    return true;
}

行列式微积分。

public double GetPositionRelativeToSegment(Point pointToTest, Point segmentStart, Point segmentEnd)
{
    return Math.Sign((pointToTest.X - segmentStart.X) * (segmentEnd.Y - segmentStart.Y) -
        (pointToTest.Y - segmentStart.Y) * (segmentEnd.X - segmentStart.X));
}

- Gabriel P.

2

我知道的方法大概是这样的。

你需要选择一个点，它在多边形外面，离几何体很远都可以。然后你从这个点开始画一条线。也就是说，你用这两个点创建一条线方程。

然后对于多边形中的每一条线，你都要检查它们是否相交。

相交的线条数之和告诉你它在内部还是外部。

如果是奇数：在内部

如果是偶数：在外部

- ufukgun

我刚学到：这是Ray casting算法，eJames已经谈论过了。 - ufukgun

我觉得你的解释很难理解...那行代码还有其他作用吗？ - fortran

射线投射通常不是一个好的解决方案，它不能很好地处理靠近顶点的点，其中投射射线会靠近一侧。对于凸形状来说，环绕规则更加健壮和快速。 - Martin Beckett

这个解决方案正是WRF代码片段所做的。 - Eric

@ufukgun，我足够聪明，能够读懂那部分文字，它说那是“起点”，那么“终点”在哪里呢？它没有说明。 - fortran

显示剩余2条评论

1

或者从写作该书的人那里查看 - 几何页面

具体来说，这个页面上，他讨论了为什么卷绕规则通常比光线交叉更好。

编辑 - 对不起，这不是Joseph O'Rourke写的优秀书籍C语言计算几何，而是Paul Bourke写的，但它仍然是一个非常非常好的几何算法源。

- Martin Beckett

你引用的页面接着列出了来自WRF的代码片段。 - Eric

0

这是我在项目中使用的版本。非常优雅简洁，适用于各种多边形。

http://www.eecs.umich.edu/courses/eecs380/HANDOUTS/PROJ2/InsidePoly.html

以下代码由Randolph Franklin编写，它返回1表示内部点，返回0表示外部点。

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
  int i, j, c = 0;
  for (i = 0, j = npol-1; i < npol; j = i++) {
    if ((((yp[i] <= y) && (y < yp[j])) ||
         ((yp[j] <= y) && (y < yp[i]))) &&
        (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
      c = !c;
  }
  return c;
}

- Jack Hack

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fortran · Accepted Answer

如果一个多边形是凸的，一种简单的检查方法是确保该点位于所有线段的同侧（如果以相同的顺序遍历）。

可以使用点积轻松检查它（因为它与由边缘法线计算的角度的余弦成正比，带有正符号的将位于右侧，带有负符号的将位于左侧）。

以下是Python代码：

RIGHT = "RIGHT"
LEFT = "LEFT"

def inside_convex_polygon(point, vertices):
    previous_side = None
    n_vertices = len(vertices)
    for n in xrange(n_vertices):
        a, b = vertices[n], vertices[(n+1)%n_vertices]
        affine_segment = v_sub(b, a)
        affine_point = v_sub(point, a)
        current_side = get_side(affine_segment, affine_point)
        if current_side is None:
            return False #outside or over an edge
        elif previous_side is None: #first segment
            previous_side = current_side
        elif previous_side != current_side:
            return False
    return True

def get_side(a, b):
    x = cosine_sign(a, b)
    if x < 0:
        return LEFT
    elif x > 0: 
        return RIGHT
    else:
        return None

def v_sub(a, b):
    return (a[0]-b[0], a[1]-b[1])

def cosine_sign(a, b):
    return a[0]*b[1]-a[1]*b[0]