Find the regions containing given coordinates

Question

Context : I'm developping a plugin for Spigot (Minecraft server plugin).

I want to define several regions for multiple purposes. I store them in a config file like this (YAML) :

Regions
  Region1:
    P1:
      X: 0
      Y: 0
      Z: 0
    P2:
      X: 1
      Y: 1
      Z: 1
  Region2:
    P1:
      X: -1
      Y: -1
      Z: -1
    P2:
      X: 2
      Y: 2
      Z: 2

As you can see, I'm storing the regions with 2 opposite coordinates.

I trying to come up with an algorithm than can store in an array all the regions that contains given coordinates.

For example, (0,0,0) => [Region1, Region2] and (2,2,2) => [Region1]

What I'm doing right now is :

Population an array with all regions
Checking if the X coordinate is between the 2 X coordinates defining the region
If not, remove the region from the array. If true, then go to 2. and check the Z coordinates, then Y.

This solution seems viable for a few regions (not exceeding 20), but since this will be used in an event that can be triggered multiple times a second, I would like to be able to do this with a better solution which can handle more regions and do it faster.

I looked at Data structures that can map a range of values to a key?, but my regions can overlap, so I can't use it this way.

Do you have any idea ?

I don't want to use Worldedit / Worldguard API, but "universal" Java APIs are fine.

A kd-tree might be a good option. Check out [this SO question](http://stackoverflow.com/questions/15827012/multi-dimensional-segment-trees) — Nico Schertler, May 15 '16 at 14:15
@NicoSchertler How would you use it for overlapping regions? — Valentin Lorentz, May 15 '16 at 14:23
@ValentinLorentz The same way you use it for any kind of extended objects. Either split them or put the region in both subtrees if the plane intersects it. — Nico Schertler, May 15 '16 at 16:41
I found a solution : I used R-Trees. I'm gonna write an answer. — Seblor, May 15 '16 at 18:06

score 1 · Accepted Answer · edited May 23 '17 at 12:23

I found a solution by using an R-tree

R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons.

I tested 2 implementations :

JSI
- Documentation
- Example
implementation of R-Tree by Russ Weeks (found on this answer)
- Source
- Unit Tests

While JSI was really simple to implement, with a full example, it needed to add 3 APIs to work correctly with no errors/warnings, and worked for 2 dimensions only (still useful since Y coordinate is not really relevent for my use in my Minecraft plugin).

So I used the second implementation, because it can handle multiple dimensions, use any object as entry, and use only one class.

Here's my code (small test for searching all the regions containing a point) :

private static final float[] ZEROES = { 0.0f, 0.0f, 0.0f };
private static final float[] POINT_FIVES = { 0.5f, 0.5f, 0.5f };
private static final float[] ONE_FIVES = { 1.5f, 1.5f, 1.5f };
private static final float[] ONES = { 1.0f, 1.0f, 1.0f };

public static void main(String[] args) {
    RTree<Object> rt = new RTree<Object>(50, 2, 3);
    rt.insert(ZEROES, ONES, "Region1");
    rt.insert(ONES, ONES, "Region2");

    System.out.println(rt.search(POINT_FIVES, ZEROES));

}

The output is :

[Region1]

Find the regions containing given coordinates

1 Answers1