拉制体育场形状

Question

我想使用这个数字，这个数字被称为体育场：

​

​

它可以用三个参数定义为与线段[AB]的距离小于或等于r的所有点的集合。

给定一个由正方形单元组成的轴向栅格，其中每个正方形都用两个整数坐标定义，那么计算一个体育场全部或部分重叠的所有单元的集合最有效的方法是什么？(我不需要这里有任何形式的反混叠)

问题：

• 我找不到体育场广场重叠测试算法
• 即使我有一个，我也必须在我的整个栅格上迭代(实际上是无限的，但我可以在它上定义一个有限的搜索区域)，并检查每个单元是否与体育场重叠。这将是一个计算繁重的操作，我需要在我的项目(一个游戏)一个相对快速的操作。

Answer 1

您可以使用Bresenham圆光栅化算法(以及其他类似中点算法)。

关键是使用对称性。让体育场(也有名字“胶囊”)中心在原点，并有参数:半径R，以及半圆D之间的距离。

从Bresenham弧的右侧开始(在(R, 0)坐标处)。生成点(x,y)以形成圆四分之一，并使反射点和移位点生成水平扫描线。

(x + D/2 , y) connect to (-x - D/2, y)
(x + D/2, -y) connect to (-x - D/2, -y)

对于任意方向，可按Y对接合点进行排序，最多可划分5个区域:扫描线、弧线、线线、线弧、弧弧。然后计算每个Y坐标的X-端坐标。