algorithm - 閉じたラスター ポリゴンと開いたラスター ポリゴンを区別するために使用できるアルゴリズムは何ですか?

Question

2 つの点配列があるとします。そのうちの 1 つは、次のようなオープン ポリゴンです。

Xes は黒い点と点 ('.') - 白いものです。

2 番目の点の配列には、閉じた多角形が含まれています。

特定の点配列が閉じた多角形か開いた多角形かを判断できるアルゴリズムの名前が必要です。この情報は、フラッディング フィルが可能かどうかを判断するために必要です (最初の例ではフラッド フィルはできませんが、2 番目の例ではフラッド フィルが可能です)。

2 種類のポリゴンを区別するためのアルゴリズムは何と呼ばれていますか?

更新 1 (2015 年 10 月 10 日 10:05 MSK):フラッド フィル エラーを防ぐために、閉じたポリゴンと開いたポリゴンを区別する必要があります。

フラッド フィル エラーは、フラッド フィルを次のような開いたポリゴンに適用した場合です。

.....
..XXX
.X..X
X...X

完全に塗りつぶされたグリッドになります。

XXXXX
XXXXX
XXXXX
XXXXX

私の当初の考えは、

1. 多角形を取り、
2. 開いているか閉じているかを確認し、
3. 閉じている場合は、フラッド フィルを適用します。

今、私はそれを別の方法で行うことができます：

1. ポリゴンを塗りつぶします。
2. グリッド全体が塗りつぶされている場合、それは開いたものであり、そうでない場合 (塗りつぶし後のグリッド内の少なくとも 1 つのポイントが白である場合)、それは閉じたものです。

ポリゴンが開いているか閉じているかを判断するためにフラッド フィルを回避する方法があれば教えてください。

Answer 1

私はこれについて何の経験もありませんが、何か他のことを研究しているときに、これを見つけて、あなたに役立つかもしれないと思いました:

http://www.cs.tufts.edu/~sarasu/courses/comp175-2009fa/pdf/comp175-05-region-filling.pdf

スライドでは、3 つの異なるアルゴリズムについて言及しています。

• X 交差配列アルゴリズム
• エッジ リスト アルゴリズム
• ピネダのアルゴリズム