Pong

July 15th 2014, R-Tree 3D Example

← July 15th 2014 Geo-Spatial Coordinate Systems | ● | July 15th 2014 Build Qt with SQLite and R-Tree Support →

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.

← July 15th 2014 Geo-Spatial Coordinate Systems | ● | July 15th 2014 Build Qt with SQLite and R-Tree Support →

Options: