QuadTree c++实验结果
1. 实验数据以及实验环境
数据集一：City of Oldenburg (OL) Road Network
结点个数：6105
数据集二：Road Network of North America (NA)
结点个数：175813
实验环境：windows7，VS2012
2. 实验结果
表2-1 实验结果
|
数据集 |
结点个数 |
QuadTree |
||||
|
结点数 |
树高 |
最大宽度 |
创建(ms) |
查询(ms) |
||
|
1 |
6105 |
19773 |
14 |
6104 |
194 |
16 |
|
2 |
175813 |
800709 |
14 |
199048 |
6814 |
640 |
3．实验分析
数据一与数据二区域均为(0.0, 0.0)~(10000.0, 10000.0)，因此数据集二中的数据比数据一密集的多。C++中使用的float最多有7位有效数字，因此当点密集时将不能够继续划分（即使double也不能解决）。
刚开始建立的QuadTree直到每个QuadTree结点只包含一个数据或所包含的区域没有数据，用数据集一测试没有问题，且可以准确查到每一个存在的节点。但对于数据集二却因没有足够的内存空间而不能够将这样的QuadTree创建（内存消耗急剧增加，创建850多万个结点时失败）。为了进一步减少空间消耗，将stack容器替换成自己写的QuadTreeNodeStack，但当结点个数达到1700多万时崩溃。
针对以上问题，修改后的QuadTree的叶子节点面积小于1.0*1.0时即使包含多个数据也不再划分，问题得到解决。
4. 实验心得
4.1存在的问题
(1) 刚开始写代码时想到哪里写到哪里，结果忙了半天却只能重新写。
(2) 对问题考虑的步骤全。比如在数据集一上能够测试，但数据集二却完全不能用，只能花时间来修改数据结构。
4.2总结
动手写代码之前一定要：
(1) 认真分析数据结构的特点，尤其特殊情况；
(2) 设计好每种数据类型，包括属性、方法等；
(3) 认真了解使用的各种库函数。
5. 源码下载：
代码1：http://download.csdn.net/detail/woniu317/6931519
代码2：http://download.csdn.net/detail/woniu317/6934665
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
