标注场景,用户可以通过多点框选择区域,生成多边形。但有些多边形不适合标注场景,会增加其他参数的计算复杂度,需要判断禁止绘制。分类根据标记的场景,多边形可分为有交点的多边形和无交点的多边形。如图:这其实就是多边形划分中的一个简单多边形和一个复杂多边形。我们可以通过多边形边之间是否有交集来判断。判断如何判断变量是否相交?如果要计算交点是否落在连接线上,不仅计算量大,而且还会因为比较精度等问题而带来麻烦。这类问题已经有更好的解决方案:相交线段的特点是端点位于相交线段的两侧,只需要判断两个端点是否在线的两侧即可segment判断线段是否可以相交。以右边的复杂多边形为例:\(point_A,point_F\)形成的\(线段a\)与\(point_C,point_D\)形成的\(线段b\)相交。\(线段a\)的两个端点\(A\)和\(F\)一定在\(线段b\)的两侧,反之亦然。如何计算线段两边的端点?数学工具矢量的叉积可以用来简化几何运算。二维计算中叉积的结果是有方向意义的。我们只需要选择一条线作为中线,将它的端点和需要判断的端点连接起来做一条新线,然后计算辅助线和中线。如果符号不同,则说明线段可以在两边相交。计算二维叉积的计算公式:$$a\timesb=\begin{bmatrix}x_a&x_b\\y_a&y_b\end{bmatrix}=x_ay_b-x_by_a$$已知图,比如\(point_A\)的坐标为\((x_1,y_1)\),顶点之间只能依次用直线连接。现在以\(b(point_C,point_D)\)为中线,以\(point_C\)为起点,连接需要计算的\(point_A,point_F\)。这时我们有一条中线,和两条新绘制的辅助线:中线\(b(point_C,point_D)\)向量表示:\(V_b(x_c-x_d,y_c-y_d)=V_b(x_b,y_b)\)辅助线\(c(point_C,point_A)\)向量表示:\(V_c(x_C-x_A,y_C-y_A)=V_c(x_c,y_c)\)辅助线\(d(point_C,point_F)\)向量表示:\(V_d(x_C-x_F,y_C-y_F)=V_d(x_d,y_d)\)计算\(V_b\timesV_c=x_b\cdoty_c-x_c\cdoty_b\)可以是正数也可以是负数,所以可以看出\(point_A\)在\(V_b\)中线的一侧。不需要知道在哪一边,只要\(V_b\timesV_d\)的结果和\(V_b\timesV_c\)的结果一样,就说明两点在同一边线段的,否则它们在两侧,这意味着线段相交。简化计算\((V_b\timesV_d)\times(V_b\timesV_c)<=0\)就知道他们不在同一边。最后,还有一件非常重要的事情。需要反过来再计算一遍。只有两者都成立才能确定线段相交。如果只算一个,只能是延长线可以相交,实际相交不一定存在。例如,以\(线段AB\)为中线,判断\(point_E\)和\(point_F\)在\(线段AB\)的两侧,计算结果相交,但实际\(线段AB\)不通过\(线段EF\)。这时只需要以\(线段EF\)为中线,计算\(point_A\)和\(point_B\)是否在两边即可。这只是两条边是否相交,剩下的只需要判断所有不相邻的边是否都相交了。对于标注场景,不会有那么多图形,计算量完全可以接受。大量的图形将需要更复杂的算法。代码interfacePoint{x:number;y:number;}typeEdge=[Point,Point];/***叉乘*/constcrossProduct=(v1:number[],v2:number[])=>{const[v1x,v1y]=v1;const[v2x,v2y]=v2;returnv1x*v2y-v2x*v1y;};/***是否可以相交*@parambaseEedge*@paramtargetEdge*/constisIntersection=(baseEedge:Edge,targetEdge:Edge)=>{const[basePointA,basePointB]=基边;const[targetPointC,targetPointD]=targetEdge;constvBase=[basePointA.x-basePointB.x,basePointA.y-basePointB.y];constvBaseC=[basePointA.x-targetPointC.x,basePointA.y-targetPointC.y];constvBaseD=[basePointA.x-targetPointD.x,basePointA.y-targetPointD.y];returncrossProduct(vBase,vBaseC)*crossProduct(vBase,vBaseD)<=0;};/***提取数组元素*/constextractArray=(array:Edge[],startIndex:number,length:number)=>{constarr=[];for(leti=0;i
