寻找多边形和圆之间的交集区域使用什么算法？

Question

我有一张地图。在地图的顶部，有一个多边形A和一个圆形B。它们相交在一起。是否有任何算法可以计算它们的交集C的面积？

- user717166

---

你需要解决多普遍的问题？多边形总是简单的（非自相交）吗？如果是，多边形总是凸的吗？圆和多边形相交时只有两个交点（如图所示）是否已知？ - Ted Hopp

@TedHopp，是的，多边形始终不会自相交。但它是非凸多边形。当圆形向多边形内部移动时，会有更多的点相交。 - user717166

要找到交集的面积，首先在两个交点之间画一条直线。然后计算多边形剩余部分的面积并加上该段的面积。 - Neil

Answer 1

假设您愿意接受圆的近似值（一个具有大量边的多边形...），那么有许多算法可用于计算多边形剪切的结果（请参见此处，以获取简短列表）。

一个简单的实现基本上是：

1. 确定多边形A的哪些点位于多边形B内部，反之亦然 2. 确定跨越内外边界的线段的交点，并 3. 从收集到的点集构建一个新的多边形。要计算该新多边形的面积，只需将其分解为一组三角形并求和它们的面积。

如果您不想做所有这些工作，请尝试JS Clipper。它可能会让您的生活更轻松。

如果您不愿意满足于对圆进行任意好的近似值，我认为您必须开始找到多边形线段与圆边界之间的交点，然后逐段积分每个部分。

- Dan Anderson

---

经过查看JS Clipper后，我不知道从哪里开始使用脚本来计算交集的面积。您能简要地给一些提示来实现这个结果吗？ - user717166

Answer 2

这可以不需要近似方法完成：

1. 找到多边形和圆的交点
2. 组合交集区域的边界 - 您将得到线段和弧的序列
3. 使用Green公式计算该区域的面积：http://en.wikipedia.org/wiki/Green%27s_theorem#Area_Calculation - Integral[border](x*dy-y*dx)

对于每个线段，计算这个积分是微不足道的 - 它只是x0 * y1-y0 * x1。

对于圆弧，它稍微冗长一些。最终结果是Cx*(y1-y0) - Cy*(x1-x0) ) + R^2*(t1-t0)，其中(Cx，Cy)是圆的中心，(x0，y0)是弧的起点，(x1，y1)是弧的终点，t0是弧的起始角度，t1是弧的结束角度。

为了让任何人都能验证这个推导，这里是它的表达式： （当然，它可以从几何上推导出来，但我是通过公式来做的）

Integral[arc](x*dy-y*dx)

Integral[t=t0..t1]( (Cx+R*cos t)*R*cos t - (Cy+R*sin t)*(-R*sin t) )dt

Integral[t=t0..t1]( (Cx+R*cos t)*R*cos t + (Cy+R*sin t)*R*sin t )dt

Integral[t=t0..t1]( Cx*R*cos t + R^2*cos^2 t + Cy*R*sin t + R^2*sin^2 t )dt

Integral[t=t0..t1]( Cx*R*cos t + Cy*R*sin t + R^2*sin^2 t + R^2*cos^2 t )dt

Integral[t=t0..t1]( Cx*R*cos t + Cy*R*sin t + R^2 )dt

Integral[t=t0..t1]( Cx*R*cos t + Cy*R*sin t )dt + R^2*(t1-t0)

积分[t=t0..t1]( Cx*R*d(sin t) - Cy*R*d(cos t) ) + R^2*(t1-t0)

Cx*R*(sin t1-sin t0) - Cy*R*(cos t1-cos t0) ) + R^2*(t1-t0)

Cx*(y1-y0) - Cy*(x1-x0) ) + R^2*(t1-t0)

- maxim1000