测试多边形周围的区域是否无障碍

Question

我有一组任意旋转填充矩形绘制在笛卡儿网格上(2D整数数组，每个单元格要么是0-空空间，要么是1-矩形像素)，并希望测试一个特定的矩形周围是否有任何障碍，因为矩形的中心已知其四边的坐标。

例如，让我们假设我们想测试矩形是否是无障碍的5单位，从它的任何一个边。标有绿色点的矩形是可以的，而未标记的是明显的碰撞。

​

对于非旋转矩形来说，这看起来很简单，但是，我很难想出能够处理旋转矩形的算法。简单地从中心开始循环，直到我们到达空空间，然后检查空空间中的障碍物，如果矩形彼此接触，似乎没有效果。

Answer 1

因为你似乎是以图像为导向的思维方式运作，所以你可以使用图像处理。

1. 对你的图像应用半径-2.5膨胀过滤器.
2. 如果两个像素的红色值都高于某个阈值，则将图像视为一个图形，其中两个像素之间有一条边缘。
3. 在它们之间有一条路径的任何矩形最多相隔5个。(不过，请注意，这将使“太近”关系的过渡结束。)