整合營銷服務(wù)商
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
習(xí) HTML 最好的方式就是邊學(xué)邊做實(shí)驗(yàn)。您可以用Dreamweaver進(jìn)行實(shí)例操作
HTML 標(biāo)題
HTML 標(biāo)題（Heading）是通過 <h1> - <h6> 等標(biāo)簽進(jìn)行定義的。
實(shí)例
[demo]
<html>
<head>
<meta charset="UTF-8">
</head>
<body>
<h1>This is heading 1</h1>
<h2>This is heading 2</h2>
<h3>This is heading 3</h3>
<h4>This is heading 4</h4>
<h5>This is heading 5</h5>
<h6>This is heading 6</h6>
<p>請(qǐng)僅僅把標(biāo)題標(biāo)簽用于標(biāo)題文本。不要僅僅為了產(chǎn)生粗體文本而使用它們。請(qǐng)使用其它標(biāo)簽或 CSS 代替。</p>
</body>
</html>
[/demo]
下是一些常用的HTML網(wǎng)頁源代碼示例，這些示例可用作HTML文檔的基礎(chǔ)：
1、創(chuàng)建一個(gè)簡單的HTML文檔結(jié)構(gòu)：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport"content="width=device-width,initial-scale=1.0">
<title>My Web Page</title>
</head>
<body>
<h1>Hello,World!</h1>
<p>This is a simple HTML webpage.</p>
</body>
</html>
2、插入圖片：
<img src="image.jpg"alt="Description of the image">
3、創(chuàng)建超鏈接：
<a href="https://www.example.com">Visit Example.com</a>
4、創(chuàng)建無序列表：
<ul>
<li>Item 1</li>
<li>Item 2</li>
<li>Item 3</li>
</ul>
5、創(chuàng)建有序列表：
<ol>
<li>First item</li>
<li>Second item</li>
<li>Third item</li>
</ol>
6、創(chuàng)建表格：
<table>
<tr>
<th>Header 1</th>
<th>Header 2</th>
</tr>
<tr>
<td>Row 1,Cell 1</td>
<td>Row 1,Cell 2</td>
</tr>
<tr>
<td>Row 2,Cell 1</td>
<td>Row 2,Cell 2</td>
</tr>
</table>
7、插入段落：
<p>This is a paragraph of text.</p>
8、插入換行符：
<p>This is some text.<br>This is on a new line.</p>
9、創(chuàng)建一個(gè)文本輸入框：
<input type="text"name="username"placeholder="Enter your username">
10、插入按鈕：
<button type="button">Click me</button>
這些示例代碼只是HTML的基礎(chǔ)，HTML具有更豐富的功能和標(biāo)記選項(xiàng)，可以根據(jù)需要進(jìn)行擴(kuò)展和定制。請(qǐng)根據(jù)您的具體需求，使用這些示例作為起點(diǎn)，構(gòu)建您自己的網(wǎng)頁。
【名揚(yáng)銀河企業(yè)網(wǎng)站系統(tǒng)】
【免費(fèi)】提供企業(yè)【網(wǎng)站源碼】，簡單易用，無須擁有代碼基礎(chǔ)。
歡迎留言或私信我們咨詢。
以上內(nèi)容由【名揚(yáng)銀河】企業(yè)網(wǎng)站系統(tǒng)原創(chuàng)發(fā)布，轉(zhuǎn)載請(qǐng)注明出處。
果你用過流程圖繪制工具，那么可能會(huì)好奇節(jié)點(diǎn)之間的連接線是如何計(jì)算出來的：
不要走開，跟隨本文一起來探究一下吧。
最終效果預(yù)覽：https://wanglin2.github.io/AssociationLineDemo/[1]
先使用Vue3搭建一下頁面的基本結(jié)構(gòu)，為了簡化canvas操作，我們使用konvajs[2]庫來繪制圖形。
頁面模板部分，提供一個(gè)容器即可：
<div class="container" ref="container"></div>
js部分，主要是使用konvajs來創(chuàng)建兩個(gè)可拖拽的矩形元素及一個(gè)連接線元素，當(dāng)然目前連接線并沒有頂點(diǎn)數(shù)據(jù)：
import { onMounted, ref } from "vue";
import Konva from "konva";
const container = ref(null);
// 創(chuàng)建兩個(gè)矩形、一個(gè)折線元素
let layer, rect1, rect2, line;
// 矩形移動(dòng)事件
const onDragMove = () => {
// 獲取矩形實(shí)時(shí)位置
console.log(rect1.x(), rect1.y(), rect2.x(), rect2.y());
};
// 初始化圖形
const init = () => {
const { width, height } = container.value.getBoundingClientRect();
// 創(chuàng)建舞臺(tái)
let stage = new Konva.Stage({
container: container.value,
width,
height,
});
// 創(chuàng)建圖層
layer = new Konva.Layer();
// 創(chuàng)建兩個(gè)矩形
rect1 = new Konva.Rect({
x: 400,
y: 200,
width: 100,
height: 100,
fill: "#fbfbfb",
stroke: "black",
strokeWidth: 4,
draggable: true,// 圖形允許拖拽
});
rect2 = new Konva.Rect({
x: 800,
y: 600,
width: 100,
height: 100,
fill: "#fbfbfb",
stroke: "black",
strokeWidth: 4,
draggable: true,
});
// 監(jiān)聽進(jìn)行拖拽事件
rect1.on("dragmove", onDragMove);
rect2.on("dragmove", onDragMove);
// 矩形添加到圖層
layer.add(rect1);
layer.add(rect2);
// 創(chuàng)建折線元素
line = new Konva.Line({
points: [],// 當(dāng)前它的頂點(diǎn)數(shù)據(jù)是空的，所以你還看不見這個(gè)元素
stroke: "green",
strokeWidth: 2,
lineJoin: "round",
});
// 折線添加到圖層
layer.add(line);
// 圖層添加到舞臺(tái)
stage.add(layer);
// 繪制
layer.draw();
};
onMounted(() => {
init();
});
效果如下：
接下來我們只要在圖形拖拽時(shí)實(shí)時(shí)計(jì)算出關(guān)聯(lián)線的頂點(diǎn)然后更新到折線元素里就可以繪制出這條連接線。
整個(gè)畫布上所有的點(diǎn)其實(shí)都是可能經(jīng)過的點(diǎn)，但是我們的連接線是【橫平豎直】的，且要盡可能是最短路線，所以考慮所有的點(diǎn)沒有必要，我們可以按照一定規(guī)則縮小范圍，然后再從中計(jì)算出最優(yōu)路線。
首先起點(diǎn)和終點(diǎn)兩個(gè)點(diǎn)肯定是必不可少的，以下圖為例，假設(shè)我們要從左上角的矩形頂部中間位置連接到右下角的矩形頂部中間位置：
接下來我們定兩個(gè)原則：
1.連接線盡量不能和圖形的邊重疊
2.連接線盡量不能穿過元素
為什么說盡量呢，因?yàn)楫?dāng)兩個(gè)元素距離過近或有重疊的話這些都是無法避免的。
結(jié)合上面兩個(gè)原則我們可以規(guī)定元素周圍一定距離內(nèi)都不允許線經(jīng)過（當(dāng)然除了連接起終點(diǎn)的線段），這樣就相當(dāng)于給元素外面套了個(gè)矩形的包圍框：
經(jīng)過起終點(diǎn)且垂直于起終點(diǎn)所在邊的直線與包圍框的交點(diǎn)一定是會(huì)經(jīng)過的，并且這兩個(gè)點(diǎn)是唯一能直接和起終點(diǎn)相連的點(diǎn)，所以我們可以把這兩個(gè)點(diǎn)當(dāng)做是“起點(diǎn)"和"終點(diǎn)”，這樣在計(jì)算的時(shí)候可以少計(jì)算兩個(gè)點(diǎn)：
在矩形移動(dòng)事件里進(jìn)行點(diǎn)的計(jì)算，首先緩存一下矩形的位置和尺寸信息，然后定義起點(diǎn)和終點(diǎn)的坐標(biāo)，最后定義一個(gè)數(shù)組用來存放所有可能經(jīng)過的點(diǎn)：
// 矩形移動(dòng)事件
const onDragMove = () => {
computedProbablyPoints();
};
// 計(jì)算所有可能經(jīng)過的點(diǎn)
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();
rect1H = rect1.height();
rect2X = rect2.x();
rect2Y = rect2.y();
rect2W = rect2.width();
rect2H = rect2.height();
// 起終點(diǎn)
startPoint = [rect1X + rect1W / 2, rect1Y];
endPoint = [rect2X + rect2W / 2, rect2Y];
// 保存所有可能經(jīng)過的點(diǎn)
let points = [];
}
因?yàn)槠鸾K點(diǎn)可以在矩形的任一方向，所以我們寫個(gè)方法來獲取偽起點(diǎn)和偽終點(diǎn)，并將它們添加到數(shù)組里：
const computedProbablyPoints = () => {
// ...
// 偽起點(diǎn)：經(jīng)過起點(diǎn)且垂直于起點(diǎn)所在邊的線與包圍框線的交點(diǎn)
let fakeStartPoint = findStartNextOrEndPrePoint(rect1, startPoint);
points.push(fakeStartPoint);
// 偽終點(diǎn)：經(jīng)過終點(diǎn)且垂直于終點(diǎn)所在邊的線與包圍框線的交點(diǎn)
let fakeEndPoint = findStartNextOrEndPrePoint(rect2, endPoint);
points.push(fakeEndPoint);
}
// 找出起點(diǎn)的下一個(gè)點(diǎn)或終點(diǎn)的前一個(gè)點(diǎn)
const MIN_DISTANCE = 30;
const findStartNextOrEndPrePoint = (rect, point) => {
// 起點(diǎn)或終點(diǎn)在左邊
if (point[0] === rect.x()) {
return [rect.x() - MIN_DISTANCE, rect.y() + rect.height() / 2];
} else if (point[1] === rect.y()) {
// 起點(diǎn)或終點(diǎn)在上邊
return [rect.x() + rect.width() / 2, rect.y() - MIN_DISTANCE];
} else if (point[0] === rect.x() + rect.width()) {
// 起點(diǎn)或終點(diǎn)在右邊
return [
rect.x() + rect.width() + MIN_DISTANCE,
rect.y() + rect.height() / 2,
];
} else if (point[1] === rect.y() + rect.height()) {
// 起點(diǎn)或終點(diǎn)在下邊
return [
rect.x() + rect.width() / 2,
rect.y() + rect.height() + MIN_DISTANCE,
];
}
};
偽起點(diǎn)和偽終點(diǎn)會(huì)形成一個(gè)矩形，這個(gè)矩形和起點(diǎn)元素包圍框可以組成一個(gè)更大的矩形，這個(gè)矩形的四個(gè)角是連接線有可能經(jīng)過的點(diǎn)：
將這幾個(gè)點(diǎn)添加到數(shù)組里，有一個(gè)點(diǎn)和偽終點(diǎn)重復(fù)了，不過沒關(guān)系，我們最后再去重即可：
const computedProbablyPoints = () => {
// ...
// 偽起點(diǎn)和偽終點(diǎn)形成的矩形 和 起點(diǎn)元素包圍框 組成一個(gè)大矩形 的四個(gè)頂點(diǎn)
points.push(
...getBoundingBox([
// 偽起點(diǎn)終點(diǎn)
fakeStartPoint,
fakeEndPoint,
// 起點(diǎn)元素包圍框
[rect1X - MIN_DISTANCE, rect1Y - MIN_DISTANCE], // 左上頂點(diǎn)
[rect1X + rect1W + MIN_DISTANCE, rect1Y + rect1H + MIN_DISTANCE], // 右下頂點(diǎn)
])
);
}
// 計(jì)算出給定點(diǎn)可以形成的最大的矩形的四個(gè)頂點(diǎn)
const getBoundingBox = (points) => {
let boundingBoxXList = [];
let boundingBoxYList = [];
points.forEach((item) => {
boundingBoxXList.push(item[0]);
boundingBoxYList.push(item[1]);
});
let minBoundingBoxX = Math.min(...boundingBoxXList);
let minBoundingBoxY = Math.min(...boundingBoxYList);
let maxBoundingBoxX = Math.max(...boundingBoxXList);
let maxBoundingBoxY = Math.max(...boundingBoxYList);
return [
[minBoundingBoxX, minBoundingBoxY],
[maxBoundingBoxX, minBoundingBoxY],
[minBoundingBoxX, maxBoundingBoxY],
[maxBoundingBoxX, maxBoundingBoxY],
];
};
從圖上可以看出來，關(guān)聯(lián)線要么從右邊連過去，要么從左邊連過去。
同樣，偽起點(diǎn)和偽終點(diǎn)形成的矩形也會(huì)和終點(diǎn)元素包圍框形成一個(gè)更大的矩形，這個(gè)矩形的四個(gè)頂點(diǎn)也是有可能會(huì)經(jīng)過的，這當(dāng)終點(diǎn)元素位于起點(diǎn)元素上方時(shí)會(huì)經(jīng)過：
// 偽起點(diǎn)和偽終點(diǎn)形成的矩形 和 終點(diǎn)元素包圍框 組成一個(gè)大矩形 的四個(gè)頂點(diǎn)
points.push(
...getBoundingBox([
// 偽起點(diǎn)終點(diǎn)
fakeStartPoint,
fakeEndPoint,
// 終點(diǎn)元素包圍框
[rect2X - MIN_DISTANCE, rect2Y - MIN_DISTANCE], // 左上頂點(diǎn)
[rect2X + rect2W + MIN_DISTANCE, rect2Y + rect2H + MIN_DISTANCE], // 右下頂點(diǎn)
])
);以上這些點(diǎn)基本能滿足起終點(diǎn)都在元素上方的情況，但是對(duì)于下面這種起點(diǎn)在上面終點(diǎn)在左邊情況就不行了：
很明顯看到如果存在下面這個(gè)點(diǎn)就可以了：
這其實(shí)就是前面所說的經(jīng)過起終點(diǎn)且垂直于起終點(diǎn)所在邊的兩條線的交點(diǎn)，求交點(diǎn)可以先根據(jù)兩個(gè)點(diǎn)計(jì)算出直線方程，再聯(lián)立兩個(gè)方程計(jì)算交點(diǎn)，但是我們的線都是橫平豎直的，所以沒必要這么麻煩，兩條線要么是平行的，要么是一條水平一條垂直，很容易羅列完所有情況：
// 計(jì)算兩條線段的交點(diǎn)
const getIntersection = (seg1, seg2) => {
// 兩條垂直線不會(huì)相交
if (seg1[0][0] === seg1[1][0] && seg2[0][0] === seg2[1][0]) {
return null;
}
// 兩條水平線不會(huì)相交
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]];
}
};
有了這個(gè)方法我們就可以把這個(gè)交點(diǎn)添加到數(shù)組里：
const computedProbablyPoints = () => {
// ...
// 經(jīng)過起點(diǎn)且垂直于起點(diǎn)所在邊的線 與 經(jīng)過終點(diǎn)且垂直于終點(diǎn)所在邊的線 的交點(diǎn)
let startEndPointVerticalLineIntersection = getIntersection([startPoint, fakeStartPoint], [endPoint, fakeEndPoint]);
startEndPointVerticalLineIntersection && points.push(startEndPointVerticalLineIntersection);
}
到這里計(jì)算出來的點(diǎn)能滿足大部分情況了，但是還有一種情況滿足不了，當(dāng)起終點(diǎn)相對(duì)時(shí)：
所以當(dāng)前面計(jì)算的startEndPointVerticalLineIntersection點(diǎn)不存在的時(shí)候我們就計(jì)算經(jīng)過偽起點(diǎn)和偽終點(diǎn)的一條垂直線和一條水平線的交點(diǎn)（黃色的兩個(gè)點(diǎn)）：
const computedProbablyPoints = () => {
// ...
// 當(dāng) 經(jīng)過起點(diǎn)且垂直于起點(diǎn)所在邊的線 與 經(jīng)過終點(diǎn)且垂直于終點(diǎn)所在邊的線 平行時(shí)，計(jì)算一條垂直線與經(jīng)過另一個(gè)點(diǎn)的偽點(diǎn)的水平線 的節(jié)點(diǎn)
if (!startEndPointVerticalLineIntersection) {
let p1 = getIntersection(
[startPoint, fakeStartPoint],// 假設(shè)經(jīng)過起點(diǎn)的垂直線是垂直的
[fakeEndPoint, [fakeEndPoint[0] + 10, fakeEndPoint[1]]]// 那么就要計(jì)算經(jīng)過偽終點(diǎn)的水平線。水平線上的點(diǎn)y坐標(biāo)相同，所以x坐標(biāo)隨便加減多少數(shù)值都可以
);
p1 && points.push(p1);
let p2 = getIntersection(
[startPoint, fakeStartPoint],// 假設(shè)經(jīng)過起點(diǎn)的垂直線是水平的
[fakeEndPoint, [fakeEndPoint[0], fakeEndPoint[1] + 10]]// 那么就要計(jì)算經(jīng)過偽終點(diǎn)的垂直線。
);
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)過的點(diǎn)就找的差不多了，一共有：
接下來進(jìn)行去重以及導(dǎo)出相關(guān)的數(shù)據(jù)：
const computedProbablyPoints = () => {
// ...
// 去重
points = removeDuplicatePoint(points);
return {
startPoint,
endPoint,
fakeStartPoint,
fakeEndPoint,
points,
};
}
// 去重
const removeDuplicatePoint = (points) => {
let res = [];
let cache = {};
points.forEach(([x, y]) => {
if (cache[x + "-" + y]) {
return;
} else {
cache[x + "-" + y] = true;
res.push([x, y]);
}
});
return res;
};
如果不考慮效率和最短距離，我們可以直接使用廣度優(yōu)先搜索或者說是回溯算法，也就是從起點(diǎn)開始，挨個(gè)嘗試起點(diǎn)周邊的點(diǎn)，到下一個(gè)點(diǎn)又挨個(gè)嘗試下一個(gè)點(diǎn)周邊所有的點(diǎn)，如果遇到終點(diǎn)，那么結(jié)束，把所經(jīng)過的點(diǎn)連接起來就是一條路徑，接下來我們嘗試一下。
在開始算法之前需要先實(shí)現(xiàn)如何找出一個(gè)點(diǎn)周邊的點(diǎn)，如果是在網(wǎng)格中，那么很簡單，一個(gè)點(diǎn)周邊的點(diǎn)就是x、y坐標(biāo)加1或減1，但是我們這些點(diǎn)彼此之間的距離是不確定的，所以只能根據(jù)坐標(biāo)進(jìn)行搜索，比如要找一個(gè)點(diǎn)右邊最近的點(diǎn)，那么根據(jù)該點(diǎn)的y坐標(biāo)進(jìn)行搜索，看有沒有y坐標(biāo)相同的點(diǎn)，有的話再找出其中最近的，當(dāng)然，還要檢測(cè)找出的這個(gè)點(diǎn)和目標(biāo)點(diǎn)的連線是否會(huì)穿過起終點(diǎn)元素，是的話這個(gè)點(diǎn)也要跳過：
// 找出一個(gè)點(diǎn)周邊的點(diǎn)
const getNextPoints = (point, points) => {
let [x, y] = point;
let xSamePoints = [];
let ySamePoints = [];
// 找出x或y坐標(biāo)相同的點(diǎn)
points.forEach((item) => {
// 跳過目標(biāo)點(diǎn)
if (checkIsSamePoint(point, item)) {
return;
}
if (item[0] === x) {
xSamePoints.push(item);
}
if (item[1] === y) {
ySamePoints.push(item);
}
});
// 找出x方向最近的點(diǎn)
let xNextPoints = getNextPoint(x, y, ySamePoints, "x");
// 找出y方向最近的點(diǎn)
let yNextPoints = getNextPoint(x, y, xSamePoints, "y");
return [...xNextPoints, ...yNextPoints];
};
// 檢測(cè)是否為同一個(gè)點(diǎn)
const checkIsSamePoint = (a, b) => {
if (!a || !b) {
return false;
}
return a[0] === b[0] && a[1] === b[1];
};
接下來就是getNextPoint方法的實(shí)現(xiàn)：
// 找出水平或垂直方向上最近的點(diǎn)
const getNextPoint = (x, y, list, dir) => {
let index = dir === "x" ? 0 : 1;// 求水平方向上最近的點(diǎn)，那么它們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)前點(diǎn)和目標(biāo)點(diǎn)的連線是否穿過起終點(diǎn)元素
if (checkLineThroughElements([x, y], cur)) {
continue;
}
// 左側(cè)或上方最近的點(diǎn)
if (cur[index] < value) {
if (nextLeftTopPoint) {
if (cur[index] > nextLeftTopPoint[index]) {
nextLeftTopPoint = cur;
}
} else {
nextLeftTopPoint = cur;
}
}
// 右側(cè)或下方最近的點(diǎn)
if (cur[index] > value) {
if (nextRIghtBottomPoint) {
if (cur[index] < nextRIghtBottomPoint[index]) {
nextRIghtBottomPoint = cur;
}
} else {
nextRIghtBottomPoint = cur;
}
}
}
return [nextLeftTopPoint, nextRIghtBottomPoint].filter((point) => {
return !!point;
});
};
checkLineThroughElements方法用來判斷一條線段是否穿過或和起終點(diǎn)元素有重疊，也是一個(gè)簡單的比較邏輯：
// 檢查兩個(gè)點(diǎn)組成的線段是否穿過起終點(diǎn)元素
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() &&
maxX >= rect.x()
) {
return true;
}
}
} else if (a[0] === b[0]) {
// 垂直線
for (let i = 0; i < rects.length; i++) {
let rect = rects[i];
if (
minX >= rect.x() &&
minX <= rect.x() + rect.width() &&
minY <= rect.y() + rect.height() &&
maxY >= rect.y()
) {
return true;
}
}
}
return false;
};
接下來就可以使用回溯算法來找出其中的一條路徑，回溯算法很簡單，因?yàn)椴皇潜疚牡闹攸c(diǎn)，所以就不詳細(xì)介紹了，有興趣的可以閱讀回溯（DFS）算法解題套路框架[3]。
計(jì)算出坐標(biāo)點(diǎn)后再更新連線元素，記得要把我們真正的起點(diǎn)和終點(diǎn)坐標(biāo)加上去：
// 矩形移動(dòng)事件
const onDragMove = () => {
// 計(jì)算出所有可能的點(diǎn)
let { startPoint, endPoint, fakeStartPoint, fakeEndPoint, points } =
computedProbablyPoints();
// 使用回溯算法找出其中一條路徑
const routes = useDFS(fakeStartPoint, fakeEndPoint, points);
// 更新連線元素
line.points(
// 加上真正的起點(diǎn)和終點(diǎn)
(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á)終點(diǎn)了
if (checkIsSamePoint(cur, endPoint)) {
res = [...path, cur];
break;
}
let key = cur[0] + "-" + cur[1];
// 該點(diǎn)已經(jīng)被選擇過了
if (used[key]) {
continue;
}
used[key] = true;
track([...path, cur], getNextPoints(cur, points));
used[key] = false;
}
};
track([], [startPoint]);
return res;
};
效果如下：
可以看到確實(shí)計(jì)算出了一條連接線路徑，但是顯然不是最短路徑，并且回溯算法是一種暴力算法，點(diǎn)多了可能會(huì)存在性能問題。
前面我們使用回溯算法找出了其中一條關(guān)聯(lián)線路徑，但是很多情況下計(jì)算出來的路徑都不是最短的，接下來我們就使用A*算法來找出最短路徑。
A*算法和回溯算法有點(diǎn)相似，但是不是盲目的挨個(gè)遍歷一個(gè)點(diǎn)周圍的點(diǎn)，而是會(huì)從中找出最有可能的點(diǎn)優(yōu)先進(jìn)行嘗試，完整的算法過程描述如下：
1.創(chuàng)建兩個(gè)數(shù)組，openList存放待遍歷的點(diǎn)，closeList存放已經(jīng)遍歷的點(diǎn)；
2.將起點(diǎn)放入openList中；
3.如果openList不為空，那么從中選取優(yōu)先級(jí)最高的點(diǎn)，假設(shè)為n：
3.1.如果n為終點(diǎn)，那么結(jié)束循環(huán)，從n出發(fā)，依次向前找出父節(jié)點(diǎn)，也就是最短路徑；
3.2.如果n不為終點(diǎn)，那么：
3.2.1.將n從openList中刪除，添加到closeList中；
3.2.2.遍歷n周圍的點(diǎn)：
3.2.2.1.如果該點(diǎn)在closeList中，那么跳過該點(diǎn)；
3.2.2.2.如果該點(diǎn)也不在openList中，那么：
3.2.2.2.1.設(shè)置n為該點(diǎn)的父節(jié)點(diǎn)；
3.2.2.2.2.計(jì)算該點(diǎn)的代價(jià)，代價(jià)越高，優(yōu)先級(jí)越低，反之越高；
3.3.3.3.3.將該點(diǎn)添加到openList；
3.2.3.繼續(xù)3的循環(huán)過程，直到找到終點(diǎn)，或openList為空，沒有結(jié)果；
根據(jù)以上過程，我們創(chuàng)建一個(gè)A*類：
// A*算法類
class AStar {
constructor() {
this.startPoint = null;
this.endPoint = null;
this.pointList = [];
// 存放待遍歷的點(diǎn)
this.openList = [];
// 存放已經(jīng)遍歷的點(diǎn)
this.closeList = [];
}
// 算法主流程
start(startPoint, endPoint, pointList) {
this.startPoint = startPoint;
this.endPoint = endPoint;
this.pointList = pointList;
this.openList = [
{
point: this.startPoint, // 起點(diǎn)加入openList
cost: 0, // 代價(jià)
parent: null, // 父節(jié)點(diǎn)
},
];
this.closeList = [];
while (this.openList.length) {
// 在openList中找出優(yōu)先級(jí)最高的點(diǎn)
let point = this.getBestPoint();
// point為終點(diǎn)，那么算法結(jié)束，輸出最短路徑
if (checkIsSamePoint(point.point, this.endPoint)) {
return this.getRoutes(point);
} else {
// 將point從openList中刪除
this.removeFromOpenList(point);
// 將point添加到closeList中
this.closeList.push(point);
// 遍歷point周圍的點(diǎn)
let nextPoints = getNextPoints(point.point, this.pointList);
for (let i = 0; i < nextPoints.length; i++) {
let cur = nextPoints[i];
// 如果該點(diǎn)在closeList中，那么跳過該點(diǎn)
if (this.checkIsInList(cur, this.closeList)) {
continue;
} else if (!this.checkIsInList(cur, this.openList)) {
// 如果該點(diǎn)也不在openList中
let pointObj = {
point: cur,
parent: point,// 設(shè)置point為當(dāng)前點(diǎn)的父節(jié)點(diǎn)
cost: 0,
};
// 計(jì)算當(dāng)前點(diǎn)的代價(jià)
this.computeCost(pointObj);
// 添加到openList中
this.openList.push(pointObj);
}
}
}
}
return []
}
// 獲取openList中優(yōu)先級(jí)最高的點(diǎn)，也就是代價(jià)最小的點(diǎn)
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é)點(diǎn)，也就是最短路徑
getRoutes(point) {
let res = [point];
let par = point.parent;
while (par) {
res.unshift(par);
par = par.parent;
}
return res.map((item) => {
return item.point;
});
}
// 將點(diǎn)從openList中刪除
removeFromOpenList(point) {
let index = this.openList.findIndex((item) => {
return checkIsSamePoint(point.point, item.point);
});
this.openList.splice(index, 1);
}
// 檢查點(diǎn)是否在列表中
checkIsInList(point, list) {
return list.find((item) => {
return checkIsSamePoint(item.point, point);
});
}
// 計(jì)算一個(gè)點(diǎn)的代價(jià)
computeCost(point) {
// TODO
}
}
代碼有點(diǎn)長，但是邏輯很簡單，start方法基本就是對(duì)前面的算法過程進(jìn)行還原，其他就是一些輔助工具方法，只有一個(gè)computeCost方法暫時(shí)沒有實(shí)現(xiàn)，這個(gè)方法也就是A*算法的核心。
A*算法的所說的節(jié)點(diǎn)優(yōu)先級(jí)是由兩部分決定的：
f(n) = g(n) + h(n)
g(n)代表節(jié)點(diǎn)n距離起點(diǎn)的代價(jià)。
f(n)代表節(jié)點(diǎn)n到終點(diǎn)的代價(jià)，當(dāng)然這個(gè)代價(jià)只是預(yù)估的。
f(n)為g(n)加上h(n)，就代表節(jié)點(diǎn)n的綜合代價(jià)，也就是優(yōu)先級(jí)，代價(jià)越低，當(dāng)然優(yōu)先級(jí)越高，修改一下computeCost方法，拆解成兩個(gè)方法：
// 計(jì)算一個(gè)點(diǎn)的優(yōu)先級(jí)
computePriority(point) {
point.cost = this.computedGCost(point) + this.computedHCost(point);
}
g(n)的計(jì)算很簡單，把它所有祖先節(jié)點(diǎn)的代價(jià)累加起來即可：
// 計(jì)算代價(jià)g(n)
computedGCost(point) {
let res = 0;
let par = point.parent;
while (par) {
res += par.cost;
par = par.parent;
}
return res;
}
而h(n)的計(jì)算就會(huì)用到曼哈頓距離，兩個(gè)點(diǎn)的曼哈頓距離指的就是這兩個(gè)點(diǎn)的水平和垂直方向的距離加起來的總距離：
對(duì)于我們的計(jì)算，也就是當(dāng)前節(jié)點(diǎn)到終點(diǎn)的曼哈頓距離：
// 計(jì)算代價(jià)h(n)
computedHCost(point) {
return (
Math.abs(this.endPoint[0] - point.point[0]) +
Math.abs(this.endPoint[1] - point.point[1])
);
}
接下來實(shí)例化一個(gè)AStar類，然后使用它來計(jì)算最短路徑：
const aStar = new AStar();
const onDragMove = () => {
let { startPoint, endPoint, fakeStartPoint, fakeEndPoint, points } =
computedProbablyPoints(startPos.value, endPos.value);
const routes = aStar.start(fakeStartPoint, fakeEndPoint, points);
// 更新連線元素
// ...
}
可以看到不會(huì)出現(xiàn)回溯算法計(jì)算出來的超長路徑。
到上一節(jié)已經(jīng)基本可以找出最短路徑，但是會(huì)存在幾個(gè)問題，本小節(jié)來試著優(yōu)化一下。
如上圖所示，垂直部分的連接線顯然離元素過近，雖然還沒有和元素重疊，但是已經(jīng)突破了包圍框，更好的連接點(diǎn)應(yīng)該是右邊兩個(gè)，下圖的情況也是類似的：
解決方法也很簡單，前面我們實(shí)現(xiàn)了一個(gè)判斷線段是否穿過或和起終點(diǎn)元素重疊的方法，我們修改一下比較條件，把比較對(duì)象由元素本身改成元素的包圍框：
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() + MIN_DISTANCE &&
maxX > rect.x() - MIN_DISTANCE
) {
return true;
}
}
} else if (a[0] === b[0]) {
// 垂直線
for (let i = 0; i < rects.length; i++) {
let rect = rects[i];
if (
minX > rect.x() - MIN_DISTANCE &&
minX < rect.x() + rect.width() + MIN_DISTANCE &&
minY < rect.y() + rect.height() + MIN_DISTANCE &&
maxY > rect.y() - MIN_DISTANCE
) {
return true;
}
}
}
return false;
};
效果如下：
目前我們的邏輯如果當(dāng)兩個(gè)元素太近了，那么是計(jì)算不出來符合要求的點(diǎn)的，自然就沒有線了：
解決方法也很簡單，當(dāng)?shù)谝淮温窂接?jì)算沒有結(jié)果時(shí)我們假設(shè)是因?yàn)榫嚯x很近導(dǎo)致的，然后我們?cè)僖詫捤赡Ｊ接?jì)算一次，所謂寬松模式就是去掉是否穿過或和元素有交叉的判斷，也就是跳過checkLineThroughElements這個(gè)方法，另外真正的起點(diǎn)和終點(diǎn)也要加入點(diǎn)列表里參加計(jì)算，并且計(jì)算的起點(diǎn)和終點(diǎn)也不再使用偽起點(diǎn)和偽終點(diǎn)，而是使用真正的起點(diǎn)和終點(diǎn)，不然會(huì)出現(xiàn)如下的情況：
首先修改一下onDragMove方法，將路徑計(jì)算單獨(dú)提成一個(gè)方法，方便復(fù)用：
const onDragMove = () => {
// 計(jì)算點(diǎn)和路徑提取成一個(gè)方法
let { startPoint, endPoint, routes } = computeRoutes();
// 如果沒有計(jì)算出來路徑，那么就以寬松模式再計(jì)算一次可能的點(diǎn)，也就是允許和元素交叉
if (routes.length <= 0) {
let res = computeRoutes(true);
routes = res.routes;
}
// 更新連線元素
updateLine(
(routes.length > 0 ? [startPoint, ...routes, endPoint] : []).reduce(
(path, cur) => {
path.push(cur[0], cur[1]);
return path;
},
[]
)
);
};
// 計(jì)算路徑
const computeRoutes = (easy) => {
// 計(jì)算出所有可能的點(diǎn)
let { startPoint, endPoint, fakeStartPoint, fakeEndPoint, points } =
computedProbablyPoints(startPos.value, endPos.value, easy);
// 使用A*算法
let routes = = aStar.start(
easy ? startPoint : fakeStartPoint,// 如果是寬松模式則使用真正的起點(diǎn)和終點(diǎn)
easy ? endPoint : fakeEndPoint,
points
);
return {
startPoint,
endPoint,
routes,
};
};
然后修改一下computedProbablyPoints方法，增加一個(gè)easy參數(shù)，當(dāng)該參數(shù)為true時(shí)就將真正的起點(diǎn)和終點(diǎn)加入點(diǎn)列表中：
const computedProbablyPoints = (startPos, endPos, easy) => {
// ...
// 是否是寬松模式
easyMode = easy;
// 保存所有可能經(jīng)過的點(diǎn)
let points = [];
// 寬松模式則把真正的起點(diǎn)和終點(diǎn)加入點(diǎn)列表中
if (easy) {
points.push(startPoint, endPoint);
}
// ...
}
最后再修改一下計(jì)算一個(gè)點(diǎn)周邊的點(diǎn)的方法，去掉是否穿過或和元素交叉的檢測(cè)：
const getNextPoint = (x, y, list, dir) => {
// ...
for (let i = 0; i < list.length; i++) {
let cur = list[i];
// 檢查當(dāng)前點(diǎn)和目標(biāo)點(diǎn)的連線是否穿過起終點(diǎn)元素，寬松模式下直接跳過該檢測(cè)
if (!easyMode && checkLineThroughElements([x, y], cur)) {
continue;
}
}
}
最終效果如下：
本文嘗試通過A*算法實(shí)現(xiàn)了尋找節(jié)點(diǎn)的關(guān)聯(lián)線路徑，原本以為難點(diǎn)在于算法，沒想到在實(shí)現(xiàn)過程中發(fā)現(xiàn)最難之處在于找點(diǎn)，如果有更好的找點(diǎn)方式歡迎評(píng)論區(qū)留言。
源碼地址：https://github.com/wanglin2/AssociationLineDemo[4]。
路徑規(guī)劃之 A* 算法[5]
LogicFlow 邊的繪制與交互[6]
[1]
https://wanglin2.github.io/AssociationLineDemo/: https://wanglin2.github.io/AssociationLineDemo/
[2]
konvajs: https://konvajs.org/
[3]
回溯（DFS）算法解題套路框架: https://labuladong.gitee.io/algo/1/6/
[4]
https://github.com/wanglin2/AssociationLineDemo: https://github.com/wanglin2/AssociationLineDemo
[5]
路徑規(guī)劃之 A* 算法: https://zhuanlan.zhihu.com/p/54510444
[6]
LogicFlow 邊的繪制與交互: http://logic-flow.org/article/article03.html
*請(qǐng)認(rèn)真填寫需求信息，我們會(huì)在24小時(shí)內(nèi)與您取得聯(lián)系。
