快速点查找和视线遍历算法

Question

我正在制作一个小型库，用于消耗地理信息系统（GIS）数据，并允许快速进行要素点、附近点和视线查询。这些数据中的大部分将包含具有大量顶点的大面积要素。

R树变种可能可行，但我想知道它们在面积查询中的表现如何。我还怀疑视线查询会破坏大部分性能增益。

具有可变大小子代的四叉树是下一个浮现在脑海中的内容。那将允许在各个子级之间建立链接，或许可以加速视线查询。

Kd树也出现在我的脑海中，尽管再次，视线查询可能会有问题。

因此，问题是，你会推荐哪种算法？

- mousebird

Answer 1

这不就是射线追踪器使用八叉树的情况吗？

- Rafe

---

是的，这属于我正在研究的空间细分算法类别。八叉树适用于三维空间，而等效的四叉树适用于二维空间。还有一类算法可以更好地组织某些问题类别的二维（或N维）数据。我正在考虑这些算法。 - mousebird

如果有人遇到这个问题，可以使用R-Tree。它们相当不错。我认为以后我会用它们来替换四叉树和调整网格。 - mousebird