如何檢測對象是否位於兩點之間

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座標交換（以及使用水平邊緣，而不是垂直邊緣）。

自然，這依賴於假定所有邊緣（線）或者是水平的或垂直的。