我在虛擬2D表面上有任意數量的點。我在同一表面上也有一個網格，沿X和Y方向有規律的點。我的任務是將每個點映射到最近的網格點。將2D點映射到固定格柵
直到網格點數量不足時，代碼已經足夠直接了。我一直在開發的代碼找到最接近的網格點，如果當前點的距離將更短，則顯示已經映射的點。
然後，我添加了第二步，將每個映射點與另一個點進行比較，如果將映射與另一個點交換產生兩個點的總映射距離的較小總和，則將它們交換。
這最後一步似乎很重要，因爲它減少了交叉地圖線的數量。 （這將用於將一個板上的點映射到另一個板上的網格上，其中連接這兩個的引腳和不會交叉的線似乎具有較高的引腳不會接觸的機會。）
問題：
可以在我的思想的人評論說，如果上面是真正優化了圖像後，（即映射分 - 總 - 將具有最小總距離），然後沒有一條線是交叉的？
並且有誰見過任何現有的算法來幫助解決這個問題。我搜查了但沒有任何結果。
的問題可以接近作爲Assignment Problem的變型，用「代理人」與它們之間的距離是所述方格和點是所述「任務」，（反之亦然）是該代理 - 任務組合的「成本」。你可以用Hungarian algorithm來解決。
要處理比點更多的網格正方形的事實，請爲您想要考慮的可能的網格正方形找到邊界框，並添加與所有網格正方形相關的成本爲0的虛擬點。匈牙利的算法是O（n ），也許你的方法已經足夠好了。
參見：
How to find the optimal mapping between two sets?
How to optimize assignment of tasks to agents with these constraints?
如果我正確理解你的主要關注點，最大限度地減少線段的總長度，你用不找最好的映射，它是在你的圖像清晰的算法。例如當兩條線段互相交叉時，簡單的數學表示如果您重新排列它們的端點以使它們不交叉，它會提供更好的總和。您可以使用這種簡單的方法（重新排列交叉項目）以更好地逼近最佳值，您應該應用交換以獲得更多的迭代次數。
在下面的圖片中，您可以看到爲什麼交叉的長度比非交叉的長（第一個問題），以及爲什麼交換一次仍然存在交叉邊緣（第二個問題和wrt評論），實際上我只畫了一個樣本人們可能需要多次交換來獲得非交叉結果。
這是一個啓發式算法，當然不是最優的，但我希望實現起來非常好，高效和簡單。
我遇到的問題是我做了第二遍，如果兩個點交換它們的映射，我會比較兩個已映射點的總和與相同的總和。我用每一點對所有其他點進行此操作，然後如果交換了兩個點，我將這兩點再次與其他所有點進行比較，以便進行可能的交換。但結果似乎並不理想。仍然需要更多的理解這裏需要什麼。 –
@Jonathan，首先如果你想要一個P時間算法，那麼其他答案暗示匈牙利算法的作用，但我認爲它在你的情況下是緩慢的。但是，如果您想要優質且快速的啓發式算法，請爲每個交叉段運行交換算法。這可能會導致新的交叉段，但總長度較小。你應該做這個交換，以合理的迭代次數穿過段。不只是2次。這取決於您輸入的大小。例如。如果您的輸入尺寸爲n，則執行n次。我想它比匈牙利語更快，而且非常接近最佳狀態。 –
順便說一句，這個問題的任何啓發式算法的好處的一個措施就像我說：計算你有多少個交叉點。我幾乎可以肯定，通過n次交換，你會得到一個非常好的結果。請注意，每次該過程可能會解決O（n），交叉。 –
我的回答，答案提供兩個問題，但經過長時間的討論，目前還不清楚什麼是OP的目標。例如。如果他知道第一個問題的答案，那他爲什麼問這個問題？或者例如我解釋說，他有一個很好的啓發，他應該通過去除交叉和數學的多個過程，我顯示爲什麼這是必需的，爲什麼它的工作原理。在Q中，他寫道，他只做了一次改進。在我寫這篇文章的評論中，他寫下了他不明白爲什麼需要多次通行證，在我把他說他知道的照片後。對不起，既不是真正的Q也不是真正的OP。 –