gpt4 book ai didi

data-structures - 对于线段数据库,查找与矩形相交的所有线段

转载 作者:行者123 更新时间:2023-12-04 04:53:06 24 4
gpt4 key购买 nike

给定大量线段,您如何有效地找到与矩形相交的所有线段?一个典型的应用是 GIS 数据库,查找当前视野范围内的所有道路。对于点,这可以通过将点存储在 KD 树中来有效地完成,但是线段的相应数据结构是什么?

如果算法考虑到线宽,则是一个奖励,但零宽度算法完全可以。

最佳答案

您可以使用线段树,就像 CGAL 中存在的一样:
dD Range and Segment Trees .该数据结构可用于所有维度,包括维度 2。

关于data-structures - 对于线段数据库,查找与矩形相交的所有线段,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17133213/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com