对于线段数据库，查找与矩形相交的所有线段
提问于 2013-06-16 12:13:45
给定一大组线段，如何有效地找到与矩形相交的所有线段？典型的应用程序是GIS数据库，查找当前视野内的所有道路。对于点，这可以通过将点存储在KD树中来有效地完成，但是线段的相应数据结构是什么？
如果算法考虑了线宽，这是一个额外的好处，但是零宽度算法是完全可以的。
回答 3
Stack Overflow用户
发布于 2013-06-16 16:22:06
您可以使用段树，就像CGAL：dD Range and Segment Trees中存在的那样。该数据结构在所有维度中都可用，包括维度2。
Stack Overflow用户
发布于 2013-06-26 19:34:33
将矩形视为一组4条线段。现在，您就有了一组n+4线段。在线段上应用扫描线算法。仅当两条直线段来自不同的集合时才执行交点。即一段来自矩形，另一段来自数据库。此外，您可以从矩形的第一个顶点开始扫描线过程，并在所有矩形线完成处理后结束。
您还可以搜索空间散列和线栅格化(用于用线数据填充空间单元格)。这可能会更快。
Stack Overflow用户
发布于 2013-07-11 20:43:43
另一种可能的数据结构是R-tree。特别是priority R-tree将为您的运行时间提供有保证的上限，但启发式变体在实践中可能更快。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17133213
复制相关文章
点击加载更多
腾讯云开发者
