2

私がプレイしているゲーム用のオンライン マップ編集プログラムを開発しようとしています。
地図のデータは少し大きいです。すべての正方形のデータを送信すると、中サイズのマップのデータは 1 MB 近くになります。

私ができると思ったのは、地図上で境界を見つけ、それに基づいてポリゴンを作成することでした。

現在私は：

  1. 最も北西の境界を見つけて、そこから始めます。私のサンプル マップでは、(3,2) です。
  2. 次に、北、東、南、西を確認し、データが 1 でない最初の未訪問の場所に移動します。
  3. 未訪問の場所がない場合は、最も歴史の古い場所に移動します。

サンプルマップ
実行した手順

これは、北部地域ではうまく機能します。しかし、南のエリアに行くと、北をチェックして、そこが未訪問の場所であることに気づき、そこに行きます。おかしくなった場所の座標は 13,11 です。

明らかに、これでは必要な境界が得られず、マップ全体を歩きません。ですから、何かを変える必要があります。

以前と同じ操作順序で境界チェックを追加することを検討しました(NESW)。ただし、それを台無しにすることも可能です。

Map2 - 境界チェック

(13,11) で北をチェックし、未訪問の場所であることを確認します。そして今回はそこに境界があるので、そこに行ってもいいと思うでしょう。

外側の境界全体を歩くにはどうすればよいですか?

ここで言及されている凸包アルゴリズムを見てみましたが、それは私が必要とするものではないと思います。私は間違っているかもしれませんが、これは凸包の結果がどのように見えるかを期待するものです。
凸包 これにより、マップのサイズが少し縮小されますが、必要のないデータがまだたくさんあります。また、マップ内のアイテムの内部境界線を取得する必要がある場合、それらも不規則になるため、サイズ縮小は失われます。

では、実際に外側の境界線を歩いていることを確認するにはどうすればよいでしょうか?

4

2 に答える 2

0

問題が正しかったかどうかはわかりませんが、外側の境界線は直交法線ベクトルの配列として表示できるようです。というかセクション。マップの正方形がセルに属するグリッドを想像してください。0 から始まる左上からセクションをマークし始めましょう。その表記では、pic の外枠の始まりです。1 は ((3, 2), (4, 2)), ((4,2), (5,2)) などになります。

各セクションは 2 つのセルに属し、それぞれの 1 つはマップ スクエア "1" であり、もう 1 つは境界線ではありません。グリッドをトラバースして、それらを簡単に収集できます。

次に、それらをサイクルに分類する必要があります。簡単だ。2 つのセクションに 1 つの共通座標がある場合、それらは単一のサイクルに属します。2 つのサイクルのセクションの下に共通の座標がある場合、それらは 1 つのサイクルであり、データを別のデータに連結するだけです。

明確に異なるサイクルのセットがある場合、最も長いサイクル、最も多くのセクションを持つサイクルが外側の境界になります。

もちろん、マップが一体になっている場合。

于 2013-05-25T17:31:53.863 に答える