屋内の場所の地図を表す画像があるとしましょう。このマップでは、特定のゾーンが「許可」され、他のゾーンは許可されていません。次に、定期的に一連の座標を取得(x,y)し、それらが「許可された」ゾーンにあるかどうかを確認する必要があります。
現時点では、手段が許す限り、このマップをboolean[][] map変数で表しています。true確認するには、次の値を確認しますmap[x][y]
ただし、私が表現している画像は非常に大きくなる可能性があり、最大 5000x5000 ピクセルとしましょう。その結果、変数がメモリ内で大きくなりすぎます (この場合、約 1 バイトかかるとmap仮定すると 25MB )。boolean
私の問題に適したデータ構造はありますか? しばらく考えていましたが、スペースをあまりとらないものは見当たりません。
前もって感謝します！
このような状況の一般的なシナリオは、構造体の array/ を使用することListですRect。次に、そのような長方形が「許可される」領域を定義することを定義します。
次に、ポイントを指定(x, y)して、配列/リストを反復処理し、そのポイントがコレクション内のいずれかの長方形の内側にあるかどうかを確認します。これには簡単に使用できますRect.contains(x,y)。問題の点が含まれているtrueかどうか、または含まれていないかどうかを答えます。Rectfalse
これにより、非常にまともなパフォーマンス/メモリ消費率が得られるはずです。「ゾーン」が長方形であると仮定して（または各ゾーンを理想的には少数の長方形の結合として表現できる）、あなたのようなアプリケーションで一般的に使用されます。
別の代替手段 (長方形がオプションでない場合) は、目立たない多角形を使用してゾーンを表すことです。これが実現可能な場合は、ここに示されている単純なアルゴリズムを使用できます: http://alienryderflex.com/polygon/これにより、特定のポイントが (非常に複雑な) ポリゴンの内側にあるかどうかをテストできO(n)ますn。マップのゾーンを定義するすべてのポリゴン。
ゾーンが非常に散らばっている場合 (つまり、偶数ポリゴンの長方形を使用してゾーンを表現するのが難しい場合)、おそらく他に単純な選択肢はありません。あなたができることは、（たとえば）行許容情報を含む配列を作成することです。行ごとに、それぞれが連続する列の値を表す 32 ビットを含む配列int[]があります。これはあなたが既に持っているものと非常に似ていますが、各値はバイト全体ではなく 1 ビットのみを使用するため、メモリ フットプリントは 8 分の 1 になります。intboolean