私は現在、2つの2次元座標（長方形の左上と右下の領域）によって定義される領域を設定する機能を1つの機能に含むゲームのプラグインを作成しています。これらのリージョンは保存され、各リージョンに関連付けられた他のさまざまなデータが含まれます。プレイヤーが世界を動き回っているので、プレイヤーの座標だけからこれらの領域の1つに入るタイミングを決定する必要があります。これは、1秒間に数百回呼び出されるため、効率的である必要があります。 。
この種の検索を効率的にサポートできるデータ構造はありますか？もしそうなら、使用するJava実装を見つけるか、必要に応じて自分で実装するためのドキュメントをどこで見つけることができますか？
また、バルクロードのみをサポートしているように見えるツリー構造がいくつか見つかりましたが、この構造にリアルタイムで値を追加および削除できる必要があります。
1次元の場合、適切なデータ構造は区間木です。
2次元のキャストを解決するには、区間木を使用して、少なくとも1つの次元に点を含む長方形をすばやく見つけ、それぞれの2番目の次元を確認するか（すでに十分に高速である可能性があります）、多くの次元への一般化は、Wikipediaの記事で簡単にスケッチされています（ただし、最初に読んだときにその一般化を理解していなかったことを認めなければなりません）。
Assuming the player moves slowly (i.e. the number of region enter or leave events is small compared to the number of regions) the following approach might be more efficient: Keep a search tree of the x-coordinates where rectangles begin or end, and an a similar tree for the y-coordinates. If a player enters or leaves a region, he must have crossed the x or y coordinate of a boundary point. That is, you would do a range query on the x search tree for the range [old_x, new_x], and check each of these rectangles. Do the same for the y-direction (not reporting duplicates).
座標を実装するには、探している機能を実装するクラスでPoint2Dを使用できます。
http://download.oracle.com/javase/6/docs/api/java/awt/geom/Point2D.html