前端JS可視化學(xué)習(xí)利用向量判斷多邊形邊界
引言
繼續(xù)鞏固我的可視化學(xué)習(xí)，向量運(yùn)算是計(jì)算機(jī)圖形學(xué)的基礎(chǔ)，本例依舊是向量的一種應(yīng)用，利用向量判斷多邊形邊界，但是多邊形的邊界判斷稍微有點(diǎn)復(fù)雜，所以除了應(yīng)用向量之外，還需要借助三角剖分的相關(guān)工具。這個例子中可視化的展示采用Canvas2D來實(shí)現(xiàn)。
問題
假設(shè)Canvas畫布上存在一個如下多邊形：
我們移動鼠標(biāo)的時候，想要實(shí)現(xiàn)一個效果，就是當(dāng)鼠標(biāo)移動到多邊形內(nèi)部的時候，將多邊形內(nèi)部的填充顏色更新成其他顏色；所以此時我們需要判斷鼠標(biāo)是否在多邊形內(nèi)部，這就涉及到多邊形邊界的判斷。
思路
首先我們先將這個多邊形繪制到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. 調(diào)用API
對于Canvas2D而言，有一個API自帶的方法，就是CanvasRenderingContext2D的isPointInPath方法。
這個方法使用起來非常簡單，我們在這個時候直接增加一個鼠標(biāo)移動事件的監(jiān)聽就可以。
const {left, top} = canvas.getBoundingClientRect();
canvas.addEventListener('mousemove', e => {
const {x: pageX, y: pageY} = e;
// 坐標(biāo)轉(zhuǎn)化
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的使用存在很大的局限性，就是它只能針對當(dāng)前繪制的圖形生效。
就比如說，如果在完成這個多邊形的繪制之后，又繪制了一個小三角形。
const triangle = [ [100, 100], [100, 200], [150, 200] ]; drawPolygon(triangle, "blue");
為了保持這個小三角形，我們還需要修改鼠標(biāo)監(jiān)聽事件，以達(dá)到更新畫布時，三角形依舊被繪制。
canvas.addEventListener('mousemove', e => {
const {pageX: x, pageY: y} = e;
// 坐標(biāo)轉(zhuǎn)化
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");
}
});此時我們再移動鼠標(biāo)，就會發(fā)現(xiàn)，在鼠標(biāo)移動到多邊形內(nèi)部時，多邊形的填充顏色并不會變，但是當(dāng)鼠標(biāo)移動到小三角形內(nèi)部時，多邊形的填充色發(fā)生了變化；這就是Canvas2D Context的isPointInPath方法所存在的局限性。
2. 自定義isPointInPath
為了突破Canvas2D API中自帶方法的局限性，最簡單的方法就是，我們手動自定義一個自己的isPointInPath方法。
具體實(shí)現(xiàn)如下：
function isPointInPath(x, y) {
// 根據(jù)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;
// 繪制多邊形，判斷點(diǎn)是否在圖形內(nèi)部
drawPolygon(cloned, vertices, "red");
ret |= cloned.isPointInPath(x, y);
if (!ret) {
// 如果不在，繼續(xù)繪制小三角形，判斷點(diǎn)是否在圖形內(nèi)部
drawPolygon(cloned, triangle, "blue");
ret |= cloned.isPointInPath(x, y);
}
return ret;
}- 首先，根據(jù)原畫布的Context創(chuàng)建一個新的Canvas對象并獲取它的上下文
- 然后繪制多邊形，并判斷鼠標(biāo)是否在多邊形內(nèi)部
- 如果不在多邊形內(nèi)部，繼續(xù)判斷是否在三角形內(nèi)部
- 最后將結(jié)果返回
可以看到，在這個自定義的方法內(nèi)部，我們依然是調(diào)用了Canvas2D Context的isPointInPath方法。
接著我們還需要修改鼠標(biāo)的監(jiān)聽事件，把判斷方法改為我們自定義的isPointInPath。
此時移動鼠標(biāo)，可以看到，當(dāng)鼠標(biāo)移動到多邊形或者三角形內(nèi)部，都可以使多邊形的填充色發(fā)生變化；這就是因?yàn)槲覀冊谧远x的isPointInPath中做的兩次判斷。
但是我們也能發(fā)現(xiàn)，雖然這種方式解決了我們在第一種方式中所碰到的問題，卻也存在其他問題，第一，是增加了很多無謂的Canvas繪圖操作；第二，是通用性差，如果圖形有修改，那么isPointInPath方法就要跟著修改，并且這個方法依賴于Canvas2D的API，如果哪天修改了繪圖方式，比如改為使用WebGL，就不能使用了。
3. 通用型isPointInPath
所以我們需要實(shí)現(xiàn)一個更具通用性的isPointInPath方法：直接通過點(diǎn)與幾何圖形的數(shù)學(xué)關(guān)系來判斷點(diǎn)是否在圖形內(nèi)，也就是我們標(biāo)題中所說的利用向量來判斷。
但是直接判斷點(diǎn)與幾何圖形的關(guān)系，還是比較困難的。這個時候，我們可以先對多邊形進(jìn)行三角剖分，三角剖分可以簡單地理解為是把多邊形表示成由多個三角形組合而成的形式；接著將點(diǎn)和對應(yīng)的多個三角形的關(guān)系進(jìn)行逐一判斷；最后得出結(jié)果。
對于三角剖分，涉及的算法稍復(fù)雜，這里我們直接使用一個成熟的、使用起來比較簡單的庫——earcut；然后就剩下最關(guān)鍵的一步，就是點(diǎn)和三角形的位置判斷。
判斷點(diǎn)是否在三角形內(nèi)部，就相對比較簡單了：
假設(shè)三角形的三個點(diǎn)是A、B、C，把三角形的三條邊分別使用向量表示，再將平面上一個點(diǎn)D連接三角形三個頂點(diǎn)得到三個向量，那么點(diǎn)D在三角形內(nèi)部的充分必要條件就是：
AB x AD、BC x BD、CA x CD三組向量的叉乘結(jié)果符號相同。就如下圖所示。
- 如果點(diǎn)在三角形內(nèi)部，就如圖上的點(diǎn)D，可以看出AB 到 AD、BC 到 BD、CA 到 CD的旋轉(zhuǎn)方向都是逆時針，旋轉(zhuǎn)方向相同，所以最后的叉乘結(jié)果符號都是相同的；
- 而如果點(diǎn)在三角形外部，就如圖上的點(diǎn)D'，可以看出AB到AD'和CA到CD'的旋轉(zhuǎn)方向是逆時針，但BC到BD'的旋轉(zhuǎn)方向是順時針，所以三組向量叉乘的結(jié)果符號并不相同
因此根據(jù)上述條件，就可以定義一個簡單的判定函數(shù)：
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;
}這個函數(shù)的前三個參數(shù)是三角形的三個頂點(diǎn)，最后一個參數(shù)是待判斷的點(diǎn)；這樣就能判斷點(diǎn)是否在三角形內(nèi)部了。
但是這個函數(shù)中還缺少一種特殊情況的判斷，就是點(diǎn)恰好在三角形某條邊上的情況。
如果一個點(diǎn)在三角形的一條邊上，那它需要滿足以下2個條件：
第一，它和所在邊某個頂點(diǎn)形成的向量與這個頂點(diǎn)所在邊的向量，這兩個向量的叉乘結(jié)果為0，即這兩個向量的夾角為180度或0度。比如點(diǎn)D在邊AB上，則AB x AD為0
第二，它和這個頂點(diǎn)形成的向量與這個頂點(diǎn)所在邊的向量，這兩個向量的點(diǎn)乘結(jié)果除以邊長的平方，結(jié)果大于等于0且小于等于1。比如點(diǎn)D在邊AB上，則0<= AB·AD/AB² <=1
這個值也就是AD在AB上的投影的長度，與AB長度的比值，大于零，說明兩個向量的夾角是0度，為同一方向，小于等于1，也就說明點(diǎn)D在線段AB上。
根據(jù)這兩個條件，我們可以對上面的判定函數(shù)進(jìn)行優(yōu)化：
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函數(shù)對某個點(diǎn)是否在三角形內(nèi)部進(jìn)行判斷了。
現(xiàn)在我們來繼續(xù)完成對點(diǎn)在多邊形內(nèi)部的判斷：
首先使用earcut庫對多邊形進(jìn)行三角剖分處理
引入earcut庫
<script src="https://unpkg.com/earcut@2.2.4/dist/earcut.dev.js"></script>
因?yàn)閑arcut庫只接受扁平化的頂點(diǎn)數(shù)據(jù)，我們需要先用數(shù)組的flat方法將頂點(diǎn)扁平化
const points = vertices.flat();
然后我們就可以把扁平化后的數(shù)據(jù)傳給earcut進(jìn)行處理了
const triangles = earcut(points); console.log(triangles);
根據(jù)打印結(jié)果，可以看到earcut的處理結(jié)果是一個數(shù)組，這個triangles數(shù)組的元素是頂點(diǎn)數(shù)據(jù)在vertices數(shù)組中的下標(biāo)；在這個數(shù)組中，每三個元素所對應(yīng)的頂點(diǎn)就構(gòu)成一個三角形。
這樣我們就完成了多邊形的三角剖分。
接著逐個判斷點(diǎn)是否在每個三角形內(nèi)部。
// 判斷點(diǎn)是否在多邊形內(nèi)部
// 將多邊形進(jìn)行三角剖分，然后判斷點(diǎn)是否在其中某個三角形內(nèi)部
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;
}根據(jù)返回的布爾值就可以知道點(diǎn)是否在多邊形內(nèi)部。
最后就是修改鼠標(biāo)監(jiān)聽事件的處理程序。
const {left, top} = canvas.getBoundingClientRect();
canvas.addEventListener('mousemove', e => {
const {pageX: x, pageY: y} = e;
// 坐標(biāo)轉(zhuǎn)化
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)); // 因?yàn)镃anvas經(jīng)過坐標(biāo)轉(zhuǎn)換，所以這里需要把頁面上點(diǎn)的坐標(biāo)也轉(zhuǎn)換一遍，才能正常判斷
if (isPointInPolygon({
vertices,
cells: triangles
}, point)
) {
drawPolygon(vertices, "green");
drawPolygon(triangle, "blue");
} else {
drawPolygon(vertices);
drawPolygon(triangle, "blue");
}
});這里需要注意，Canvas2D自帶的API在進(jìn)行判斷時，應(yīng)該是自動對鼠標(biāo)對應(yīng)的點(diǎn)的坐標(biāo)進(jìn)行了轉(zhuǎn)換，所以我們使用自定義的方法時，不能直接使用offsetX和offsetY，需要自己去將點(diǎn)的坐標(biāo)根據(jù)坐標(biāo)系的轉(zhuǎn)換計(jì)算出對應(yīng)在畫布上的坐標(biāo)。
此時，我們再去移動鼠標(biāo)，就可以看到，當(dāng)鼠標(biāo)移動到多邊形內(nèi)部或者多邊形的邊時，多邊形的填充色發(fā)生了改變，也就說明我們的判斷生效了；這就成功應(yīng)用了向量來判斷多邊形邊界。
以上就是前端JS可視化學(xué)習(xí)利用向量判斷多邊形邊界的詳細(xì)內(nèi)容，更多關(guān)于前端JS可視化學(xué)的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
videojs+swiper實(shí)現(xiàn)淘寶商品詳情輪播圖
這篇文章主要為大家詳細(xì)介紹了videojs+swiper實(shí)現(xiàn)淘寶商品詳情輪播圖，輪播翻動，視頻暫停，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-04-04
微信小程序 簡易計(jì)算器實(shí)現(xiàn)代碼實(shí)例
這篇文章主要介紹了微信小程序 簡易計(jì)算器實(shí)現(xiàn)代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-09-09
js純前端實(shí)現(xiàn)騰訊cos文件上傳功能的示例代碼
這篇文章主要介紹了vue純前端實(shí)現(xiàn)騰訊cos文件上傳功能的示例代碼,小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-05-05
js實(shí)現(xiàn)當(dāng)鼠標(biāo)移到表格上時顯示這一格全部內(nèi)容的代碼
下面小編就為大家?guī)硪黄猨s實(shí)現(xiàn)當(dāng)鼠標(biāo)移到表格上時顯示這一格全部內(nèi)容的代碼。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-06-06
在TypeScript中,泛型是一種創(chuàng)建可復(fù)用代碼組件的工具。這種組件不只能被一種類型使用,而是能被多種類型復(fù)用。類似于參數(shù)的作用,泛型是一種用以增強(qiáng)類(classes)、類型(types)和接口(interfaces)能力的非常可靠的手段2022-09-09
面向?qū)ο蟆脒M(jìn)行執(zhí)行某個事件，就去找事件對應(yīng)的對象，把事情落實(shí)到對象身上，在程序中一切皆是對象，對象包含屬性和方法，面向?qū)ο笕筇卣鳎悍庋b、繼承、多態(tài)2022-10-10
這篇文章主要為大家詳細(xì)介紹了js實(shí)現(xiàn)拖動緩動效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-01-01
本節(jié)主要介紹了javascript獲取函數(shù)形參個數(shù)的具體實(shí)現(xiàn)，需要的朋友可以參考下2014-07-07
OpenCV.js實(shí)現(xiàn)喬丹動圖素描效果圖文教程
這篇文章主要為大家介紹了OpenCV.js實(shí)現(xiàn)喬丹動圖素描效果的圖文教程示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-08-08
Bootstrap的Carousel配合dropload.js實(shí)現(xiàn)移動端滑動切換圖片
這篇文章主要介紹了bootstrap的Carousel配合dropload.js實(shí)現(xiàn)移動端滑動切換圖片,實(shí)現(xiàn)方法非常簡單，具有參考借鑒價值，需要的朋友可以參考下2017-03-03