日韩成人免费在线_国产成人一二_精品国产免费人成电影在线观..._日本一区二区三区久久久久久久久不

當前位置:首頁 > 科技  > 軟件

圖形遍歷效率低?試試 R 樹

來源: 責編: 時間:2024-01-10 09:34:59 202觀看
導讀大家好,我是前端西瓜哥。今天我們來看看 R 樹是什么?以及它為什么能夠提高圖形的檢索速度。R 樹(R-tree)是一種 空間索引技術,能夠是從大量的節點中,快速找到特定范圍的元素集合,而不用一個不落地遍歷所有節點。思路和其他索

TGt28資訊網——每日最新資訊28at.com

大家好,我是前端西瓜哥。TGt28資訊網——每日最新資訊28at.com

今天我們來看看 R 樹是什么?以及它為什么能夠提高圖形的檢索速度。TGt28資訊網——每日最新資訊28at.com

R 樹(R-tree)是一種 空間索引技術,能夠是從大量的節點中,快速找到特定范圍的元素集合,而不用一個不落地遍歷所有節點。TGt28資訊網——每日最新資訊28at.com

思路和其他索引算法(比如 B 樹、跳表)有點像,但 R 樹針對的是高維數據的查詢 。R 樹的 “R” 指的是矩形(Rectangle)。TGt28資訊網——每日最新資訊28at.com

舉個具體的例子,假設有一張地圖,上面有幾百萬個節點,要快速找某個位置半徑 2 公里的所有餐館的信息。TGt28資訊網——每日最新資訊28at.com

低效的做法是遍歷這幾百萬的節點的位置,判斷距離是否小于 2 公里。TGt28資訊網——每日最新資訊28at.com

但如果用上索引技術,比如 R 樹,我們就能利用索引去 空間換時間,快速拿到特定范圍的節點超集,比如幾千個。TGt28資訊網——每日最新資訊28at.com

接著只需要遍歷這幾千個節點去判斷符合條件的節點就可以了,而不需要完完整整遍歷所有的節點。TGt28資訊網——每日最新資訊28at.com

除此之外還可以:TGt28資訊網——每日最新資訊28at.com

  • 快速檢索平面中和選區矩形相交的二維圖形;
  • 在數據庫中快速找出多維度的產品,比如價格、庫存、過期時間在特定范圍的商品。

R 樹的數據結構

下面看一下在圖形編輯器的一個場景。TGt28資訊網——每日最新資訊28at.com

我們構建了一棵圖形樹,圖形樹的圖形有位置、寬高等屬性,并渲染在畫布上。TGt28資訊網——每日最新資訊28at.com

需要實現選擇功能,繪制一個矩形選區,使和該選區矩形相交的圖形高亮。TGt28資訊網——每日最新資訊28at.com

TGt28資訊網——每日最新資訊28at.com

為實現這個能力,我們計算圖形樹上的每個圖形的包圍盒:一個用 minX,minY、maxX、maxY 表達的一個矩形,它剛好包圍住圖形。TGt28資訊網——每日最新資訊28at.com

包圍盒的作用是簡化碰撞算法,一些復雜的圖形,比如貝塞爾曲線,如果要嚴格意義上判斷碰撞,是要進行復雜的計算的,在有大量圖形的場景下,性能非常糟糕。TGt28資訊網——每日最新資訊28at.com

所以業內常用矩形包圍盒的碰撞來簡化,這種算法非常簡單高效,可直接用來替代原本復雜精細的碰撞檢測,或是在進行復雜碰撞算法前先做一層過濾,避免無謂的復雜運算。TGt28資訊網——每日最新資訊28at.com

// 矩形是否相交function intersects(a, b) {  return b.minX <= a.maxX &&         b.minY <= a.maxY &&         b.maxX >= a.minX &&         b.maxY >= a.minY;}

這個包圍盒特點,就很適合拿來應用 R 樹來提高圖形樹的 檢索效率。TGt28資訊網——每日最新資訊28at.com

R 樹的數據結構是一個平衡樹。TGt28資訊網——每日最新資訊28at.com

和其他索引樹類似,R 樹的葉子節點是數據節點,保存有圖形信息和它的最小包圍矩形(MBR)。TGt28資訊網——每日最新資訊28at.com

最小包圍矩形其實就是包圍盒。TGt28資訊網——每日最新資訊28at.com

結構大概類似這樣:TGt28資訊網——每日最新資訊28at.com

