{"id":5011,"date":"2021-01-31T12:54:31","date_gmt":"2021-01-31T04:54:31","guid":{"rendered":"https:\/\/damogame.cn\/wordpress\/?p=5011"},"modified":"2021-01-31T12:54:31","modified_gmt":"2021-01-31T04:54:31","slug":"%e5%9b%9b%e5%8f%89%e6%a0%91%e7%a9%ba%e9%97%b4%e7%b4%a2%e5%bc%95%e5%8e%9f%e7%90%86%e5%8f%8a%e5%85%b6%e5%ae%9e%e7%8e%b0","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/5011","title":{"rendered":"\u56db\u53c9\u6811\u7a7a\u95f4\u7d22\u5f15\u539f\u7406\u53ca\u5176\u5b9e\u73b0"},"content":{"rendered":"

\u539f\u6587\u5730\u5740<\/a><\/h1>\n

 <\/p>\n

\u5468\u65ed\u5149<\/a>\u00a02013-10-05 15:59:19\u00a0\u00a086366\u00a0\u00a0\u6536\u85cf\u00a044<\/p>\n

\u5206\u7c7b\u4e13\u680f\uff1a\u00a0GIS\u5e95\u5c42\u5f00\u53d1<\/a>\u00a0GIS\u5e95\u5c42\u5f00\u53d1<\/a><\/p>\n

\u7248\u6743<\/p>\n

\u4eca\u5929\u4f9d\u7136\u5728\u653e\u5047\u4e2d\uff0c\u5728\u6b64\u5c06\u4ee5\u524d\u5728\u5b66\u6821\u5199\u7684\u56db\u53c9\u6811\u7684\u4e1c\u897f\u62ff\u51fa\u6765\u548c\u5927\u5bb6\u5206\u4eab\u3002<\/p>\n

\u56db\u53c9\u6811\u7d22\u5f15\u7684\u57fa\u672c\u601d\u60f3\u662f\u5c06\u5730\u7406\u7a7a\u95f4\u9012\u5f52\u5212\u5206\u4e3a\u4e0d\u540c\u5c42\u6b21\u7684\u6811\u7ed3\u6784\u3002\u5b83\u5c06\u5df2\u77e5\u8303\u56f4\u7684\u7a7a\u95f4\u7b49\u5206\u6210\u56db\u4e2a\u76f8\u7b49\u7684\u5b50\u7a7a\u95f4\uff0c\u5982\u6b64\u9012\u5f52\u4e0b\u53bb\uff0c\u76f4\u81f3\u6811\u7684\u5c42\u6b21\u8fbe\u5230\u4e00\u5b9a\u6df1\u5ea6\u6216\u8005\u6ee1\u8db3\u67d0\u79cd\u8981\u6c42\u540e\u505c\u6b62\u5206\u5272\u3002\u56db\u53c9\u6811\u7684\u7ed3\u6784\u6bd4\u8f83\u7b80\u5355\uff0c\u5e76\u4e14\u5f53\u7a7a\u95f4\u6570\u636e\u5bf9\u8c61\u5206\u5e03\u6bd4\u8f83\u5747\u5300\u65f6\uff0c\u5177\u6709\u6bd4\u8f83\u9ad8\u7684\u7a7a\u95f4\u6570\u636e\u63d2\u5165\u548c\u67e5\u8be2\u6548\u7387\uff0c\u56e0\u6b64\u56db\u53c9\u6811\u662fGIS<\/i>\u4e2d\u5e38\u7528\u7684\u7a7a\u95f4\u7d22\u5f15\u4e4b\u4e00\u3002\u5e38\u89c4\u56db\u53c9\u6811\u7684\u7ed3\u6784\u5982\u56fe\u6240\u793a\uff0c\u5730\u7406\u7a7a\u95f4\u5bf9\u8c61\u90fd\u5b58\u50a8\u5728\u53f6\u5b50\u8282\u70b9\u4e0a\uff0c\u4e2d\u95f4\u8282\u70b9\u4ee5\u53ca\u6839\u8282\u70b9\u4e0d\u5b58\u50a8\u5730\u7406\u7a7a\u95f4\u5bf9\u8c61\u3002<\/p>\n

\u00a0<\/i><\/p>\n

\u56db\u53c9\u6811\u793a\u610f\u56fe<\/p>\n

\u00a0<\/i><\/p>\n

\u56db\u53c9\u6811\u5bf9\u4e8e\u533a\u57df\u67e5\u8be2\uff0c\u6548\u7387\u6bd4\u8f83\u9ad8\u3002\u4f46\u5982\u679c\u7a7a\u95f4\u5bf9\u8c61\u5206\u5e03\u4e0d\u5747\u5300\uff0c\u968f\u7740\u5730\u7406\u7a7a\u95f4\u5bf9\u8c61\u7684\u4e0d\u65ad\u63d2\u5165\uff0c\u56db\u53c9\u6811\u7684\u5c42\u6b21\u4f1a\u4e0d\u65ad\u5730\u52a0\u6df1\uff0c\u5c06\u5f62\u6210\u4e00\u68f5\u4e25\u91cd\u4e0d\u5e73\u8861\u7684\u56db\u53c9\u6811\uff0c\u90a3\u4e48\u6bcf\u6b21\u67e5\u8be2\u7684\u6df1\u5ea6\u5c06\u5927\u5927\u7684\u589e\u591a\uff0c\u4ece\u800c\u5bfc\u81f4\u67e5\u8be2\u6548\u7387\u7684\u6025\u5267\u4e0b\u964d\u3002<\/p>\n

\u00a0<\/i><\/p>\n

\u672c\u8282\u5c06\u4ecb\u7ecd\u4e00\u79cd\u6539\u8fdb\u7684\u56db\u53c9\u6811\u7d22\u5f15\u7ed3\u6784\u3002\u56db\u53c9\u6811\u7ed3\u6784\u662f\u81ea\u9876\u5411\u4e0b\u9010\u6b65\u5212\u5206\u7684\u4e00\u79cd\u6811\u72b6\u7684\u5c42\u6b21\u7ed3\u6784\u3002\u4f20\u7edf\u7684\u56db\u53c9\u6811\u7d22\u5f15\u5b58\u5728\u7740\u4ee5\u4e0b\u51e0\u4e2a\u7f3a\u70b9\uff1a<\/p>\n

(1)<\/i>\u7a7a\u95f4\u5b9e\u4f53\u53ea\u80fd\u5b58\u50a8\u5728\u53f6\u5b50\u8282\u70b9\u4e2d\uff0c\u4e2d\u95f4\u8282\u70b9\u4ee5\u53ca\u6839\u8282\u70b9\u4e0d\u80fd\u5b58\u50a8\u7a7a\u95f4\u5b9e\u4f53\u4fe1\u606f\uff0c\u968f\u7740\u7a7a\u95f4\u5bf9\u8c61\u7684\u4e0d\u65ad\u63d2\u5165\uff0c\u6700\u7ec8\u4f1a\u5bfc\u81f4\u56db\u53c9\u6811\u6811\u7684\u5c42\u6b21\u6bd4\u8f83\u6df1\uff0c\u5728\u8fdb\u884c\u7a7a\u95f4\u6570\u636e\u7a97\u53e3\u67e5\u8be2\u7684\u65f6\u5019\u6548\u7387\u4f1a\u6bd4\u8f83\u4f4e\u4e0b\u3002<\/p>\n

(2)<\/i>\u540c\u4e00\u4e2a\u5730\u7406\u5b9e\u4f53\u5728\u56db\u53c9\u6811\u7684\u5206\u88c2\u8fc7\u7a0b\u4e2d\u6781\u6709\u53ef\u80fd\u5b58\u50a8\u5728\u591a\u4e2a\u8282\u70b9\u4e2d\uff0c\u8fd9\u6837\u5c31\u5bfc\u81f4\u4e86\u7d22\u5f15\u5b58\u50a8\u7a7a\u95f4\u7684\u6d6a\u8d39\u3002<\/p>\n

(3)<\/i>\u7531\u4e8e\u5730\u7406\u7a7a\u95f4\u5bf9\u8c61\u53ef\u80fd\u5206\u5e03\u4e0d\u5747\u8861\uff0c\u8fd9\u6837\u4f1a\u5bfc\u81f4\u5e38\u89c4\u56db\u53c9\u6811\u751f\u6210\u4e00\u68f5\u6781\u4e3a\u4e0d\u5e73\u8861\u7684\u6811\uff0c\u8fd9\u6837\u4e5f\u4f1a\u9020\u6210\u6811\u7ed3\u6784\u7684\u4e0d\u5e73\u8861\u4ee5\u53ca\u5b58\u50a8\u7a7a\u95f4\u7684\u6d6a\u8d39\u3002<\/p>\n

\u76f8\u5e94\u7684\u6539\u8fdb\u65b9\u6cd5\uff0c\u5c06\u5730\u7406\u5b9e\u4f53\u4fe1\u606f\u5b58\u50a8\u5728\u5b8c\u5168\u5305\u542b\u5b83\u7684\u6700\u5c0f\u77e9\u5f62\u8282\u70b9\u4e2d\uff0c\u4e0d\u5b58\u50a8\u5728\u5b83\u7684\u7236\u8282\u70b9\u4e2d\uff0c\u6bcf\u4e2a\u5730\u7406\u5b9e\u4f53\u53ea\u5728\u6811\u4e2d\u5b58\u50a8\u4e00\u6b21\uff0c\u907f\u514d\u5b58\u50a8\u7a7a\u95f4\u7684\u6d6a\u8d39\u3002\u9996\u5148\u751f\u6210\u6ee1\u56db\u53c9\u6811\uff0c\u907f\u514d\u5728\u5730\u7406\u5b9e\u4f53\u63d2\u5165\u65f6\u9700\u8981\u91cd\u65b0\u5206\u914d\u5185\u5b58\uff0c\u52a0\u5feb\u63d2\u5165\u7684\u901f\u5ea6\uff0c\u6700\u540e\u5c06\u7a7a\u7684\u8282\u70b9\u6240\u5360\u5185\u5b58\u7a7a\u95f4\u91ca\u653e\u6389\u3002\u6539\u8fdb\u540e\u7684\u56db\u53c9\u6811\u7ed3\u6784\u5982\u4e0b\u56fe\u6240\u793a\u3002\u56db\u53c9\u6811\u7684\u6df1\u5ea6\u4e00\u822c\u53d6\u7ecf\u9a8c\u503c4-7<\/i>\u4e4b\u95f4\u4e3a\u6700\u4f73\u3002<\/p>\n

\u00a0<\/i><\/p>\n

\u56fe\u6539\u8fdb\u7684\u56db\u53c9\u6811\u7ed3\u6784<\/p>\n

\u00a0<\/i><\/p>\n

\u4e3a\u4e86\u7ef4\u62a4\u7a7a\u95f4\u7d22\u5f15\u4e0e\u5bf9\u5b58\u50a8\u5728\u6587\u4ef6\u6216\u6570\u636e\u5e93\u4e2d\u7684\u7a7a\u95f4\u6570\u636e\u7684\u4e00\u81f4\u6027\uff0c\u4f5c\u8005\u8bbe\u8ba1\u4e86\u5982\u4e0b\u7684\u6570\u636e\u7ed3\u6784\u652f\u6301\u56db\u53c9\u6811\u7684\u64cd\u4f5c\u3002<\/p>\n

(1)<\/i>\u56db\u5206\u533a\u57df\u6807\u8bc6<\/p>\n

\u5206\u522b\u5b9a\u4e49\u4e86\u4e00\u4e2a\u5e73\u9762\u533a\u57df\u7684\u56db\u4e2a\u5b50\u533a\u57df\u7d22\u5f15\u53f7\uff0c\u53f3\u4e0a\u4e3a\u7b2c\u4e00\u8c61\u96500<\/i>\uff0c\u5de6\u4e0a\u4e3a\u7b2c\u4e8c\u8c61\u96501<\/i>\uff0c\u5de6\u4e0b\u4e3a\u7b2c\u4e09\u8c61\u96502<\/i>\uff0c\u53f3\u4e0b\u4e3a\u7b2c\u56db\u8c61\u96503<\/i>\u3002<\/p>\n

typedef enum<\/i><\/p>\n

{<\/i><\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0UR = 0,\/\/ UR<\/i>\u7b2c\u4e00\u8c61\u9650<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0UL = 1,\u00a0\/\/ UL<\/i>\u4e3a\u7b2c\u4e8c\u8c61\u9650<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0LL = 2,\u00a0\/\/ LL<\/i>\u4e3a\u7b2c\u4e09\u8c61\u9650<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0LR = 3\u00a0\u00a0\/\/ LR<\/i>\u4e3a\u7b2c\u56db\u8c61\u9650<\/p>\n

}QuadrantEnum;<\/i><\/p>\n

(2)<\/i>\u7a7a\u95f4\u5bf9\u8c61\u6570\u636e\u7ed3\u6784<\/p>\n

\u7a7a\u95f4\u5bf9\u8c61\u6570\u636e\u7ed3\u6784\u662f\u5bf9\u5730\u7406\u7a7a\u95f4\u5bf9\u8c61\u7684\u8fd1\u4f3c\uff0c\u5728\u7a7a\u95f4\u7d22\u5f15\u4e2d\uff0c\u76f8\u5f53\u4e00\u90e8\u5206\u90fd\u662f\u91c7\u7528MBR<\/i>\u4f5c\u4e3a\u8fd1\u4f3c\u3002<\/p>\n

\/*<\/i>\u7a7a\u95f4\u5bf9\u8c61MBR<\/i>\u4fe1\u606f*\/<\/i><\/p>\n

typedef struct SHPMBRInfo<\/i><\/p>\n

{<\/i><\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int nID;\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/<\/i>\u7a7a\u95f4\u5bf9\u8c61ID<\/i>\u53f7<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0MapRect Box;\u00a0\u00a0\u00a0\u00a0\/\/<\/i>\u7a7a\u95f4\u5bf9\u8c61MBR<\/i>\u8303\u56f4\u5750\u6807<\/p>\n

}SHPMBRInfo;<\/i><\/p>\n

nID<\/i>\u662f\u7a7a\u95f4\u5bf9\u8c61\u7684\u6807\u8bc6\u53f7\uff0cBox<\/i>\u662f\u7a7a\u95f4\u5bf9\u8c61\u7684\u6700\u5c0f\u5916\u5305\u77e9\u5f62\uff08MBR<\/i>\uff09\u3002<\/p>\n

(3)<\/i>\u56db\u53c9\u6811\u8282\u70b9\u6570\u636e\u7ed3\u6784<\/p>\n

\u56db\u53c9\u6811\u8282\u70b9\u662f\u56db\u53c9\u6811\u7ed3\u6784\u7684\u4e3b\u8981\u7ec4\u6210\u90e8\u5206\uff0c\u4e3b\u8981\u7528\u4e8e\u5b58\u50a8\u7a7a\u95f4\u5bf9\u8c61\u7684\u6807\u8bc6\u53f7\u548cMBR<\/i>\uff0c\u4e5f\u662f\u56db\u53c9\u6811\u7b97\u6cd5\u64cd\u4f5c\u7684\u4e3b\u8981\u90e8\u5206\u3002<\/p>\n

\/*<\/i>\u56db\u53c9\u6811\u8282\u70b9\u7c7b\u578b\u7ed3\u6784*\/<\/i><\/p>\n

typedef struct QuadNode<\/i><\/p>\n

{<\/i><\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0MapRect\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Box;\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/<\/i>\u8282\u70b9\u6240\u4ee3\u8868\u7684\u77e9\u5f62\u533a\u57df<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0nShpCount;\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/<\/i>\u8282\u70b9\u6240\u5305\u542b\u7684\u6240\u6709\u7a7a\u95f4\u5bf9\u8c61\u4e2a\u6570<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0SHPMBRInfo* pShapeObj;\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/<\/i>\u7a7a\u95f4\u5bf9\u8c61\u6307\u9488\u6570\u7ec4<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0nChildCount;\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/<\/i>\u5b50\u8282\u70b9\u4e2a\u6570<\/p>\n

\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0QuadNode\u00a0*children[4];\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/<\/i>\u6307\u5411\u8282\u70b9\u7684\u56db\u4e2a\u5b69\u5b50<\/p>\n

}QuadNode;<\/i><\/p>\n

Box<\/i>\u662f\u4ee3\u8868\u56db\u53c9\u6811\u5bf9\u5e94\u533a\u57df\u7684\u6700\u5c0f\u5916\u5305\u77e9\u5f62\uff0c\u4e0a\u4e00\u5c42\u7684\u8282\u70b9\u7684\u6700\u5c0f\u5916\u5305\u77e9\u5f62\u5305\u542b\u4e0b\u4e00\u5c42\u6700\u5c0f\u5916\u5305\u77e9\u5f62\u533a\u57df\uff1bnShpCount<\/i>\u4ee3\u8868\u672c\u8282\u70b9\u5305\u542b\u7684\u7a7a\u95f4\u5bf9\u8c61\u7684\u4e2a\u6570\uff1bpShapeObj<\/i>\u4ee3\u8868\u6307\u5411\u7a7a\u95f4\u5bf9\u8c61\u5b58\u50a8\u5730\u5740\u7684\u9996\u5730\u5740\uff0c\u540c\u4e00\u4e2a\u8282\u70b9\u7684\u7a7a\u95f4\u5bf9\u8c61\u5728\u5185\u5b58\u4e2d\u8fde\u7eed\u5b58\u50a8\uff1bnChildCount<\/i>\u4ee3\u8868\u8282\u70b9\u62e5\u6709\u7684\u5b50\u8282\u70b9\u7684\u6570\u76ee\uff1bchildren<\/i>\u662f\u6307\u5411\u5b69\u5b50\u8282\u70b9\u6307\u9488\u7684\u6570\u7ec4\u3002<\/p>\n

\u4e0a\u8ff0\u7406\u8bba\u90e8\u5206\u90fd\u90fd\u8bb2\u7684\u5dee\u4e0d\u591a\u4e86\uff0c\u4e0b\u9762\u5c31\u8d34\u4e0a\u6211\u7684C\u8bed\u8a00\u5b9e\u73b0\u7248\u672c\u4ee3\u7801\u3002<\/p>\n

\u5934\u6587\u4ef6\u5982\u4e0b\uff1a<\/p>\n

    \n
  1. #ifndef __QUADTREE_H_59CAE94A_E937_42AD_AA27_794E467715BB__<\/li>\n
  2. #define __QUADTREE_H_59CAE94A_E937_42AD_AA27_794E467715BB__<\/li>\n
  3. \/* \u4e00\u4e2a\u77e9\u5f62\u533a\u57df\u7684\u8c61\u9650\u5212\u5206\uff1a:<\/i><\/li>\n
  4. UL(1) | UR(0)<\/i><\/li>\n
  5. ———-|———–<\/i><\/li>\n
  6. LL(2) | LR(3)<\/i><\/li>\n
  7. \u4ee5\u4e0b\u5bf9\u8be5\u8c61\u9650\u7c7b\u578b\u7684\u679a\u4e3e<\/i><\/li>\n
  8. *\/<\/i><\/li>\n
  9. typedef enum<\/li>\n
  10. {<\/li>\n
  11. UR = 0,<\/li>\n
  12. UL = 1,<\/li>\n
  13. LL = 2,<\/li>\n
  14. LR = 3<\/li>\n
  15. }QuadrantEnum;<\/li>\n
  16. \/*\u7a7a\u95f4\u5bf9\u8c61MBR\u4fe1\u606f*\/<\/i><\/li>\n
  17. typedef struct SHPMBRInfo<\/li>\n
  18. {<\/li>\n
  19. int nID; \/\/\u7a7a\u95f4\u5bf9\u8c61ID\u53f7<\/i><\/li>\n
  20. MapRect Box; \/\/\u7a7a\u95f4\u5bf9\u8c61MBR\u8303\u56f4\u5750\u6807<\/i><\/li>\n
  21. }SHPMBRInfo;<\/li>\n
  22. \/* \u56db\u53c9\u6811\u8282\u70b9\u7c7b\u578b\u7ed3\u6784 *\/<\/i><\/li>\n
  23. typedef struct QuadNode<\/li>\n
  24. {<\/li>\n
  25. MapRect Box; \/\/\u8282\u70b9\u6240\u4ee3\u8868\u7684\u77e9\u5f62\u533a\u57df<\/i><\/li>\n
  26. int nShpCount; \/\/\u8282\u70b9\u6240\u5305\u542b\u7684\u6240\u6709\u7a7a\u95f4\u5bf9\u8c61\u4e2a\u6570<\/i><\/li>\n
  27. SHPMBRInfo* pShapeObj; \/\/\u7a7a\u95f4\u5bf9\u8c61\u6307\u9488\u6570\u7ec4<\/i><\/li>\n
  28. int nChildCount; \/\/\u5b50\u8282\u70b9\u4e2a\u6570<\/i><\/li>\n
  29. QuadNode *children[4]; \/\/\u6307\u5411\u8282\u70b9\u7684\u56db\u4e2a\u5b69\u5b50 <\/i><\/li>\n
  30. }QuadNode;<\/li>\n
  31. \/* \u56db\u53c9\u6811\u7c7b\u578b\u7ed3\u6784 *\/<\/i><\/li>\n
  32. typedef struct quadtree_t<\/li>\n
  33. {<\/li>\n
  34. QuadNode *root;<\/li>\n
  35. int depth; \/\/ \u56db\u53c9\u6811\u7684\u6df1\u5ea6 <\/i><\/li>\n
  36. }QuadTree;<\/li>\n
  37. \/\/\u521d\u59cb\u5316\u56db\u53c9\u6811\u8282\u70b9<\/i><\/li>\n
  38. QuadNode *InitQuadNode();<\/li>\n
  39. \/\/\u5c42\u6b21\u521b\u5efa\u56db\u53c9\u6811\u65b9\u6cd5\uff08\u6ee1\u56db\u53c9\u6811\uff09<\/i><\/li>\n
  40. void CreateQuadTree(int depth,GeoLayer *poLayer,QuadTree* pQuadTree);<\/li>\n
  41. \/\/\u521b\u5efa\u5404\u4e2a\u5206\u652f<\/i><\/li>\n
  42. void CreateQuadBranch(int depth,MapRect &rect,QuadNode** node);<\/li>\n
  43. \/\/\u6784\u5efa\u56db\u53c9\u6811\u7a7a\u95f4\u7d22\u5f15<\/i><\/li>\n
  44. void BuildQuadTree(GeoLayer*poLayer,QuadTree* pQuadTree);<\/li>\n
  45. \/\/\u56db\u53c9\u6811\u7d22\u5f15\u67e5\u8be2(\u77e9\u5f62\u67e5\u8be2)<\/i><\/li>\n
  46. void SearchQuadTree(QuadNode* node,MapRect &queryRect,vector<int>& ItemSearched);<\/li>\n
  47. \/\/\u56db\u53c9\u6811\u7d22\u5f15\u67e5\u8be2(\u77e9\u5f62\u67e5\u8be2)\u5e76\u884c\u67e5\u8be2<\/i><\/li>\n
  48. void SearchQuadTreePara(vector<QuadNode*> resNodes,MapRect &queryRect,vector<int>& ItemSearched);<\/li>\n
  49. \/\/\u56db\u53c9\u6811\u7684\u67e5\u8be2\uff08\u70b9\u67e5\u8be2\uff09<\/i><\/li>\n
  50. void PtSearchQTree(QuadNode* node,double cx,double cy,vector<int>& ItemSearched);<\/li>\n
  51. \/\/\u5c06\u6307\u5b9a\u7684\u7a7a\u95f4\u5bf9\u8c61\u63d2\u5165\u5230\u56db\u53c9\u6811\u4e2d<\/i><\/li>\n
  52. void Insert(long key,MapRect &itemRect,QuadNode* pNode);<\/li>\n
  53. \/\/\u5c06\u6307\u5b9a\u7684\u7a7a\u95f4\u5bf9\u8c61\u63d2\u5165\u5230\u56db\u53c9\u6811\u4e2d<\/i><\/li>\n
  54. void InsertQuad(long key,MapRect &itemRect,QuadNode* pNode);<\/li>\n
  55. \/\/\u5c06\u6307\u5b9a\u7684\u7a7a\u95f4\u5bf9\u8c61\u63d2\u5165\u5230\u56db\u53c9\u6811\u4e2d<\/i><\/li>\n
  56. void InsertQuad2(long key,MapRect &itemRect,QuadNode* pNode);<\/li>\n
  57. \/\/\u5224\u65ad\u4e00\u4e2a\u8282\u70b9\u662f\u5426\u662f\u53f6\u5b50\u8282\u70b9<\/i><\/li>\n
  58. bool IsQuadLeaf(QuadNode* node);<\/li>\n
  59. \/\/\u5220\u9664\u591a\u4f59\u7684\u8282\u70b9<\/i><\/li>\n
  60. bool DelFalseNode(QuadNode* node);<\/li>\n
  61. \/\/\u56db\u53c9\u6811\u904d\u5386(\u6240\u6709\u8981\u7d20)<\/i><\/li>\n
  62. void TraversalQuadTree(QuadNode* quadTree,vector<int>& resVec);<\/li>\n
  63. \/\/\u56db\u53c9\u6811\u904d\u5386\uff08\u6240\u6709\u8282\u70b9\uff09<\/i><\/li>\n
  64. void TraversalQuadTree(QuadNode* quadTree,vector<QuadNode*>& arrNode);<\/li>\n
  65. \/\/\u91ca\u653e\u6811\u7684\u5185\u5b58\u7a7a\u95f4<\/i><\/li>\n
  66. void ReleaseQuadTree(QuadNode** quadTree);<\/li>\n
  67. \/\/\u8ba1\u7b97\u56db\u53c9\u6811\u6240\u5360\u7684\u5b57\u8282\u7684\u5927\u5c0f<\/i><\/li>\n
  68. long CalByteQuadTree(QuadNode* quadTree,long& nSize);<\/li>\n
  69. #endif<\/li>\n<\/ol>\n

    \n\u6e90\u6587\u4ef6\u5982\u4e0b\uff1a<\/p>\n

      \n
    1. #include “QuadTree.h”<\/li>\n
    2. QuadNode *InitQuadNode()<\/li>\n
    3. {<\/li>\n
    4. QuadNode *node = new QuadNode;<\/li>\n
    5. node->Box.maxX = 0;<\/li>\n
    6. node->Box.maxY = 0;<\/li>\n
    7. node->Box.minX = 0;<\/li>\n
    8. node->Box.minY = 0;<\/li>\n
    9. for (int i = 0; i < 4; i ++)<\/li>\n
    10. {<\/li>\n
    11. node->children[i] = NULL;<\/li>\n
    12. }<\/li>\n
    13. node->nChildCount = 0;<\/li>\n
    14. node->nShpCount = 0;<\/li>\n
    15. node->pShapeObj = NULL;<\/li>\n
    16. return node;<\/li>\n
    17. }<\/li>\n
    18. void CreateQuadTree(int depth,GeoLayer *poLayer,QuadTree* pQuadTree)<\/li>\n
    19. {<\/li>\n
    20. pQuadTree->depth = depth;<\/li>\n
    21. GeoEnvelope env; \/\/\u6574\u4e2a\u56fe\u5c42\u7684MBR<\/i><\/li>\n
    22. poLayer->GetExtent(&env);<\/li>\n
    23. MapRect rect;<\/li>\n
    24. rect.minX = env.MinX;<\/li>\n
    25. rect.minY = env.MinY;<\/li>\n
    26. rect.maxX = env.MaxX;<\/li>\n
    27. rect.maxY = env.MaxY;<\/li>\n
    28. \/\/\u521b\u5efa\u5404\u4e2a\u5206\u652f<\/i><\/li>\n
    29. CreateQuadBranch(depth,rect,&(pQuadTree->root));<\/li>\n
    30. int nCount = poLayer->GetFeatureCount();<\/li>\n
    31. GeoFeature **pFeatureClass = new GeoFeature*[nCount];<\/li>\n
    32. for (int i = 0; i < poLayer->GetFeatureCount(); i ++)<\/li>\n
    33. {<\/li>\n
    34. pFeatureClass[i] = poLayer->GetFeature(i);<\/li>\n
    35. }<\/li>\n
    36. \/\/\u63d2\u5165\u5404\u4e2a\u8981\u7d20<\/i><\/li>\n
    37. GeoEnvelope envObj; \/\/\u7a7a\u95f4\u5bf9\u8c61\u7684MBR<\/i><\/li>\n
    38. \/\/#pragma omp parallel for<\/i><\/li>\n
    39. for (int i = 0; i < nCount; i ++)<\/li>\n
    40. {<\/li>\n
    41. pFeatureClass[i]->GetGeometry()->getEnvelope(&envObj);<\/li>\n
    42. rect.minX = envObj.MinX;<\/li>\n
    43. rect.minY = envObj.MinY;<\/li>\n
    44. rect.maxX = envObj.MaxX;<\/li>\n
    45. rect.maxY = envObj.MaxY;<\/li>\n
    46. InsertQuad(i,rect,pQuadTree->root);<\/li>\n
    47. }<\/li>\n
    48. \/\/DelFalseNode(pQuadTree->root);<\/i><\/li>\n
    49. }<\/li>\n
    50. void CreateQuadBranch(int depth,MapRect &rect,QuadNode** node)<\/li>\n
    51. {<\/li>\n
    52. if (depth != 0)<\/li>\n
    53. {<\/li>\n
    54. *node = InitQuadNode(); \/\/\u521b\u5efa\u6811\u6839<\/i><\/li>\n
    55. QuadNode *pNode = *node;<\/li>\n
    56. pNode->Box = rect;<\/li>\n
    57. pNode->nChildCount = 4;<\/li>\n
    58. MapRect boxs[4];<\/li>\n
    59. pNode->Box.Split(boxs,boxs+1,boxs+2,boxs+3);<\/li>\n
    60. for (int i = 0; i < 4; i ++)<\/li>\n
    61. {<\/li>\n
    62. \/\/\u521b\u5efa\u56db\u4e2a\u8282\u70b9\u5e76\u63d2\u5165\u76f8\u5e94\u7684MBR<\/i><\/li>\n
    63. pNode->children[i] = InitQuadNode();<\/li>\n
    64. pNode->children[i]->Box = boxs[i];<\/li>\n
    65. CreateQuadBranch(depth-1,boxs[i],&(pNode->children[i]));<\/li>\n
    66. }<\/li>\n
    67. }<\/li>\n
    68. }<\/li>\n
    69. void BuildQuadTree(GeoLayer *poLayer,QuadTree* pQuadTree)<\/li>\n
    70. {<\/li>\n
    71. assert(poLayer);<\/li>\n
    72. GeoEnvelope env; \/\/\u6574\u4e2a\u56fe\u5c42\u7684MBR<\/i><\/li>\n
    73. poLayer->GetExtent(&env);<\/li>\n
    74. pQuadTree->root = InitQuadNode();<\/li>\n
    75. QuadNode* rootNode = pQuadTree->root;<\/li>\n
    76. rootNode->Box.minX = env.MinX;<\/li>\n
    77. rootNode->Box.minY = env.MinY;<\/li>\n
    78. rootNode->Box.maxX = env.MaxX;<\/li>\n
    79. rootNode->Box.maxY = env.MaxY;<\/li>\n
    80. \/\/\u8bbe\u7f6e\u6811\u7684\u6df1\u5ea6( \u6839\u636e\u7b49\u6bd4\u6570\u5217\u7684\u6c42\u548c\u516c\u5f0f)<\/i><\/li>\n
    81. \/\/pQuadTree->depth = log(poLayer->GetFeatureCount()*3\/8.0+1)\/log(4.0);<\/i><\/li>\n
    82. int nCount = poLayer->GetFeatureCount();<\/li>\n
    83. MapRect rect;<\/li>\n
    84. GeoEnvelope envObj; \/\/\u7a7a\u95f4\u5bf9\u8c61\u7684MBR<\/i><\/li>\n
    85. for (int i = 0; i < nCount; i ++)<\/li>\n
    86. {<\/li>\n
    87. poLayer->GetFeature(i)->GetGeometry()->getEnvelope(&envObj);<\/li>\n
    88. rect.minX = envObj.MinX;<\/li>\n
    89. rect.minY = envObj.MinY;<\/li>\n
    90. rect.maxX = envObj.MaxX;<\/li>\n
    91. rect.maxY = envObj.MaxY;<\/li>\n
    92. InsertQuad2(i,rect,rootNode);<\/li>\n
    93. }<\/li>\n
    94. DelFalseNode(pQuadTree->root);<\/li>\n
    95. }<\/li>\n
    96. void SearchQuadTree(QuadNode* node,MapRect &queryRect,vector<int>& ItemSearched)<\/li>\n
    97. {<\/li>\n
    98. assert(node);<\/li>\n
    99. \/\/int coreNum = omp_get_num_procs();<\/i><\/li>\n
    100. \/\/vector<int> * pResArr = new vector<int>[coreNum];<\/i><\/li>\n
    101. if (NULL != node)<\/li>\n
    102. {<\/li>\n
    103. for (int i = 0; i < node->nShpCount; i ++)<\/li>\n
    104. {<\/li>\n
    105. if (queryRect.Contains(node->pShapeObj[i].Box)<\/li>\n
    106. || queryRect.Intersects(node->pShapeObj[i].Box))<\/li>\n
    107. {<\/li>\n
    108. ItemSearched.push_back(node->pShapeObj[i].nID);<\/li>\n
    109. }<\/li>\n
    110. }<\/li>\n
    111. \/\/\u5e76\u884c\u641c\u7d22\u56db\u4e2a\u5b69\u5b50\u8282\u70b9<\/i><\/li>\n
    112. \/*#pragma omp parallel sections<\/i><\/li>\n
    113. {<\/i><\/li>\n
    114. #pragma omp section<\/i><\/li>\n
    115. if ((node->children[0] != NULL) && <\/i><\/li>\n
    116. (node->children[0]->Box.Contains(queryRect)<\/i><\/li>\n
    117. || node->children[0]->Box.Intersects(queryRect)))<\/i><\/li>\n
    118. {<\/i><\/li>\n
    119. int tid = omp_get_thread_num();<\/i><\/li>\n
    120. SearchQuadTree(node->children[0],queryRect,pResArr[tid]);<\/i><\/li>\n
    121. }<\/i><\/li>\n
    122. #pragma omp section<\/i><\/li>\n
    123. if ((node->children[1] != NULL) && <\/i><\/li>\n
    124. (node->children[1]->Box.Contains(queryRect)<\/i><\/li>\n
    125. || node->children[1]->Box.Intersects(queryRect)))<\/i><\/li>\n
    126. {<\/i><\/li>\n
    127. int tid = omp_get_thread_num();<\/i><\/li>\n
    128. SearchQuadTree(node->children[1],queryRect,pResArr[tid]);<\/i><\/li>\n
    129. }<\/i><\/li>\n
    130. #pragma omp section<\/i><\/li>\n
    131. if ((node->children[2] != NULL) && <\/i><\/li>\n
    132. (node->children[2]->Box.Contains(queryRect)<\/i><\/li>\n
    133. || node->children[2]->Box.Intersects(queryRect)))<\/i><\/li>\n
    134. {<\/i><\/li>\n
    135. int tid = omp_get_thread_num();<\/i><\/li>\n
    136. SearchQuadTree(node->children[2],queryRect,pResArr[tid]);<\/i><\/li>\n
    137. }<\/i><\/li>\n
    138. #pragma omp section<\/i><\/li>\n
    139. if ((node->children[3] != NULL) && <\/i><\/li>\n
    140. (node->children[3]->Box.Contains(queryRect)<\/i><\/li>\n
    141. || node->children[3]->Box.Intersects(queryRect)))<\/i><\/li>\n
    142. {<\/i><\/li>\n
    143. int tid = omp_get_thread_num();<\/i><\/li>\n
    144. SearchQuadTree(node->children[3],queryRect,pResArr[tid]);<\/i><\/li>\n
    145. }<\/i><\/li>\n
    146. }*\/<\/i><\/li>\n
    147. for (int i = 0; i < 4; i ++)<\/li>\n
    148. {<\/li>\n
    149. if ((node->children[i] != NULL) &&<\/li>\n
    150. (node->children[i]->Box.Contains(queryRect)<\/li>\n
    151. || node->children[i]->Box.Intersects(queryRect)))<\/li>\n
    152. {<\/li>\n
    153. SearchQuadTree(node->children[i],queryRect,ItemSearched);<\/li>\n
    154. \/\/node = node->children[i]; \/\/\u975e\u9012\u5f52<\/i><\/li>\n
    155. }<\/li>\n
    156. }<\/li>\n
    157. }<\/li>\n
    158. \/*for (int i = 0 ; i < coreNum; i ++)<\/i><\/li>\n
    159. {<\/i><\/li>\n
    160. ItemSearched.insert(ItemSearched.end(),pResArr[i].begin(),pResArr[i].end());<\/i><\/li>\n
    161. }*\/<\/i><\/li>\n
    162. }<\/li>\n
    163. void SearchQuadTreePara(vector<QuadNode*> resNodes,MapRect &queryRect,vector<int>& ItemSearched)<\/li>\n
    164. {<\/li>\n
    165. int coreNum = omp_get_num_procs();<\/li>\n
    166. omp_set_num_threads(coreNum);<\/li>\n
    167. vector<int>* searchArrs = new vector<int>[coreNum];<\/li>\n
    168. for (int i = 0; i < coreNum; i ++)<\/li>\n
    169. {<\/li>\n
    170. searchArrs[i].clear();<\/li>\n
    171. }<\/li>\n
    172. #pragma omp parallel for<\/li>\n
    173. for (int i = 0; i < resNodes.size(); i ++)<\/li>\n
    174. {<\/li>\n
    175. int tid = omp_get_thread_num();<\/li>\n
    176. for (int j = 0; j < resNodes[i]->nShpCount; j ++)<\/li>\n
    177. {<\/li>\n
    178. if (queryRect.Contains(resNodes[i]->pShapeObj[j].Box)<\/li>\n
    179. || queryRect.Intersects(resNodes[i]->pShapeObj[j].Box))<\/li>\n
    180. {<\/li>\n
    181. searchArrs[tid].push_back(resNodes[i]->pShapeObj[j].nID);<\/li>\n
    182. }<\/li>\n
    183. }<\/li>\n
    184. }<\/li>\n
    185. for (int i = 0; i < coreNum; i ++)<\/li>\n
    186. {<\/li>\n
    187. ItemSearched.insert(ItemSearched.end(),<\/li>\n
    188. searchArrs[i].begin(),searchArrs[i].end());<\/li>\n
    189. }<\/li>\n
    190. delete [] searchArrs;<\/li>\n
    191. searchArrs = NULL;<\/li>\n
    192. }<\/li>\n
    193. void PtSearchQTree(QuadNode* node,double cx,double cy,vector<int>& ItemSearched)<\/li>\n
    194. {<\/li>\n
    195. assert(node);<\/li>\n
    196. if (node->nShpCount >0) \/\/\u8282\u70b9 <\/i><\/li>\n
    197. {<\/li>\n
    198. for (int i = 0; i < node->nShpCount; i ++)<\/li>\n
    199. {<\/li>\n
    200. if (node->pShapeObj[i].Box.IsPointInRect(cx,cy))<\/li>\n
    201. {<\/li>\n
    202. ItemSearched.push_back(node->pShapeObj[i].nID);<\/li>\n
    203. }<\/li>\n
    204. }<\/li>\n
    205. }<\/li>\n
    206. else if (node->nChildCount >0) \/\/\u8282\u70b9<\/i><\/li>\n
    207. {<\/li>\n
    208. for (int i = 0; i < 4; i ++)<\/li>\n
    209. {<\/li>\n
    210. if (node->children[i]->Box.IsPointInRect(cx,cy))<\/li>\n
    211. {<\/li>\n
    212. PtSearchQTree(node->children[i],cx,cy,ItemSearched);<\/li>\n
    213. }<\/li>\n
    214. }<\/li>\n
    215. }<\/li>\n
    216. \/\/\u627e\u51fa\u91cd\u590d\u5143\u7d20\u7684\u4f4d\u7f6e<\/i><\/li>\n
    217. sort(ItemSearched.begin(),ItemSearched.end()); \/\/\u5148\u6392\u5e8f,\u9ed8\u8ba4\u5347\u5e8f<\/i><\/li>\n
    218. vector<int>::iterator unique_iter =<\/li>\n
    219. unique(ItemSearched.begin(),ItemSearched.end());<\/li>\n
    220. ItemSearched.erase(unique_iter,ItemSearched.end());<\/li>\n
    221. }<\/li>\n
    222. void Insert(long key, MapRect &itemRect,QuadNode* pNode)<\/li>\n
    223. {<\/li>\n
    224. QuadNode *node = pNode; \/\/\u4fdd\u7559\u6839\u8282\u70b9\u526f\u672c<\/i><\/li>\n
    225. SHPMBRInfo pShpInfo;<\/li>\n
    226. \/\/\u8282\u70b9\u6709\u5b69\u5b50<\/i><\/li>\n
    227. if (0 < node->nChildCount)<\/li>\n
    228. {<\/li>\n
    229. for (int i = 0; i < 4; i ++)<\/li>\n
    230. {<\/li>\n
    231. \/\/\u5982\u679c\u5305\u542b\u6216\u76f8\u4ea4\uff0c\u5219\u5c06\u8282\u70b9\u63d2\u5165\u5230\u6b64\u8282\u70b9<\/i><\/li>\n
    232. if (node->children[i]->Box.Contains(itemRect)<\/li>\n
    233. || node->children[i]->Box.Intersects(itemRect))<\/li>\n
    234. {<\/li>\n
    235. \/\/node = node->children[i];<\/i><\/li>\n
    236. Insert(key,itemRect,node->children[i]);<\/li>\n
    237. }<\/li>\n
    238. }<\/li>\n
    239. }<\/li>\n
    240. \/\/\u5982\u679c\u5f53\u524d\u8282\u70b9\u5b58\u5728\u4e00\u4e2a\u5b50\u8282\u70b9\u65f6<\/i><\/li>\n
    241. else if (1 == node->nShpCount)<\/li>\n
    242. {<\/li>\n
    243. MapRect boxs[4];<\/li>\n
    244. node->Box.Split(boxs,boxs+1,boxs+2,boxs+3);<\/li>\n
    245. \/\/\u521b\u5efa\u56db\u4e2a\u8282\u70b9\u5e76\u63d2\u5165\u76f8\u5e94\u7684MBR<\/i><\/li>\n
    246. node->children[UR] = InitQuadNode();<\/li>\n
    247. node->children[UL] = InitQuadNode();<\/li>\n
    248. node->children[LL] = InitQuadNode();<\/li>\n
    249. node->children[LR] = InitQuadNode();<\/li>\n
    250. node->children[UR]->Box = boxs[0];<\/li>\n
    251. node->children[UL]->Box = boxs[1];<\/li>\n
    252. node->children[LL]->Box = boxs[2];<\/li>\n
    253. node->children[LR]->Box = boxs[3];<\/li>\n
    254. node->nChildCount = 4;<\/li>\n
    255. for (int i = 0; i < 4; i ++)<\/li>\n
    256. {<\/li>\n
    257. \/\/\u5c06\u5f53\u524d\u8282\u70b9\u4e2d\u7684\u8981\u7d20\u79fb\u52a8\u5230\u76f8\u5e94\u7684\u5b50\u8282\u70b9\u4e2d<\/i><\/li>\n
    258. for (int j = 0; j < node->nShpCount; j ++)<\/li>\n
    259. {<\/li>\n
    260. if (node->children[i]->Box.Contains(node->pShapeObj[j].Box)<\/li>\n
    261. || node->children[i]->Box.Intersects(node->pShapeObj[j].Box))<\/li>\n
    262. {<\/li>\n
    263. node->children[i]->nShpCount += 1;<\/li>\n
    264. node->children[i]->pShapeObj =<\/li>\n
    265. (SHPMBRInfo*)malloc(node->children[i]->nShpCount*sizeof(SHPMBRInfo));<\/li>\n
    266. memcpy(node->children[i]->pShapeObj,&(node->pShapeObj[j]),sizeof(SHPMBRInfo));<\/li>\n
    267. free(node->pShapeObj);<\/li>\n
    268. node->pShapeObj = NULL;<\/li>\n
    269. node->nShpCount = 0;<\/li>\n
    270. }<\/li>\n
    271. }<\/li>\n
    272. }<\/li>\n
    273. for (int i = 0; i < 4; i ++)<\/li>\n
    274. {<\/li>\n
    275. \/\/\u5982\u679c\u5305\u542b\u6216\u76f8\u4ea4\uff0c\u5219\u5c06\u8282\u70b9\u63d2\u5165\u5230\u6b64\u8282\u70b9<\/i><\/li>\n
    276. if (node->children[i]->Box.Contains(itemRect)<\/li>\n
    277. || node->children[i]->Box.Intersects(itemRect))<\/li>\n
    278. {<\/li>\n
    279. if (node->children[i]->nShpCount == 0) \/\/\u5982\u679c\u4e4b\u524d\u6ca1\u6709\u8282\u70b9<\/i><\/li>\n
    280. {<\/li>\n
    281. node->children[i]->nShpCount += 1;<\/li>\n
    282. node->pShapeObj =<\/li>\n
    283. (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->children[i]->nShpCount);<\/li>\n
    284. }<\/li>\n
    285. else if (node->children[i]->nShpCount > 0)<\/li>\n
    286. {<\/li>\n
    287. node->children[i]->nShpCount += 1;<\/li>\n
    288. node->children[i]->pShapeObj =<\/li>\n
    289. (SHPMBRInfo *)realloc(node->children[i]->pShapeObj,<\/li>\n
    290. sizeof(SHPMBRInfo)*node->children[i]->nShpCount);<\/li>\n
    291. }<\/li>\n
    292. pShpInfo.Box = itemRect;<\/li>\n
    293. pShpInfo.nID = key;<\/li>\n
    294. memcpy(node->children[i]->pShapeObj,<\/li>\n
    295. &pShpInfo,sizeof(SHPMBRInfo));<\/li>\n
    296. }<\/li>\n
    297. }<\/li>\n
    298. }<\/li>\n
    299. \/\/\u5f53\u524d\u8282\u70b9\u6ca1\u6709\u7a7a\u95f4\u5bf9\u8c61<\/i><\/li>\n
    300. else if (0 == node->nShpCount)<\/li>\n
    301. {<\/li>\n
    302. node->nShpCount += 1;<\/li>\n
    303. node->pShapeObj =<\/li>\n
    304. (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);<\/li>\n
    305. pShpInfo.Box = itemRect;<\/li>\n
    306. pShpInfo.nID = key;<\/li>\n
    307. memcpy(node->pShapeObj,&pShpInfo,sizeof(SHPMBRInfo));<\/li>\n
    308. }<\/li>\n
    309. }<\/li>\n
    310. void InsertQuad(long key,MapRect &itemRect,QuadNode* pNode)<\/li>\n
    311. {<\/li>\n
    312. assert(pNode != NULL);<\/li>\n
    313. if (!IsQuadLeaf(pNode)) \/\/\u975e\u53f6\u5b50\u8282\u70b9<\/i><\/li>\n
    314. {<\/li>\n
    315. int nCorver = 0; \/\/\u8de8\u8d8a\u7684\u5b50\u8282\u70b9\u4e2a\u6570<\/i><\/li>\n
    316. int iIndex = -1; \/\/\u88ab\u54ea\u4e2a\u5b50\u8282\u70b9\u5b8c\u5168\u5305\u542b\u7684\u7d22\u5f15\u53f7<\/i><\/li>\n
    317. for (int i = 0; i < 4; i ++)<\/li>\n
    318. {<\/li>\n
    319. if (pNode->children[i]->Box.Contains(itemRect)<\/li>\n
    320. && pNode->Box.Contains(itemRect))<\/li>\n
    321. {<\/li>\n
    322. nCorver += 1;<\/li>\n
    323. iIndex = i;<\/li>\n
    324. }<\/li>\n
    325. }<\/li>\n
    326. \/\/\u5982\u679c\u88ab\u67d0\u4e00\u4e2a\u5b50\u8282\u70b9\u5305\u542b\uff0c\u5219\u8fdb\u5165\u8be5\u5b50\u8282\u70b9<\/i><\/li>\n
    327. if (\/*pNode->Box.Contains(itemRect) || <\/i><\/li>\n
    328. pNode->Box.Intersects(itemRect)*\/<\/i>1 <= nCorver)<\/li>\n
    329. {<\/li>\n
    330. InsertQuad(key,itemRect,pNode->children[iIndex]);<\/li>\n
    331. }<\/li>\n
    332. \/\/\u5982\u679c\u8de8\u8d8a\u4e86\u591a\u4e2a\u5b50\u8282\u70b9\uff0c\u76f4\u63a5\u653e\u5728\u8fd9\u4e2a\u8282\u70b9\u4e2d<\/i><\/li>\n
    333. else if (nCorver == 0)<\/li>\n
    334. {<\/li>\n
    335. if (pNode->nShpCount == 0) \/\/\u5982\u679c\u4e4b\u524d\u6ca1\u6709\u8282\u70b9<\/i><\/li>\n
    336. {<\/li>\n
    337. pNode->nShpCount += 1;<\/li>\n
    338. pNode->pShapeObj =<\/li>\n
    339. (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*pNode->nShpCount);<\/li>\n
    340. }<\/li>\n
    341. else<\/li>\n
    342. {<\/li>\n
    343. pNode->nShpCount += 1;<\/li>\n
    344. pNode->pShapeObj =<\/li>\n
    345. (SHPMBRInfo *)realloc(pNode->pShapeObj,sizeof(SHPMBRInfo)*pNode->nShpCount);<\/li>\n
    346. }<\/li>\n
    347. SHPMBRInfo pShpInfo;<\/li>\n
    348. pShpInfo.Box = itemRect;<\/li>\n
    349. pShpInfo.nID = key;<\/li>\n
    350. memcpy(pNode->pShapeObj+pNode->nShpCount-1,&pShpInfo,sizeof(SHPMBRInfo));<\/li>\n
    351. }<\/li>\n
    352. }<\/li>\n
    353. \/\/\u5982\u679c\u662f\u53f6\u5b50\u8282\u70b9\uff0c\u76f4\u63a5\u653e\u8fdb\u53bb<\/i><\/li>\n
    354. else if (IsQuadLeaf(pNode))<\/li>\n
    355. {<\/li>\n
    356. if (pNode->nShpCount == 0) \/\/\u5982\u679c\u4e4b\u524d\u6ca1\u6709\u8282\u70b9<\/i><\/li>\n
    357. {<\/li>\n
    358. pNode->nShpCount += 1;<\/li>\n
    359. pNode->pShapeObj =<\/li>\n
    360. (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*pNode->nShpCount);<\/li>\n
    361. }<\/li>\n
    362. else<\/li>\n
    363. {<\/li>\n
    364. pNode->nShpCount += 1;<\/li>\n
    365. pNode->pShapeObj =<\/li>\n
    366. (SHPMBRInfo *)realloc(pNode->pShapeObj,sizeof(SHPMBRInfo)*pNode->nShpCount);<\/li>\n
    367. }<\/li>\n
    368. SHPMBRInfo pShpInfo;<\/li>\n
    369. pShpInfo.Box = itemRect;<\/li>\n
    370. pShpInfo.nID = key;<\/li>\n
    371. memcpy(pNode->pShapeObj+pNode->nShpCount-1,&pShpInfo,sizeof(SHPMBRInfo));<\/li>\n
    372. }<\/li>\n
    373. }<\/li>\n
    374. void InsertQuad2(long key,MapRect &itemRect,QuadNode* pNode)<\/li>\n
    375. {<\/li>\n
    376. QuadNode *node = pNode; \/\/\u4fdd\u7559\u6839\u8282\u70b9\u526f\u672c<\/i><\/li>\n
    377. SHPMBRInfo pShpInfo;<\/li>\n
    378. \/\/\u8282\u70b9\u6709\u5b69\u5b50<\/i><\/li>\n
    379. if (0 < node->nChildCount)<\/li>\n
    380. {<\/li>\n
    381. for (int i = 0; i < 4; i ++)<\/li>\n
    382. {<\/li>\n
    383. \/\/\u5982\u679c\u5305\u542b\u6216\u76f8\u4ea4\uff0c\u5219\u5c06\u8282\u70b9\u63d2\u5165\u5230\u6b64\u8282\u70b9<\/i><\/li>\n
    384. if (node->children[i]->Box.Contains(itemRect)<\/li>\n
    385. || node->children[i]->Box.Intersects(itemRect))<\/li>\n
    386. {<\/li>\n
    387. \/\/node = node->children[i];<\/i><\/li>\n
    388. Insert(key,itemRect,node->children[i]);<\/li>\n
    389. }<\/li>\n
    390. }<\/li>\n
    391. }<\/li>\n
    392. \/\/\u5982\u679c\u5f53\u524d\u8282\u70b9\u5b58\u5728\u4e00\u4e2a\u5b50\u8282\u70b9\u65f6<\/i><\/li>\n
    393. else if (0 == node->nChildCount)<\/li>\n
    394. {<\/li>\n
    395. MapRect boxs[4];<\/li>\n
    396. node->Box.Split(boxs,boxs+1,boxs+2,boxs+3);<\/li>\n
    397. int cnt = -1;<\/li>\n
    398. for (int i = 0; i < 4; i ++)<\/li>\n
    399. {<\/li>\n
    400. \/\/\u5982\u679c\u5305\u542b\u6216\u76f8\u4ea4\uff0c\u5219\u5c06\u8282\u70b9\u63d2\u5165\u5230\u6b64\u8282\u70b9<\/i><\/li>\n
    401. if (boxs[i].Contains(itemRect))<\/li>\n
    402. {<\/li>\n
    403. cnt = i;<\/li>\n
    404. }<\/li>\n
    405. }<\/li>\n
    406. \/\/\u5982\u679c\u6709\u4e00\u4e2a\u77e9\u5f62\u5305\u542b\u6b64\u5bf9\u8c61\uff0c\u5219\u521b\u5efa\u56db\u4e2a\u5b69\u5b50\u8282\u70b9<\/i><\/li>\n
    407. if (cnt > -1)<\/li>\n
    408. {<\/li>\n
    409. for (int i = 0; i < 4; i ++)<\/li>\n
    410. {<\/li>\n
    411. \/\/\u521b\u5efa\u56db\u4e2a\u8282\u70b9\u5e76\u63d2\u5165\u76f8\u5e94\u7684MBR<\/i><\/li>\n
    412. node->children[i] = InitQuadNode();<\/li>\n
    413. node->children[i]->Box = boxs[i];<\/li>\n
    414. }<\/li>\n
    415. node->nChildCount = 4;<\/li>\n
    416. InsertQuad2(key,itemRect,node->children[cnt]); \/\/\u9012\u5f52<\/i><\/li>\n
    417. }<\/li>\n
    418. \/\/\u5982\u679c\u90fd\u4e0d\u5305\u542b\uff0c\u5219\u76f4\u63a5\u5c06\u5bf9\u8c61\u63d2\u5165\u6b64\u8282\u70b9<\/i><\/li>\n
    419. if (cnt == -1)<\/li>\n
    420. {<\/li>\n
    421. if (node->nShpCount == 0) \/\/\u5982\u679c\u4e4b\u524d\u6ca1\u6709\u8282\u70b9<\/i><\/li>\n
    422. {<\/li>\n
    423. node->nShpCount += 1;<\/li>\n
    424. node->pShapeObj =<\/li>\n
    425. (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);<\/li>\n
    426. }<\/li>\n
    427. else if (node->nShpCount > 0)<\/li>\n
    428. {<\/li>\n
    429. node->nShpCount += 1;<\/li>\n
    430. node->pShapeObj =<\/li>\n
    431. (SHPMBRInfo *)realloc(node->pShapeObj,<\/li>\n
    432. sizeof(SHPMBRInfo)*node->nShpCount);<\/li>\n
    433. }<\/li>\n
    434. pShpInfo.Box = itemRect;<\/li>\n
    435. pShpInfo.nID = key;<\/li>\n
    436. memcpy(node->pShapeObj,<\/li>\n
    437. &pShpInfo,sizeof(SHPMBRInfo));<\/li>\n
    438. }<\/li>\n
    439. }<\/li>\n
    440. \/\/\u5f53\u524d\u8282\u70b9\u6ca1\u6709\u7a7a\u95f4\u5bf9\u8c61<\/i><\/li>\n
    441. \/*else if (0 == node->nShpCount)<\/i><\/li>\n
    442. {<\/i><\/li>\n
    443. node->nShpCount += 1;<\/i><\/li>\n
    444. node->pShapeObj = <\/i><\/li>\n
    445. (SHPMBRInfo*)malloc(sizeof(SHPMBRInfo)*node->nShpCount);<\/i><\/li>\n
    446. pShpInfo.Box = itemRect;<\/i><\/li>\n
    447. pShpInfo.nID = key;<\/i><\/li>\n
    448. memcpy(node->pShapeObj,&pShpInfo,sizeof(SHPMBRInfo));<\/i><\/li>\n
    449. }*\/<\/i><\/li>\n
    450. }<\/li>\n
    451. bool IsQuadLeaf(QuadNode* node)<\/li>\n
    452. {<\/li>\n
    453. if (NULL == node)<\/li>\n
    454. {<\/li>\n
    455. return 1;<\/li>\n
    456. }<\/li>\n
    457. for (int i = 0; i < 4; i ++)<\/li>\n
    458. {<\/li>\n
    459. if (node->children[i] != NULL)<\/li>\n
    460. {<\/li>\n
    461. return 0;<\/li>\n
    462. }<\/li>\n
    463. }<\/li>\n
    464. return 1;<\/li>\n
    465. }<\/li>\n
    466. bool DelFalseNode(QuadNode* node)<\/li>\n
    467. {<\/li>\n
    468. \/\/\u5982\u679c\u6ca1\u6709\u5b50\u8282\u70b9\u4e14\u6ca1\u6709\u8981\u7d20<\/i><\/li>\n
    469. if (node->nChildCount ==0 && node->nShpCount == 0)<\/li>\n
    470. {<\/li>\n
    471. ReleaseQuadTree(&node);<\/li>\n
    472. }<\/li>\n
    473. \/\/\u5982\u679c\u6709\u5b50\u8282\u70b9<\/i><\/li>\n
    474. else if (node->nChildCount > 0)<\/li>\n
    475. {<\/li>\n
    476. for (int i = 0; i < 4; i ++)<\/li>\n
    477. {<\/li>\n
    478. DelFalseNode(node->children[i]);<\/li>\n
    479. }<\/li>\n
    480. }<\/li>\n
    481. return 1;<\/li>\n
    482. }<\/li>\n
    483. void TraversalQuadTree(QuadNode* quadTree,vector<int>& resVec)<\/li>\n
    484. {<\/li>\n
    485. QuadNode *node = quadTree;<\/li>\n
    486. int i = 0;<\/li>\n
    487. if (NULL != node)<\/li>\n
    488. {<\/li>\n
    489. \/\/\u5c06\u672c\u8282\u70b9\u4e2d\u7684\u7a7a\u95f4\u5bf9\u8c61\u5b58\u50a8\u6570\u7ec4\u4e2d<\/i><\/li>\n
    490. for (i = 0; i < node->nShpCount; i ++)<\/li>\n
    491. {<\/li>\n
    492. resVec.push_back((node->pShapeObj+i)->nID);<\/li>\n
    493. }<\/li>\n
    494. \/\/\u904d\u5386\u5b69\u5b50\u8282\u70b9<\/i><\/li>\n
    495. for (i = 0; i < node->nChildCount; i ++)<\/li>\n
    496. {<\/li>\n
    497. if (node->children[i] != NULL)<\/li>\n
    498. {<\/li>\n
    499. TraversalQuadTree(node->children[i],resVec);<\/li>\n
    500. }<\/li>\n
    501. }<\/li>\n
    502. }<\/li>\n
    503. }<\/li>\n
    504. void TraversalQuadTree(QuadNode* quadTree,vector<QuadNode*>& arrNode)<\/li>\n
    505. {<\/li>\n
    506. deque<QuadNode*> nodeQueue;<\/li>\n
    507. if (quadTree != NULL)<\/li>\n
    508. {<\/li>\n
    509. nodeQueue.push_back(quadTree);<\/li>\n
    510. while (!nodeQueue.empty())<\/li>\n
    511. {<\/li>\n
    512. QuadNode* queueHead = nodeQueue.at(0); \/\/\u53d6\u961f\u5217\u5934\u7ed3\u70b9<\/i><\/li>\n
    513. arrNode.push_back(queueHead);<\/li>\n
    514. nodeQueue.pop_front();<\/li>\n
    515. for (int i = 0; i < 4; i ++)<\/li>\n
    516. {<\/li>\n
    517. if (queueHead->children[i] != NULL)<\/li>\n
    518. {<\/li>\n
    519. nodeQueue.push_back(queueHead->children[i]);<\/li>\n
    520. }<\/li>\n
    521. }<\/li>\n
    522. }<\/li>\n
    523. }<\/li>\n
    524. }<\/li>\n
    525. void ReleaseQuadTree(QuadNode** quadTree)<\/li>\n
    526. {<\/li>\n
    527. int i = 0;<\/li>\n
    528. QuadNode* node = *quadTree;<\/li>\n
    529. if (NULL == node)<\/li>\n
    530. {<\/li>\n
    531. return;<\/li>\n
    532. }<\/li>\n
    533. else<\/li>\n
    534. {<\/li>\n
    535. for (i = 0; i < 4; i ++)<\/li>\n
    536. {<\/li>\n
    537. ReleaseQuadTree(&node->children[i]);<\/li>\n
    538. }<\/li>\n
    539. free(node);<\/li>\n
    540. node = NULL;<\/li>\n
    541. }<\/li>\n
    542. node = NULL;<\/li>\n
    543. }<\/li>\n
    544. long CalByteQuadTree(QuadNode* quadTree,long& nSize)<\/li>\n
    545. {<\/li>\n
    546. if (quadTree != NULL)<\/li>\n
    547. {<\/li>\n
    548. nSize += sizeof(QuadNode)+quadTree->nChildCount*sizeof(SHPMBRInfo);<\/li>\n
    549. for (int i = 0; i < 4; i ++)<\/li>\n
    550. {<\/li>\n
    551. if (quadTree->children[i] != NULL)<\/li>\n
    552. {<\/li>\n
    553. nSize += CalByteQuadTree(quadTree->children[i],nSize);<\/li>\n
    554. }<\/li>\n
    555. }<\/li>\n
    556. }<\/li>\n
    557. return 1;<\/li>\n
    558. }<\/li>\n<\/ol>\n

      \n\u4ee3\u7801\u6709\u70b9\u957f\uff0c\u6709\u9700\u8981\u7684\u670b\u53cb\u53ef\u4ee5\u501f\u9274\u5e76\u81ea\u5df1\u4f18\u5316\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"

      \u539f\u6587\u5730\u5740   \u5468\u65ed\u5149\u00a02013<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[],"tags":[119],"class_list":["post-5011","post","type-post","status-publish","format-standard","hentry","tag-03-"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/5011","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=5011"}],"version-history":[{"count":0,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/5011\/revisions"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=5011"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=5011"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=5011"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}