两凸多边形相交区域和相交区域面积的计算
最近的GIS开发中有这个需求,大学没教过多少计算几何的东西,所以相关知识基本上是一片空白。为了解决这个需求还是花了点时间,所以这里大概记录下思路。具体的代码就不贴了。
两个凸多边形A,B的相交区域面积计算,这里采用如下两步进行计算:
一、 计算相交区域对应的多边形,记为intersect
大体分为下面几个步骤:
1.记录A位于B中的所有顶点
2.记录B位于A中的所有顶点
3.记录A与B每一条边的交点
4.对由上面3步得到的点集进行去重,则得到了A与B相交区域对应多边形的顶点集合,这个顶点集合是无序的。
5.对这个顶点集合进行排序,将其顶点排序为凸多边形。
对于1,2需要用到知识——如何判断点位于多边形内?能搜索到很多资料,我这里用的是角度和法。
对于3,边与边的相交判断同样有很多方法,我这里用的是跨立法。此外需要注意特殊情况:A与B的某些边存在共线重叠。
对于5,可以计算出重心O,然后根据重心和顶点A,B的两个向量的向量叉积来判断AB的方向。如果OA与OB叉积大于0,则OB在OA的逆时针方向,同样能在网上找到很多资料。
二、计算intersect的面积(计算多边形的面积)
采用的方法是以任意顶点出发,通过与其他顶点连线将整个多边形切割成多个三角形,然后对三角形的面积进行计算。
大概的要点就是上面这些了。
下面是效果图: