銀行pos機(jī)刷卡資金流程圖

新聞資訊2 | 2023-07-18 22:52 | 投稿人：pos機(jī)之家

網(wǎng)上有很多關(guān)于銀行pos機(jī)刷卡資金流程圖,如何連接流程圖的兩個節(jié)點的知識，也有很多人為大家解答關(guān)于銀行pos機(jī)刷卡資金流程圖的問題，今天pos機(jī)之家(www.www690aa.com)為大家整理了關(guān)于這方面的知識，讓我們一起來看下吧!

本文目錄一覽：

1、銀行pos機(jī)刷卡資金流程圖

銀行pos機(jī)刷卡資金流程圖

如果你用過流程圖繪制工具，那么可能會好奇節(jié)點之間的連接線是如何計算出來的：

不要走開，跟隨本文一起來探究一下吧。

最終效果預(yù)覽：https://wanglin2.github.io/AssociationLineDemo/[1]

基本結(jié)構(gòu)

先使用Vue3搭建一下頁面的基本結(jié)構(gòu)，為了簡化canvas操作，我們使用konvajs[2]庫來繪制圖形。

頁面模板部分，提供一個容器即可：

js部分，主要是使用konvajs來創(chuàng)建兩個可拖拽的矩形元素及一個連接線元素，當(dāng)然目前連接線并沒有頂點數(shù)據(jù)：

import { onMounted, ref } from "vue";import Konva from "konva";const container = ref(null);// 創(chuàng)建兩個矩形、一個折線元素let layer, rect1, rect2, line;// 矩形移動事件const onDragMove = () => { // 獲取矩形實時位置 console.log(rect1.x(), rect1.y(), rect2.x(), rect2.y());};// 初始化圖形const init = () => { const { width="360px",height="auto" />

效果如下：

接下來我們只要在圖形拖拽時實時計算出關(guān)聯(lián)線的頂點然后更新到折線元素里就可以繪制出這條連接線。

計算出關(guān)聯(lián)線最有可能經(jīng)過的點

整個畫布上所有的點其實都是可能經(jīng)過的點，但是我們的連接線是【橫平豎直】的，且要盡可能是最短路線，所以考慮所有的點沒有必要，我們可以按照一定規(guī)則縮小范圍，然后再從中計算出最優(yōu)路線。

首先起點和終點兩個點肯定是必不可少的，以下圖為例，假設(shè)我們要從左上角的矩形頂部中間位置連接到右下角的矩形頂部中間位置：

接下來我們定兩個原則：

1.連接線盡量不能和圖形的邊重疊

2.連接線盡量不能穿過元素

為什么說盡量呢，因為當(dāng)兩個元素距離過近或有重疊的話這些都是無法避免的。

結(jié)合上面兩個原則我們可以規(guī)定元素周圍一定距離內(nèi)都不允許線經(jīng)過（當(dāng)然除了連接起終點的線段），這樣就相當(dāng)于給元素外面套了個矩形的包圍框：

經(jīng)過起終點且垂直于起終點所在邊的直線與包圍框的交點一定是會經(jīng)過的，并且這兩個點是唯一能直接和起終點相連的點，所以我們可以把這兩個點當(dāng)做是“起點"和"終點”，這樣在計算的時候可以少計算兩個點：

在矩形移動事件里進(jìn)行點的計算，首先緩存一下矩形的位置和尺寸信息，然后定義起點和終點的坐標(biāo)，最后定義一個數(shù)組用來存放所有可能經(jīng)過的點：

// 矩形移動事件const onDragMove = () => { computedProbablyPoints();};// 計算所有可能經(jīng)過的點let rect1X, rect1Y, rect1W, rect1H, rect2X, rect2Y, rect2W, rect2H;let startPoint = null, endPoint = null;const computedProbablyPoints = () => { // 保存矩形的尺寸、位置信息 rect1X = rect1.x(); rect1Y = rect1.y(); rect1W = rect1.width="360px",height="auto" />

因為起終點可以在矩形的任一方向，所以我們寫個方法來獲取偽起點和偽終點，并將它們添加到數(shù)組里：

