algorithm - 曲線が閉じているかどうかを効率的に理解する方法

Question

曲線が閉じているかどうかを理解する効率的な方法は何ですか?

おそらく 1 つの方法はフラッド フィル アルゴリズムであり、それを使用してチェックします。フラッド フィルが事前に定義されたバウンディング ボックスを離れる場合は、形状の外側にあります。それ以外の場合は、フラッド フィルが終了すると、シェイプ内にいます。

しかし、それは効率的な方法ですか？

tnx。

Answer 1

曲線をグラフとして見てください。頂点はピクセルであり、エッジは隣接するピクセル間にあります。テストが行​​われます:

• 単純な曲線は、すべての頂点に 2 つの隣接点があり、グラフが接続されている場合です。
• 交差していない単純な曲線は、すべての頂点に 2 つの隣接点があり、グラフが接続されていない場合です。部品数はグラフ分割で求める。
• 8 曲線は、1 つを除くすべての頂点に 2 つの隣接点があり、その 1 つに 4 つの隣接点があり、グラフが接続されている場合です。
• ...

グラフ/サブグラフの接続と分割のテストは、グラフ トラバーサルによって行われます。

Answer 2

2 つの別々のポインターで曲線に沿って歩くことができますか? もしそうなら、それを行い、1 つのポインターを 2 倍の速さでトラバースするように設定します。ループが閉じている場合、ポインターは 1 点で重なります。