存储连续多边形的最佳数据结构是什么?

6

很抱歉,我对这个问题的措辞非常困扰。

我卡在了应该使用哪种数据结构(或数据结构组合)来存储彼此相邻的多边形排列上(就像任何真实世界的地图一样)。

我应该澄清:我的意思是让一个点以固定速度穿过这些多边形的地图(景观)。整个地图都覆盖在多边形上-没有空间未分类;地图中的每个点都属于某个多边形。这意味着所有多边形都与另一个多边形或地图边缘接壤。地图是有界的,但理想情况下,地图的大小或所代表的多边形数量不应该影响结果。每个多边形都有一个名称(这很重要,因为每个点现在至少属于两个命名的多边形)。穿过地图的点应始终知道它所在的多边形的名称,并且当它从一个多边形穿越到另一个多边形时,该点还应该被通知。(如果需要任何其他澄清,请评论。)

有没有可接受的方法来做到这一点?

--编辑--

多边形是固定的。所有点和边缘都需要预先硬编码。点和边缘永远不会不可预测或随机更改(如果它们发生任何更改,将是对偶然的固定事件的响应)。


1
多边形提前固定了吗?地图有多大?多边形可以改变吗?此外,多边形一定是凸的吗? - templatetypedef
如果是第一人称的景观,您可能想看看类似于这种方法的东西。 - dwn
它可以被视为一个多边形的二维地图。它也不需要以图形方式表示。点只需要知道其X和Y位置变量告诉它相对于存储的多边形在哪里即可。尽管图形化表示有助于我作为人类理解模拟,但是就点而言,这应该并不必要。 - 13rave
2个回答

3
这个技术术语叫做平面直线图,一个合适的表示方法是双连通边列表(DCEL)。
你的数据结构要求之一似乎是能够执行(快速)点定位查询。(这个点属于哪个多边形?)有经典的解决方案,其中可以推荐梯形分解
我不知道“边界”查询的合适解决方案,即找到与(可能)线性轨迹的交点。您可能可以从点定位问题中进行调整,但这可能会很棘手。
无论如何,如果您的多边形具有合理数量的顶点,则通过依次尝试所有边来找到与给定直线的所有交点并不是什么大问题。使用DCEL表示,当您离开一个多边形时,您知道您进入了哪一个。
如果我是你,我会从DCEL结构、点在多边形内算法和线多边形交点算法(本质上是相同的)开始。

1
构建 2D线段树,其中每个2D区间对应一个多边形的边界框,值类型对应于多边形本身(其边缘列表)。
在代理从p1移动到p2后,针对线段树运行窗口查询:搜索与由p1和p2定义的矩形相交/包含的所有2D区间(边界框)。
对于这些边界框中的每个多边形,请检查它是否包含p2。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接