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

Question

对不起，我在措辞这个问题时遇到了很多麻烦。

我被困在我应该使用什么数据结构(或数据结构的组合)来存储相互接壤的多边形排列(就像任何现实世界的 map 一样)。

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

有没有公​​认的方法来做到这一点？

- 编辑 -

多边形是固定的。所有点和边都需要预先硬编码。点和边永远不会发生不可预测或随机的变化(如果它们发生变化，那将是对不常见的固定事件的响应)。

Answer 1

描述这种情况的技术术语是 planar straight-line graph , 一个合适的表示是 doubly connected edge list (直流电)。

您的数据结构的要求之一似乎是执行(快速)点位置查询的可能性。 (这个点属于哪个多边形？)有经典的解决方案，其中可以推荐trapezoidal decomposition .

我不知道“边界”查询的合适解决方案，即找到具有(可能)线性轨迹的交叉点。您可能可以从点定位问题中进行调整，但这肯定会很棘手。

无论如何，如果您的多边形具有合理数量的顶点，则通过依次尝试所有边来找到与给定直线的所有交点并不是什么大问题。使用 DCEL 表示，当你离开一个多边形时，你知道你进入了哪一个。

如果我是你，我会从 DCEL 结构开始，即 point-in-polygon算法和线-多边形相交算法(本质上是相同的)。