有沒有算法來確定2D空間中的一組點是否構成一個封閉區域？

Question

我有一組點（x，y），我想知道它是否構成一個封閉區域（在一個矩形的2D柵格內）。這似乎是一個簡單的問題，但經過半個小時的谷歌搜索，我無法找到解決此問題的算法。有沒有一個已知的算法來解決這個問題？用C++或C＃編寫的例程（甚至是僞代碼）將是理想的。

編輯： 我在這裏處理的具體問題是一個繪圖程序，其中應用程序用戶應該繪製圍繞感興趣區域的邊界。我想警告用戶，如果他們繪製的邊界不構成封閉區域。

Answer 1

看來你想知道給定的一組點是否包含一個封閉的區域。幸運的是，這有一個簡單而靈活的答案:)

假設給出的點集是在白色背景上繪製的一組黑色像素。 只需從已知的外部點（例如（0，0））開始黑色填充填充。現在看看圖像中是否還有白色像素。如果是這樣，那麼原始繪製的像素至少包含1個封閉區域。

如果您曾經在粗略的位圖繪圖程序中使用鼠標繪製任何東西，您會知道小缺陷很容易形成 - 例如，如果您繪製的是自由曲線，則急劇轉動，然後沿不同的方向繼續該曲線，這可能是因爲您無意中創建了1或2個白色像素的微小氣泡。幸運的是，該算法可以輕鬆考慮這些因素：只需計算填充洪水後剩餘的白色像素數量，並且只有當此計數超過某個大於1的選定閾值時才返回「YES」（您可能希望使閾值成比例，以允許繪製每個像素的給定數量的缺陷）。爲了進一步控制，在填充洪水之後，可以識別並刪除低於某個固定「缺陷閾值」大小的所有白色像素島。可以通過暫時嘗試圖像中每個像素的填充來完成檢測，並在超過閾值大小時停止（並撤消）。

所有這些操作（包括檢測和去除小缺陷）在圖像中的像素數量中僅佔用線性時間。洪水填充是一種簡單而快速的算法，但如果您想要更快的速度，您可以填充給定像素集的邊界框，每邊向外擴展1個像素。