《英雄聯盟》夏季賽總決賽今日開打！JDG對陣LNG首發名單來了 Knight：準備三連冠
8月5日消息，今日17:00，《英雄聯盟》2023LPL夏季賽總決賽將正式開打，由JDG對陣LNG。對兩支隊伍來說，這場比賽不僅要爭奪夏季賽冠軍，更要決定誰才是LPL賽區一
大家好，我是前端西瓜哥。
今天我們來看看 R 樹是什么？以及它為什么能夠提高圖形的檢索速度。
R 樹（R-tree）是一種 空間索引技術，能夠是從大量的節點中，快速找到特定范圍的元素集合，而不用一個不落地遍歷所有節點。
思路和其他索引算法（比如 B 樹、跳表）有點像，但 R 樹針對的是高維數據的查詢 。R 樹的 “R” 指的是矩形（Rectangle）。
舉個具體的例子，假設有一張地圖，上面有幾百萬個節點，要快速找某個位置半徑 2 公里的所有餐館的信息。
低效的做法是遍歷這幾百萬的節點的位置，判斷距離是否小于 2 公里。
但如果用上索引技術，比如 R 樹，我們就能利用索引去 空間換時間，快速拿到特定范圍的節點超集，比如幾千個。
接著只需要遍歷這幾千個節點去判斷符合條件的節點就可以了，而不需要完完整整遍歷所有的節點。
除此之外還可以：
下面看一下在圖形編輯器的一個場景。
我們構建了一棵圖形樹，圖形樹的圖形有位置、寬高等屬性，并渲染在畫布上。
需要實現選擇功能，繪制一個矩形選區，使和該選區矩形相交的圖形高亮。
為實現這個能力，我們計算圖形樹上的每個圖形的包圍盒：一個用 minX，minY、maxX、maxY 表達的一個矩形，它剛好包圍住圖形。
包圍盒的作用是簡化碰撞算法，一些復雜的圖形，比如貝塞爾曲線，如果要嚴格意義上判斷碰撞，是要進行復雜的計算的，在有大量圖形的場景下，性能非常糟糕。
所以業內常用矩形包圍盒的碰撞來簡化，這種算法非常簡單高效，可直接用來替代原本復雜精細的碰撞檢測，或是在進行復雜碰撞算法前先做一層過濾，避免無謂的復雜運算。
// 矩形是否相交function intersects(a, b) { return b.minX <= a.maxX && b.minY <= a.maxY && b.maxX >= a.minX && b.maxY >= a.minY;}這個包圍盒特點，就很適合拿來應用 R 樹來提高圖形樹的 檢索效率。
R 樹的數據結構是一個平衡樹。
和其他索引樹類似，R 樹的葉子節點是數據節點，保存有圖形信息和它的最小包圍矩形（MBR）。
最小包圍矩形其實就是包圍盒。
結構大概類似這樣：
{ minX: 20, minY: 40, maxX: 30, maxY: 50, // 保存圖形數據，比如圖形對象 id，或圖形對象本身 data: {}};R 樹會將距離相近的數據節點收集起來，并放到同一個父節點下。這個父節點是 索引節點，不會保存圖形信息，但會記錄子節點的合并的包圍盒數據。
父節點如果多了，也會把它們收集起來，放到一個新的父節點下。
這樣就形成了一個樹的結構。
實際生產環境，推薦使用一個名為 RBush 的高性能 NPM 庫。
代碼用法示例：
import RBush from "rbush";// 創建一個 R 樹實例const tree = new RBush();// 也可以指定一個索引節點最多有幾個子節點，默認是 9 個const tree2 = new RBush(16);檢索的過程如下：
提供一個選區矩形，從根節點開始，往下遞歸查找判斷選取矩形是否和當前節點矩形相交。
直到可能相交的節點遍歷完結束，然后返回 result 數組。
RBush 的搜索寫法：
const result = tree.search({ minX: 20, minY: 20, maxX: 80, maxY: 70,});其源碼實現：
class RBush { // ... search(bbox) { let node = this.data; const result = []; if (!intersects(bbox, node)) return result; const toBBox = this.toBBox; const nodesToSearch = []; while (node) { for (let i = 0; i < node.children.length; i++) { const child = node.children[i]; const childBBox = node.leaf ? toBBox(child) : child; if (intersects(bbox, childBBox)) { // 1. 遍歷到數據節點 if (node.leaf) result.push(child); // 2. 索引節點 // 2.1. 包含關系，索引節點下的所有數據節點都加進 result else if (contains(bbox, childBBox)) this._all(child, result); // 2.2. 相交不包含關系，繼續判斷相交 else nodesToSearch.push(child); } } node = nodesToSearch.pop(); } return result; } _all(node, result) { const nodesToSearch = []; while (node) { if (node.leaf) result.push(...node.children); else nodesToSearch.push(...node.children); node = nodesToSearch.pop(); } return result; }}在圖形編輯器初始化的時候，我們要計算圖形樹所有圖形的包圍盒，然后插入到 R 樹上。
RBush 插入單個節點的寫法：
const item = { minX: 20, minY: 40, maxX: 30, maxY: 50, graphId: '123',};tree.insert(item);支持批量插入節點，RBush 針對批量添加做了優化，效率比單個插入更高。
tree.load([item1, item2, /* ... */]);R 數作為索引數據，是要實時更新。
為此，我們需在每次圖形物理屬性改變的時候，重新計算包圍盒，并更新 R 樹。
tree.remove(item);tree.insert(newItem);還有一種同樣可以減少遍歷節點數量的算法，叫做 四叉樹（Quadtree）碰撞檢測。
四叉樹將視口界面分割成多個區域，每個區域記住自己包含了哪些圖形。
然后移動目標圖形時，判斷它落在哪個區域，取出所在區域的圖形，這些圖形集合就是和目標圖形發生碰撞圖形的超集。
當一個區域的圖形數量過多時，又會進行分裂，再次分成 4 個區域。
四叉樹更適合圖形均勻分布的場景，如果不均勻，會產生大量空節點，且查詢效率會降低。
R 樹除了處理二維，還可以處理更高維度的數據，相比四叉樹更適合范圍查詢。
本文鏈接：http://www.www897cc.com/showinfo-26-59641-0.html圖形遍歷效率低？試試 R 樹
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號