{"id":920,"date":"2018-04-25T00:33:52","date_gmt":"2018-04-24T16:33:52","guid":{"rendered":"http:\/\/www.whudj.cn\/?p=920"},"modified":"2018-05-01T20:28:08","modified_gmt":"2018-05-01T12:28:08","slug":"kd%e6%a0%91%e7%9a%84%e4%b8%bb%e8%a6%81%e7%ae%97%e6%b3%95%e4%bb%a5%e5%8f%8aflannpcl%e7%9a%84%e5%ae%9e%e7%8e%b0%e5%88%86%e6%9e%90","status":"publish","type":"post","link":"http:\/\/www.whudj.cn\/?p=920","title":{"rendered":"KD\u6811\u7684\u4e3b\u8981\u7b97\u6cd5\u4ee5\u53caFLANN(PCL)\u7684\u5b9e\u73b0\u5206\u6790"},"content":{"rendered":"<p>kd\u6811\u53ef\u80fd\u662f\u6211\u4eec\u6700\u719f\u6089\u7684\u7a7a\u95f4\u7d22\u5f15\u3002kd\u6811\u7684\u5168\u79f0\u662fk-dimensional tree,\u987e\u540d\u601d\u4e49\uff0c\u662f\u4e00\u79cd\u5c06\u591a\u7ef4\u6570\u636e\u7ec4\u7ec7\u8d77\u6765\u7684\u6570\u636e\u7ed3\u6784\u3002\u4e0d\u4ec5\u670d\u52a1\u4e8e\u8ba1\u7b97\u51e0\u4f55\u9886\u57df\uff0c\u800c\u4e14\u5728\u7edf\u8ba1\u5206\u6790\u3001\u673a\u5668\u5b66\u4e60\u9886\u57df\u90fd\u662f\u975e\u5e38\u6d3b\u8dc3\u7684\u3002\u672c\u6587\u5c06\u4e3b\u8981\u56f4\u7ed5kd\u6811\u7684\u7ed3\u6784\u3001\u6784\u5efa\u3001\u534a\u5f84\u641c\u7d22\uff08\u8303\u56f4\u641c\u7d22\uff09\u3001\u6700\u8fd1\u90bb\u641c\u7d22(KNN)\u7b49\u4e3b\u8981\u7684\u7b97\u6cd5\u8fdb\u884c\u5c55\u5f00\uff0c\u540c\u65f6\u4e5f\u4f1a\u6d89\u53ca\u5230\u8fd1\u4f3c\u6700\u8fd1\u90bb\u4e0e\u6700\u8fd1\u90bb\u7b97\u6cd5\u7684\u533a\u522b\uff0cspliting \u7b56\u7565\u7b49\u6709\u8da3\u7684\u7ec6\u8282\u3002\u5e76\u4e14\uff0c\u6211\u8fd8\u4f1a\u4ecb\u7ecd\u90e8\u5206FLANN\u5e93(\u88abPCL\u4f7f\u7528)\u5bf9\u4e0a\u8ff0\u7b97\u6cd5\u7684\u5b9e\u73b0\u65b9\u5f0f\u3002\u5728\u6587\u7ae0\u672b\u5c3e\uff0c\u63d0\u4f9b\u4e86c++\u5b9e\u73b0\u4ee3\u7801\u3002<!--more--><\/p>\n<p><span style=\"text-decoration: underline;\"><strong>1.kd\u6811\u7684\u7ed3\u6784<\/strong><\/span><\/p>\n<p>kd\u6811\u662f\u4e00\u79cd\u4e8c\u53c9\u6811\u3002\u5e76\u4e14\u4e0e\u4e8c\u5206\u67e5\u627e\u6811(BST)\u6bd4\u8f83\u7c7b\u4f3c\u3002BST\u53ef\u4ee5\u5c06\u4e00\u7ec4\u5b9e\u6570\u9012\u5f52\u7684\u8fdb\u884c\u5212\u5206\uff0c\u7c7b\u4f3c\u7684\uff0c\u5728\u6bcf\u4e00\u5c42\u4e0akd\u6811\u6cbf\u7740\u6309\u7167\u67d0\u4e2a\u7ef4\u5ea6\u5c06\u6570\u636e\u5206\u4e3a\u4e24\u7ec4\uff0c\u4e24\u7ec4\u6570\u636e\u4f9d\u6b21\u8fdb\u884c\u5206\u5272\u5f62\u6210\u5b50\u6811\u3002\u5206\u5272\u7684\u5bf9\u8c61\u79f0\u4e4b\u4e3a\u8d85\u5e73\u9762(hyperplane)\uff0c\u8d85\u5e73\u9762\u5782\u76f4\u4e0e\u5bf9\u5e94\u7ef4\u5ea6\u7684\u8f74\u3002\u7406\u60f3\u7684\u8d85\u5e73\u9762\u662f\u5bf9\u5e94\u7ef4\u5ea6\u7684\u4e2d\u4f4d\u6570(median)\uff0c\u8fd9\u6837\u53ef\u4ee5\u4fdd\u8bc1\u6811\u7684\u5e73\u8861(balance),\u4ece\u800c\u964d\u4f4e\u6811\u7684\u6df1\u5ea6\u3002<\/p>\n<p>\u4e0b\u56fe\u6240\u793a\uff0c\u662fk=2\u65f6\u7684\u4e00\u9897kd\u6811\u3002\u9700\u8981\u63d0\u9192\u7684\u662f\u8fdb\u884c\u5212\u5206(split)\u7684\u7ef4\u5ea6\u7684\u987a\u5e8f\u53ef\u4ee5\u662f\u4efb\u610f\u7684\uff0c\u4e0d\u4e00\u5b9a\u6309\u7167x,y,z,x,y,z\u2026\u7684\u987a\u5e8f\u8fdb\u884c\u3002\u6bcf\u4e00\u4e2a\u8282\u70b9\u90fd\u4f1a\u8bb0\u5f55\u5212\u5206\u7684\u7ef4\u5ea6\u3002FLANN\u4e2d\u6709\u5212\u5206\u7ef4\u5ea6\u9009\u62e9\u7684\u7b97\u6cd5\u3002<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-924\" src=\"http:\/\/www.whudj.cn\/wp-content\/uploads\/2018\/04\/2dtree.png\" alt=\"\" width=\"500\" height=\"254\" \/><\/p>\n<p><strong><span style=\"text-decoration: underline;\">2.kd\u6811\u7684\u6784\u5efa(construction)<\/span><\/strong><\/p>\n<p>kd\u6811\u7684\u6784\u5efa\u662f\u91c7\u7528\u7684\u662f\u975e\u5e38\u5178\u578b\u7684\u9012\u5f52\u65b9\u6cd5\u3002\u53ef\u4ee5\u7528\u4e0b\u9762\u7684\u4f2a\u4ee3\u7801\u8868\u793a\u3002\u5176\u4e2d\uff0c\u9012\u5f52\u7ec8\u6b62\u6761\u4ef6\u662f\u8f93\u5165\u7684\u70b9\u7684\u4e2a\u6570\u5c0f\u4e8e\u53f6\u5b50\u8282\u70b9\u6700\u5927\u70b9\u4e2a\u6570\uff1b\u800c\u9012\u5f52\u7684\u90e8\u5206\u662f\u5c06\u8f93\u5165\u70b9\u5728\u4e2d\u4f4d\u6570\u5904\u5206\u4e3a\u4e24\u4e2a\u90e8\u5206\uff0c\u5206\u522b\u6784\u5efa\u5de6\u53f3\u5b50\u6811\u3002<\/p>\n<pre class=\"lang:c++ decode:true\">Node BuildTree(vector&lt;int&gt; inputs,int start,int end)\r\n{\r\n\tint size = end - start;\r\n\tDimension dim = SelectDimension(inputs,start,end);\r\n\tint median = Partition(inputs,start,end,dim);\r\n\tNode* pNode = new Node(inputs,start,end,dim,median);\r\n\tif(size &gt; _leaf_max_size)\r\n\t{\r\n\t\tpNode-&gt;left = BuildTree(inputs,start,median);\r\n\t\tpNode-&gt;right = BuildTree(inputs,median,end);\r\n\t}\r\n}<\/pre>\n<p>\u5177\u4f53\u5b9e\u73b0\u4ee3\u7801\u53ef\u4ee5\u5230\u672c\u6587\u6700\u540e\u4e00\u8282\u83b7\u53d6\u3002<\/p>\n<p>\u73b0\u5728\u6709\u4e24\u4e2a\u5177\u4f53\u7684\u95ee\u9898\u9700\u8981\u8003\u8651\uff1a<\/p>\n<p><span style=\"text-decoration: underline;\"><strong>2.1 \u600e\u6837\u9009\u62e9\u54ea\u4e00\u7ef4\u5ea6\u8fdb\u884c\u5212\u5206<\/strong><\/span><\/p>\n<p>\u5728\u300acomputational geometry\u300b(Mark de Berg\u7b49\u8457)\u4e00\u4e66\u4e2d\uff0c\u5c06kd\u6811\u7684\u7ef4\u5ea6\u5212\u5206\u4e0e\u6811\u7684\u6df1\u5ea6\u5173\u8054\uff0c\u6bd4\u5982 \u7ef4\u5ea6 = \u6df1\u5ea6%\u603b\u7ef4\u5ea6,\u8fd9\u6837\uff0ckd\u6811\u7684\u7ef4\u5ea6\u5212\u5206\u5c31\u4fdd\u6301x,y,z,&#8230;,x,y,z&#8230;\u7684\u987a\u5e8f\u3002\u5f88\u591a\u7f51\u4e0a\u7684\u5176\u4ed6\u5b9e\u73b0\u4e5f\u662f\u5982\u6b64\u3002\u5b9e\u9645\u4e0a\uff0c<strong>\u5e76\u4e0d\u4e00\u5b9a\u8981\u4fdd\u6301\u8fd9\u6837\u7684\u987a\u5e8f<\/strong>\u3002\u800c\u4e14\uff0c\u4e0d\u540c\u7684\u5212\u5206\u987a\u5e8f\uff0c\u5f80\u5f80\u80fd\u7ed9kd\u6811\u7684\u6548\u7387\u5e26\u6765\u5f71\u54cd\u3002<\/p>\n<p>\u56e0\u4e3a\u70b9\u6570\u4e0e\u7ef4\u6570\u662f\u56fa\u5b9a\u7684\uff0ckd\u6811\u7684\u6df1\u5ea6(depth)\u4e5f\u662f\u56fa\u5b9a\u7684\uff0c\u5982\u679c\u91c7\u7528\u5747\u5300\u5212\u5206\u7684\u65b9\u5f0f\uff0c\u5728\u5206\u6563\u7a0b\u5ea6\u6bd4\u8f83\u5c0f\u7684\u7ef4\u5ea6\u4e0a\u8fc7\u5ea6\u5212\u5206\uff0c\u52bf\u5fc5\u4f1a\u9020\u6210\u5206\u6563\u7ef4\u5ea6\u8f83\u5927\u7684\u7ef4\u5ea6\u5212\u5206\u4e0d\u5145\u5206\uff0c\u66f4\u5bb9\u6613\u5bfc\u81f4\u201c\u957f\u6761\u5f62\u201d\u533a\u57df\u51fa\u73b0\u3002\u5728\u5404\u7ef4\u5ea6\u67e5\u8be2\u6982\u7387\u76f8\u540c\u7684\u60c5\u51b5\u4e0b\uff0c\u957f\u6761\u5f62\u80af\u5b9a\u66f4\u5bb9\u6613\u88ab\u547d\u4e2d\uff0c\u5bfc\u81f4\u88ab\u67e5\u8be2\u6b21\u6570\u8fc7\u591a\u800c\u6548\u7387\u4e0d\u4f73\u3002<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-931\" src=\"http:\/\/www.whudj.cn\/wp-content\/uploads\/2018\/04\/split_yxy.png\" alt=\"\" width=\"500\" height=\"281\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-932\" src=\"http:\/\/www.whudj.cn\/wp-content\/uploads\/2018\/04\/split_xxy.png\" alt=\"\" width=\"500\" height=\"287\" \/><\/p>\n<p>\u4ee5\u4e0a\u4e24\u56fe\u4e3a\u4f8b\uff0c\u540c\u6837\u7684\u8f93\u5165\u6570\u636e(\u4e8c\u7ef4)\uff0c\u91c7\u7528y-x-y\u7684\u5212\u5206\u65b9\u5f0f\u4e0ex-x-y\u7684\u65b9\u5f0f\u5f97\u5230\u7684\u6548\u679c\uff0c\u53ef\u4ee5\u770b\u5230\uff0c\u540e\u4e00\u79cd\u5212\u5206\u6bd4\u8f83\u5145\u5206\uff0c\u4ece\u800c\u67e5\u8be2\u6d89\u53ca\u65e0\u5173\u5206\u652f\u7684\u60c5\u51b5\u6bd4\u8f83\u5c0f\uff0c\u67e5\u8be2\u6548\u7387\u53ef\u80fd\u4f1a\u6bd4\u8f83\u9ad8(\u5177\u4f53\u9ad8\u4e0d\u9ad8\u8981\u770b\u67e5\u8be2\u8303\u56f4\u662f\u4e0d\u662f\u8d8b\u5411\u4e8e\u6b63\u65b9\u5f62)\u3002<\/p>\n<p><span style=\"text-decoration: underline;\"><strong>2.2 \u5982\u4f55\u51cf\u5c0fpartition \u4e2dswap\u5f15\u53d1\u7684\u6027\u80fd\u95ee\u9898 \u4ee5\u53ca FLANN\u7684\u89e3\u51b3\u65b9\u6848<\/strong><\/span><\/p>\n<p>\u5728kd\u6811\u7684\u6784\u5efa\u4e2d\uff0c\u6d89\u53ca\u5230\u4e86\u9891\u7e41\u7684\u4f9d\u636e\u8d85\u5e73\u9762\u8fdb\u884c\u5206\u5272\u7684\u95ee\u9898\u3002\u56e0\u4e3akd\u6811\u662f\u9762\u5411\u9ad8\u7ef4\u6570\u636e\u7684\uff0c\u9ad8\u7ef4\u6570\u636e\u7684\u70b9\u7684\u5c3a\u5bf8\u901a\u5e38\u6bd4\u8f83\u5927\uff0c\u5982\u679c\u76f4\u63a5\u9488\u5bf9\u6570\u636e\u672c\u8eab\u8fdb\u884cswap\uff0c\u90a3\u4e48\u4f1a\u591a\u6b21\u8c03\u7528\u70b9\u6570\u636e\u672c\u8eab\u7684\u62f7\u8d1d\u8d4b\u503c\u51fd\u6570\uff0c\u5f00\u9500\u6bd4\u8f83\u5927\u3002\u6709\u6ca1\u6709\u6bd4\u8f83\u5408\u9002\u7684\u7684\u65b9\u6cd5\uff1f<\/p>\n<p>\u5176\u4e00\u5c31\u662f\u91c7\u7528\u6307\u9488\u4f5c\u4e3a\u6570\u7ec4\u5143\u7d20\uff0c\u800c\u4e0d\u662f\u5bf9\u8c61\u672c\u8eab\uff0c\u8fd9\u6837 \u6307\u9488\u7684swap\u5c31\u8981\u5ec9\u4ef7\u5f88\u591a\u4e86\u3002\u4f46\u662f\u8fd9\u6837\u7684\u8bdd\uff0c\u76f8\u5f53\u4e8e\u5bf9\u8f93\u5165\u6570\u636e\u5c31\u6709\u8981\u6c42\u4e86\uff0c\u6050\u6015\u9002\u7528\u6027\u4e0d\u5f3a\u3002<\/p>\n<p>\u8fd8\u6709\u4e00\u79cd\u65b9\u6cd5\u5c31\u662fFLANN\u4f7f\u7528\u7684\u65b9\u5f0f\uff0c\u6bd4\u8f83\u63d0\u5021\u4f7f\u7528\u3002\u5177\u4f53\u65b9\u6cd5\u662f\uff0c\u7531\u4f7f\u7528kd\u6811\u8005\u6301\u6709\u6570\u636e\uff0c\u4f20\u7ed9kd\u6811\u7684\u662f\u4e0e\u8f93\u5165\u6570\u636epoints\u7b49\u957f\u7684index\u6570\u7ec4indices\uff0cindices[i] \u6807\u8bc6\u6570\u636e\u7684\u7d22\u5f15\uff0c\u56e0\u6b64\u8c03\u6574\u540e\u7684 \\( p_i = points[indices[i]] \\) \u5f53\u6570\u7ec4partition\u7684\u65f6\u5019\uff0c\u8c03\u6574\u7684\u53ea\u662f indices\u7684\u6570\u503c\uff0c\u5f00\u9500\u5c31\u8981\u5c0f\u5f88\u591a\u4e86\uff0c\u800c\u4e14\u8c03\u7528\u8005\u6301\u6709\u7684\u6570\u636e\u7684\u987a\u5e8f\u5e76\u6ca1\u6709\u53d1\u751f\u6539\u53d8\u3002<\/p>\n<p>\u8fd9\u6837\uff0c\u53ef\u4ee5\u7ed9\u51fa\u4e00\u79cd<span class=\"lang:c++ decode:true crayon-inline \">kdtree::Node<\/span>\u00a0\u7684\u8bbe\u8ba1\uff1a<\/p>\n<pre class=\"lang:c++ decode:true \">namespace kdtree\r\n{\r\n\tclass Node\r\n\t{\r\n\tpublic:\r\n\t\tNode* left;\t\t\t\/\/left child\r\n\t\tNode* right;\t\t\/\/right child\r\n\t\tint begin;\t\t\t\/\/start index [close\r\n\t\tint end;\t\t\t\t\/\/end index  (open\r\n\t\tint dimension;\t\/\/cut dimension\r\n\t\tdouble pivot;\t\t\/\/cut value\r\n\t};\r\n}<\/pre>\n<p><strong><span style=\"text-decoration: underline;\">2.3 \u8d85\u5e73\u9762\u786e\u5b9a\u7b97\u6cd5<\/span><\/strong><\/p>\n<p>\u524d\u6587\u6211\u4eec\u63d0\u5230\uff0c\u6700\u7406\u60f3\u7684\u8d85\u5e73\u9762\u662f\u4e2d\u4f4d\u6570\u3002\u786e\u5b9a\u4e2d\u4f4d\u6570\u7684\u7b97\u6cd5\u6709\u82e5\u5e72\u79cd\u3002\u51e0\u5e74\u524d\u6211\u6700\u521d\u5b9e\u73b0kd\u6811\u7684\u65f6\u5019\uff0c\u66fe\u7ecf\u91c7\u7528<span class=\"lang:c++ decode:true crayon-inline \"> std::sort<\/span> \u5b9e\u73b0\uff0c\u5176\u5b9e\u662f\u4e00\u79cd\u975e\u5e38\u6d6a\u8d39\u7684\u65b9\u5f0f\uff0c\u56e0\u4e3a\u4e2d\u4f4d\u6570\u5e76\u4e0d\u8981\u6c42\u6570\u636e\u5b8c\u5168\u6392\u5e8f\uff0c\u800c\u662f\u8981\u6c42\u5728\u4e2d\u4f4d\u6570\u5de6\u4fa7\u7684\u6570\u636e\u4e0d\u5927\u4e8e\u4e2d\u4f4d\u6570\uff0c\u4e2d\u4f4d\u6570\u53f3\u4fa7\u7684\u6570\u636e\u4e0d\u5c0f\u4e8e\u4e2d\u4f4d\u6570\u800c\u5df2\u3002\u663e\u7136\uff0c\u590d\u6742\u5ea6\u4e3a\\(O(nlogn)\\)\u7684\u6392\u5e8f\u7b97\u6cd5\u7528\u529b\u8fc7\u5ea6\u4e86\u3002\u5b9e\u73b0\u4e2d\u4f4d\u6570\u5206\u5272\u7684\u6700\u4f73\u7b97\u6cd5\u662f<span class=\"lang:c++ decode:true crayon-inline\">std::nth_element<\/span>, \u5176\u7b97\u6cd5\u590d\u6742\u5ea6\u4e3a\\(O(n)\\) ,\u7cfb\u6570\u4e3a2\u5de6\u53f3\u3002\u662f\u975e\u5e38\u7406\u60f3\u7684\u3002<\/p>\n<p>FLANN\u7684\u8bbe\u8ba1\u662f\uff1a\u6839\u636e\u6570\u636e\u7684\u8303\u56f4\u786e\u5b9a\u9996\u5c3e(\u6700\u5c0f\u6700\u5927\u503c)\u5e73\u5747\u503c\uff0c\u6839\u636e\u9996\u5c3e\u5747\u503c\u5c06\u6570\u636e\u5206\u5272\u6210\u4e09\u90e8\u5206\uff0c\u201c\u4e2d\u4f4d\u6570\u201d\u7684\u53d6\u503c\u7531\u4ee5\u4e0b\u51e0\u79cd\u60c5\u51b5\u5224\u65ad\u4ea7\u751f\uff1a<\/p>\n<div id=\"attachment_939\" style=\"width: 510px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-939\" class=\"wp-image-939 size-full\" src=\"http:\/\/www.whudj.cn\/wp-content\/uploads\/2018\/04\/flann_median.png\" alt=\"\" width=\"500\" height=\"117\" \/><p id=\"caption-attachment-939\" class=\"wp-caption-text\">flann \u7684 median \u7b97\u6cd5<\/p><\/div>\n<ol>\n<li>\u5f53 limit1 &gt; count\/2\u65f6\uff0cmedian = limit1;<\/li>\n<li>\u5426\u5219\u5f53 limit2 &lt; count2\u65f6 median = limit2;<\/li>\n<li>\u5426\u5219 median = count\/2;<\/li>\n<\/ol>\n<p>\u8fd9\u79cd\u65b9\u5f0f \u7684\u590d\u6742\u5ea6\u4e5f\u4e3a\\(O(n))\\\uff0c\u4f46\u662f\u7cfb\u6570\u8f83\u4f4e\uff0c\u6bd4nth_element\u7684\u901f\u5ea6\u5feb\u3002\u4e0d\u8fc7\uff0c\u8fd9\u79cd\u65b9\u6cd5\u4e5f\u5b58\u5728\u95ee\u9898\u3002\u5f53\u8f93\u5165\u6570\u636e\u5206\u5e03\u4e0d\u5747\u5300\u65f6\uff0c\u91c7\u7528\u9996\u5c3e\u5e73\u5747\u503c\u8fdb\u884c\u5212\u5206\u7684\u65b9\u5f0f\u5f88\u5bb9\u6613\u5bfc\u81f4\u6811\u4e0d\u5747\u8861\u4ece\u800c\u4f7f\u5f97\u6811\u7684\u6df1\u5ea6\u589e\u52a0\uff0c\u67e5\u8be2\u6548\u7387\u964d\u4f4e\u3002<\/p>\n<p><span style=\"text-decoration: underline;\"><strong>3. \u8303\u56f4\u67e5\u8be2(Range Search)\u3001\u534a\u5f84\u67e5\u8be2(Redius Search)<\/strong><\/span><\/p>\n<p>\u8303\u56f4\u67e5\u8be2\u4e0e\u534a\u5f84\u67e5\u8be2\u5dee\u5f02\u4e0d\u5927\uff0c\u53ef\u4ee5\u653e\u5728\u4e00\u8d77\u8bb2\u3002<\/p>\n<p>\u56e0\u4e3aKD\u6811\u672c\u8d28\u4e0a\u662f\u4e00\u79cd\u6811\uff0c\u56e0\u6b64\u6211\u4eec\u7684\u7a7a\u95f4\u67e5\u8be2\uff08\u5305\u62ec\u6700\u8fd1\u90bb\u67e5\u8be2\uff0c\u8303\u56f4\u67e5\u8be2\u7b49\uff09\u90fd\u662f\u6811\u904d\u5386\u7b97\u6cd5\u7684\u4e00\u79cd\u3002\u5982\u679c\u6811\u4e0d\u662f\u4e00\u79cdBST\uff0c\u90a3\u4e48\u67e5\u8be2\u4e00\u6b21\u53ef\u80fd\u8981\u904d\u5386\u6574\u4e2a\u6811\uff0c\u5e76\u4e0d\u80fd\u8d77\u5230\u52a0\u901f\u4f5c\u7528\u3002KD\u6811\u4e0e\u5176\u4ed6\u6811\u7ed3\u6784\u7684\u7a7a\u95f4\u7d22\u5f15\u7684\u4f5c\u7528\u5c31\u662f\u5728\u6839\u8282\u70b9\u53ef\u4ee5\u5224\u65ad\u5b50\u6811\u7684\u60c5\u51b5\uff0c\u5728\u6839\u8282\u70b9\u53ef\u4ee5\u5224\u65ad\u4e0b\u4e00\u6b65\u7684\u641c\u7d22\u65b9\u5411\uff0c\u5b8c\u5168\u4e0d\u5fc5\u8981\u641c\u7d22\u7684\u8282\u70b9\u4e0d\u4f1a\u904d\u5386\uff0c\u8fd9\u6837\uff0c\u7d22\u5f15\u8d77\u5230\u4e86\u52a0\u901f\u67e5\u8be2\u7684\u4f5c\u7528\u3002<\/p>\n<p>\u5177\u4f53\u5230KD\u6811\uff0c\u6211\u4eec\u9700\u8981\u89e3\u51b3\u7684\u73b0\u5b9e\u95ee\u9898\u5c31\u662f\u8282\u70b9\u7a7a\u95f4\u8303\u56f4\u7684\u786e\u5b9a\u3002\u57282.2\u8282Node\u70b9\u7684\u8bbe\u8ba1\u4e0a\uff0c\u5e76\u6ca1\u6709\u8bb0\u5f55Node\u7684\u7a7a\u95f4\u8303\u56f4\u3002\u8fd9\u662f\u56e0\u4e3a\u6bcf\u4e2aNode\u7684\u8303\u56f4\u53ef\u4ee5\u5728\u6811\u7684\u904d\u5386\u8fc7\u7a0b\u4e2d\u540c\u6b65\u5b8c\u6210\uff0c\u5e76\u4e0d\u9700\u8981\u7279\u522b\u8bb0\u5f55\u3002<\/p>\n<p>\\( region(lc(v)) = region(v)\\cap l(v)^{left} \\)<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-946\" src=\"http:\/\/www.whudj.cn\/wp-content\/uploads\/2018\/04\/leftchild.png\" alt=\"\" width=\"200\" height=\"226\" \/><\/p>\n<p>\u4e0a\u56fe\u662f \u300acomputational geometry\u300b\u4e2d\u5de6\u5b50\u6811\u8303\u56f4\u786e\u5b9a\u7684\u65b9\u6cd5\u3002\u53f3\u5b50\u6811\u4e0e\u4e4b\u7c7b\u4f3c\u3002<\/p>\n<p>\u56e0\u6b64\uff0c\u4e00\u4e2aRangeSearch\u5c31\u662f\u4e00\u4e2a\u6811\u7684\u540e\u5e8f\u904d\u5386\u7b97\u6cd5\u7684\u6539\u7248\u3002\u4f2a\u4ee3\u7801\u5982\u4e0b\u6240\u793a\uff08\u5b9e\u73b0\u4ee3\u7801\u5728\u6587\u672b\uff09<\/p>\n<pre class=\"lang:c++ decode:true \">RangeSearch(BBox searchBox,Node* pNode,BBox current_extent)\r\n{\r\n\tif(pNode-&gt;isLeaf())\r\n\t{\r\n\t\t\/\/report all points that within searchBox\r\n\t}else\r\n\t{\r\n\t\tBBox leftregion;\/\/leftregion \u7684\u8303\u56f4\u662f current_extent trim \u6389 pNode-&gt;pivot\r\n\t\tif(searchBox.contains(leftregion))\r\n\t\t{\r\n\t\t\t\/\/report all points in pNode-&gt;left;\r\n\t\t}\r\n\t\telse if(searchBox.intersects(leftregion))\r\n\t\t{\r\n\t\t\tRangeSearch(searchBox,pNode-&gt;left,leftregion);\/\/recursive call\r\n\t\t}\r\n\t\t\r\n\t\tBBox rightregion; \/\/rightregion \u7684\u8303\u56f4\u662f current_extent trim pNode-&gt;pivot\r\n\t\tif(searchBox.contains(rightregion))\r\n\t\t{\r\n\t\t\t\/\/report all points in pNode-&gt;right;\r\n\t\t}else if(searchBox.intersects(rightregion))\r\n\t\t{\r\n\t\t\tRangeSearch(searchBox,pNode-&gt;right,rightregion);\/\/recursive call\r\n\t\t}\t\r\n\t}\r\n}<\/pre>\n<p>\u534a\u5f84\u67e5\u8be2\uff08radius search\uff09\u53ef\u4ee5\u5b8c\u5168\u7c7b\u6bd4\u4e0a\u9762\u7684\u7b97\u6cd5\u8fdb\u884c\u5b9e\u73b0\uff0c\u53ea\u4e0d\u8fc7\u67e5\u8be2\u533a\u57df\u9700\u8981\u4ece range search\u7684\u00a0 bounding box \u6362\u6210 \u5706\u6216\u7403\u4f53(\u6839\u636e\u7ef4\u5ea6)\uff0c\u540c\u65f6\u9700\u8981\u5b9e\u73b0contains,intersects\u7b49\u65b9\u6cd5\u3002<\/p>\n<p><strong><span style=\"text-decoration: underline;\">4.\u6700\u8fd1\u90bb\u67e5\u8be2(Nearest Neighbour)<\/span><\/strong><\/p>\n<p>\u6309\u7167\u95ee\u9898\u7684\u590d\u6742\u7a0b\u5ea6\uff0c\u53ef\u4ee5\u5206\u89e3\u4e3a\u4e24\u4e2a\u65b9\u9762 1-NN\u4e0e k-NN\uff0c\u5206\u522b\u8868\u793a\u8ddd\u79bb\u641c\u7d22\u70b9\u6700\u8fd1\u7684\u4e00\u4e2a\u70b9\u4ee5\u53ca\u6700\u8fdc\u7684k\u4e2a\u70b9\u3002\u4e24\u8005\u7684\u7b97\u6cd5\u7c7b\u4f3c\uff0ck-NN\u53ef\u4ee5\u57281-NN\u57fa\u7840\u4e0a\u7565\u4f5c\u4fee\u6539\u5f97\u5230\u3002<\/p>\n<p><span style=\"text-decoration: underline;\"><strong>4.1 1-NN<\/strong><\/span><\/p>\n<p>\u6700\u8fd1\u90bb\u67e5\u8be2\u4e0e\u8303\u56f4\u67e5\u8be2\u4e0d\u540c\u3002\u53ef\u4ee5\u8bf4rangesearch(radius search)\u7684\u60c5\u51b5\u662f\u201c\u56fa\u5b9a\u201d\u7684\uff0c\u901a\u8fc7\u641c\u7d22\u8303\u56f4\u4e0e\u5f53\u524d\u8282\u70b9\u7684\u8303\u56f4\u8fdb\u884c\u6bd4\u5bf9\uff0c\u5c31\u53ef\u4ee5\u5f97\u5230\u56fa\u5b9a\u7684\u641c\u7d22\u8def\u5f84\u3002\u800c\u6700\u8fd1\u90bb\u7684\u60c5\u51b5\u4e0d\u540c\u3002\u6700\u8fd1\u90bb\u5728\u641c\u7d22\u65f6\u7ef4\u62a4\u4e86\u4e0e\u641c\u7d22\u70b9\u6700\u8fd1\u7684\u53f6\u5b50\u7684\u8ddd\u79bb\uff0c\u901a\u8fc7\u5224\u65ad\u641c\u7d22\u70b9\u5230\u5176\u4ed6\u8282\u70b9\u7684\u8ddd\u79bb\u7684\u4e0b\u754c\u201c\u526a\u6389\u201d\u6ca1\u6709\u5fc5\u8981\u8bbf\u95ee\u7684\u8282\u70b9\u3002<\/p>\n<p>\u7ef4\u62a4\u4e00\u4e2a\u641c\u7d22\u70b9\u5230\u76ee\u524d\u627e\u5230\u6700\u8fd1\u53f6\u5b50\u8282\u70b9\u7684\u6700\u5c0f\u503c\\(shortestDistance\\)\uff0c\u521d\u59cb\u503c\u4e3aDOUBLE_MAX;<\/p>\n<p>\u8ba1\u7b97\u641c\u7b97\u70b9\u5230 \u5f53\u524d\u8282\u70b9\u7684\u5916\u754c\u77e9\u5f62\u7684\u6700\u5c0f\u8ddd\u79bb\\(min\\_shorest\\_dis\\),\u5982\u679c\u8fd9\u4e2a\u8ddd\u79bb\u8d85\u8fc7\u4e86\\(shortestDistance\\)\uff0c\u90a3\u4e48\u8fd9\u4e2a\u8282\u70b9\u6ca1\u6709\u5fc5\u8981\u641c\u7d22\uff0c\u56e0\u4e3a\\(min\\_shorest\\_dis\\)\u4ee3\u8868\u7684\u5c31\u662f\u5f53\u524d\u8282\u70b9\u4e2d\u6240\u6709\u70b9\u5230\u76ee\u6807\u8282\u70b9\u7684\u6700\u5c0f\u503c\u7684\u4e0b\u754c\u3002<\/p>\n<ol>\n<li>\u5982\u679c\u5f53\u524d\u8282\u70b9\u4e3a\u53f6\u5b50\u8282\u70b9\uff0c\u5219\u66f4\u65b0\u6700\u5c0f\u503c\u548c\u6700\u5c0f\u8ddd\u79bb\u3002<\/li>\n<li>\u5982\u679c\u5f53\u524d\u8282\u70b9\u975e\u53f6\u5b50\u8282\u70b9\uff0c\u5219\u4ece\u4e24\u4e2a\u5b50\u8282\u70b9\u4e2d\u4f18\u9009\u4e00\u4e2a\uff08\u82f1\u6587\u79f0\u4e3apriorty search\uff09\u4e00\u4e2a\u8282\u70b9\u4f18\u5148\u8fdb\u884c\u641c\u7d22\uff0c\u7136\u540e\u518d\u641c\u7d22\u53e6\u5916\u4e00\u4e2a\u8282\u70b9\u3002\u8fd9\u4e00\u6b65\u975e\u5e38\u4f53\u73b0\u51faNN \u201c\u52a8\u6001\u201d\u7684\u7279\u6027\uff0c\u5982\u679c\u524d\u9762\u66f4\u65b0\u4e86\u6700\u77ed\u8ddd\u79bb\uff0c\u90a3\u4e48\u540e\u9762\u5c31\u53ef\u4ee5\u201c\u526a\u6389\u201d\u4e00\u4e9b\u4e0d\u5fc5\u8981\u7684\u8282\u70b9\u4e86\u3002\u4e3a\u4ec0\u4e48\u8fd8\u8981\u641c\u7d22\u540e\u4e00\u4e2a\u8282\u70b9\u5462\uff1f\u56e0\u4e3a\u201c\u4f18\u9009\u201d\u7684\u8282\u70b9\u4e0d\u4e00\u5b9a\u771f\u6b63\u5305\u542b\u6700\u8fd1\u70b9\u3002\u5982\u4e0b\u56fe\u6240\u793a\uff1a\u4f18\u9009\u8282\u70b9\u5728left,\u4f46\u662f\u6700\u8fd1\u70b9\u5728right\u3002<img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-956 aligncenter\" src=\"http:\/\/www.whudj.cn\/wp-content\/uploads\/2018\/04\/priorty_search.png\" alt=\"\" width=\"300\" height=\"168\" \/><\/li>\n<li>\u6309\u7167\u641c\u7d22\u987a\u5e8f\uff0c\u540e\u4e00\u6b21\u5982\u679c\u627e\u5230\u66f4\u8fd1\u7684\uff0c\u5219\u4f7f\u7528\u540e\u4e00\u6b21\u641c\u7d22\u7684\u7ed3\u679c\uff0c\u6ca1\u6709\u5219\u53d6\u524d\u4e00\u6b21\u7684\u3002<\/li>\n<\/ol>\n<p>\u6700\u8fd1\u90bb\u641c\u7d22\u7684\u4f2a\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n<pre class=\"lang:c++ decode:true\">int NearestNeighbour(Point searchPoint,Node* pNode,const BBox&amp; current_extent, double&amp; shortestDistance)\r\n{\r\n\t\/**\r\n\t\t\u641c\u7d22\u70b9\u5230subtree\u5916\u63a5\u77e9\u5f62\u7684\u8ddd\u79bb\u8868\u793a\u4e86\u70b9\u5230sutree \u4e2d\u6240\u6709\u70b9\u6700\u5c0f\u8ddd\u79bb\u7684\u4e0b\u754c\uff0c\r\n\t\t\u5c31\u662f\u8bf4\u6700\u8fd1\u8ddd\u79bb\u4e00\u5b9a\u4e0d\u5c0f\u4e8e\u8fd9\u4e2a\u6570\uff0c\u5982\u679c\u8fd9\u4e2a\u6570\u6bd4\u5f53\u524d\u7684\u6700\u5c0f\u8ddd\u79bb shortestDistance \u8fd8\u5927\r\n\t\t\u6574\u4e2a\u5b50\u6811\u5c31\u53ef\u4ee5\u4e0d\u7528\u8bbf\u95ee\u4e86\uff0c\u8d77\u5230\u4e86\u52a0\u901f\u4f5c\u7528\r\n\t*\/\r\n\tdouble min_shortest_dis = shortestDistance(searchPoint,current_extent);\r\n\tif(min_shortest_dis &gt;= shortestDistance)\r\n\t\treturn -1;\r\n\t\r\n\tif(pNode-&gt;isLeaf())\r\n\t{\r\n\t\t\/\/find points with shortest distance to searchPoint\r\n\t\t\/\/TO-DO Update shortestDistance\r\n\t\treturn nearestneighbour_index;\r\n\t}else\r\n\t{\r\n\t\tBBox leftRegion; \/\/leftRegion \u7531 current_extent trim\u5f97\u5230\r\n\t\tdouble dis_to_left = ShorestDistance(searchPoint,leftRegion);\r\n\t\tBBox rightRegion;\/\/rightRegion \u7531 current_extent trim \u5f97\u5230\r\n\t\tdouble dis_to_right = ShorestDistance(searchPoint,rightRegion);\r\n\t\t\/**\r\n\t\t\u786e\u5b9aleft,right \u4f18\u5148\u67e5\u8be2\u54ea\u4e00\u5757\uff0c\u5f53\u7136\u662f\u62e5\u6709\u66f4\u8fd1\u8ddd\u79bb\u7684\u5177\u6709 priority\r\n\t\t\u4f46\u662f\uff0c\u8fd9\u4e5f\u4ec5\u4e3a\u4f18\u5148\u6743\u800c\u5df2\uff0c\u4e0d\u80fd\u9760\u5176\u62e5\u6709\u6700\u53ef\u80fd\u6700\u8fd1\u90bb\u800c\u6392\u51fa\u53e6\u4e00\u5b50\u6811\r\n\t\t*\/\r\n\t\tif(dis_to_left&lt;dis_to_right)\r\n\t\t{\r\n\t\t     int left = NearestNeighbour(searchPoint,pNode-&gt;left,leftRegion,shortestDistance);\r\n\t\t     int right = NearestNeighbour(searchPoint,pNode-&gt;rihgt,rightRegion,shortestDistance);\r\n\t\t      return right == -1 ? left : right;\r\n\t\t}else\r\n\t\t{\r\n\t\t\tint right = NearestNeighbour(searchPoint,pNode-&gt;rihgt,rightRegion,shortestDistance);\r\n\t\t\tint left = NearestNeighbour(searchPoint,pNode-&gt;left,leftRegion,shortestDistance);\r\n\t\t\treturn left == -1? right:left;\r\n\t\t}\r\n\t}\r\n\treturn -1;\/\/dummy\r\n}<\/pre>\n<p>\u8fd9\u91cc\u9762\u4f1a\u6709\u4e00\u4e2a\u5b50\u95ee\u9898\u9700\u8981\u89e3\u51b3\uff0c\u70b9\u5230\u5916\u63a5\u77e9\u5f62\uff08\u6216\u8005\u66f4\u9ad8\u7ef4\u5ea6\u7684\u8303\u56f4\uff09\u7684\u6700\u8fd1\u8ddd\u79bb\u5982\u4f55\u5224\u65ad\u3002\u6211\u4eec\u89c4\u5b9a\uff0c\u5982\u679c\u70b9\u5728\u77e9\u5f62\u5185\u90e8\uff08\u6216\u77e9\u5f62\u4e0a\uff09\u5219\u8ba4\u4e3a\u70b9\u5230\u77e9\u5f62\u7684\u8ddd\u79bb\u4e3a0.\u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0cstackoverflow \u4e0a\u6709\u5bf9\u5e94\u7684\u89e3\u51b3\u65b9\u6848\uff1a<a href=\"https:\/\/stackoverflow.com\/questions\/5254838\/calculating-distance-between-a-point-and-a-rectangular-box-nearest-point\">stackoverflow\u4e0a\u5bf9\u70b9\u5230 \u77e9\u5f62(\u5916\u4fa7)\u6700\u8fd1\u8ddd\u79bb\u7684\u5b9e\u73b0<\/a><\/p>\n<p><strong><span style=\"text-decoration: underline;\">4.2 k-NN<\/span><\/strong><\/p>\n<p>k-NN\u4e0e1-NN\u7684\u6574\u4f53\u601d\u8def\u5e76\u6ca1\u6709\u5927\u7684\u533a\u522b\uff0c\u589e\u52a0\u7684\u90e8\u5206\u662f\uff0ck-NN\u9700\u8981\u7ef4\u62a4\u4e00\u4e2a\u5f53\u524d\u6700\u8fd1\u70b9\u5217\u8868nearest_neighbors\uff0c\u5e76\u4e14\u4f7fnearest_neighbors\u4e2d\u7684\u8ddd\u79bb\u6700\u8fdc\u70b9\uff08FLANN\u4e2d\u79f0\u4e3aworest distance\uff09\u66f4\u65b0 \\(shortestDistance\\)\u3002\u5f53\u6709\u66f4\u8fd1\u70b9\u65f6\uff0c\u4f7f\u5176\u52a0\u5165nearest_neighbors\uff0c\u5e76\u4e14\u4f7f\u7528nearest_neighbors \u4e2d\u7684\u6700\u8fdc\u70b9\u66f4\u65b0\\(shortestDistance\\)\u3002\u4e24\u70b9\u9700\u8981\u6ce8\u610f\uff1a<\/p>\n<ol>\n<li>\u5f53nearest_neighbors\u7684size\u4e0d\u8db3k\u65f6\uff0c\u4e0d\u80fd\u4f7f\u7528\u5176\u4e2d\u6700\u8fdc\u70b9\u66f4\u65b0\\(shortestDistance\\)\u3002<\/li>\n<li>\u56e0\u4e3a\u9891\u7e41\u53d6\u8ddd\u79bb\u6700\u5927\u503c\uff0c\u5efa\u8bae\u91c7\u7528<span class=\"lang:c++ decode:true crayon-inline \">std::priority_queue<\/span>\u00a0\u5b9e\u73b0\uff0c\u5176 <span class=\"lang:c++ decode:true crayon-inline \">push()<\/span>\u00a0,<span class=\"lang:c++ decode:true crayon-inline \">pop()<\/span>\u00a0\u65b9\u6cd5\u590d\u6742\u5ea6\u4e3a\\(O(log(n))\\),<span class=\"lang:c++ decode:true crayon-inline \">top()<\/span>\u00a0\u65b9\u6cd5\u590d\u6742\u7684\u4e3a\\(O(1)\\)\u3002<\/li>\n<\/ol>\n<p><strong><span style=\"text-decoration: underline;\">5.\u8fd1\u4f3c\u6700\u8fd1\u90bb\u67e5\u8be2\uff08Approximate Nearest Neighbor\uff09<\/span><\/strong><\/p>\n<p>FLANN\u7684\u5168\u79f0\u662f \u201cFast Library for Approximate Nearest Neighbors\u201d \uff0c\u5176\u4e2d\u7684\u201cApproximate\u201d\u6307\u7684\u662f\u4ec0\u4e48\u5462\uff1f\u5176\u5b9e\u6211\u4eec\u77e5\u9053\uff0cNN\u8fc7\u6ee4Node\u7684\u6761\u4ef6\u662f\u5f53\u524d\u641c\u7d22\u534a\u5f84(\u6700\u77ed\u8ddd\u79bb)\\( r \\) \u4f4e\u4e8e \u70b9\u5230 Node\u5916\u63a5\u77e9\u5f62\u7684\u8ddd\u79bb\uff0cANN\u901a\u8fc7\u5c06 \\( r \\)\u9664\u4ee5 \u5927\u4e8e1\u7684\u7cfb\u6570\\(\\alpha\\)\uff0c\u4f7f\u5f97Node \u66f4\u5bb9\u6613\u88ab\u8fc7\u6ee4\uff0c\u4ece\u800c\u52a0\u5feb\u4e86\u67e5\u8be2\u901f\u5ea6\uff0c\u4f46\u662f\u5f97\u5230\u7684\u7ed3\u679c\u4e5f\u662f\u8fd1\u4f3c\u7684\u6700\u8fd1\u70b9\u3002\u6839\u636e\u53c2\u8003\u6587\u732e\uff0cANN\u80fd\u4f7f NN\u7684\u67e5\u8be2\u901f\u5ea6\u63d0\u9ad810-100\u500d\u3002<\/p>\n<p>\u53c2\u8003\u6587\u732e\u4e09\u5bf9ANN\u7684\u89e3\u91ca\u6700\u4e3a\u76f4\u89c2\uff1a<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-959\" src=\"http:\/\/www.whudj.cn\/wp-content\/uploads\/2018\/04\/ann.png\" alt=\"\" width=\"500\" height=\"377\" \/><\/p>\n<p>\u5728FLANN\u4e2d\uff0c\u53ef\u4ee5\u770b\u5230 kdtree \u62e5\u6709\u63a5\u53e3\u00a0<span class=\"lang:c++ decode:true crayon-inline\">setEpsilon (float eps)<\/span>\u00a0\u8bbe\u7f6eepsilon \u3002\\(\\epsilon\\)\u5bf9\u5e94\u4e0a\u5f0f\u4e2d\u7684 \\(\\alpha = \\epsilon+1\\)\u3002\u4e0d\u7ecf\u8bbe\u7f6e\u7684\u8bdd\uff0cepsilon\u9ed8\u8ba4\u503c\u4e3a0\u3002<\/p>\n<p><span style=\"text-decoration: underline;\"><strong>6.\u53c2\u8003\u6587\u732e\uff1a<\/strong><\/span><\/p>\n<p><a href=\"https:\/\/www.cs.cmu.edu\/~ckingsf\/bioinfo-lectures\/kdrangenn.pdf\">https:\/\/www.cs.cmu.edu\/~ckingsf\/bioinfo-lectures\/kdrangenn.pdf<\/a><\/p>\n<p><a href=\"https:\/\/www.cs.cmu.edu\/~ckingsf\/bioinfo-lectures\/kdtrees.pdf\">https:\/\/www.cs.cmu.edu\/~ckingsf\/bioinfo-lectures\/kdtrees.pdf<\/a><\/p>\n<p><a href=\"https:\/\/courses.cs.washington.edu\/courses\/cse599c1\/13wi\/slides\/lsh-hashkernels-annotated.pdf\">https:\/\/courses.cs.washington.edu\/courses\/cse599c1\/13wi\/slides\/lsh-hashkernels-annotated.pdf<\/a><\/p>\n<p><strong><span style=\"text-decoration: underline;\">7.\u5b9e\u73b0\u4ee3\u7801\uff1a<\/span><\/strong><\/p>\n<p><a href=\"http:\/\/www.whudj.cn\/wp-content\/uploads\/2018\/04\/kdtree.h\" target=\"_blank\" rel=\"noopener\">kdtree.h<\/a><\/p>\n<p><a href=\"http:\/\/www.whudj.cn\/wp-content\/uploads\/2018\/04\/kdtree.cpp_.txt\" target=\"_blank\" rel=\"noopener\">kdtree.cpp<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>kd\u6811\u53ef\u80fd\u662f\u6211\u4eec\u6700\u719f\u6089\u7684\u7a7a\u95f4\u7d22\u5f15\u3002kd\u6811\u7684\u5168\u79f0\u662fk-dimensional tr &hellip; <a href=\"http:\/\/www.whudj.cn\/?p=920\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[15],"tags":[],"_links":{"self":[{"href":"http:\/\/www.whudj.cn\/index.php?rest_route=\/wp\/v2\/posts\/920"}],"collection":[{"href":"http:\/\/www.whudj.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.whudj.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.whudj.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.whudj.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=920"}],"version-history":[{"count":38,"href":"http:\/\/www.whudj.cn\/index.php?rest_route=\/wp\/v2\/posts\/920\/revisions"}],"predecessor-version":[{"id":968,"href":"http:\/\/www.whudj.cn\/index.php?rest_route=\/wp\/v2\/posts\/920\/revisions\/968"}],"wp:attachment":[{"href":"http:\/\/www.whudj.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=920"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.whudj.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=920"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.whudj.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=920"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}