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

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)]})

像这样。 (仍然不知道 edges 列表是否更好？)

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

我决定将每个点(使用 x 坐标排序)存储在排序列表(使用二等分)中。获取板坯。但是，我无法找到一种方法来确定板如何与区域边缘相交，或者如何如图所示划分板。其实我确实找到了一种方法，但我觉得它不可行。我可以检查从平板左侧开始到右侧结束的边缘。这意味着边缘正在穿过平板。这很好，但是要实现这一点，每次给出新节点并且区域增加时我都必须检查几乎一半的顶点。所以这种方法对我来说听起来很失败。还有一个问题是知道板中的区域属于哪个区域。鉴于我们这样做是为了避免逐一检查所有区域以提高速度。

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

注意1:我不确定数据结构，我应该为区域做一个结构吗？还是点？或边缘？或者我需要一个用于创建搜索树的结构吗？我必须在此结构中存储什么？

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

提前致谢。

Answer 1

我建议您也只使用您的顶点作为引用。使用边列表来表示图形，并为每条边分配一个左右入射区域。现在在你的平板分解中使用这些边。一旦你找到你的板和你的板部分你也知道它的区域作为你的点引用附近的两个边缘。