資訊專欄INFORMATION COLUMN
摘要：我們在上文源碼解析發(fā)現(xiàn)版的節(jié)點碰撞采用四叉樹進(jìn)行了優(yōu)化。那么版本的力導(dǎo)圖具體和版的有何不同點呢，四叉樹又如何優(yōu)化碰撞校驗的呢原文鏈接被重命名為。性能的提高歸功于的新的四叉樹。
我們在上文源碼解析發(fā)現(xiàn)v4版的節(jié)點碰撞采用四叉樹進(jìn)行了優(yōu)化。
那么V4版本的力導(dǎo)圖具體和v3版的有何不同點呢，四叉樹又如何優(yōu)化碰撞校驗的呢？
https://github.com/xswei/D3-V... (原文鏈接)
d3.layout.force被重命名為d3.forceSimulation。新的力導(dǎo)向仿真使用速度Verlet算法而不是位置Verlet算法，即追蹤節(jié)點的位置(node.x，node.y)和速度(node.vx,node.vy)而不是之前的位置(node.px，node.py)。
現(xiàn)在的力導(dǎo)向仿真可以很好的擴(kuò)展：你可以指定哪些受力。這個方法使得作品更柔和。新的力導(dǎo)向也更靈活：可以為每個節(jié)點和連接設(shè)置參數(shù)。可以指定多帶帶的x和y來代替force.gravity。新的link force代替force.linkStrength并且更穩(wěn)定。新的many-body force代替原有的force.charge并且支持最小距離參數(shù)。性能的提高歸功于4.0的新的四叉樹。4.0提供了沖突解決和向中對齊的方法。
新的力導(dǎo)向仿真避免不確定性，比如在3.x中結(jié)點的初始位置是隨機(jī)的，如果結(jié)點沒有初始位置，則被放置在一個類似葉序圖案上。
力導(dǎo)向仿真提供了一些方法來控制結(jié)點"過熱"(根本停不下來那種),比如simulation.alphaMin和simulation.alphaDecay和內(nèi)部計時器。調(diào)用simulation.alpha時對內(nèi)部計時器沒有影響，它由simulation.stop和simulatonrestart獨立控制。與3.x一樣，4.0使用simulation.tick來打點。force.frition由simulation.velocityDecay代替。新的simulation.alphaTarget方法允許設(shè)置期望的仿真"溫度"(什么時候停下來)。這樣可以使仿真重新開始然后再次冷卻，提高了交互過程中的穩(wěn)定性。
force布局不再依賴拖拽行為，因為你可以直接創(chuàng)建一個可拖動的力導(dǎo)向布局。設(shè)置node.fx和node.fy來修正節(jié)點的位置。simulation.find方法替代了泰森多邊形的SVG疊加，以找到最近節(jié)點的引用。
四叉樹是什么鬼四叉樹（quad-tree）是一種數(shù)據(jù)結(jié)構(gòu)，是一種每個節(jié)點最多有四個子樹的數(shù)據(jù)結(jié)構(gòu)。
四叉樹的定義是：它的每個節(jié)點下至多可以有四個子節(jié)點，通常把一部分二維空間細(xì)分為四個象限或區(qū)域并把該區(qū)域里的相關(guān)信息存入到四叉樹節(jié)點中。
四叉樹可以用來做什么用來在數(shù)據(jù)庫中放置和定位文件（稱作記錄或鍵）
2D空間碰撞校驗
地理空間劃分常用于GIS查詢
圖像處理
基于四叉樹2D空間碰撞校驗d3.v4里的force就是使用到四叉樹的碰撞校驗。該方法也經(jīng)常被游戲領(lǐng)域使用到。
我們來觀察一下：每個實體根據(jù)他在2D空間的位置而被放入這些子節(jié)點（正方形區(qū)域）中的一個里。任何不能正好在一個節(jié)點區(qū)域內(nèi)的物體會被放在父節(jié)點。完全處于一個子區(qū)域內(nèi)的點是不會與另一個區(qū)域的點碰撞的，這使得我們在做碰撞校驗或者獲取相鄰的節(jié)點時成倍的減少校驗計算。
以上圖為例，存儲方式有多種。存儲的最大差異在意當(dāng)實體坐標(biāo)位于區(qū)域邊上的時候，該實體應(yīng)存儲在哪個位置。
存儲方法一：
那么所有實體只能與以自己為跟節(jié)點的樹的所有節(jié)點上的實體才有可能發(fā)生碰撞。
同理，實體只能與自身所在象限的其他實體發(fā)生碰撞（這里暫時先不考慮碰撞半徑）。
d3-quadtree 的四叉樹API地址：https://github.com/d3/d3-quad...
中文地址：https://github.com/Leannechn/...
代碼試運行地址：https://runkit.com/npm/d3-qua...
d3-quadtree采用的第二種存儲方式，為了避免浮點計算的精確度問題，最小區(qū)域單位為1
創(chuàng)建只有一個實體的四叉樹
// 測試代碼二
var d3Quadtree = require("d3-quadtree")
var data = [[1.1,1.2]];
var tree = d3Quadtree.quadtree().addAll(data);
這里我們要說明幾個變量和函數(shù)名的含義
Quadtree.extend() // [[x0,y0],[x1,y1]]四叉樹的邊界，即矩形的左上頂點的坐標(biāo)，與右下頂點坐標(biāo) Quadtree.x0 // 正方形區(qū)域左上頂點坐標(biāo)x Quadtree.y0 // 正方形區(qū)域左上頂點坐標(biāo)y Quadtree.x1 // 正方形區(qū)域右下頂點坐標(biāo)x Quadtree.y1 // 正方形區(qū)域右下頂點坐標(biāo)y
root
/
第一象限：_root[0] 第三象限：_root[2]==> [2,6]
/
/
第一象限：_root0-->[1.1,1.2] 第二象限：_root0-->[3,1]
在理解了四叉樹的存儲之后，我們在看d3-quadtree的API。是否一目了然了呢！
下文我們來看看d3-quadtree的源碼。
1.1
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/82325.html
摘要：設(shè)置力導(dǎo)圖點陣中心碰撞其他引用模塊構(gòu)造常量函數(shù)微小晃動隨機(jī)數(shù)四叉樹模塊設(shè)置力導(dǎo)圖點陣中心此處代碼使用的是單例對象模式，讀者要注意，切勿與類對象理解混了。 首先先推薦一下某呆翻譯的d3-force的中文文檔：https://github.com/xswei/D3-V... 。 在我們解讀源碼前還請讀者先熟悉一下force相關(guān)的API,以及es6語法 . 如有分析不當(dāng)之處還請留言指出，謝謝...
摘要：本篇文章已授權(quán)微信公眾號郭霖獨家發(fā)布老規(guī)矩先上圖最近沒有什么時間，后面項目再補(bǔ)上詳細(xì)說明百度地圖新增點聚合功能。百度地圖是把整個地球是按照一個平面來展開，并且通過墨卡托投影投射到坐標(biāo)軸上面。上圖很明顯墨卡托投影把整張世界地圖投影成。 本篇文章已授權(quán)微信公眾號 guolin_blog （郭霖）獨家發(fā)布 老規(guī)矩先上圖最近 沒有什么時間，后面項目再補(bǔ)上詳細(xì)說明 showImg(https:/...
摘要：最近想要研究研究地形的渲染，然后就想起了四叉樹，在網(wǎng)上看了一篇相關(guān)的文章，準(zhǔn)備拿實現(xiàn)一下備用。四叉樹的定義是它的每個節(jié)點下至多可以有四個子節(jié)點，通常把一部分二維空間細(xì)分為四個象限或區(qū)域并把該區(qū)域里的相關(guān)信息存入到四叉樹節(jié)點中。 最近想要研究研究webgl地形的渲染，然后就想起了四叉樹，在網(wǎng)上看了一篇相關(guān)的文章，準(zhǔn)備拿javascript實現(xiàn)一下備用。 四叉樹原理 （這部分就直...
摘要：源碼剖析由于紅黑樹的操作我這里不說了，所以這里基本上也就沒什么源碼可以講了，因為這里面重要的算法都是，這里的是指，他們是算法導(dǎo)論的作者，也就是說里面算法都是參照算法導(dǎo)論的偽代碼。因為紅黑樹是平衡的二叉搜索樹，所以其包含操作的時間復(fù)雜度都為。 本文章首發(fā)于個人博客，鑒于sf博客樣式具有賞心悅目的美感，遂發(fā)表于此，供大家學(xué)習(xí)、批評。本文還在不斷更新中，最新版可移至個人博客。? 繼上篇文章...
閱讀 954·2021-11-25 09:43
閱讀 2290·2019-08-30 15:55
閱讀 3153·2019-08-30 15:44
閱讀 2052·2019-08-29 16:20
閱讀 1452·2019-08-29 12:12
閱讀 1608·2019-08-26 12:19
閱讀 2282·2019-08-26 11:49
閱讀 1711·2019-08-26 11:42
