获取圆内整数点

分析

圆心位置无所谓，我们先计算相对坐标最后进行统一平移就好，所以圆心就当做（0,0），然后拿半径为7的圆举例：

首先，圆是对称图形，所以我们可以只计算八分之一圆的点，然后在对称到整个圆即可。也就是说我们可以只计算y = x线下部分的半圆。

八分之一圆

首先是获取坐标轴上的点，也就是（0,0）-（0,7）；

然后获取y = x上的点，此时需要根据勾股定理算出直线和圆的交点并向下取整，也就是floor(radius / sqrt(2))，从（1，1）取到他。

剩下的需要继续分析：

剩下的区域

剩下的就是被红线包围的区域，这些线都很好获取。我们不妨将这个区域使用蓝线分为上下两部分，其中下面一部分的点都在圆内，较为好计算。

首先获得蓝线，就是竖着的红线与圆的交点纵坐标值向下取整：floor(sqrt(7 * 7 - 6* 6))；

下半部分的直角梯形的计算很简单，循环即可。

然后是上半部分，比较困难，每一行都需要计算与圆相交点的坐标，并逐行添加。

然后是对称，很简单。不过记得如果圆心坐标不是（0,0）要在最后对所有点进行一个偏移。

代码实现

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
struct Point2i
{
	Point2i()
	{
		x = 0;
		y = 0;
	}

	Point2i(const int& _x, const int& _y)
	{
		x = _x;
		y = _y;
	}

	int x, y;
};


// 获取给定圆内的整数点
std::vector<Point2i> GetAllPointInCircle(const Point2i& center, const int& radius)
{
	assert(radius > 0);

	std::vector<Point2i> points;
	// 坐标轴
	for (int i = 0; i <= radius; i++)
	{
		points.push_back(Point2i(i, 0));
	}
	// y = x
	int maxI = floor(radius / SQRT2);
	for (int i = 1; i <= maxI; i++)
	{
		points.push_back(Point2i(i, i));
	}
	// 其他点
	// 下部分
	int xBottomMax = radius - 1;
	int yBottomMax = floor(sqrt(radius * radius - xBottomMax * xBottomMax));
	for (int i = 1; i <= yBottomMax; i++)
	{
		for (int j = i + 1; j <= xBottomMax; j++)
		{
			points.push_back(Point2i(j, i));
		}
	}

	// 上部分
	for (int i = yBottomMax + 1; i <= maxI; i++)
	{
		int xMaxUpper = floor(sqrt(radius * radius - i * i));
		for (int j = i + 1; j <= xMaxUpper; j++)
		{
			points.push_back(Point2i(j, i));
		}
	}

	// 做对称
	// 根据y = x对称
	int pointNum;
	pointNum = points.size();
	for (int i = 0; i < pointNum; i++)
	{
		if (points[i].x != points[i].y)
		{
			points.push_back(Point2i(points[i].y, points[i].x));
		}
	}

	// 根据y轴对称
	pointNum = points.size();
	for (int i = 0; i < pointNum; i++)
	{
		if (points[i].x != 0)
		{
			points.push_back(Point2i(-points[i].x, points[i].y));
		}
	}

	// 根据x轴对称
	pointNum = points.size();
	for (int i = 0; i < pointNum; i++)
	{
		if (points[i].y != 0)
		{
			points.push_back(Point2i(points[i].x, -points[i].y));
		}
	}

	// 把圆平移到圆心
	for (auto& point : points)
	{
		point.x += center.x;
		point.y += center.y;
	}
	return points;
}

分析

其中最耗的肯定属这些开方运算，我进行了一个分析：

半径 开方 开方总数 如果使用平方距离
7 1 + 1 2 196
8 1 + 2 3 256
9 1 + 2 3 324
10 1 + 3 4 400
11 1 + 3 4 484
64 1 + 34 35 16384

平方根数量公式

图像

还算可以接受

获取圆环内整数点

分析

有了上面获取圆内点的前置知识，我们只需要在加入数组的时候判断是不是在小圆内就可以了。

同样也是红线中的上半部分计算比较痛苦。

代码实现

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// 获取给定圆环内的整数点
std::vector<Point2i> GetAllPointInRing(const Point2i& center, const int& radiusSmall, const int& radiusBig)
{
	assert(radiusBig > radiusSmall);
	assert(radiusSmall >= 0);

	std::vector<Point2i> points;
	// 坐标轴上的
	for (int i = radiusSmall + 1; i <= radiusBig; i++)
	{
		points.push_back(Point2i(i, 0));
	}

	// y = x上的
	int maxXSmall = floor(radiusSmall / SQRT2);
	int maxXBig = floor(radiusBig / SQRT2);
	for (int i = maxXSmall + 1; i <= maxXBig; i++)
	{
		points.push_back(Point2i(i, i));
	}

	// 其他的
	// 下部分
	int maxXBottomSmall = radiusSmall - 1;
	int maxYBottomSmall = floor(sqrt(radiusSmall * radiusSmall - maxXBottomSmall * maxXBottomSmall));
	int maxXBottomBig = radiusBig - 1;
	int maxYBottomBig = floor(sqrt(radiusBig * radiusBig - maxXBottomBig * maxXBottomBig));

	for (int i = 1; i <= maxYBottomBig; i++)
	{
		// 如果到了小圆上半部分，每行先计算那一行小圆的最大x值
		// 只要比小圆对角线y值大的点一定不在小圆里，所以这里不计算
		int xMaxUpperSmall = 0;
		if (i > maxYBottomSmall && i <= maxXSmall)
		{
			xMaxUpperSmall = floor(sqrt(radiusSmall * radiusSmall - i * i));
		}
		for (int j = i + 1; j <= maxXBottomBig; j++)
		{
			// 如果在小圆的直角梯形内直接丢弃
			if (j <= maxXBottomSmall && i <= maxYBottomSmall) continue;
			// 如果在小圆上半部分且比x值那一行小圆的最大x值小，也丢弃
			if (i > maxYBottomSmall && i <= maxXSmall)
			{
				if (j <= xMaxUpperSmall) continue;
			}
			points.push_back(Point2i(j, i));
		}
	}

	// 上部分
	for (int i = maxYBottomBig + 1; i <= maxXBig; i++)
	{
		int xMaxUpper = floor(sqrt(radiusBig * radiusBig - i * i));
		// 这里与上面一样，只要比小圆对角线y值大，就一定不在小圆里，不需要判断
		int xMaxUpperSmall = 0;
		if (i <= maxXSmall)
		{
			xMaxUpperSmall = floor(sqrt(radiusSmall * radiusSmall - i * i));
		}
		for (int j = i + 1; j <= xMaxUpper; j++)
		{
			if (i <= maxXSmall)
			{
				if (j <= xMaxUpperSmall) continue;
			}
			points.push_back(Point2i(j, i));
		}
	}

	// 对称
	···

	// 平移到圆心
	···
}

其他

在计算其他点上半部分的时候需要一行一开方操作，考虑可以将特定那部分换成一个长方形中所有点的计算平方距离操作，如果平方距离大于平方半径，那就在圆外。不过这种操作需要更多的乘法，远多于开方，具体性能还需要做测试。

资源

https://github.com/1keven1/Get-lattice-point-in-circle-ring