如何在c#中实现凸多边形中点的有效测试算法

Question

简单的问题-查找一个点是否在凸多边形内。有一个算法还没有被描述，因为它是在Wolfram语言中，我有一些错误。这是我的文件:

private static bool PointInside2D(Vector2 point, Vector2 lineStart, Vector2 lineEnd) {
    var v1 = lineStart - point;
    var edge = lineStart - lineEnd;
    return !(edge.x * v1.y - edge.y * v1.x < 0);
}
private static bool PointInsideRect2D(Vector2 point, IList<Vector2> rect) {
    var lastPoint = rect.Count - 1;
    bool? lastResult = null;
    for (var i = 0; i < lastPoint; ++i) {
        if (lastResult == null) {
            lastResult = PointInside2D(point, rect[i], rect[i + 1]);
        }
        else {
            if (lastResult != PointInside2D(point, rect[i], rect[i + 1])) {
                return false;
            }
        }
    }
    return lastResult == PointInside2D( point, rect[lastPoint], rect[0] );
}

和它不工作可悲的是…我看了一些参考实现在这里尝试他们似乎也不工作。

测试数据我使用的是凸:

 [(262.8, 669.1); (1623.9, 718.2); (200.4, 895.4); (1817.8, 1540.8)]

， (288, 815)和(1078, 890)作为测试点。

谁能解释一下我在那个算法/它的实现中犯了什么错?

Answer 1

我相信你的算法是正确的。它测试被测试点是否位于多边形所有边的同一侧(左或右)。但它要求多边形声明中的所有点按顺时针或逆时针顺序排序，对于[(262.8,669.1)]则不是这样;(1623.9, 718.2);(200.4, 895.4);(1817.8, 1540.8)] .

当我改变多边形中点的顺序时，下面的程序似乎返回正确的结果:

    public static void Main()
    {
        Vector2 p1 = new Vector2(288, 815);
        Vector2 p2 = new Vector2(1078, 890);
        //Please notice order of points is changed to clockwise
        IList<Vector2> Polygon = new List<Vector2>(new Vector2[] { new Vector2(262.8f, 669.1f), new Vector2(200.4f, 895.4f), new Vector2(1817.8f, 1540.8f), new Vector2(1623.9f, 718.2f) });
        bool p1Result = PointInsideRect2D(p1, Polygon);
        bool p2Result = PointInsideRect2D(p2, Polygon);
    }
    private static bool PointInside2D(Vector2 point, Vector2 lineStart, Vector2 lineEnd)
    {
        var v1 = lineStart - point;
        var edge = lineStart - lineEnd;
        return !(edge.X * v1.Y - edge.Y * v1.X < 0);
    }
    private static bool PointInsideRect2D(Vector2 point, IList<Vector2> rect)
    {
        var lastPoint = rect.Count - 1;
        bool? lastResult = null;
        for (var i = 0; i < lastPoint; ++i)
        {
            if (lastResult == null)
            {
                lastResult = PointInside2D(point, rect[i], rect[i + 1]);
            }
            else
            {
                if (lastResult != PointInside2D(point, rect[i], rect[i + 1]))
                {
                    return false;
                }
            }
        }
        return lastResult == PointInside2D(point, rect[lastPoint], rect[0]);
    }