{"id":328,"date":"2014-12-06T01:37:20","date_gmt":"2014-12-05T17:37:20","guid":{"rendered":"http:\/\/www.hightopo.com\/blog\/?p=328"},"modified":"2014-12-06T08:50:31","modified_gmt":"2014-12-06T00:50:31","slug":"ht-for-web%e5%8f%af%e8%a7%86%e5%8c%96quadtree%e5%9b%9b%e5%8f%89%e6%a0%91%e7%a2%b0%e6%92%9e%e6%a3%80%e6%b5%8b","status":"publish","type":"post","link":"https:\/\/www.hightopo.com\/blog\/328.html","title":{"rendered":"HT for Web\u53ef\u89c6\u5316QuadTree\u56db\u53c9\u6811\u78b0\u649e\u68c0\u6d4b"},"content":{"rendered":"<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Quadtree\">QuadTree<\/a>\u56db\u53c9\u6811\u987e\u540d\u601d\u4e49\u5c31\u662f\u6811\u72b6\u7684\u6570\u636e\u7ed3\u6784\uff0c\u5176\u6bcf\u4e2a\u8282\u70b9\u6709\u56db\u4e2a\u5b69\u5b50\u8282\u70b9\uff0c\u53ef\u5c06\u4e8c\u7ef4\u5e73\u9762\u9012\u5f52\u5206\u5272\u5b50\u533a\u57df\u3002QuadTree\u5e38\u7528\u4e8e\u7a7a\u95f4\u6570\u636e\u5e93\u7d22\u5f15\uff0c3D\u7684\u690e\u4f53\u53ef\u89c1\u533a\u57df\u88c1\u526a\uff0c\u751a\u81f3\u56fe\u7247\u5206\u6790\u5904\u7406\uff0c\u6211\u4eec\u4eca\u5929\u4ecb\u7ecd\u7684\u662fQuadTree\u6700\u5e38\u88ab\u6e38\u620f\u9886\u57df\u4f7f\u7528\u5230\u7684\u78b0\u649e\u68c0\u6d4b\u3002\u91c7\u7528QuadTree\u7b97\u6cd5\u5c06\u5927\u5927\u51cf\u5c11\u9700\u8981\u6d4b\u8bd5\u78b0\u649e\u7684\u6b21\u6570\uff0c\u4ece\u800c\u63d0\u9ad8\u6e38\u620f\u5237\u65b0\u6027\u80fd\uff0c\u672c\u6587\u4f8b\u5b50\u57fa\u4e8e<a href=\"http:\/\/www.hightopo.com\/\">HT for Web<\/a>\u7684\u56fe\u5f62\u5f15\u64ce\uff0c\u901a\u8fc7<a href=\"http:\/\/www.hightopo.com\/\">GraphView<\/a>\u548c<a href=\"http:\/\/www.hightopo.com\/\">Graph3dView<\/a>\u5171\u4eab\u540c\u4e00\u6570\u636e\u6a21\u578b<a href=\"http:\/\/www.hightopo.com\/\">DataModel<\/a>\uff0c\u540c\u65f6\u5448\u73b0QuadTree\u7b97\u6cd5\u4e0b\u76842D\u548c3D\u78b0\u649e\u89c6\u56fe\u6548\u679c\uff1a<\/p>\n<p><a href=\"http:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.41.24-AM.png\"><img loading=\"lazy\" class=\"alignnone size-full wp-image-329\" alt=\"Screen Shot 2014-12-06 at 12.41.24 AM\" src=\"http:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.41.24-AM.png\" width=\"981\" height=\"612\" srcset=\"https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.41.24-AM.png 981w, https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.41.24-AM-300x187.png 300w, https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.41.24-AM-200x124.png 200w\" sizes=\"(max-width: 981px) 100vw, 981px\" \/><\/a><\/p>\n<p>QuadTree\u7684\u5b9e\u73b0\u6709\u5f88\u591a\u6210\u719f\u7684\u7248\u672c\uff0c\u6211\u9009\u62e9\u7684\u662f\u00a0<a href=\"https:\/\/github.com\/timohausmann\/quadtree-js\/\">https:\/\/github.com\/timohausmann\/quadtree-js\/<\/a>\u00a0\u56db\u53c9\u6811\u7684\u7b97\u6cd5\u5f88\u7b80\u5355\uff0c\u56e0\u6b64\u8fd9\u4e2a\u5f00\u6e90\u5e93\u4e5f\u5c31\u4e24\u767e\u6765\u884c\u4ee3\u7801\u3002\u4f7f\u7528\u4e5f\u975e\u5e38\u7b80\u5355\uff0c\u6784\u5efa\u4e00\u4e2aQuadtree\u5bf9\u8c61\uff0c\u7b2c\u4e00\u4e2a\u53c2\u6570\u4f20\u5165rect\u4fe1\u606f\u5236\u5b9a\u6e38\u620f\u7a7a\u95f4\u8303\u56f4\uff0c\u5728\u6bcf\u6b21requestAnimationFrame\u5237\u65b0\u5e27\u65f6\uff0c\u5148\u901a\u8fc7quadtree.clear()\u6e05\u9664\u8001\u6570\u636e\uff0c\u901a\u8fc7quadtree.insert(rect)\u63d2\u5165\u65b0\u7684\u8282\u70b9\u77e9\u5f62\u533a\u57df\uff0c\u8fd9\u6837quadtree\u5c31\u521d\u59cb\u5316\u597d\u4e86\uff0c\u5269\u4e0b\u5c31\u662f\u6839\u636e\u9700\u8981\u8c03\u7528quadtree.retrieve(rect)\u83b7\u53d6\u6307\u5b9a\u77e9\u5f62\u533a\u57df\u4e0b\uff0c\u4e0e\u5176\u53ef\u80fd\u76f8\u4ea4\u9700\u8981\u68c0\u6d4b\u7684\u77e9\u5f62\u5bf9\u8c61\u6570\u7ec4\u3002<\/p>\n<p>\u6211\u6784\u5efa\u4e86<a href=\"http:\/\/www.hightopo.com\/\">HT<\/a>\u7684<a href=\"http:\/\/www.hightopo.com\/\">GraphView<\/a>\u548c<a href=\"http:\/\/www.hightopo.com\/\">Graph3dView<\/a>\u4e24\u4e2a\u7ec4\u4ef6\uff0c\u901a\u8fc7<a href=\"http:\/\/www.hightopo.com\/\">ht.widget.SplitView<\/a>\u5de6\u53f3\u5206\u5272\uff0c\u7531\u4e8e\u4e24\u4e2a\u89c6\u56fe\u90fd\u5171\u4eab\u540c\u4e00DataModel\uff0c\u56e0\u6b64\u6211\u4eec\u5269\u4e0b\u7684\u5173\u6ce8\u70b9\u4ec5\u662f\u5bf9DataModel\u7684\u6570\u636e\u64cd\u4f5c\uff0c\u6784\u5efa\u4e86200\u4e2aht.Node\u5bf9\u8c61\uff0c\u6bcf\u4e2a\u5bf9\u8c61\u7684attr\u5c5e\u6027\u4e0a\u4fdd\u5b58\u4e86\u968f\u673a\u7684\u8fd0\u52a8\u65b9\u5411vx\u548cvy\uff0c\u540c\u65f6\u4fdd\u5b58\u4e86\u5c06\u8981\u53cd\u590d\u63d2\u5165quadtree\u7684\u77e9\u5f62\u5bf9\u8c61\uff0c\u8fd9\u6837\u907f\u514d\u6bcf\u5e27\u66f4\u65b0\u65f6\u53cd\u590d\u521b\u5efa\u5bf9\u8c61\uff0c\u540c\u65f6\u77e9\u5f62\u5bf9\u8c61\u4e5f\u5f15\u7528\u4e86ht.Node\u5bf9\u8c61\uff0c\u7528\u6765\u5f53\u901a\u8fc7quadtree.retrieve(rect)\u83b7\u53d6\u9700\u8981\u68c0\u6d4b\u7684\u77e9\u5f62\u5bf9\u8c61\u65f6\uff0c\u6211\u4eec\u80fd\u6307\u5b9a\u5176\u6240\u5173\u8054\u7684ht.Node\u5bf9\u8c61\uff0c\u56e0\u4e3a\u6211\u4eec\u9700\u8981\u5bf9\u6700\u7ec8\u68c0\u6d4b\u4e3a\u78b0\u649e\u7684\u56fe\u5143\u8bbe\u7f6e\u4e0a\u7ea2\u989c\u8272\u7684\u6548\u679c\uff0c\u4e5f\u5c31\u662fht.Node\u5e73\u65f6\u663e\u793a\u9ed8\u8ba4\u7684\u84dd\u8272\uff0c\u5f53\u4e92\u76f8\u78b0\u649e\u65f6\u5c06\u6539\u53d8\u4e3a\u7ea2\u8272\u3002<\/p>\n<p>\u9700\u8981\u6ce8\u610f\u4ecequadtree.retrieve(rect)\u83b7\u53d6\u9700\u8981\u68c0\u6d4b\u7684\u77e9\u5f62\u5bf9\u8c61\u6570\u7ec4\u4e2d\u4f1a\u5305\u542b\u81ea\u8eab\u56fe\u5143\uff0c\u540c\u65f6\u8fd9\u4e9b\u4ec5\u4ec5\u662f\u53ef\u80fd\u4f1a\u78b0\u649e\u7684\u56fe\u5143\uff0c\u5e76\u4e0d\u610f\u5473\u7740\u5df2\u7ecf\u78b0\u649e\u4e86\uff0c\u7531\u4e8e\u6211\u4eec\u4f8b\u5b50\u662f\u77e9\u5f62\uff0c\u56e0\u6b64\u91c7\u7528ht.Default.intersectsRect(r1, r2)\u6700\u7ec8\u5224\u65ad\u662f\u5426\u76f8\u4ea4\uff0c\u5982\u679c\u4f60\u7684\u4f8b\u5b50\u662f\u5706\u5f62\u5219\u53ef\u4ee5\u91c7\u7528\u8ba1\u7b97\u4e24\u4e2a\u5706\u5fc3\u8ddd\u79bb\u662f\u5426\u5c0f\u4e8e\u4e24\u4e2a\u534a\u5f84\u6765\u51b3\u5b9a\u662f\u5426\u76f8\u4ea4\uff0c\u56e0\u6b64\u6700\u7ec8\u5224\u65ad\u7684\u6807\u51c6\u6839\u636e\u6e38\u620f\u7c7b\u578b\u4f1a\u6709\u5dee\u5f02\u3002<\/p>\n<p>\u91c7\u7528\u4e86QuadTree\u8fd8\u662f\u6781\u5927\u4e86\u63d0\u9ad8\u4e86\u8fd0\u7b97\u6027\u80fd\uff0c\u5426\u5219100\u4e2a\u56fe\u5143\u5c31\u9700\u8981100*100\u6b21\u7684\u76d1\u6d4b\uff0c\u6211\u8fd9\u4e2a\u4f8b\u5b50\u573a\u666f\u4e0b\u4e00\u822c\u4e5f\u5c31100*(10~30)\u7684\u91cf\uff1a<a href=\"http:\/\/v.youku.com\/v_show\/id_XODQyNTA1NjY0.html\">http:\/\/v.youku.com\/v_show\/id_XODQyNTA1NjY0.html<\/a><br \/>\n<iframe loading=\"lazy\" src=\"http:\/\/player.youku.com\/embed\/XODQyNTA1NjY0\" height=\"498\" width=\"510\" allowfullscreen=\"\" frameborder=\"0\"><\/iframe><br \/>\n<a style=\"line-height: 1.5em;\" href=\"http:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.42.35-AM.png\"><img loading=\"lazy\" class=\"alignnone size-full wp-image-330\" alt=\"Screen Shot 2014-12-06 at 12.42.35 AM\" src=\"http:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.42.35-AM.png\" width=\"991\" height=\"632\" srcset=\"https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.42.35-AM.png 991w, https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.42.35-AM-300x191.png 300w, https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.42.35-AM-200x127.png 200w\" sizes=\"(max-width: 991px) 100vw, 991px\" \/><\/a><span style=\"line-height: 1.5em;\"><br \/>\n<\/span><\/p>\n<p>\u9664\u4e86\u78b0\u649e\u68c0\u6d4b\u5916QuadTree\u7b97\u6cd5\u8fd8\u6709\u5f88\u591a\u6709\u8da3\u7684\u5e94\u7528\u9886\u57df\uff0c\u6709\u5174\u8da3\u53ef\u4ee5\u73a9\u73a9\u8fd9\u4e2a\u00a0<a href=\"https:\/\/github.com\/fogleman\/Quads\">https:\/\/github.com\/fogleman\/Quads<\/a><\/p>\n<p><a href=\"http:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.52.17-AM.png\"><img loading=\"lazy\" class=\"alignnone size-full wp-image-331\" alt=\"Screen Shot 2014-12-06 at 12.52.17 AM\" src=\"http:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.52.17-AM.png\" width=\"655\" height=\"335\" srcset=\"https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.52.17-AM.png 655w, https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.52.17-AM-300x153.png 300w, https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.52.17-AM-200x102.png 200w\" sizes=\"(max-width: 655px) 100vw, 655px\" \/><\/a><\/p>\n<p>\u6240\u6709\u4ee3\u7801\u5982\u4e0b\u4f9b\u53c2\u8003\uff1a<\/p>\n<pre class=\"&quot;brush:javascript\u201d\">function init(){  \r\n\td = 200;\r\n\tspeed = 8;\r\n\tdataModel = new ht.DataModel();                                \r\n\tg3d = new ht.graph3d.Graph3dView(dataModel);                                                  \r\n\tg2d = new ht.graph.GraphView(dataModel);                   \r\n\tmainSplit = new ht.widget.SplitView(g3d, g2d);                   \r\n\tmainSplit.addToDOM();                                        \r\n\tg2d.translate(300, 220);      \r\n\tg2d.setZoom(0.8, true);\r\n\r\n\tfor(var i=0; i&lt;100; i++) {\r\n\t\tvar node = new ht.Node();\r\n\t\tnode.s3(randMinMax(5, 30), 10, randMinMax(5, 30));\r\n\t\tnode.p3(randMinMax(-d\/2, d\/2), 0, randMinMax(-d\/2, d\/2));\r\n\t\tnode.s({\r\n\t\t\t'batch': 'group',\r\n\t\t\t'shape': 'rect',\r\n\t\t\t'shape.border.width': 1,\r\n\t\t\t'shape.border.color': 'white',\r\n\t\t\t'wf.visible': true,\r\n\t\t\t'wf.color': 'white'\r\n\t\t});\r\n\t\tnode.a({\r\n\t\t\tvx: randMinMax(-speed, speed),\r\n\t\t\tvy: randMinMax(-speed, speed),\r\n\t\t\tobj: {\r\n\t\t\t\twidth: node.getWidth(),\r\n\t\t\t\theight: node.getHeight(),\r\n\t\t\t\tdata: node\r\n\t\t\t}\r\n\t\t});                    \r\n\t\tdataModel.add(node);\r\n\t}                \r\n\tcreateShape([\r\n\t\t{x: -d, y: d},\r\n\t\t{x: d, y: d},\r\n\t\t{x: d, y: -d},\r\n\t\t{x: -d, y: -d},\r\n\t\t{x: -d, y: d}\r\n\t]);                   \r\n\tquadtree = new Quadtree({ x: -d, y: -d, width: d, height: d });                                \r\n\trequestAnimationFrame(update);\r\n}               \r\nfunction update() {   \r\n\tquadtree.clear();                \r\n\tdataModel.each(function(data){\r\n\t\tif(!(data instanceof ht.Shape)){\r\n\t\t\tvar position = data.getPosition();\r\n\t\t\tvar vx = data.a('vx');\r\n\t\t\tvar vy = data.a('vy');\r\n\t\t\tvar w = data.getWidth()\/2;\r\n\t\t\tvar h = data.getHeight()\/2;\r\n\t\t\tvar x = position.x + vx;\r\n\t\t\tvar y = position.y + vy;\r\n\t\t\tif(x - w &lt; -d){ \t\t\t\tdata.a('vx', -vx); \t\t\t\tx = -d + w; \t\t\t} \t\t\tif(x + w &gt; d){\r\n\t\t\t\tdata.a('vx', -vx);\r\n\t\t\t\tx = d - w;\r\n\t\t\t}\r\n\t\t\tif(y - h &lt; -d){ \t\t\t\tdata.a('vy', -vy); \t\t\t\ty = -d + h; \t\t\t} \t\t\tif(y + h &gt; d){\r\n\t\t\t\tdata.a('vy', -vy);\r\n\t\t\t\ty = d - h;\r\n\t\t\t}\r\n\t\t\tdata.setPosition(x, y);                        \r\n\t\t\tvar obj = data.a('obj');\r\n\t\t\tobj.x = x - w;\r\n\t\t\tobj.y = y - h;\r\n\r\n\t\t\tquadtree.insert(obj);\r\n\t\t\tsetColor(data, undefined);\r\n\t\t}\r\n\t});                \r\n\tdataModel.each(function(data){\r\n\t\tif(!(data instanceof ht.Shape)){ \r\n\t\t\tvar obj = data.a('obj');\r\n\t\t\tvar objs = quadtree.retrieve(obj);\r\n\t\t\tif(objs.length &gt; 1){                            \r\n\t\t\t\tfor(var i=0; i&lt;objs.length; i++ ) {\r\n\t\t\t\t\tvar data2 = objs[i].data;\r\n\t\t\t\t\tif(data === data2){\r\n\t\t\t\t\t\tcontinue;\r\n\t\t\t\t\t}\r\n\t\t\t\t\tif(ht.Default.intersectsRect(obj, data2.a('obj'))){\r\n\t\t\t\t\t\tsetColor(data, 'red');\r\n\t\t\t\t\t\tsetColor(data2, 'red');\r\n\t\t\t\t\t}                                \r\n\t\t\t\t}                             \r\n\t\t\t}\r\n\t\t}\r\n\t});\r\n\trequestAnimationFrame(update);                    \r\n}                        \r\nfunction randMinMax(min, max) {\r\n\treturn min + (Math.random() * (max - min));\r\n}                      \r\nfunction createShape(points){\r\n\tshape = new ht.Shape();\r\n\tshape.setPoints(points);\r\n\tshape.setThickness(4);\r\n\tshape.setTall(10);                                \r\n\tshape.s({\r\n\t\t'all.color': 'red',\r\n\t\t'shape.background': null,\r\n\t\t'shape.border.width': 2,\r\n\t\t'shape.border.color': 'red'                    \r\n\t});                \r\n\tdataModel.add(shape); \r\n\treturn shape;\r\n}\r\nfunction setColor(data, color){\r\n\tdata.s({\r\n\t\t'all.color': color,\r\n\t\t'shape.background': color\r\n\t});\r\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Quadtree\">QuadTree<\/a>\u56db\u53c9\u6811\u987e\u540d\u601d\u4e49\u5c31\u662f\u6811\u72b6\u7684\u6570\u636e\u7ed3\u6784\uff0c\u5176\u6bcf\u4e2a\u8282\u70b9\u6709\u56db\u4e2a\u5b69\u5b50\u8282\u70b9\uff0c\u53ef\u5c06\u4e8c\u7ef4\u5e73\u9762\u9012\u5f52\u5206\u5272\u5b50\u533a\u57df\u3002QuadTree\u5e38\u7528\u4e8e\u7a7a\u95f4\u6570\u636e\u5e93\u7d22\u5f15\uff0c3D\u7684\u690e\u4f53\u53ef\u89c1\u533a\u57df\u88c1\u526a\uff0c\u751a\u81f3\u56fe\u7247\u5206\u6790\u5904\u7406\uff0c\u6211\u4eec\u4eca\u5929\u4ecb\u7ecd\u7684\u662fQuadTree\u6700\u5e38\u88ab\u6e38\u620f\u9886\u57df\u4f7f\u7528\u5230\u7684\u78b0\u649e\u68c0\u6d4b\u3002\u91c7\u7528QuadTree\u7b97\u6cd5\u5c06\u5927\u5927\u51cf\u5c11\u9700\u8981\u6d4b\u8bd5\u78b0\u649e\u7684\u6b21\u6570\uff0c\u4ece\u800c\u63d0\u9ad8\u6e38\u620f\u5237\u65b0\u6027\u80fd\uff0c\u672c\u6587\u4f8b\u5b50\u57fa\u4e8e<a href=\"http:\/\/www.hightopo.com\/\">HT for Web<\/a>\u7684\u56fe\u5f62\u5f15\u64ce\uff0c\u901a\u8fc7<a href=\"http:\/\/www.hightopo.com\/\">GraphView<\/a>\u548c<a href=\"http:\/\/www.hightopo.com\/\">Graph3dView<\/a>\u5171\u4eab\u540c\u4e00\u6570\u636e\u6a21\u578b<a href=\"http:\/\/www.hightopo.com\/\">DataModel<\/a>\uff0c\u540c\u65f6\u5448\u73b0QuadTree\u7b97\u6cd5\u4e0b\u76842D\u548c3D\u78b0\u649e\u89c6\u56fe\u6548\u679c\uff1a<\/p>\n<p><a href=\"http:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.41.24-AM.png\"><img loading=\"lazy\" class=\"alignnone size-full wp-image-329\" alt=\"Screen Shot 2014-12-06 at 12.41.24 AM\" src=\"http:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.41.24-AM.png\" width=\"981\" height=\"612\" srcset=\"https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.41.24-AM.png 981w, https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.41.24-AM-300x187.png 300w, https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.41.24-AM-200x124.png 200w\" sizes=\"(max-width: 981px) 100vw, 981px\" \/><\/a><\/p>\n<p>QuadTree\u7684\u5b9e\u73b0\u6709\u5f88\u591a\u6210\u719f\u7684\u7248\u672c\uff0c\u6211\u9009\u62e9\u7684\u662f\u00a0<a href=\"https:\/\/github.com\/timohausmann\/quadtree-js\/\">https:\/\/github.com\/timohausmann\/quadtree-js\/<\/a>\u00a0\u56db\u53c9\u6811\u7684\u7b97\u6cd5\u5f88\u7b80\u5355\uff0c\u56e0\u6b64\u8fd9\u4e2a\u5f00\u6e90\u5e93\u4e5f\u5c31\u4e24\u767e\u6765\u884c\u4ee3\u7801\u3002\u4f7f\u7528\u4e5f\u975e\u5e38\u7b80\u5355\uff0c\u6784\u5efa\u4e00\u4e2aQuadtree\u5bf9\u8c61\uff0c\u7b2c\u4e00\u4e2a\u53c2\u6570\u4f20\u5165rect\u4fe1\u606f\u5236\u5b9a\u6e38\u620f\u7a7a\u95f4\u8303\u56f4\uff0c\u5728\u6bcf\u6b21requestAnimationFrame\u5237\u65b0\u5e27\u65f6\uff0c\u5148\u901a\u8fc7quadtree.clear()\u6e05\u9664\u8001\u6570\u636e\uff0c\u901a\u8fc7quadtree.insert(rect)\u63d2\u5165\u65b0\u7684\u8282\u70b9\u77e9\u5f62\u533a\u57df\uff0c\u8fd9\u6837quadtree\u5c31\u521d\u59cb\u5316\u597d\u4e86\uff0c\u5269\u4e0b\u5c31\u662f\u6839\u636e\u9700\u8981\u8c03\u7528quadtree.retrieve(rect)\u83b7\u53d6\u6307\u5b9a\u77e9\u5f62\u533a\u57df\u4e0b\uff0c\u4e0e\u5176\u53ef\u80fd\u76f8\u4ea4\u9700\u8981\u68c0\u6d4b\u7684\u77e9\u5f62\u5bf9\u8c61\u6570\u7ec4\u3002<\/p>\n<p>\u6211\u6784\u5efa\u4e86<a href=\"http:\/\/www.hightopo.com\/\">HT<\/a>\u7684<a href=\"http:\/\/www.hightopo.com\/\">GraphView<\/a>\u548c<a href=\"http:\/\/www.hightopo.com\/\">Graph3dView<\/a>\u4e24\u4e2a\u7ec4\u4ef6\uff0c\u901a\u8fc7<a href=\"http:\/\/www.hightopo.com\/\">ht.widget.SplitView<\/a>\u5de6\u53f3\u5206\u5272\uff0c\u7531\u4e8e\u4e24\u4e2a\u89c6\u56fe\u90fd\u5171\u4eab\u540c\u4e00DataModel\uff0c\u56e0\u6b64\u6211\u4eec\u5269\u4e0b\u7684\u5173\u6ce8\u70b9\u4ec5\u662f\u5bf9DataModel\u7684\u6570\u636e\u64cd\u4f5c\uff0c\u6784\u5efa\u4e86200\u4e2aht.Node\u5bf9\u8c61\uff0c\u6bcf\u4e2a\u5bf9\u8c61\u7684attr\u5c5e\u6027\u4e0a\u4fdd\u5b58\u4e86\u968f\u673a\u7684\u8fd0\u52a8\u65b9\u5411vx\u548cvy\uff0c\u540c\u65f6\u4fdd\u5b58\u4e86\u5c06\u8981\u53cd\u590d\u63d2\u5165quadtree\u7684\u77e9\u5f62\u5bf9\u8c61\uff0c\u8fd9\u6837\u907f\u514d\u6bcf\u5e27\u66f4\u65b0\u65f6\u53cd\u590d\u521b\u5efa\u5bf9\u8c61\uff0c\u540c\u65f6\u77e9\u5f62\u5bf9\u8c61\u4e5f\u5f15\u7528\u4e86ht.Node\u5bf9\u8c61\uff0c\u7528\u6765\u5f53\u901a\u8fc7quadtree.retrieve(rect)\u83b7\u53d6\u9700\u8981\u68c0\u6d4b\u7684\u77e9\u5f62\u5bf9\u8c61\u65f6\uff0c\u6211\u4eec\u80fd\u6307\u5b9a\u5176\u6240\u5173\u8054\u7684ht.Node\u5bf9\u8c61\uff0c\u56e0\u4e3a\u6211\u4eec\u9700\u8981\u5bf9\u6700\u7ec8\u68c0\u6d4b\u4e3a\u78b0\u649e\u7684\u56fe\u5143\u8bbe\u7f6e\u4e0a\u7ea2\u989c\u8272\u7684\u6548\u679c\uff0c\u4e5f\u5c31\u662fht.Node\u5e73\u65f6\u663e\u793a\u9ed8\u8ba4\u7684\u84dd\u8272\uff0c\u5f53\u4e92\u76f8\u78b0\u649e\u65f6\u5c06\u6539\u53d8\u4e3a\u7ea2\u8272\u3002<\/p>\n<p>\u9700\u8981\u6ce8\u610f\u4ecequadtree.retrieve(rect)\u83b7\u53d6\u9700\u8981\u68c0\u6d4b\u7684\u77e9\u5f62\u5bf9\u8c61\u6570\u7ec4\u4e2d\u4f1a\u5305\u542b\u81ea\u8eab\u56fe\u5143\uff0c\u540c\u65f6\u8fd9\u4e9b\u4ec5\u4ec5\u662f\u53ef\u80fd\u4f1a\u78b0\u649e\u7684\u56fe\u5143\uff0c\u5e76\u4e0d\u610f\u5473\u7740\u5df2\u7ecf\u78b0\u649e\u4e86\uff0c\u7531\u4e8e\u6211\u4eec\u4f8b\u5b50\u662f\u77e9\u5f62\uff0c\u56e0\u6b64\u91c7\u7528ht.Default.intersectsRect(r1, r2)\u6700\u7ec8\u5224\u65ad\u662f\u5426\u76f8\u4ea4\uff0c\u5982\u679c\u4f60\u7684\u4f8b\u5b50\u662f\u5706\u5f62\u5219\u53ef\u4ee5\u91c7\u7528\u8ba1\u7b97\u4e24\u4e2a\u5706\u5fc3\u8ddd\u79bb\u662f\u5426\u5c0f\u4e8e\u4e24\u4e2a\u534a\u5f84\u6765\u51b3\u5b9a\u662f\u5426\u76f8\u4ea4\uff0c\u56e0\u6b64\u6700\u7ec8\u5224\u65ad\u7684\u6807\u51c6\u6839\u636e\u6e38\u620f\u7c7b\u578b\u4f1a\u6709\u5dee\u5f02\u3002<\/p>\n<p>\u91c7\u7528\u4e86QuadTree\u8fd8\u662f\u6781\u5927\u4e86\u63d0\u9ad8\u4e86\u8fd0\u7b97\u6027\u80fd\uff0c\u5426\u5219100\u4e2a\u56fe\u5143\u5c31\u9700\u8981100*100\u6b21\u7684\u76d1\u6d4b\uff0c\u6211\u8fd9\u4e2a\u4f8b\u5b50\u573a\u666f\u4e0b\u4e00\u822c\u4e5f\u5c31100*(10~30)\u7684\u91cf\uff1a<a href=\"http:\/\/v.youku.com\/v_show\/id_XODQyNTA1NjY0.html\">http:\/\/v.youku.com\/v_show\/id_XODQyNTA1NjY0.html<\/a><br \/>\n<iframe loading=\"lazy\" src=\"http:\/\/player.youku.com\/embed\/XODQyNTA1NjY0\" height=\"498\" width=\"510\" allowfullscreen=\"\" frameborder=\"0\"><\/iframe><br \/>\n<a style=\"line-height: 1.5em;\" href=\"http:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.42.35-AM.png\"><img loading=\"lazy\" class=\"alignnone size-full wp-image-330\" alt=\"Screen Shot 2014-12-06 at 12.42.35 AM\" src=\"http:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.42.35-AM.png\" width=\"991\" height=\"632\" srcset=\"https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.42.35-AM.png 991w, https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.42.35-AM-300x191.png 300w, https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.42.35-AM-200x127.png 200w\" sizes=\"(max-width: 991px) 100vw, 991px\" \/><\/a><span style=\"line-height: 1.5em;\"><br \/>\n<\/span><\/p>\n<p>\u9664\u4e86\u78b0\u649e\u68c0\u6d4b\u5916QuadTree\u7b97\u6cd5\u8fd8\u6709\u5f88\u591a\u6709\u8da3\u7684\u5e94\u7528\u9886\u57df\uff0c\u6709\u5174\u8da3\u53ef\u4ee5\u73a9\u73a9\u8fd9\u4e2a\u00a0<a href=\"https:\/\/github.com\/fogleman\/Quads\">https:\/\/github.com\/fogleman\/Quads<\/a><\/p>\n<p><a href=\"http:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.52.17-AM.png\"><img loading=\"lazy\" class=\"alignnone size-full wp-image-331\" alt=\"Screen Shot 2014-12-06 at 12.52.17 AM\" src=\"http:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.52.17-AM.png\" width=\"655\" height=\"335\" srcset=\"https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.52.17-AM.png 655w, https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.52.17-AM-300x153.png 300w, https:\/\/www.hightopo.com\/blog\/wp-content\/uploads\/2014\/12\/Screen-Shot-2014-12-06-at-12.52.17-AM-200x102.png 200w\" sizes=\"(max-width: 655px) 100vw, 655px\" \/><\/a><\/p>\n<p>\u6240\u6709\u4ee3\u7801\u5982\u4e0b\u4f9b\u53c2\u8003\uff1a<\/p>\n<pre class=\"&quot;brush:javascript\u201d\">function init(){  \r\n\td = 200;\r\n\tspeed = 8;\r\n\tdataModel = new ht.DataModel();                                \r\n\tg3d = new ht.graph3d.Graph3dView(dataModel);                                                  \r\n\tg2d = new ht.graph.GraphView(dataModel);                   \r\n\tmainSplit = new ht.widget.SplitView(g3d, g2d);                   \r\n\tmainSplit.addToDOM();                                        \r\n\tg2d.translate(300, 220);      \r\n\tg2d.setZoom(0.8, true);\r\n\r\n\tfor(var i=0; i&lt;100; i++) {\r\n\t\tvar node = new ht.Node();\r\n\t\tnode.s3(randMinMax(5, 30), 10, randMinMax(5, 30));\r\n\t\tnode.p3(randMinMax(-d\/2, d\/2), 0, randMinMax(-d\/2, d\/2));\r\n\t\tnode.s({\r\n\t\t\t'batch': 'group',\r\n\t\t\t'shape': 'rect',\r\n\t\t\t'shape.border.width': 1,\r\n\t\t\t'shape.border.color': 'white',\r\n\t\t\t'wf.visible': true,\r\n\t\t\t'wf.color': 'white'\r\n\t\t});\r\n\t\tnode.a({\r\n\t\t\tvx: randMinMax(-speed, speed),\r\n\t\t\tvy: randMinMax(-speed, speed),\r\n\t\t\tobj: {\r\n\t\t\t\twidth: node.getWidth(),\r\n\t\t\t\theight: node.getHeight(),\r\n\t\t\t\tdata: node\r\n\t\t\t}\r\n\t\t});                    \r\n\t\tdataModel.add(node);\r\n\t}                \r\n\tcreateShape([\r\n\t\t{x: -d, y: d},\r\n\t\t{x: d, y: d},\r\n\t\t{x: d, y: -d},\r\n\t\t{x: -d, y: -d},\r\n\t\t{x: -d, y: d}\r\n\t]);                   \r\n\tquadtree = new Quadtree({ x: -d, y: -d, width: d, height: d });                                \r\n\trequestAnimationFrame(update);\r\n}               \r\nfunction update() {   \r\n\tquadtree.clear();                \r\n\tdataModel.each(function(data){\r\n\t\tif(!(data instanceof ht.Shape)){\r\n\t\t\tvar position = data.getPosition();\r\n\t\t\tvar vx = data.a('vx');\r\n\t\t\tvar vy = data.a('vy');\r\n\t\t\tvar w = data.getWidth()\/2;\r\n\t\t\tvar h = data.getHeight()\/2;\r\n\t\t\tvar x = position.x + vx;\r\n\t\t\tvar y = position.y + vy;\r\n\t\t\tif(x - w &lt; -d){ \t\t\t\tdata.a('vx', -vx); \t\t\t\tx = -d + w; \t\t\t} \t\t\tif(x + w &gt; d){\r\n\t\t\t\tdata.a('vx', -vx);\r\n\t\t\t\tx = d - w;\r\n\t\t\t}\r\n\t\t\tif(y - h &lt; -d){ \t\t\t\tdata.a('vy', -vy); \t\t\t\ty = -d + h; \t\t\t} \t\t\tif(y + h &gt; d){\r\n\t\t\t\tdata.a('vy', -vy);\r\n\t\t\t\ty = d - h;\r\n\t\t\t}\r\n\t\t\tdata.setPosition(x, y);                        \r\n\t\t\tvar obj = data.a('obj');\r\n\t\t\tobj.x = x - w;\r\n\t\t\tobj.y = y - h;\r\n\r\n\t\t\tquadtree.insert(obj);\r\n\t\t\tsetColor(data, undefined);\r\n\t\t}\r\n\t});                \r\n\tdataModel.each(function(data){\r\n\t\tif(!(data instanceof ht.Shape)){ \r\n\t\t\tvar obj = data.a('obj');\r\n\t\t\tvar objs = quadtree.retrieve(obj);\r\n\t\t\tif(objs.length &gt; 1){                            \r\n\t\t\t\tfor(var i=0; i&lt;objs.length; i++ ) {\r\n\t\t\t\t\tvar data2 = objs[i].data;\r\n\t\t\t\t\tif(data === data2){\r\n\t\t\t\t\t\tcontinue;\r\n\t\t\t\t\t}\r\n\t\t\t\t\tif(ht.Default.intersectsRect(obj, data2.a('obj'))){\r\n\t\t\t\t\t\tsetColor(data, 'red');\r\n\t\t\t\t\t\tsetColor(data2, 'red');\r\n\t\t\t\t\t}                                \r\n\t\t\t\t}                             \r\n\t\t\t}\r\n\t\t}\r\n\t});\r\n\trequestAnimationFrame(update);                    \r\n}                        \r\nfunction randMinMax(min, max) {\r\n\treturn min + (Math.random() * (max - min));\r\n}                      \r\nfunction createShape(points){\r\n\tshape = new ht.Shape();\r\n\tshape.setPoints(points);\r\n\tshape.setThickness(4);\r\n\tshape.setTall(10);                                \r\n\tshape.s({\r\n\t\t'all.color': 'red',\r\n\t\t'shape.background': null,\r\n\t\t'shape.border.width': 2,\r\n\t\t'shape.border.color': 'red'                    \r\n\t});                \r\n\tdataModel.add(shape); \r\n\treturn shape;\r\n}\r\nfunction setColor(data, color){\r\n\tdata.s({\r\n\t\t'all.color': color,\r\n\t\t'shape.background': color\r\n\t});\r\n}<\/pre>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/www.hightopo.com\/blog\/wp-json\/wp\/v2\/posts\/328"}],"collection":[{"href":"https:\/\/www.hightopo.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.hightopo.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.hightopo.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.hightopo.com\/blog\/wp-json\/wp\/v2\/comments?post=328"}],"version-history":[{"count":4,"href":"https:\/\/www.hightopo.com\/blog\/wp-json\/wp\/v2\/posts\/328\/revisions"}],"predecessor-version":[{"id":335,"href":"https:\/\/www.hightopo.com\/blog\/wp-json\/wp\/v2\/posts\/328\/revisions\/335"}],"wp:attachment":[{"href":"https:\/\/www.hightopo.com\/blog\/wp-json\/wp\/v2\/media?parent=328"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.hightopo.com\/blog\/wp-json\/wp\/v2\/categories?post=328"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.hightopo.com\/blog\/wp-json\/wp\/v2\/tags?post=328"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}