非自交任意多边形与矩形框的交集面积计算方法
1、应用背景
在对象识别的AI计算时，有时需要限定检测区域，即目标对象落在限定区域内有效，在区域外忽略。
转换为数学模型为：目标检测框与限定区域（非自交多边形）的交集面积除以目标检测框面积（类似于IOU值），超过门限（如50%），判定为在限定区域内。
整个问题归结为计算目标检测框与限定区域的交集面积。
多边形用顶点列表表示：点集P={pi|i=0,1,…,n-1}，为顺序的n个点，n>=3，则多边形为：p0->p1->…->pn-1->p0。对于点p(i)，p(i-1)表示前一个点，p(i+1)表示后一个点。本文下面涉及到p(i)，如果i小于0，则i=(i+n) % n。
约定输入多边形为非自交的，所谓自交，如ABCD是正常矩形，则ABDC就是自交的。
限定区域，可以表示为多个多边形的列表（本算法要求限定区域的多边形之间的交集为空，否则需要计算凸多边形之间的交集）。
2、算法步骤
2.1、先计算多边形的方向，是顺时针，还是逆时针。
图像坐标，X轴方向从左到右，Y轴方向从上到下。顺时针为1，逆时针为-1。
搜索多变形最左侧点，如果最左侧点有多个，取左侧最下面的点。不妨设该点为p1，对应下标为k，计算点p的叉乘。p0表示p1的前一点，p2表示p1的后一点。
即向量p0p1与向量p1p2的叉乘：cross_product = (p1.x-p0.x) (p2.y-p1.y) – (p1.y-p0.y)(p2.x-p1.x)
如果cross_product>0，为顺时针；cross_product
2.2、处理凹多边形
检测多边形的凸性，如果为凹多边形，则切分为多个凸多边形；如果为凸多边形，则返回。
对于多边形P，逐点计算叉乘，如果cross_product*clockwise 小于等于 0，则认为是凹点，表示多边形为凹多边形。
针对第一个凹点p(i)，从p(i-2)开始反向扫描，检测向量p(i-1)p(i)与向量p(i)p(k)的叉乘，k=i-2,…0,1,..i+1-n，取得反向扫描的第一个凹点p(c-1)的之后一点p(c)，即表示最大的凸多边形。切分p(c),…p(i)为新的多边形P1，p(i)p(c)连线为切分线，p(i)、p(c)及余下的点组成剩余多边形P2。
对于切分得到的多边形P1和P2，递归使用本算法，直到所有多边形都是凸多边形。
算法的效果图如下：
2.3、计算所有凸多边形的外接矩形
针对已得到的凸多边形列表，逐个计算外接矩形。得到外接矩形列表：outBoundRectangeList。外接矩形与凸多边形一一对应。
使用外接矩形，可以简化后续处理。
2.4、计算外接矩形与目标检测框的交集
目标检测框为矩形，外接矩形与目标检测框的交集，结果为矩形或空集。如果为空集，表示凸多边形与目标检测框无交，如果交集非空，则进入下一步处理。
2.5、计算交集矩形与凸多边形的交集多边形
以交集矩形的4条边线所在直线，分别计算直线与凸多边形的交点，按上边线、右边线、下边线、左边线次序。根据交集矩形的生成方法，各边线与凸多边形必然都有交点，如果交点为多边形顶点，则进一步判断顶点的2条边的邻接点是否在边线的同一侧，如果为同一侧，则该顶点算两个点。如果2个邻接点在边线的两侧或有一边在边线上，则计为一个点。这样，每条边线与凸多边形的交点都是两个。
对于上边的两个交点，y轴的值为rcy1,设x轴的值分别为x1和x2，交集矩形的上边端点x轴值为rcx1和rcx2，则上边线段的交集线段：
v1=max(rcx1,min(x1,x2))
v2=min(rcx2,max(x1,x2))
如果v1>v2，表示线段无交集；如果v1==v2，表示一个交点；如果v1小于v2，则交集上边线段端点(v1,rxy1)和(v2,rxy1)。将交点加入交集多边形中，添加顺序，按顺时针次序方向加入，无交集则不加。
类似方法处理右边线，下边线，左边线。
最后得到：交集矩形与凸多边形的交集多边形，可能的形状如下：
2.6、计算交集多边形面积
交集多边形为凸多边形，因此面积计算可使用三角形方法，以p0点为固定点，依次取p(i-1)和p(i),i=2,..,n-1，得到三角形列表。
三角形的面积计算，假设三点分别为p1=(x1,y1),p2=(x2,y2),p3=(x3,y3)，则三角形面积为:
S=(x1y2-x2y1+x3y1-x1y3+x2y3-x3y2)/2=[x1(y2-y3)-x2(y1-y3)+x3(y1-y2)]/2，这个公式可使用行列式表示：
[S=\left| \begin{array}{cccc} x1 & y1 & 1 \ x2 & y2 & 1 \ x3 & y3 & 1 \end{array} \right| * 1/2 ]
利用三角形坐标计算面积的公式推导如下：
如下图的三角形：
三角形面积等于外接矩形框面积减去三个着色的三角形面积，图像坐标Y轴从上到下，即：
S=(x2-x3) (y3-y1)-((x2-x1)(y2-y1)+(x2-x3) (y3-y2)+(x1-x3)(y3-y1))/2
整理后，即可得到之前的三角形面积公式。
累加交集多边形的所有三角形的面积，得到一个交集多边形的面积。
2.7、计算凸多边形与目标检测框的交集多边形面积
累加所有凸多边形与目标检测框的交集多边形面积。效果图如下：
Original: https://www.cnblogs.com/alabo1999/p/16727352.html
Author: 阿拉伯1999
Title: 非自交任意多边形与矩形框的交集面积计算方法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/801981/
转载文章受原作者版权保护。转载请注明原作者出处！