如何测试点是否在2D整数坐标中的凸多边形内？

Question

多边形作为Vector2I对象列表(2维,整数坐标)给出.如何测试给定点是否在内？我在网上找到的所有实现都失败了一些微不足道的反例.写一个正确的实现似乎很难.语言并不重要,因为我会自己移植它.

Answer 1

如果它是凸的,那么检查它的一个简单方法是该点位于所有段的同一侧(如果以相同的顺序遍历).

您可以使用十字产品轻松检查(因为它与段和点之间形成的角度的余弦成正比,带有正号的那些将位于右侧,而那些带有负号的位于左侧).

这是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 = x_product(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 x_product(a, b):
    return a[0]*b[1]-a[1]*b[0]

Answer 2

Ray Casting或Winding方法是此问题最常见的方法.有关详细信息,请参阅Wikipedia文章.

另外,请查看此页面以获取C中记录完备的解决方案.

Answer 3

如果多边形是凸的,那么在C#中,以下实现" 如果总是在同一侧测试 "方法,并且最多在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 < polygon.Count - 1 ? i + 1 : 0;

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