如何有效地测试任意多边形是否与正方形相交？
How to efficiently test whether an arbitrary polygon intersects with a square?
多边形可能是凸面也可能不是。我们可以假设正方形的边缘与 X 轴和 Y 轴对齐。
计算交集[多边形交集的简单算法]1 太过分了，因为我只需要知道它们是否相交（是或否）。
我不确定它是否是最知名的算法（实际上我更确定有更好的知名算法），但我相信这个解决方案应该有效。
想法是将问题"reduction"做成多边形裁剪到裁剪区域的问题（即将问题转换成不同的问题并用解决新问题的算法解决） .做这样的减少：
- 如果您最终将多边形的某些部分留在裁剪区域内 - 那么就会有一个交集
- 如果你最终有一组空的多边形顶点——即你在裁剪区域内没有任何东西——那么就没有交点
用于多边形裁剪的 Sutherland-Hodgman 算法会执行此操作 - 如果多边形穿过裁剪区域 - 它最终会为您提供表示裁剪多边形的顶点列表。如果多边形完全在裁剪区域之外（即没有交叉点）——那么它最终会为您提供一个空列表，因为实际上没有可以在裁剪区域内绘制的多边形部分。
您可以在此处找到有关裁剪多边形的 Sutherland-Hodgman 算法的说明：https://www.youtube.com/watch?v=Euuw72Ymu0M
您可以遍历多边形的边缘并检查其中一条是否与您的正方形相交。如果有人这样做，那么您就完成了。否则只需测试 1) 正方形的中心是否属于多边形 2) 多边形中的任意点是否属于正方形或 3) 1) 和 2) 的 none 是否成立。在情况 1) 和 2) 中它们确实重叠，在情况 3) 中它们不重叠。
多边形可能是凸面也可能不是。我们可以假设正方形的边缘与 X 轴和 Y 轴对齐。
计算交集[多边形交集的简单算法]1 太过分了，因为我只需要知道它们是否相交（是或否）。
我不确定它是否是最知名的算法（实际上我更确定有更好的知名算法），但我相信这个解决方案应该有效。
想法是将问题"reduction"做成多边形裁剪到裁剪区域的问题（即将问题转换成不同的问题并用解决新问题的算法解决） .做这样的减少：
- 如果您最终将多边形的某些部分留在裁剪区域内 - 那么就会有一个交集
- 如果你最终有一组空的多边形顶点——即你在裁剪区域内没有任何东西——那么就没有交点
用于多边形裁剪的 Sutherland-Hodgman 算法会执行此操作 - 如果多边形穿过裁剪区域 - 它最终会为您提供表示裁剪多边形的顶点列表。如果多边形完全在裁剪区域之外（即没有交叉点）——那么它最终会为您提供一个空列表，因为实际上没有可以在裁剪区域内绘制的多边形部分。
您可以在此处找到有关裁剪多边形的 Sutherland-Hodgman 算法的说明：https://www.youtube.com/watch?v=Euuw72Ymu0M
您可以遍历多边形的边缘并检查其中一条是否与您的正方形相交。如果有人这样做，那么您就完成了。否则只需测试 1) 正方形的中心是否属于多边形 2) 多边形中的任意点是否属于正方形或 3) 1) 和 2) 的 none 是否成立。在情况 1) 和 2) 中它们确实重叠，在情况 3) 中它们不重叠。