Pong

## July 15th 2014, R-Tree 3D Example

Since ECEF is a more efficient coordinate system than geographic coordinates, let’s see how R-Trees can be utilized with ECEF.

First off, we need a 3D search space:

CREATE VIRTUAL TABLE ecef USING rtree(
id,              -- Integer primary key
minX, maxX,      -- Minimum and maximum X coordinate
minY, maxY,      -- Minimum and maximum Y coordinate
minZ, maxZ       -- Minimum and maximum Z coordinate
);


Then we insert the Eiffel tower (LLH(48.858701,2.294573,53)) into the ECEF coordinate system. To get the respective ECEF coordinate we use the “coord” tool of libMini:

echo “LLH(48.858701,2.294573,53)” | coord


yields

ECEF(4200945.26,168328.841,4780274.98)


So the Eiffel tower is x=4200km away from the earth’s bisecting ECEF yz-plane, y=168km “east” of the Greenwich meridian and z=4780km “north” of the equatorial plane:

Finally, we insert a 3D bounding box that maps to the above 3D point into the 3D R-Tree:

INSERT INTO ecef VALUES(
1,                       -- Primary key -- Eiffel tower point
4200945.26, 4200945.26,  -- ECEF x-range
168328.841, 168328.841,  -- ECEF y-range
4780274.98, 4780274.98   -- ECEF z-range
);


Since the Eiffel Tower is not a singular point but has an elevation of 324 meters, we better insert a bounding box with uniform size of 400 meters including the Eiffel Tower into the R-Tree:

INSERT INTO ecef VALUES(
2,                       -- Primary key -- Eiffel tower bbox
4200745.26, 4201145.26,  -- ECEF x-range
168128.841, 168528.841,  -- ECEF y-range
4780074.98, 4780474.98   -- ECEF z-range
);


And search the north hemisphere for contained objects:

SELECT id FROM ecef
WHERE maxZ>=0;


Unsurprisingly, the object ids 1&2 turn out to be the result.

If we search the south hemisphere:

SELECT id FROM ecef
WHERE minZ<=0;


We do not find a contained object, of course.