如何检测对象是否位于两点之间

Question

目前我正在研究最小走廊长度算法，部分设置涉及到问题中所有相邻点的列表。目前我有两个数组：一个在x坐标上用相邻点排序，另一个在y坐标上用点排序。另外，通过简单地查看两个列表中的附近点，我发现邻接点，如果点具有相同的y（在列表中按x相邻排序），则它们位于同一行上。同样，如果他们有相同的x（在y列表中）谎言在同一行上。

例如，假设我们有以下的房间：

然后用X-相邻点列表将按照以下顺序几点：{V1，V2，V3，V4，V5， ... v21，v22}（它们保持与它们标记的顺序相同） 此外，具有y个相邻点的列表将为：{v22，v16，v14，v9，v4，v13，v8，v3，v21 ，... v5，v1}（基本上是y = x上图的反映）

如前所述，通过查看列表中的附近点找到相邻点。该工程罚款最高分，但是它失败以下边缘情况：

为X相邻的列表将有{V1，V2，...... V6，V7 ... V11，V12 }并且我的算法会将v6和v7检测为相邻点。 如何检测到这两点之间有空间？请注意，我有一组矩形和顶点也可用于我。 在此先感谢。

Answer 1

我会建议放弃你的基于位置的方法，因为没有办法告诉V6和V7在您的最后一个例子是否为相邻（即连接）仅在他们的位置，并根据。相反，请指定graph指示哪些点连接到哪些其他点：这些点将成为图的顶点，并且您在每对相邻/连接的顶点之间添加一条边。

构建图表，你可以试试这个算法（只是把我的头顶部）：

1. 创建具有给定顶点的图和无毛边
2. 组顶点（分）他们的x坐标。创建顶点映射到组，或者用其他方式查找给定顶点所在的组。
3. 对于每个组，使用该组中的顶点创建一个disjoint set data structure。
4. 迭代通过矩形的所有垂直边缘，并且对于每个边缘，在那个边缘的端部对应于所述两个顶点子集执行联合。
5. 遍历组，并为每个组遍历其子集。对于每个子集，首先按y坐标对该子集中的顶点进行排序，然后在连续顶点对之间添加边。

然后重复步骤2-5，其中x的作用和y坐标交换（以及使用水平边缘，而不是垂直边缘）。

自然，这依赖于假定所有边缘（线）或者是水平的或垂直的。