三角剖分求圆和多边形的面积并
三角剖分是一个思想,可以用来求一些计算几何的问题。这里讲解如何用三角剖分的思想来求圆和简单多边形的面积并
设圆的圆心为 p,半径为 r
我们为多边形的每条边定义一个逆时针的方向,则对于每条边 →ab 都能和圆心构成一个三角形 pab,我们定义这个三角形的有向面积为 →pa×→pb,则此时整个多边形的面积就是所有边和圆心构成的三角形的有向面积的和。这是一个求简单多边形面积的常用方法。
这样我们能很容易得到多边形和圆的面积,而他们的面积并就应该是多边形的面积加上圆的面积再减去多边形和圆的交集的面积。
因此我们接下来的问题就是求出多边形和圆的交集的面积。我们还是看多边形每条边和圆心构成的三角形,此时我们不计算每个三角形的面积,我们计算每个三角形和圆的交集的有向面积,如果我们能求出每个三角形和圆的交集的有向面积,则所有三角形和圆的交集的有向面积的和恰好就是多边形和圆的交集的面积。可以自行画图理解,重点在于有向面积。
然后问题就变成了对于每个三角形,求一下它和圆的交集的面积,这样我们将问题从求一个多边形和圆的交集变成了求一个三角形和圆的交集,求多边形和圆的交集情况非常的多,完全考虑不完,但是三角形就比较固定了,能考虑的情况也比较少,这样我们就可以进一步分情况来讨论,这也是三角剖分的核心思想。
然后考虑三角形 pab 和圆的交集的所有情况。
第一种情况,a,b 两点都在圆内,此时三角形和圆的交集就是三角形的面积,直接用叉积计算即可。
第二种情况,a,b 都在圆外且边 ab 不经过圆,设 pb 和 pa 的夹角为 θ,此时的交集就是一个半径为 r 角度为 θ 的扇形,也可以直接计算。
第三种情况,a 在圆外,b 在圆内,设 ab 和圆的交点是 q,则此时我们可以将交集分成一个三角形和一个扇形,三角形用叉积,扇形求一下夹角套扇形公式计算。
第四种情况,a 在圆内,b 在圆外,这一个情况和第三种情况类似,不再多说。
第五种情况,a,b 都在圆外且边 ab 经过圆,此时的交集可以分成两个扇形和一个三角形,三个部分分开计算即可。
到此我们就将所有三角形和圆的交集的情况都考虑清楚了,接下来只需要根据不同的情况来计算交集的面积即可,最终将每个三角形和圆的交集的有向面积加在一起就是多边形和圆的交集的面积了。
在求三角形和圆的交集的时候,我们需要快速的知道边和圆的两个交点 a,b 的位置,可以联立方程然后解方程求出来,这里用向量的方式来求,我们可以先求一下 p 到 ab 的垂足 e,p 加上 ab 顺时针旋转 90。 后的向量就是 p 到 ab 的垂线,求一下垂线和 ab 的交点就是 e。然后求一下 p 到 ab 的距离,就可以用勾股定理求出 ea 的距离,我们知道 ea 的距离和方向,就能通过 e 的坐标得到 a 的坐标。b 就是 e 往反方向走同样距离得到的坐标。
另外,区分第二种情况和第五种情况我们可以通过判断 p 在 ab 的垂足 e 是否在 ab 上,如果在 ab 上,说明是第五种情况,否则是第二种情况。
以上就是三角剖分求圆和多边形的面积并的具体思路和细节,其中涉及很多计算几何的常用操作,可以参考 计算几何的基础知识