共计 2754 个字符，预计需要花费 7 分钟才能阅读完成。
标注场景下，用户能够选取多点框选一个区域，这样会生成一个多边形。但某些多边形不适宜标注场景，还会减少其余参数计算复杂度，须要判断进去禁止绘制。
分类
依据标注的场景，能够将多边形演绎为边有交点多边形与边无无交点多边形。如图：
这样实际上就是多边形划分中的简略多边形与简单多边形。
咱们能够通过多边形边之间是否有相交来判断。
判断
怎么判断变是否相交呢？
如果去计算交点是否落于连线上，不仅计算量大，而且还会因为比拟精度等问题导致麻烦。这类问题早已有更好的计划：相交的线段的特色是端点别离位于相交的线段两侧，只须要判断两个端点是否在线段两侧就能判断线段是否能相交。
以左边简单多边形举例：
\(点_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 中罕用的数学方法 - 用于测试形态与形态是否相交
