序章
より大きなプログラム（ボリュームグラフィックスのレンダリングに関連する）の一部として、任意の（ただし有限の）三角形の2Dメッシュに特定の方法でラベルを付ける必要がある、小さいがトリッキーなサブ問題があります。少し前に、その時点で使用していたテストメッシュに十分なソリューション（以下を参照）を作成しましたが、考えられるすべてのメッシュに対してこのアプローチがうまく機能しない可能性があることに気付きました。今、私はついに現在のソリューションがまったくうまく機能しないメッシュに遭遇しました-そして私はまったく異なる種類のアプローチを考え出すべきであるように見えます。残念ながら、自分の考え方をリセットすることはできないようです。そのため、ここで質問したいと思いました。
問題
下の写真を考えてみましょう。（色は問題の一部ではありません。視覚化を改善（？）するために色を追加しただけです。また、エッジ幅の変化はまったく関係のないアーティファクトです。）
すべての三角形（たとえば、オレンジ色のABCと緑色のABD）について、3つのエッジのそれぞれに、「0」または「1」などの2つのラベルのいずれかを付ける必要があります。要件は2つだけです。
- 三角形のすべてのエッジに同じラベルを付けることができるわけではありません。つまり、三角形ごとに2つの「0」と1つの「1」、または2つの「1」と1つの「0」が必要です。
- エッジが2つの三角形で共有されている場合は、両方で同じラベルを付ける必要があります。つまり、画像のエッジABが三角形ABCの場合は「0」とラベル付けされている場合、ABDの場合も「0」とラベル付けされている必要があります。
メッシュは本物の2Dメッシュであり、有限です。つまり、メッシュはラップせず、明確に定義された外側の境界があります。明らかに、境界線では要件を満たすのは非常に簡単ですが、内部ではさらに難しくなります。
直感的には、証明できなくても、少なくとも1つの解決策が常に存在する必要があるように見えます。（通常、いくつかあります-それらのいずれか1つで十分です。）
現在のソリューション
私の現在の解決策は本当にブルートフォースの解決策です（完全を期すためにここで提供されています-このセクションをスキップしてください）：
- 三角形の4つのセットを維持します-ラベル付けされる残りのエッジの可能なカウント（0..3）ごとに1つ。最初は、すべての三角形がセット内にあり、3つのエッジにラベルが付けられたままになっています。
- ラベルのないエッジを持つ三角形がある限り：
まだ三角形が残っている、割り当てられていないエッジのゼロ以外の最小数を見つけます。言い換えれば、いつでも、ラベル付けが部分的に完了している三角形の数を最小限に抑えるように努めています。残りのエッジの数は1から3の間です。次に、この特定の数のエッジが割り当てられるように、そのような三角形を1つ選択します。この三角形に対して、次のようにします。- 残りのエッジのラベル付けが、他の三角形のラベル付けによってすでに適用されているかどうかを確認します。その場合は、上記の要件2で示されているようにラベルを割り当てます。
- これにより行き止まりになる場合（つまり、現在の三角形で要件＃1を満たせなくなる場合）、プロセス全体を最初からやり直します。
- 次のように残りのエッジを割り当てます。
- これまでにラベル付けされたエッジがない場合は、最初のエッジをランダムに割り当てます。
- 1つのエッジがすでに割り当てられている場合は、反対のラベルが付けられるように2番目のエッジを割り当てます。
- 2つのエッジが割り当てられた場合：同じラベルが付いている場合は、3番目のエッジに反対のラベルを割り当てます（明らかに）。2つのラベルが異なる場合は、3番目のラベルをランダムに割り当てます。
- 未割り当てのエッジの数が異なる場合は、三角形のセットを更新します。
- 私たちがここに着いたら、解決策があります-やったー！
通常、このアプローチは数回の反復で解決策を見つけますが、最近、アルゴリズムが1〜2千回の再試行後にのみ終了する傾向があるメッシュに遭遇しました...これは明らかに、終了しないメッシュが存在する可能性があることを示唆しています。
今、私は常に解決策を見つけることが保証されている決定論的アルゴリズムが欲しいです。メッシュはそれほど大きくなく、ラベル付けは基本的に新しいメッシュがロードされたときにのみ実行する必要があるため、計算の複雑さはそれほど大きな問題ではありません。これは常に発生するわけではありません。したがって、（たとえば）指数関数を使用するアルゴリズムそれが機能する限り、複雑さは問題ないはずです。（しかしもちろん：より効率的であるほど良いです。）
ここまで読んでいただきありがとうございます。さて、どんな助けでも大歓迎です！
編集：提案された解決策に基づく結果
残念ながら、Dialecticusによって提案されたアプローチを機能させることができません。うまくいかなかったかもしれません...とにかく、開始点が緑色の点で示されている次のメッシュを考えて
みましょう。少しズームインしてみましょう...
それでは、アルゴリズムを開始しましょう。最初のステップの後、ラベル付けは次のようになります（赤=「スター付きパス」、青=「リング状パス」）：
これまでのところ良好です。2番目のステップの後：
そして3番目：
... 4番目：
しかし今、私たちは問題を抱えています！もう1ラウンドやりましょう。ただし、マゼンタでプロットされた三角形に注意してください。
私の現在の実装によると、マゼンタの三角形のすべてのエッジはリングパス上にあるため、青色である必要があります。これは事実上反例になります。どういうわけか間違っているかもしれません...しかし、いずれにせよ、開始ノードに最も近い2つのエッジを赤にすることはできません。3番目のラベルが赤で表示されている場合、そのソリューションはもはやアイデアに実際には適合していないようです。
ところで、これが使用されたデータです。各行は1つのエッジを表し、列は次のように解釈されます。
- 最初のノードのインデックス
- 2番目のノードのインデックス
- 最初のノードのx座標
- 最初のノードのy座標
- 2番目のノードのx座標
- 2番目のノードのy座標
開始ノードは、インデックス1を持つノードです。
次に、RafałDowgirdによって提案された方法を試してみるべきだと思います...しかし、おそらくしばらくの間、まったく異なることをする必要があります:)