石頭智能洗地機A10 Plus體驗：雙向自清潔治好了我的懶癌
一、前言和介紹專為家庭請假懶人而生的石頭科技在近日又帶來了自己的全新旗艦新品，石頭智能洗地機A10 Plus。從這個產品名上就不難看出，這次石頭推出的并不是常見的掃地機器
大家好，我是前端西瓜哥。
今天我們來看看 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號