回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我正在处理一个编程挑战,因为我需要找到给定点所属的区域。这里有一些解决这个问题的方法。在</p>
<p><a href="https://en.wikipedia.org/wiki/Point_location" rel="nofollow noreferrer">Point Location</a></p>
<p>所以我决定使用slab分解,它足够快,更容易实现,而且空间对我来说不是什么问题。然而,我有麻烦从哪里开始。这是加州大学圣巴巴拉分校(UC Santa Barbara)制作的pdf文件中的板分解示例。在</p>
<p><a href="https://i.stack.imgur.com/hTJzi.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/hTJzi.jpg" alt="Slab decomposition"/></a></p>
<p>我将几何图形存储在节点字典中,就像无向图(使用坐标)。在</p>
<pre><code>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)]})
</code></pre>
<p>像这样。(仍然不知道<strong>边</strong>列表是否更好?)在</p>
<p>现在我知道如何解决这个问题了,但是很难决定采用哪种方式来实现,因为输入将是一个非常复杂的几何形状,并且找到点将耗费大量的cpu资源。在</p>
<p>我决定将每个点(使用x坐标排序)存储在一个排序列表中(使用对分)。获取板坯。但是,我找不到一个方法来找到板如何与区域边缘相交,或者如何如图所示分割板。事实上,我确实找到了一个方法,但我觉得不可行。我可以检查从板的左边开始到右边结束的边缘。也就是说边缘穿过了石板。这是很好的,但是为了完成这一点,我必须检查几乎一半的顶点,每次一个新的节点和区域增加。所以这个方法对我来说是个失败。还有一个问题是要知道板中的区域属于哪个区域。考虑到我们这样做是为了避免逐个检查所有区域以提高速度。在</p>
<p>如果你能给我一些关于这个主题的想法,我不需要任何代码。我只需要有经验的用户的建议。我被卡住了,因为我不知道如何实现它,我不想以错误的方式开始重写它。(我可以向你保证这不是家庭作业。)</p>
<p><strong>注1:</strong>我无法确定数据结构,是否应为区域创建一个结构?,还是为了积分?还是边缘?或者我需要一个结构来创建一个搜索树?我要在这个结构中存储什么?在</p>
<p><strong>注2:</strong>我知道如何找到点所在的板。我也知道如何在板子里用二进制搜索找到点。我缺乏更多的感性知识,因此缺乏经验。比如首先如何表示区域。在</p>
<p>提前谢谢。在</p>