# 視覺化學習：利用向量判斷多邊形邊界

2023-11-30 15:01:11

### 思路

``````<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

``````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);
}
});
``````

``````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");
}
});
``````

#### 2. 自定義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物件並獲取它的上下文
• 然後繪製多邊形，並判斷滑鼠是否在多邊形內部
• 如果不在多邊形內部，繼續判斷是否在三角形內部
• 最後將結果返回

#### 3. 通用型isPointInPath

AB x AD、BC x BD、CA x CD三組向量的叉乘結果符號相同。就如下圖所示。

• 如果點在三角形內部，就如圖上的點D，可以看出AB 到 AD、BC 到 BD、CA 到 CD的旋轉方向都是逆時針，旋轉方向相同，所以最後的叉乘結果符號都是相同的；

``````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

``````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;
}
``````

1. 首先使用earcut庫對多邊形進行三角剖分處理

1. 引入earcut庫

``````<script src="https://unpkg.com/[email protected]/dist/earcut.dev.js"></script>
``````
2. 因為earcut庫只接受扁平化的頂點資料，我們需要先用陣列的flat方法將頂點扁平化

``````const points = vertices.flat();
``````
3. 然後我們就可以把扁平化後的資料傳給earcut進行處理了

``````const triangles = earcut(points);
console.log(triangles);
``````

根據列印結果，可以看到earcut的處理結果是一個陣列，這個triangles陣列的元素是頂點資料在vertices陣列中的下標；在這個陣列中，每三個元素所對應的頂點就構成一個三角形。

這樣我們就完成了多邊形的三角剖分。

2. 接著逐個判斷點是否在每個三角形內部。

``````// 判斷點是否在多邊形內部
// 將多邊形進行三角剖分，然後判斷點是否在其中某個三角形內部
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;
}
``````

根據返回的布林值就可以知道點是否在多邊形內部。

3. 最後就是修改滑鼠監聽事件的處理程式。

``````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，需要自己去將點的座標根據座標系的轉換計算出對應在畫布上的座標。