使用回转数判断某点是否在多边形内部

Posted on In

这是偶然间想到的一个问题，平常我们经常接触到的都是判断规则图形和点的位置关系。对于不规则图形和点位置关系的判断只想到了“计算面积”的方法，查阅之后又发现了使用“射线”和“回转数”的判断方法，特别是使用回转数判断的方法

JavaScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function PointInPolygon(point, polygon) {
    var angleSum = 0;
    var polygonLength = polygon.length;

    for (var i = 0; i < polygonLength; i++) {
        var pointA = polygon[i];
        var pointB

        if (i == 0) {
            pointB = polygon[polygonLength - 1];
        }
        else {
            pointB = polygon[i - 1];
        }

        // 点在边上
        if ((pointA.x - point.x) * (point.x - pointB.x) >= 0 &&
            (pointA.y - point.y) * (point.y - pointB.y) >= 0 &&
            (point.x - pointA.x) * (pointB.y - pointA.y) == (point.y - pointA.y) * (pointB.x - pointA.x)) {
            return true;
        }

        // 点与多边形相邻顶点的夹角
        var angle = Math.atan2(pointA.y - point.y, pointA.x - point.x) - Math.atan2(pointB.y - point.y, pointB.x - point.x)

        // 夹角取值范围（-π 到 π）
        if (angle >= Math.PI) {
            angle = angle - Math.PI * 2;
        } else if (angle <= -Math.PI) {
            angle = angle + Math.PI * 2;
        }

        angleSum += angle;
    }

    if (Math.round(angleSum / Math.PI) != 0) {
        return true;
    }
    else {
        return false;
    }
}

C# 实现

1
2
3
4
5
public class Point
{
    public float x { get; set; }
    public float y { get; set; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class PointAndPolygon
{
    public static bool PointInPolygon(Point point, Point[] polygon)
    {

        double angleSum = 0;
        int polygonLength = polygon.Length;

        for (var i = 0; i < polygonLength; i++)
        {
            Point pointA = polygon[i];
            Point pointB = null;

            if (i == 0)
            {
                pointB = polygon[polygonLength - 1];
            }
            else
            {
                pointB = polygon[i - 1];
            }

            // 点在边上
            if ((pointA.x - point.x) * (point.x - pointB.x) >= 0 &&
                (pointA.y - point.y) * (point.y - pointB.y) >= 0 &&
                (point.x - pointA.x) * (pointB.y - pointA.y) == (point.y - pointA.y) * (pointB.x - pointA.x))
            {
                return true;
            }

            // 点与多边形相邻顶点的夹角
            double angle = Math.Atan2(pointA.y - point.y, pointA.x - point.x) - Math.Atan2(pointB.y - point.y, pointB.x - point.x);

            // 夹角取值范围（-π 到 π）
            if (angle >= Math.PI)
            {
                angle = angle - Math.PI * 2;
            }
            else if (angle <= -Math.PI)
            {
                angle = angle + Math.PI * 2;
            }

            angleSum += angle;
        };

        if (Math.Round(angleSum / Math.PI) != 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}