const computedProbablyPoints = () => { // ... // 偽起點：經(jīng)過起點且垂直于起點所在邊的線與包圍框線的交點 let fakeStartPoint = findStartNextOrEndPrePoint(rect1, startPoint); points.push(fakeStartPoint); // 偽終點：經(jīng)過終點且垂直于終點所在邊的線與包圍框線的交點 let fakeEndPoint = findStartNextOrEndPrePoint(rect2, endPoint); points.push(fakeEndPoint);}// 找出起點的下一個點或終點的前一個點const MIN_DISTANCE = 30;const findStartNextOrEndPrePoint = (rect, point) => { // 起點或終點在左邊 if (point[0] === rect.x()) { return [rect.x() - MIN_DISTANCE, rect.y() + rect.height() / 2]; } else if (point[1] === rect.y()) { // 起點或終點在上邊 return [rect.x() + rect.width="360px",height="auto" />

偽起點和偽終點會形成一個矩形，這個矩形和起點元素包圍框可以組成一個更大的矩形，這個矩形的四個角是連接線有可能經(jīng)過的點：

將這幾個點添加到數(shù)組里，有一個點和偽終點重復(fù)了，不過沒關(guān)系，我們最后再去重即可：

從圖上可以看出來，關(guān)聯(lián)線要么從右邊連過去，要么從左邊連過去。

同樣，偽起點和偽終點形成的矩形也會和終點元素包圍框形成一個更大的矩形，這個矩形的四個頂點也是有可能會經(jīng)過的，這當(dāng)終點元素位于起點元素上方時會經(jīng)過：

// 偽起點和偽終點形成的矩形和終點元素包圍框組成一個大矩形的四個頂點points.push( ...getBoundingBox([ // 偽起點終點 fakeStartPoint, fakeEndPoint, // 終點元素包圍框 [rect2X - MIN_DISTANCE, rect2Y - MIN_DISTANCE], // 左上頂點 [rect2X + rect2W + MIN_DISTANCE, rect2Y + rect2H + MIN_DISTANCE], // 右下頂點 ]));

以上這些點基本能滿足起終點都在元素上方的情況，但是對于下面這種起點在上面終點在左邊情況就不行了：

很明顯看到如果存在下面這個點就可以了：

這其實就是前面所說的經(jīng)過起終點且垂直于起終點所在邊的兩條線的交點，求交點可以先根據(jù)兩個點計算出直線方程，再聯(lián)立兩個方程計算交點，但是我們的線都是橫平豎直的，所以沒必要這么麻煩，兩條線要么是平行的，要么是一條水平一條垂直，很容易羅列完所有情況：

// 計算兩條線段的交點const getIntersection = (seg1, seg2) => { // 兩條垂直線不會相交 if (seg1[0][0] === seg1[1][0] && seg2[0][0] === seg2[1][0]) { return null; } // 兩條水平線不會相交 if (seg1[0][1] === seg1[1][1] && seg2[0][1] === seg2[1][1]) { return null; } // seg1是水平線、seg2是垂直線 if (seg1[0][1] === seg1[1][1] && seg2[0][0] === seg2[1][0]) { return [seg2[0][0], seg1[0][1]]; } // seg1是垂直線、seg2是水平線 if (seg1[0][0] === seg1[1][0] && seg2[0][1] === seg2[1][1]) { return [seg1[0][0], seg2[0][1]]; }};

有了這個方法我們就可以把這個交點添加到數(shù)組里：

const computedProbablyPoints = () => { // ... // 經(jīng)過起點且垂直于起點所在邊的線與經(jīng)過終點且垂直于終點所在邊的線的交點 let startEndPointVerticalLineIntersection = getIntersection([startPoint, fakeStartPoint], [endPoint, fakeEndPoint]); startEndPointVerticalLineIntersection && points.push(startEndPointVerticalLineIntersection);}

到這里計算出來的點能滿足大部分情況了，但是還有一種情況滿足不了，當(dāng)起終點相對時：

所以當(dāng)前面計算的startEndPointVerticalLineIntersection點不存在的時候我們就計算經(jīng)過偽起點和偽終點的一條垂直線和一條水平線的交點（黃色的兩個點）：

const computedProbablyPoints = () => { // ... // 當(dāng) 經(jīng)過起點且垂直于起點所在邊的線與經(jīng)過終點且垂直于終點所在邊的線平行時，計算一條垂直線與經(jīng)過另一個點的偽點的水平線的節(jié)點 if (!startEndPointVerticalLineIntersection) { let p1 = getIntersection( [startPoint, fakeStartPoint],// 假設(shè)經(jīng)過起點的垂直線是垂直的 [fakeEndPoint, [fakeEndPoint[0] + 10, fakeEndPoint[1]]]// 那么就要計算經(jīng)過偽終點的水平線。水平線上的點y坐標(biāo)相同，所以x坐標(biāo)隨便加減多少數(shù)值都可以 ); p1 && points.push(p1); let p2 = getIntersection( [startPoint, fakeStartPoint],// 假設(shè)經(jīng)過起點的垂直線是水平的 [fakeEndPoint, [fakeEndPoint[0], fakeEndPoint[1] + 10]]// 那么就要計算經(jīng)過偽終點的垂直線。 ); p2 && points.push(p2); // 下面同上 let p3 = getIntersection( [endPoint, fakeEndPoint], [fakeStartPoint, [fakeStartPoint[0] + 10, fakeStartPoint[1]]] ); p3 && points.push(p3); let p4 = getIntersection( [endPoint, fakeEndPoint], [fakeStartPoint, [fakeStartPoint[0], fakeStartPoint[1] + 10]] ); p4 && points.push(p4); }}

到這里可能經(jīng)過的點就找的差不多了，一共有：

接下來進(jìn)行去重以及導(dǎo)出相關(guān)的數(shù)據(jù)：

如果不考慮效率和最短距離，我們可以直接使用廣度優(yōu)先搜索或者說是回溯算法，也就是從起點開始，挨個嘗試起點周邊的點，到下一個點又挨個嘗試下一個點周邊所有的點，如果遇到終點，那么結(jié)束，把所經(jīng)過的點連接起來就是一條路徑，接下來我們嘗試一下。

在開始算法之前需要先實現(xiàn)如何找出一個點周邊的點，如果是在網(wǎng)格中，那么很簡單，一個點周邊的點就是x、y坐標(biāo)加1或減1，但是我們這些點彼此之間的距離是不確定的，所以只能根據(jù)坐標(biāo)進(jìn)行搜索，比如要找一個點右邊最近的點，那么根據(jù)該點的y坐標(biāo)進(jìn)行搜索，看有沒有y坐標(biāo)相同的點，有的話再找出其中最近的，當(dāng)然，還要檢測找出的這個點和目標(biāo)點的連線是否會穿過起終點元素，是的話這個點也要跳過：

// 找出一個點周邊的點const getNextPoints = (point, points) => { let [x, y] = point; let xSamePoints = []; let ySamePoints = []; // 找出x或y坐標(biāo)相同的點 points.forEach((item) => { // 跳過目標(biāo)點 if (checkIsSamePoint(point, item)) { return; } if (item[0] === x) { xSamePoints.push(item); } if (item[1] === y) { ySamePoints.push(item); } }); // 找出x方向最近的點 let xNextPoints = getNextPoint(x, y, ySamePoints, "x"); // 找出y方向最近的點 let yNextPoints = getNextPoint(x, y, xSamePoints, "y"); return [...xNextPoints, ...yNextPoints];};// 檢測是否為同一個點const checkIsSamePoint = (a, b) => { if (!a || !b) { return false; } return a[0] === b[0] && a[1] === b[1];};

接下來就是getNextPoint方法的實現(xiàn)：

// 找出水平或垂直方向上最近的點const getNextPoint = (x, y, list, dir) => { let index = dir === "x" ? 0 : 1;// 求水平方向上最近的點，那么它們y坐標(biāo)都是相同的，要比較x坐標(biāo)，反之亦然 let value = dir === "x" ? x : y; let nextLeftTopPoint = null; let nextRIghtBottomPoint = null; for (let i = 0; i < list.length; i++) { let cur = list[i]; // 檢查當(dāng)前點和目標(biāo)點的連線是否穿過起終點元素 if (checkLineThroughElements([x, y], cur)) { continue; } // 左側(cè)或上方最近的點 if (cur[index] < value) { if (nextLeftTopPoint) { if (cur[index] > nextLeftTopPoint[index]) { nextLeftTopPoint = cur; } } else { nextLeftTopPoint = cur; } } // 右側(cè)或下方最近的點 if (cur[index] > value) { if (nextRIghtBottomPoint) { if (cur[index] < nextRIghtBottomPoint[index]) { nextRIghtBottomPoint = cur; } } else { nextRIghtBottomPoint = cur; } } } return [nextLeftTopPoint, nextRIghtBottomPoint].filter((point) => { return !!point; });};

checkLineThroughElements方法用來判斷一條線段是否穿過或和起終點元素有重疊，也是一個簡單的比較邏輯：

// 檢查兩個點組成的線段是否穿過起終點元素const checkLineThroughElements = (a, b) => { let rects = [rect1, rect2]; let minX = Math.min(a[0], b[0]); let maxX = Math.max(a[0], b[0]); let minY = Math.min(a[1], b[1]); let maxY = Math.max(a[1], b[1]); // 水平線 if (a[1] === b[1]) { for (let i = 0; i < rects.length; i++) { let rect = rects[i]; if ( minY >= rect.y() && minY <= rect.y() + rect.height() && minX <= rect.x() + rect.width="360px",height="auto" />

接下來就可以使用回溯算法來找出其中的一條路徑，回溯算法很簡單，因為不是本文的重點，所以就不詳細(xì)介紹了，有興趣的可以閱讀回溯（DFS）算法解題套路框架[3]。

計算出坐標(biāo)點后再更新連線元素，記得要把我們真正的起點和終點坐標(biāo)加上去：

// 矩形移動事件const onDragMove = () => { // 計算出所有可能的點 let { startPoint, endPoint, fakeStartPoint, fakeEndPoint, points } = computedProbablyPoints(); // 使用回溯算法找出其中一條路徑 const routes = useDFS(fakeStartPoint, fakeEndPoint, points); // 更新連線元素 line.points( // 加上真正的起點和終點 (routes.length > 0 ? [startPoint, ...routes, endPoint] : []).reduce( (path, cur) => { path.push(cur[0], cur[1]); return path; }, [] ) );};// 使用回溯算法尋找路徑const useDFS = (startPoint, endPoint, points) => { let res = []; let used = {}; let track = (path, selects) => { for (let i = 0; i < selects.length; i++) { let cur = selects[i]; // 到達(dá)終點了 if (checkIsSamePoint(cur, endPoint)) { res = [...path, cur]; break; } let key = cur[0] + "-" + cur[1]; // 該點已經(jīng)被選擇過了 if (used[key]) { continue; } used[key] = true; track([...path, cur], getNextPoints(cur, points)); used[key] = false; } }; track([], [startPoint]); return res;};

效果如下：

可以看到確實計算出了一條連接線路徑，但是顯然不是最短路徑，并且回溯算法是一種暴力算法，點多了可能會存在性能問題。

使用A*算法結(jié)合曼哈頓路徑計算最短路徑

前面我們使用回溯算法找出了其中一條關(guān)聯(lián)線路徑，但是很多情況下計算出來的路徑都不是最短的，接下來我們就使用A*算法來找出最短路徑。

A*算法和回溯算法有點相似，但是不是盲目的挨個遍歷一個點周圍的點，而是會從中找出最有可能的點優(yōu)先進(jìn)行嘗試，完整的算法過程描述如下：

1.創(chuàng)建兩個數(shù)組，openList存放待遍歷的點，closeList存放已經(jīng)遍歷的點；

2.將起點放入openList中；

3.如果openList不為空，那么從中選取優(yōu)先級最高的點，假設(shè)為n：

3.1.如果n為終點，那么結(jié)束循環(huán)，從n出發(fā)，依次向前找出父節(jié)點，也就是最短路徑；

3.2.如果n不為終點，那么：

3.2.1.將n從openList中刪除，添加到closeList中；

3.2.2.遍歷n周圍的點：

3.2.2.1.如果該點在closeList中，那么跳過該點；

3.2.2.2.如果該點也不在openList中，那么：

3.2.2.2.1.設(shè)置n為該點的父節(jié)點；

3.2.2.2.2.計算該點的代價，代價越高，優(yōu)先級越低，反之越高；

3.3.3.3.3.將該點添加到openList；

3.2.3.繼續(xù)3的循環(huán)過程，直到找到終點，或openList為空，沒有結(jié)果；

根據(jù)以上過程，我們創(chuàng)建一個A*類：

// A*算法類class AStar { constructor() { this.startPoint = null; this.endPoint = null; this.pointList = []; // 存放待遍歷的點 this.openList = []; // 存放已經(jīng)遍歷的點 this.closeList = []; } // 算法主流程 start(startPoint, endPoint, pointList) { this.startPoint = startPoint; this.endPoint = endPoint; this.pointList = pointList; this.openList = [ { point: this.startPoint, // 起點加入openList cost: 0, // 代價 parent: null, // 父節(jié)點 }, ]; this.closeList = []; while (this.openList.length) { // 在openList中找出優(yōu)先級最高的點 let point = this.getBestPoint(); // point為終點，那么算法結(jié)束，輸出最短路徑 if (checkIsSamePoint(point.point, this.endPoint)) { return this.getRoutes(point); } else { // 將point從openList中刪除 this.removeFromOpenList(point); // 將point添加到closeList中 this.closeList.push(point); // 遍歷point周圍的點 let nextPoints = getNextPoints(point.point, this.pointList); for (let i = 0; i < nextPoints.length; i++) { let cur = nextPoints[i]; // 如果該點在closeList中，那么跳過該點 if (this.checkIsInList(cur, this.closeList)) { continue; } else if (!this.checkIsInList(cur, this.openList)) { // 如果該點也不在openList中 let pointObj = { point: cur, parent: point,// 設(shè)置point為當(dāng)前點的父節(jié)點 cost: 0, }; // 計算當(dāng)前點的代價 this.computeCost(pointObj); // 添加到openList中 this.openList.push(pointObj); } } } } return [] } // 獲取openList中優(yōu)先級最高的點，也就是代價最小的點 getBestPoint() { let min = Infinity; let point = null; this.openList.forEach((item) => { if (item.cost < min) { point = item; min = item.cost; } }); return point; } // 從point出發(fā)，找出其所有祖宗節(jié)點，也就是最短路徑 getRoutes(point) { let res = [point]; let par = point.parent; while (par) { res.unshift(par); par = par.parent; } return res.map((item) => { return item.point; }); } // 將點從openList中刪除 removeFromOpenList(point) { let index = this.openList.findIndex((item) => { return checkIsSamePoint(point.point, item.point); }); this.openList.splice(index, 1); } // 檢查點是否在列表中 checkIsInList(point, list) { return list.find((item) => { return checkIsSamePoint(item.point, point); }); } // 計算一個點的代價 computeCost(point) { // TODO }}

代碼有點長，但是邏輯很簡單，start方法基本就是對前面的算法過程進(jìn)行還原，其他就是一些輔助工具方法，只有一個computeCost方法暫時沒有實現(xiàn)，這個方法也就是A*算法的核心。

A*算法的所說的節(jié)點優(yōu)先級是由兩部分決定的：

f(n) = g(n) + h(n)

g(n)代表節(jié)點n距離起點的代價。

f(n)代表節(jié)點n到終點的代價，當(dāng)然這個代價只是預(yù)估的。

f(n)為g(n)加上h(n)，就代表節(jié)點n的綜合代價，也就是優(yōu)先級，代價越低，當(dāng)然優(yōu)先級越高，修改一下computeCost方法，拆解成兩個方法：

// 計算一個點的優(yōu)先級computePriority(point) { point.cost = this.computedGCost(point) + this.computedHCost(point);}

g(n)的計算很簡單，把它所有祖先節(jié)點的代價累加起來即可：

// 計算代價g(n)computedGCost(point) { let res = 0; let par = point.parent; while (par) { res += par.cost; par = par.parent; } return res;}

而h(n)的計算就會用到曼哈頓距離，兩個點的曼哈頓距離指的就是這兩個點的水平和垂直方向的距離加起來的總距離：

對于我們的計算，也就是當(dāng)前節(jié)點到終點的曼哈頓距離：

// 計算代價h(n)computedHCost(point) { return ( Math.abs(this.endPoint[0] - point.point[0]) + Math.abs(this.endPoint[1] - point.point[1]) );}

接下來實例化一個AStar類，然后使用它來計算最短路徑：

const aStar = new AStar();const onDragMove = () => { let { startPoint, endPoint, fakeStartPoint, fakeEndPoint, points } = computedProbablyPoints(startPos.value, endPos.value); const routes = aStar.start(fakeStartPoint, fakeEndPoint, points); // 更新連線元素 // ...}

可以看到不會出現(xiàn)回溯算法計算出來的超長路徑。

優(yōu)化

到上一節(jié)已經(jīng)基本可以找出最短路徑，但是會存在幾個問題，本小節(jié)來試著優(yōu)化一下。

1.連接線突破了包圍框

如上圖所示，垂直部分的連接線顯然離元素過近，雖然還沒有和元素重疊，但是已經(jīng)突破了包圍框，更好的連接點應(yīng)該是右邊兩個，下圖的情況也是類似的：

解決方法也很簡單，前面我們實現(xiàn)了一個判斷線段是否穿過或和起終點元素重疊的方法，我們修改一下比較條件，把比較對象由元素本身改成元素的包圍框：

export const checkLineThroughElements = (a, b) => { // ... // 水平線 if (a[1] === b[1]) { for (let i = 0; i < rects.length; i++) { let rect = rects[i]; if ( minY > rect.y() - MIN_DISTANCE &&// 增加或減去MIN_DISTANCE來將比較目標(biāo)由元素改成元素的包圍框 minY < rect.y() + rect.height() + MIN_DISTANCE && minX < rect.x() + rect.width="360px",height="auto" />

效果如下：

2.距離太近沒有連接線

目前我們的邏輯如果當(dāng)兩個元素太近了，那么是計算不出來符合要求的點的，自然就沒有線了：

解決方法也很簡單，當(dāng)?shù)谝淮温窂接嬎銢]有結(jié)果時我們假設(shè)是因為距離很近導(dǎo)致的，然后我們再以寬松模式計算一次，所謂寬松模式就是去掉是否穿過或和元素有交叉的判斷，也就是跳過checkLineThroughElements這個方法，另外真正的起點和終點也要加入點列表里參加計算，并且計算的起點和終點也不再使用偽起點和偽終點，而是使用真正的起點和終點，不然會出現(xiàn)如下的情況：

首先修改一下onDragMove方法，將路徑計算單獨提成一個方法，方便復(fù)用：

然后修改一下computedProbablyPoints方法，增加一個easy參數(shù)，當(dāng)該參數(shù)為true時就將真正的起點和終點加入點列表中：

const computedProbablyPoints = (startPos, endPos, easy) => { // ... // 是否是寬松模式 easyMode = easy; // 保存所有可能經(jīng)過的點 let points = []; // 寬松模式則把真正的起點和終點加入點列表中 if (easy) { points.push(startPoint, endPoint); } // ...}

最后再修改一下計算一個點周邊的點的方法，去掉是否穿過或和元素交叉的檢測：

最終效果如下：

總結(jié)

本文嘗試通過A*算法實現(xiàn)了尋找節(jié)點的關(guān)聯(lián)線路徑，原本以為難點在于算法，沒想到在實現(xiàn)過程中發(fā)現(xiàn)最難之處在于找點，如果有更好的找點方式歡迎評論區(qū)留言。

源碼地址：https://github.com/wanglin2/AssociationLineDemo[4]。

參考文章

路徑規(guī)劃之 A* 算法[5]

LogicFlow 邊的繪制與交互[6]

參考資料

[1]

https://wanglin2.github.io/AssociationLineDemo/: https://wanglin2.github.io/AssociationLineDemo/

[2]