填充凸形的有效方法

Question

說我有一個封閉的形狀，如下圖所示，我有邊緣像素。什麼是最有效的方式來填充形狀，即把像素「開」裏面的造型，如果：

1）我所有的邊緣像素

2）我最邊緣的像素，而不是全部（如圖所示）。

Answer 1

這一切都取決於情況。

如果你手動創建幀緩衝區（基本上使用一個字節數組或類似的東西），你必須迭代你想改變的所有像素。因此，例如，開始於一個行的最左邊緣：上排

跳轉一個正確的形狀的

• 查找開始並接通像素，直到發現行形狀的第二端部（或行結束）
• 繼續對下一行

這當然只有當你擁有所有邊緣像素的工作。看看Marching Squares，可以得到一些幫助。

而且請更具體。 「最有效的方式來填充形狀」取決於很多你根本渲染庫的，如果它是光柵圖形等等...

編輯 注意，該算法的速度要快得多，如果你能生成邊緣像素，那麼不需要尋找邊緣的開始。

Answer 2

之前，您可以填寫的東西，你需要確定確切的邊界，在這種情況下，將構成識別圈內部。

之後，你可以檢查每個像素的圓周圍的一個框，如果它實際上在它。由於您必須對圓內的每個像素執行一些操作，並且圓中像素的數量與邊界正方形的像素數成線性關係（假設對於某個常量，邊界正方形的邊具有長度「半徑*常量」），則此操作應該接近最佳。

Answer 3

1. 如果單詞「裏面」的話，邊界中的中斷將破壞意義。
2. 像人類視網膜一樣的神經網絡在進行這種處理時非常高效。
3. 在計算機上，您需要花時間來定義「內部」的含義。差距有多大？如何扭曲的邊界？
4. 模擬一個很大的圓形蟲子彈回「內部」周圍 - 太大而不能穿過間隙但小於邊界的最小曲率半徑?????

Answer 4

標準flood fill算法將是一個凸形相當有效，並且將處理的情況下，形狀較不凸起的比你的預期。不幸的是它需要一個不間斷的輪廓。

Answer 5

構造凸包並添加缺失的像素。然後使用掃描線算法填充多邊形。