本文探讨前端JS中利用向量运算判断点是否在多边形内部的方法。通过对比Canvas2D原生API的局限性，引入基于向量叉乘符号判断点与三角形位置关系的算法，并结合earcut库进行三角剖分，实现通用且高效的边界检测方案。
引言
为了深化可视化学习，本文继续探讨向量运算在计算机图形学中的应用。作为基础工具，向量可用于判断多边形边界，但由于边界判定相对复杂，除了向量应用外，还需借助三角剖分工具。本示例通过Canvas2D实现可视化展示。
问题
假设Canvas画布上存在一个如下多边形：
在鼠标移动过程中，期望实现当鼠标进入多边形内部时，更新其填充颜色。这要求我们准确判断鼠标位置是否位于多边形内部，即解决多边形边界判定问题。
思路
首先，将多边形绘制到Canvas画布上。
<canvas width="512" height="512"></canvas>canvas {
width: 512px;
height: 512px;
border: 1px solid #eee;
}const canvas = document.querySelector('canvas');
const ctx = canvas.getContext('2d');
ctx.translate(canvas.width / 2, canvas.height / 2);
ctx.scale(1, -1);
const vertices = [
[ -179.2, 128 ],
[ -102.4, 76.8 ],
[ -64, 181.76 ],
[ -25.6, 143.36 ],
[ -25.6, 33.28 ],
[ 102.4, 53.76 ],
[ 0, -153.6 ],
[ -76.8, -76.8 ],
[ -153.6, -76.8 ],
[ -115.2, 0 ]
];
drawPolygon(vertices);
function drawPolygon(vertices, fillStyle = "red") {
ctx.beginPath();
ctx.moveTo(...vertices[0]);
for (let i = 1; i < vertices.length; i ++) {
ctx.lineTo(...vertices[i]);
}
ctx.closePath();
ctx.fillStyle = fillStyle;
ctx.fill();
}1. 调用API
Canvas2D提供了CanvasRenderingContext2D的isPointInPath方法。
该方法使用简便，只需添加鼠标移动事件监听即可实现检测。
const {left, top} = canvas.getBoundingClientRect();
canvas.addEventListener('mousemove', e => {
const {x: pageX, y: pageY} = e;
// 坐标转化
const offsetX = x - left;
const offsetY = y - top;
// 清除画布
ctx.clearRect(-256, -256, 512, 512);
if (ctx.isPointInPath(offsetX, offsetY)) {
drawPolygon(vetices, "green");
} else {
drawPolygon(vetices);
}
});然而，该API存在显著局限：它仅对当前绘制的图形生效。
例如，若在多边形绘制完成后又绘制了一个小三角形。
const triangle = [
[100, 100],
[100, 200],
[150, 200]
];
drawPolygon(triangle, "blue");为保持小三角形的显示，需修改鼠标监听事件以在每次更新画布时重绘三角形。
canvas.addEventListener('mousemove', e => {
const {pageX: x, pageY: y} = e;
// 坐标转化
const offsetX = x - left;
const offsetY = y - top;
// 清除画布
ctx.clearRect(-256, -256, 512, 512);
if (ctx.isPointInPath(offsetX, offsetY)) {
drawPolygon(vertices, "green");
drawPolygon(triangle, "blue");
} else {
drawPolygon(vertices);
drawPolygon(triangle, "blue");
}
});此时移动鼠标会发现，当鼠标位于多边形内部时，填充颜色不变；仅当鼠标位于小三角形内部时，多边形填充色才发生变化。这体现了Canvas2D Context中isPointInPath方法的局限性。
2. 自定义isPointInPath
为突破Canvas2D内置API的限制，最简单的方法是手动实现自定义的isPointInPath方法。
具体实现如下：
function isPointInPath(x, y) {
// 根据ctx重新clone一个新的Canvas对象
const cloned = ctx.canvas.cloneNode().getContext('2d');
cloned.translate(canvas.width / 2, canvas.height / 2);
cloned.scale(1, -1);
let ret = false;
// 绘制多边形，判断点是否在图形内部
drawPolygon(cloned, vertices, "red");
ret |= cloned.isPointInPath(x, y);
if (!ret) {
// 如果不在，继续绘制小三角形，判断点是否在图形内部
drawPolygon(cloned, triangle, "blue");
ret |= cloned.isPointInPath(x, y);
}
return ret;
}- 首先，基于原画布Context创建新的Canvas对象并获取其上下文。
- 接着绘制多边形，并判断鼠标是否位于多边形内部。
- 若不在多边形内部，则继续判断是否位于三角形内部。
- 最后返回判断结果。
可见，自定义方法内部依然调用了Canvas2D Context的isPointInPath方法。
随后，需修改鼠标监听事件，将判断逻辑替换为自定义的isPointInPath。
此时移动鼠标，当鼠标位于多边形或三角形内部时，多边形填充色均会变化，这得益于自定义方法中的双重判断。
尽管此方式解决了前一种方式的问题，但仍存在缺陷：一是增加了大量冗余的Canvas绘图操作；二是通用性差，若图形修改，isPointInPath方法需随之调整；此外，该方法依赖Canvas2D API，若绘图方式改为WebGL则无法使用。
3. 通用型isPointInPath
因此，我们需要实现更具通用性的isPointInPath方法：直接通过点与几何图形的数学关系判断点是否在图形内，即利用向量进行判断。
直接判断点与几何图形的关系较为困难。此时，可先对多边形进行三角剖分，即将多边形表示为多个三角形的组合；接着逐一判断点与各三角形的关系；最后得出结果。
三角剖分算法较为复杂，此处直接使用成熟且易用的earcut库；剩余关键步骤为判断点与三角形的位置关系。
判断点是否在三角形内部相对简单：
假设三角形的三个顶点为A、B、C，将三条边表示为向量，并将平面上一点D与三角形三个顶点连接得到三个向量。点D位于三角形内部的充分必要条件是：
AB x AD、BC x BD、CA x CD三组向量的叉乘结果符号相同。如下图所示。
- 若点位于三角形内部（如图中的点D），AB到AD、BC到BD、CA到CD的旋转方向均为逆时针，旋转方向一致，故叉乘结果符号相同；
- 若点位于三角形外部（如图中的点D'），AB到AD'和CA到CD'的旋转方向为逆时针，但BC到BD'的旋转方向为顺时针，故三组向量叉乘结果符号不同。
因此，根据上述条件可定义简单的判定函数：
function inTriangle(p1, p2, p3, point) {
const a = p2.copy().minus(p1);
const b = p3.copy().minus(p2);
const c = p1.copy().minus(p3);
const u1 = point.copy().minus(p1);
const u2 = point.copy().minus(p2);
const u3 = point.copy().minus(p3);
const s1 = Math.sign(a.cross(u1));
const s2 = Math.sign(b.cross(u2));
const s3 = Math.sign(c.cross(u3));
return s1 === s2 && s2 === s3;
}该函数前三个参数为三角形顶点，最后一个参数为待判断点，从而判断点是否在三角形内部。
但该函数尚缺一种特殊情况判断，即点恰好位于三角形某条边上的情况。
若点位于三角形的一条边上，需满足以下两个条件：
第一，该点与所在边某顶点形成的向量与该顶点所在边的向量，其叉乘结果为0，即两向量夹角为180度或0度。例如点D在边AB上，则AB x AD为0。
第二，该点与顶点形成的向量与该顶点所在边的向量，其点乘结果除以边长的平方，结果大于等于0且小于等于1。例如点D在边AB上，则0 <= AB·AD/AB² <= 1。
该值表示AD在AB上的投影长度与AB长度的比值。大于零说明两向量夹角为0度，方向相同；小于等于1说明点D在线段AB上。
基于这两个条件，可对上述判定函数进行优化：
function inTriangle(p1, p2, p3, point) {
const a = p2.copy().minus(p1);
const b = p3.copy().minus(p2);
const c = p1.copy().minus(p3);
const u1 = point.copy().minus(p1);
const u2 = point.copy().minus(p2);
const u3 = point.copy().minus(p3);
const s1 = Math.sign(a.cross(u1));
let p = a.dot(u1) / a.length ** 2;
if (s1 === 0 && p >= 0 && p <= 1) return true;
const s2 = Math.sign(b.cross(u2));
p = b.dot(u2) / b.length ** 2;
if (s2 === 0 && p >= 0 && p <= 1) return true;
const s3 = Math.sign(c.cross(u3));
p = c.dot(u3) / c.length ** 2;
if(s3 === 0 && p >= 0 && p <= 1) return true;
return s1 === s2 && s2 === s3;
}如此，即可使用inTriangle函数判断某点是否在三角形内部。
接下来继续完成点在多边形内部的判断：
首先使用earcut库对多边形进行三角剖分处理。
引入earcut库。
<script src="https://unpkg.com/earcut@2.2.4/dist/earcut.dev.js"></script>因earcut库仅接受扁平化的顶点数据，需先用数组的flat方法将顶点扁平化。
const points = vertices.flat();随后将扁平化后的数据传入earcut进行处理。
const triangles = earcut(points);
console.log(triangles);根据打印结果，可见earcut处理结果为一个数组，该triangles数组的元素为顶点数据在vertices数组中的下标；在此数组中，每三个元素对应的顶点构成一个三角形。
至此，完成多边形的三角剖分。
接着逐个判断点是否位于每个三角形内部。
// 判断点是否在多边形内部
// 将多边形进行三角剖分，然后判断点是否在其中某个三角形内部
function isPointInPolygon({vertices, cells}, point) {
let ret = false;
for(let i = 0; i < cells.length; i += 3) {
const p1 = new Vector2D(...vertices[cells[i]]);
const p2 = new Vector2D(...vertices[cells[i + 1]]);
const p3 = new Vector2D(...vertices[cells[i + 2]]);
if (inTriangle(p1, p2, p3, point)) {
ret = true;
break;
}
}
return ret;
}根据返回的布尔值即可确定点是否在多边形内部。
最后，修改鼠标监听事件的处理程序。
const {left, top} = canvas.getBoundingClientRect();
canvas.addEventListener('mousemove', e => {
const {pageX: x, pageY: y} = e;
// 坐标转化
const offsetX = x - left;
const offsetY = y - top;
ctx.clearRect(-256, -256, 512, 512);
const point = new Vector2D((offsetX - canvas.width / 2), (canvas.height / 2 - offsetY)); // 因为Canvas经过坐标转换，所以这里需要把页面上点的坐标也转换一遍，才能正常判断
if (isPointInPolygon({
vertices,
cells: triangles
}, point)
) {
drawPolygon(vertices, "green");
drawPolygon(triangle, "blue");
} else {
drawPolygon(vertices);
drawPolygon(triangle, "blue");
}
});需注意，Canvas2D内置API在判断时会自动转换鼠标对应点的坐标，因此使用自定义方法时，不能直接使用offsetX和offsetY，需自行根据坐标系转换计算点在画布上的坐标。
此时，移动鼠标可见，当鼠标位于多边形内部或边上时，多边形填充色发生改变，说明判断生效；成功应用向量判断了多边形边界。
以上为前端JS可视化学习利用向量判断多边形边界的详细内容，更多关于前端JS可视化学的资料请关注本站其它相关文章！