如何检测圆形和多边形是否重叠？

Question

我正在实现一个可以检测圆形和多边形是否重叠的功能。我拥有多边形的所有点，并且知道圆的中心点和半径。

我检查了两种情况：

• 多边形顶点在圆内
• 圆心在多边形内

但是，在其他情况下，圆形和多边形重叠，如附图所示。谁能建议验证找到交叉点？

Answer 1

这里是一种可能的方法。

• 如果多边形顶点之一在圆内，则存在重叠。

• 如果圆心在多边形内部，则它们重叠。请注意，对于非凸形状，此测试并非无关紧要。例如，考虑类似于细螺旋的多边形。

• 否则，对于多边形的每个边（a，b）：

  • 查找p，圆心向线（a，b）的投影。
  • 如果p到圆心的距离大于半径，则此边缘没有重叠。
  • 否则，如果p在a和b之间（所以p_x在a_x和b_x之间，并且p_y在a_y和b_y之间，以包括水平和垂直边缘的情况，则该边缘存在重叠，否则不存在。） >