私は、プレイヤーが1ポイントずつ移動し、それらの後ろにパスを残すゲームを構築しています。彼らは自分の道を越えることはできません。そして、道が終わったら、すべての囲まれた点を捕らえる必要があります。私は、どのアルゴリズムを調べる必要があるのかを数学的に知る経験はありませんが、形状を矩形に分割し、各矩形に含まれる点を見つける必要があると思います。2Dポリゴンの囲まれた点を見つける
私は凸包アルゴリズムを指していましたし、しばらくそれを見てから、所与の点群の凸面を見つけたようです。それはうまくいきません。
問題を解決するためのアルゴリズムが見つかりませんでした。探索するアルゴリズムや問題を直接解決できるアルゴリズムの方向性を探している場合は、
プレイヤーは上下左右にしか動かすことができないため、ポリゴンのすべての頂点(?)は常に直角になります。
例プレーン:
0 1 2 3 4
0 [x] [x] [x] [ ] [ ]
1 [x] [o] [x] [ ] [ ]
2 [x] [o] [x] [x] [x]
3 [x] [o] [o] [o] [x]
4 [x] [x] [x] [x] [x]
ストアド・ポイント(例:平面上の 'X' としてマーク)
[
[0,0],
[0,1],
[0,2],
[1,2],
[2,2],
[2,3],
[2,4],
[3,4],
[4,4],
[4,3],
[4,2],
[4,1],
[4,0],
[3,0],
[2,0],
[1,0]
]
目的ポイント(例:平面上の 'O' としてマークされた)
[
[1,1],
[2,1],
[3,1],
[3,2],
[3,3],
]
他のプレーン例:
0 1 2 3 4
0 [ ] [x] [x] [x] [ ]
1 [ ] [x] [o] [x] [ ]
2 [x] [x] [o] [x] [x]
3 [x] [o] [o] [o] [x]
4 [x] [x] [x] [x] [x]
0 1 2 3 4
0 [x] [x] [x] [ ] [ ]
1 [x] [o] [x] [ ] [ ]
2 [x] [x] [x] [x] [x]
3 [ ] [x] [o] [o] [x]
4 [ ] [x] [x] [x] [x]
@AndrasDeak擬似コードも歓迎します。私はちょうど問題と、私が知っている言語で自分自身を貸す提案されたタグを利用しました。 – OneNeptune
私のコメントが十分に直接的ではない場合:純粋にアルゴリズム的な質問で言語タグに迷惑をかけないでください。その答えは擬似コードになる可能性があります。誰でもアルゴリズム設計に興味があるなら、そのタグに従います。 –
@AndrasDeakあなたの建設的なコメントをありがとう、私はあなたの提案を反映するために質問を編集しました。ご協力ありがとうございます。 – OneNeptune