22
我在2D圖像中隨機選擇了一組像素。對於圖像中的每個其他像素，我需要找出集合K中的哪個像素最接近它（使用標準的sqrt（dx^2 + dy^2）度量距離）。我知道每個像素可能有多個解決方案。顯然，它可以通過強制對抗集合中的每個像素來完成，但是我寧願避免這一點，因爲它效率不高。任何其他好建議？給定點的最近點
乾杯。
Q
給定點的最近點
A
回答
31
不要忘記，你不需要打擾平方根。
如果你只是想找到最近的一個（而不是實際距離），只需使用dx^2 + dy^2，它會給你每個項目的距離平方，這是一樣有用。
如果你沒有數據結構包裝這個像素列表，你只需要對它們進行測試。
如果您有一定的靈活性，有許多減少工作量的好方法。製作一個Quadtree，或保留像素的排序列表（按x排序並按y排序），以便更快地縮小搜索範圍。
5
這被稱爲最近鄰搜索。唐納德克努特稱之爲郵局問題。
有許多解決方案：線性搜索，局部敏感哈希，矢量近似文件和空間分區。
谷歌搜索這些應該幫助。
1
取決於此圖形填充像素的密度如何，最好從原始像素向外搜索。
我編寫了類似於圖形終端仿真的東西。我最終做的是編制一個從中心點出現的方形螺旋形狀的搜索模式，然後讓它增長直到碰到什麼東西。即使在舊的CPU上，這也足夠快。
+0
對於單點來說，我的算法「足夠好」。對於整個隊伍來說，Voronoi聽起來像是一個贏家。我會收回我的答案，除了一些未來的讀者可能有單點要求。 – 2009-12-14 17:47:19
4
另一個提示：距離總是大於或等於每一個座標差，始終小於或等於它們的總和，即
d >= dx, d >= dy, d <= dx + dy.
這可以幫助你做的排序效率更高。
5
你正在試圖做的是建立一個voronoi diagram這可以在O進行使用plane sweep
7
（N日誌N）的Voronoi Diagrams建設是Computational Geometry一個分支。 Delaunay Triangulations的構建涉及類似的考慮。您可以根據需要調整以下Delaunay algorithms之一。
- 翻轉算法
- 增量
- 分而治之
- 掃掠跡線
6
把點的KD樹，這是非常快的找到最近的鄰居後。有關詳細信息，請參閱維基百科上的this文章。
14
我將不得不同意jk和Ewan製作Voronoi Diagram。這將分割多邊形中的空間。 K中的每個點都有一個多邊形，描述了與其最接近的所有點。 現在當你得到一個點的查詢時，你需要找到它所在的多邊形。這個問題被稱爲Point Location，可以通過構建一個Trapezoidal Map來解決。
jk已經鏈接到使用Fortune's algorithm的Voronoi Diagram的創建，這需要O（n log n）個計算步驟和成本O（n）空間。 This website向您顯示如何製作梯形圖以及如何查詢它。您還可以找到一些界限有：
預計創建時間：爲O（n log n）的
預期的空間複雜度：O（n）的
但最重要的，預計查詢時間：O（log n）的。這（理論上）比kD樹的O（√n）更好。
我的來源（除了上面的鏈接）是：Computational Geometry: algorithms and applications，第六和第七章。
在那裏你會找到關於兩個數據結構的詳細信息（包括詳細的證明）。 Google圖書版本只包含您需要的部分內容，但其他鏈接應該足以滿足您的需求。如果你對這樣的事情感興趣，就買這本書吧（這本書是一本好書）。
好想法！對於大型數據集，這會極大地減少運行時間。 – 2009-12-14 14:18:28
既然你在處理像素，這也意味着你可以下降到整數數學，這是另一個巨大的速度獎金 – 2009-12-14 14:21:53
@rikh即使你確實需要距離，一旦你知道哪個點是最近的。 – 2009-12-14 14:22:17