点定位算法的正确数据结构

Question

我正在处理一个编程挑战，因为我需要找到给定点所属的区域。这里有一些解决这个问题的方法。在

Point Location

所以我决定使用slab分解，它足够快，更容易实现，而且空间对我来说不是什么问题。然而，我有麻烦从哪里开始。这是加州大学圣巴巴拉分校（UC Santa Barbara）制作的pdf文件中的板分解示例。在

我将几何图形存储在节点字典中，就像无向图（使用坐标）。在

defaultdict(<type 'list'>, {(4.0, 5.0): [(1.0, 2.0), (2.0, 3.0), (3.0, 5.0)],
 (1.0, 2.0): [(2.0, 3.0), (2.0, 4.0), (3.0, 5.0), (4.0, 5.0)],
 (2.0, 3.0): [(1.0, 2.0), (2.0, 4.0), (4.0, 5.0)],
 (2.0, 4.0): [(1.0, 2.0), (2.0, 3.0), (3.0, 5.0)],
 (3.0, 5.0): [(1.0, 2.0), (2.0, 4.0), (4.0, 5.0)]})

像这样。（仍然不知道边列表是否更好？）在

现在我知道如何解决这个问题了，但是很难决定采用哪种方式来实现，因为输入将是一个非常复杂的几何形状，并且找到点将耗费大量的cpu资源。在

我决定将每个点（使用x坐标排序）存储在一个排序列表中（使用对分）。获取板坯。但是，我找不到一个方法来找到板如何与区域边缘相交，或者如何如图所示分割板。事实上，我确实找到了一个方法，但我觉得不可行。我可以检查从板的左边开始到右边结束的边缘。也就是说边缘穿过了石板。这是很好的，但是为了完成这一点，我必须检查几乎一半的顶点，每次一个新的节点和区域增加。所以这个方法对我来说是个失败。还有一个问题是要知道板中的区域属于哪个区域。考虑到我们这样做是为了避免逐个检查所有区域以提高速度。在

如果你能给我一些关于这个主题的想法，我不需要任何代码。我只需要有经验的用户的建议。我被卡住了，因为我不知道如何实现它，我不想以错误的方式开始重写它。（我可以向你保证这不是家庭作业。）

注1:我无法确定数据结构，是否应为区域创建一个结构？，还是为了积分？还是边缘？或者我需要一个结构来创建一个搜索树？我要在这个结构中存储什么？在

注2:我知道如何找到点所在的板。我也知道如何在板子里用二进制搜索找到点。我缺乏更多的感性知识，因此缺乏经验。比如首先如何表示区域。在

提前谢谢。在

Answer 1

我建议使用你的顶点也只参考。使用边列表来表示图形，并为每个边指定一个左右入射区域。现在在板分解中使用这些边。一旦找到板和板零件，就可以知道它的区域，因为靠近点的两条边都指向它。在

Answer 2

如果您知道您的数据将被多次用于定位多个点，那么预处理原始平面图并将其分解为板是有意义的。然后，您所面临的数据结构问题将简化为板表示问题。在

什么是石板？它实际上是一个一维的边序列。因此，您将把原始问题简化为两个二进制搜索-第一个在slab数组中，第二个在edge数组中。边数组中的二进制搜索应该稍微修改一下-你需要找到一对边，从上到下（我指的是你的图片）尽可能靠近测试点。在

当然，您需要在边数组的某个地方存储对原始面标签的引用。在