{  minX: 20,  minY: 40,  maxX: 30,  maxY: 50,  // 保存圖形數據,比如圖形對象 id,或圖形對象本身  data: {}};

R 樹會將距離相近的數據節點收集起來,并放到同一個父節點下。這個父節點是 索引節點,不會保存圖形信息,但會記錄子節點的合并的包圍盒數據。TGt28資訊網——每日最新資訊28at.com

父節點如果多了,也會把它們收集起來,放到一個新的父節點下。TGt28資訊網——每日最新資訊28at.com

這樣就形成了一個樹的結構。TGt28資訊網——每日最新資訊28at.com

TGt28資訊網——每日最新資訊28at.com

實際生產環境,推薦使用一個名為 RBush 的高性能 NPM 庫。TGt28資訊網——每日最新資訊28at.com

代碼用法示例:TGt28資訊網——每日最新資訊28at.com

import RBush from "rbush";// 創建一個 R 樹實例const tree = new RBush();// 也可以指定一個索引節點最多有幾個子節點,默認是 9 個const tree2 = new RBush(16);

R 樹的檢索

檢索的過程如下:TGt28資訊網——每日最新資訊28at.com

提供一個選區矩形,從根節點開始,往下遞歸查找判斷選取矩形是否和當前節點矩形相交。TGt28資訊網——每日最新資訊28at.com

  • 若不相交,其下的節點也不會相交,該節點對應的子樹就不需要繼續遞歸了。
  • 若相交且為數據節點(葉子節點),將其放到 result 數組。
  • 若是包含關系,其下的所有數據節點放到 result 數組。
  • 若相交但并不包含,則遍歷其下的子節點,重復前面的操作。

直到可能相交的節點遍歷完結束,然后返回 result 數組。TGt28資訊網——每日最新資訊28at.com

RBush 的搜索寫法:TGt28資訊網——每日最新資訊28at.com

const result = tree.search({  minX: 20,  minY: 20,  maxX: 80,  maxY: 70,});

其源碼實現:TGt28資訊網——每日最新資訊28at.com

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 樹的更新

1、初始化

在圖形編輯器初始化的時候,我們要計算圖形樹所有圖形的包圍盒,然后插入到 R 樹上。TGt28資訊網——每日最新資訊28at.com

RBush 插入單個節點的寫法:TGt28資訊網——每日最新資訊28at.com

const item = {  minX: 20,  minY: 40,  maxX: 30,  maxY: 50,  graphId: '123',};tree.insert(item);

支持批量插入節點,RBush 針對批量添加做了優化,效率比單個插入更高。TGt28資訊網——每日最新資訊28at.com

tree.load([item1, item2, /* ... */]);

2、更新

R 數作為索引數據,是要實時更新。TGt28資訊網——每日最新資訊28at.com

為此,我們需在每次圖形物理屬性改變的時候,重新計算包圍盒,并更新 R 樹。TGt28資訊網——每日最新資訊28at.com

tree.remove(item);tree.insert(newItem);

四叉樹(Quadtree)

還有一種同樣可以減少遍歷節點數量的算法,叫做 四叉樹(Quadtree)碰撞檢測。TGt28資訊網——每日最新資訊28at.com

四叉樹將視口界面分割成多個區域,每個區域記住自己包含了哪些圖形。TGt28資訊網——每日最新資訊28at.com

然后移動目標圖形時,判斷它落在哪個區域,取出所在區域的圖形,這些圖形集合就是和目標圖形發生碰撞圖形的超集。TGt28資訊網——每日最新資訊28at.com

當一個區域的圖形數量過多時,又會進行分裂,再次分成 4 個區域。TGt28資訊網——每日最新資訊28at.com

TGt28資訊網——每日最新資訊28at.com

四叉樹更適合圖形均勻分布的場景,如果不均勻,會產生大量空節點,且查詢效率會降低。TGt28資訊網——每日最新資訊28at.com

R 樹除了處理二維,還可以處理更高維度的數據,相比四叉樹更適合范圍查詢。TGt28資訊網——每日最新資訊28at.com

本文鏈接:http://www.www897cc.com/showinfo-26-59641-0.html圖形遍歷效率低?試試 R 樹

聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。郵件:2376512515@qq.com

上一篇: 別再找了,關于延時關閉訂單,這里有10種方案~

下一篇: 教你如何使用 eval 函數解析和執行字符串代碼,讓你的程序更加智能!

標簽:
  • 熱門焦點
Top 主站蜘蛛池模板: 崇信县| 鱼台县| 曲阜市| 青冈县| 潼南县| 永定县| 河西区| 兖州市| 石林| 吉林市| 绥棱县| 东城区| 宁乡县| 从化市| 汝南县| 佛教| 郸城县| 昌黎县| 淮阳县| 东台市| 哈尔滨市| 聂拉木县| 绥滨县| 桓仁| 黔江区| 夏津县| 邛崃市| 布拖县| 南雄市| 伊金霍洛旗| 双桥区| 孟村| 安图县| 富阳市| 宁德市| 怀柔区| 类乌齐县| 哈巴河县| 定陶县| 福安市| 宁强县|