标注场景下,用户能够选取多点框选一个区域,这样会生成一个多边形。但某些多边形不适宜标注场景,还会减少其余参数计算复杂度,须要判断进去禁止绘制。
分类
依据标注的场景,能够将多边形演绎为边有交点多边形与边无无交点多边形。如图:
这样实际上就是多边形划分中的简略多边形与简单多边形。
咱们能够通过多边形边之间是否有相交来判断。
判断
怎么判断变是否相交呢?
如果去计算交点是否落于连线上,不仅计算量大,而且还会因为比拟精度等问题导致麻烦。这类问题早已有更好的计划:相交的线段的特色是端点别离位于相交的线段两侧,只须要判断两个端点是否在线段两侧就能判断线段是否能相交。
以左边简单多边形举例:
\( 点_A,点_F \)组成的\( 线段a \)与\( 点_C,点_D \)组成的\( 线段b \)相交。\( 线段a \)的两个端点\( A \)、\( F \)必然在\( 线段b \)的两侧,反之亦然。
如何计算出端点在线段两侧呢?
能够利用数学工具向量的叉乘(Cross product)来简化几何运算,叉乘在二维计算上的后果是具备方向含意的。
咱们只需抉择一条线作为中线,将其端点与须要判断的端点连贯做出新的线,而后辅助线与中线运算,如果符号相异则阐明是在两侧,线段是能够相交的。
计算
二维叉乘的计算公式:
$$a \times b = \begin{bmatrix} x_a & x_b \\ y_a & y_b \end{bmatrix}= x_a y_b - x_b y_a$$
已知图形的各个顶点坐标,比方\( 点_A \)坐标为\( (x_1,y_1) \),并且顶点仅能程序直线相连。
当初取\( b(点_C,点_D) \)作中线,取\( 点_C \)为终点,连贯须要计算的\( 点_A,点_F \),这时候咱们有了一条中线,与两条新画的辅助线:
中线\( b(点_C,点_D) \)向量示意:\( V_b(x_c - x_d, y_c - y_d) = V_b(x_b, y_b) \)
辅助线\( c(点_C,点_A) \)向量示意:\( V_c(x_C - x_A, y_C - y_A) = V_c(x_c, y_c) \)
辅助线\( d(点_C,点_F) \)向量示意:\( V_d(x_C - x_F, y_C - y_F) = V_d(x_d, y_d) \)
计算\( V_b \times V_c = x_b \cdot y_c - x_c \cdot y_b \)可得出正负,由此可知\( 点_A \)在\( V_b \)中线的一侧。
无需晓得在哪一侧,只有\( V_b \times V_d \)的后果与\( V_b \times V_c \)正负雷同,则阐明两点在线段的同一侧,反之则在两侧,代表线段相交。
简化运算\( (V_b \times V_d) \times (V_b \times V_c) <= 0 \)即知不在同一侧。
最初还有一个很重要,须要反向再算一次,两者皆成立能力确认线段相交。
如果只算一个,只是延长线能够相交,但理论并不一定有相交。例如
取\( 线段AB \)作中线,判断\( 点_E \)与\( 点_F \)是在\( 线段AB \)两侧,计算结果是相交的,但理论\( 线段AB \)并未通过\( 线段EF \)。这时候只有以\( 线段EF \)作中线再计算一次\( 点_A \)、\( 点_B \)是否在两侧即可。
这只是两条边是否相交,剩下只有一一判断所有非相邻边是否相交即可。
对于标注场景不会有那么多图形,计算量齐全能够承受,大量图形就得上更简单的算法了。
代码
interface Point { x: number; y: number;}type Edge = [Point, Point];/** * 叉乘 */const crossProduct = (v1: number[], v2: number[]) => { const [v1x, v1y] = v1; const [v2x, v2y] = v2; return v1x * v2y - v2x * v1y;};/** * 是否能够相交 * @param baseEedge * @param targetEdge */const isIntersection = (baseEedge: Edge, targetEdge: Edge) => { const [basePointA, basePointB] = baseEedge; const [targetPointC, targetPointD] = targetEdge; const vBase = [basePointA.x - basePointB.x, basePointA.y - basePointB.y]; const vBaseC = [basePointA.x - targetPointC.x, basePointA.y - targetPointC.y]; const vBaseD = [basePointA.x - targetPointD.x, basePointA.y - targetPointD.y]; return crossProduct(vBase, vBaseC) * crossProduct(vBase, vBaseD) <= 0;};/** * 提取数组元素 */const extractArray = (array: Edge[], startIndex: number, length: number) => { const arr = []; for (let i = 0; i < length; i++) { arr.push(array[(startIndex + i) % array.length]); } return arr;};/** * 是否是简单多边形 * @param points 多边形的顶点 */const isComplexPolygon = (points: Point[]) => { const length = points.length; if (length < 4) return false; const edges = points.reduce<Edge[]>((edges, startPoint, i, array) => { const endPoint = array[(i + 1) % length]; edges.push([startPoint, endPoint]); // [起始点, 完结点] return edges; }, []); // 逐边判断 相邻的边无需判断 for (const [i, baseEdge] of Object.entries(edges)) { const nonadjacentEdge = extractArray(edges, Number(i) + 2, edges.length - 3); const flag = nonadjacentEdge.some( (edge) => isIntersection(baseEdge, edge) && isIntersection(edge, baseEdge) ); if (flag) return true; } return false;};
参考资料
简略多边形断定和修复
立体向量疾速入门
向量运算:叉乘
js中罕用的数学方法-用于测试形态与形态是否相交