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

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

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