我正在处理一个编程挑战，因为我需要找到给定点所属的区域。这里有一些方法可以解决这个问题。
所以我决定使用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：我知道如何找到该点所在的板块。我也知道如何在平板内使用二进制搜索找到点。我缺乏更多的概念知识，因此缺乏经验。就像首先如何表示区域一样。
提前致谢。