存储连续多边形的最佳数据结构？

Question

对不起,我在写这个问题时遇到了很多麻烦.

我坚持使用什么数据结构(或数据结构的组合)来存储彼此接壤的多边形排列(就像任何真实世界的地图一样).

我应该澄清一下:我的意思是通过这些多边形的地图(风景)以固定的速度移动一个点.整个景观都被多边形所覆盖 - 没有空间被分类; 地图中的每个点都属于某个多边形.这意味着所有多边形在所有边上都与另一个多边形或地图边缘相邻.地图是有界的,但理想情况下,地图的大小或表示多少多边形无关紧要.每个多边形都有一个名称(这很重要,因为每个点现在属于至少两个命名多边形).在地图中移动的点应始终知道它所在的多边形的名称,并且每当它从一个多边形跨越到另一个多边形的边界时,也应该通知该点.(如果需要任何其他说明,请发表评论.)

有没有可以接受的方法呢？

- 编辑 -

多边形是固定的.所有点和边缘都需要事先进行硬编码.点和边缘永远不会无法预测或随机变化(如果它们完全改变,它将响应不常见的固定事件).

Answer 1

构建一个 2D 线段树，其中每个 2D 间隔对应于多边形的边界框，值类型对应于多边形本身（其边的列表）。

代理从 p1 移动到 p2 后，对线段树运行窗口查询：搜索与 p1 和 p2 定义的矩形中包含的 / 相交的所有 2D 间隔（边界框）。

对于这些边界框中的每个多边形，检查它是否包含 p2。