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

Question

我有地图。在地图顶部有一个多边形A和一个圆B.它们相互交叉。任何算法都可以计算交点C的面积？

Answer 1

假设您愿意接近圆（具有大量边的多边形...），那么有一堆算法可用于计算多边形裁剪的结果（请参阅here一个简短的清单）。

一个简单的实现漂亮归结为：

1. 确定哪些设置的多边形A的点位于多边形B内，反之亦然
2. 确定交点为线段的交叉该内外点边界和
3. 从收集的点集构造一个新的多边形。要计算该新多边形的面积，可以将其分解为三角形集合并求和它们的面积。

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

如果你不愿意用你的圆圈的任意好的近似值做，我想你必须开始找出多边形线段和圆的边界之间的交点，然后逐段地整合每个段。

Answer 2

这可以在不近似做到：多边形和圆形

相交的区域的撰写边界之间

1. 发现路口 - 你将有线段和圆弧区域
2. 计算面积的序列使用格林公式：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^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)

Integral[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)