samdivine / simulate_a_pattern

模拟一个物理现象，用途不明

这玩意儿就是用来模拟一个物理现象的

该现象可以简单解释为按照一定的规则从若干个点生成几棵不会交叉的树，这些树从图论角度上来讲是严格的二叉树。

总共实现了两个版本的四叉树：一个是预先生成的四叉树，另一个是动态生成的四叉树

预先生成的四叉树会生成大量用不到的叶子节点，受限于内存以及Python自身的一些限制，在我的测试中最大深度只能取到10，在点数规模进一步放大后，会遇到一些性能瓶颈

动态生成的四叉树会在插入点的时候才生成对应的叶子节点，由于在实际应用中插入的点的空间位置比较接近，因此总共生成的叶子节点数量较少，可以选择更深的深度。我在测试过程中最多试过400,000个点，用时3分钟左右生成，而使用预生成二叉树的版本受限于最大深度，应对100,000点的场景就力有未逮，半个小时后还没出结果……

以下以实际生成 20000 个点为目标来对比效率（某台式机上）

使用预生成四叉树版本的效率

初始化时间： 8.74 s

生成所有点和线的时间： 17.25 s

画圆时间： 23.96 s

画线时间： 161.43 s

画图时间： 185.39 s

不使用四叉树版本的效率

初始化时间： 0 s

生成所有点和线时间： 419.76 s

画圆时间：25.86 s

画线时间：157.07 s

画图时间：182.93 s

使用动态生成四叉树版本的效率（生成 100,000 个点）

初始化时间： 0 s

生成所有点和线的时间： 40.86 s

画圆时间： 878.72 s

致谢

感谢psfile项目提供简便的postscript文件写支持

感谢John M. Zelle编写graphics.py为python 2.7提供简便的调用Tkinter画图的功能