如何在同一像素組中找到距離另一個像素最遠的像素

「組」是指像素集合中的每個像素在同一個集合中至少有一個相鄰像素，該圖形顯示一個小組。如何在同一像素組中找到距離另一個像素最遠的像素

An example of a group

我想找到其具有從指定像素的最大直線距離（例如，綠色像素）的像素。連接兩個像素的直線（紅線）不得離開組。

我的解決方案是循環遍歷度數並模擬從具有度數的綠色像素開始的行的進度，並查看哪條線行進了最遠的距離。

longestDist = 0 
bestDegree = -1 
farthestX = -1 
farthestY = -1 
FOR EACH degree from 0 to 360 
    dx=longestDist * cos(degree); 
    dy=longestDist * sin(degree); 
    IF Point(x+dx , y+dy) does not belong to the group 
     Continue with next degree 
     //Because it must not be the longest line, so skip it 
    END IF 
    (farthestX , farthestY) = simulate(x,y,degree) 
    d = findDistance(x , y , farthestX , farthestY) 
    IF d > longestDist 
     longestDist = d 
     bestDegree = degree 
    END IF 
END FOR

這顯然不是最好的算法。因此我在這裏尋求幫助。

謝謝你，併爲我可憐的英語感到抱歉。

來源

2012-09-20 Raytheon

請注意，您可以放棄所有內部像素的計算。 – dfens

而且你不需要使用角度。你只需要使用畢達哥拉斯定理;） – dfens

@dfens：「內部像素」 - 爲什麼？其中之一可能是解決方案。 –

首先，請注意，算法中的角度離散化可能取決於網格的大小。如果這個步驟太大，您可能會錯過某些細胞，如果它太小，您將最終一次又一次訪問同一個細胞。

我建議您枚舉區域中的單元格，然後單獨測試每個單元格的條件。枚舉可以使用廣度優先搜索或深度優先搜索完成（我認爲後者會更好，因爲它可以讓人快速建立下界並進行修剪）。

可以維持到目前爲止發現的最遠點X和該區域中的每個新點，檢查（a）該點是否比迄今發現的點離得更遠，以及（b）它是否通過只有直線穿過該區域的細胞。如果兩個條件都滿足，更新X，否則繼續搜索。如果條件（a）不滿足，條件（b）不必檢查。

的這種解決方案的複雜性將是O(N*M)，其中N是細胞在區域的數量和M是區域（max(width,height)）的較大尺寸。如果性能是本質的，可以應用更復雜的啓發式算法，但對於合理大小的網格，這應該可以正常工作。

來源

2012-09-20 10:05:24 Qnan

搜索像素，而不是斜率。僞代碼。

bestLength = 0 
for each pixel in pixels 
    currentLength = findDistance(x, y, pixel.x, pixel.y) 
    if currentLength > bestLength 
    if goodLine(x, y, pixel.x, pixel.y) 
     bestLength = currentLength 
     bestX = pixel.x 
     bestY = pixel.y 
    end 
    end 
end

您可能想對像素降序排列| dx | + | dy |在那之前。

來源

2012-09-20 10:11:52 iced

這不處理連接線停留在區域內的要求。 – davec

我不會使用角度。但我敢肯定，最大距離總是在集合邊緣的兩個像素之間，因此我會跟蹤輪廓：從集合中的任何像素到任意方向，直到到達集合的邊緣。然後沿邊緣順時針移動（couter）。以任何像素爲出發點，並且您將能夠找到最大的距離。它仍然非常貪婪，但我認爲它可能會給你一個改進的替代起點。

編輯：我剛剛想到的是：當你有一個開始像素s和結束像素e。在使用s的第一次迭代中，相應的e將相鄰（順時針方向沿着邊緣的下一個）。當您沿邊緣迭代時，可能會出現這種情況，即在s和e之間沒有設置直線。在這種情況下，這條線會碰到另一部分邊緣（像素爲p）。您可以在該像素（e = p）

EDIT2繼續邊緣的迭代：如果你打了p你就會知道，有可能是s和e之間不再距離，這樣在s下一個迭代可以跳過邊緣的整個部分（介於s和p之間），並再次開始於p。

編輯3：使用上述方法找到第一個p。以p作爲下一個s並繼續。重複，直到你再次到達你的第一個p。最大距離將在兩個p之間，除非該組的邊緣是凸面的，在這種情況下，您不會找到p。

免責聲明：這是未經測試，只是從我頭頂的想法，沒有圖紙已經做出證實我的要求，一切都可能是錯的（也就是想想看自己，你實現它之前; d）

來源

2012-09-20 10:13:24 Mene

使用雙數據結構：

一個包含按角度排序的像素。
第二個按距離排序（對於快速訪問，這應該也包含第一個數據結構的「指針」）。

瀏覽排序的角度，檢查線條在區域內的每個像素。一些像素將具有相同的角度，所以你可以沿着線從原點走，直到你離開該區域。您可以消除超出該點的所有像素。另外，如果最大距離增加，請移除距離較短的所有像素。

來源

2012-09-20 10:49:12

將您的區域視爲多邊形而不是像素集合。從這裏你可以得到一個線段列表（你的多邊形的邊緣）。

從您的起始像素到正在檢查的每個像素繪製一條線。不與多邊形的任何線段相交的最長線表示距像素的直線可達的最遠像素。

您可以對此進行各種優化以及檢查一些邊緣案例，但如果您在我發佈這些內容之前瞭解了這個想法，請告知我們......特別是，您是否明白我的意思，將其視爲多邊形而不是像素的集合？

要補充，這種方法將比任何基於角度的方法或方法都要快得多，這種方法或方法需要除「最小像素集合外的所有像素」都「行走」。你可以進一步優化，因爲你的問題相當於找到一個多邊形邊緣的最遠端點，它可以從你的起始點通過一條不相交的直線到達。這可以在O（N^2）中完成，其中N是邊的數量。請注意，N將比像素數量小得多，並且許多算法提出使用角度和/或像素迭代將取決於像素的數量。

來源

2012-11-07 18:32:18 davec

如何在同一像素組中找到距離另一個像素最遠的像素

回答

相關問題