R-Tree C/C++ Example
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. Wikipedia
Using RaimaDB, it is simple to implement the R-tree data structure for quick look up times and efficient organization.
The Schema
A unique ID for each row in the database and an array of 4 doubles that will hold the coordinates of two points on an x/y axis are what will be used in this example. The second column containing the coordinates is where the R-tree data structure will be utilized.
When searching for data, a bounding box can be created that will return all data either inside of the designated area or data that is just touching the bounding box.
This will be seen later on in the example.
CREATE TABLE rtree_table ( id char(20) primary key, rect DOUBLE ARRAY[4] KEY USING R_TREE NOT NULL );
C/C++ Implementation
In the code shown below, geographic coordinates will be inserted into the r-tree and a bounding-box look up will be created to search a specific area for rows of the database.
Each time the program is initiated we will delete all of the data in the database.
/* ----------------------------------------------------------------------------
*
* Raima Database Manager
*
* Copyright (c) 2020 Raima Inc., All rights reserved.
*
* Use of this software, whether in source code format, or in executable,
* binary object code form, is governed by the Raima LICENSE which
* is fully described in the LICENSE.TXT file, included within this
* distribution of files.
*
* ----------------------------------------------------------------------------
*/
#include "rdmapi.h"
#include "rdmtfsapi.h"
#include "rtreeCPP_structs.h"
#include "rtreeCPP_cat.h"
#include "rtreeCPP_gen_api.h"
#include "cpp-tfs.h"
#include "cpp-exception.h"
#include "cpp-transaction.h"
#include <iostream>
using namespace RDM_CPP;
using namespace RDM_CPP::RTREECPP;
#define FIXED_FLOAT(x) std::fixed << (x)
/** \file rtreeExample.c
\brief Simple r-tree example using the RDM C++ API
This example will show you how to manage 2 dimensional data, using an
r-tree index.
The example will insert several rows containing point data which
will be put into an r-tree.
The example will then perform a series of queries to retrieve the data
that meet specific criteria.
*/
/** \brief Delete all data from the database
This function will remove all rows from all tables in the database.
*/
static void delete_data (Db_rtreeCPP db)
{
RDM_TABLE_ID tablesToLock[1] = {TABLE_RTREE_TABLE};
std::cout << "Removing all data from the database" << std::endl;
/* Start an update transaction */
db.StartUpdate (tablesToLock, 1);
try
{
db.DeleteAllRows ();
db.End ();
} catch (rdm_exception e)
{
db.EndRollback ();
throw;
}
}
Here, the geographic coordinates will be inserted into the R-tree. This is very similar to any row insert that you have executed when using RaimaDB.
/** \brief Print the contents of a rectangle
*/
static void printRectangle (double rect[4])
{
std::cout << "{ (" << std::fixed << rect[0] << ", " << rect[1] << "), ("
<< rect[2] << ", " << rect[3] << ") }";
}
/** \brief Insert rows into the RTREE_TABLE table
This function will insert two rows into the RTREE_TABLE table.
*/
static void insert_data (Db_rtreeCPP db)
{
uint32_t ii;
RDM_TABLE_ID tablesToLock[1] = {TABLE_RTREE_TABLE};
RTREE_TABLE row_data[] =
{/* utm coordinates */
/* id | x-min | y-min | x-max | y-max
*/
{"T_SIG_4356_UTM",
{536606.1538, 5279277.737, 536606.1538, 5279277.737}},
{"T_SIG_4357_UTM",
{536610.0608, 5279253.421, 536610.0608, 5279253.421}},
{"T_SIG_4358_UTM",
{536584.7699, 5279251.706, 536584.7699, 5279251.706}},
{"T_SIG_4359_UTM",
{536588.0522, 5279278.956, 536588.0522, 5279278.956}},
{"T_SIG_4405_UTM",
{536175.4322, 5278455.695, 536175.4322, 5278455.695}},
{"T_SIG_4406_UTM",
{536159.8151, 5278443.372, 536159.8151, 5278443.372}},
{"T_SIG_4407_UTM",
{536143.4427, 5278455.941, 536143.4427, 5278455.941}},
{"T_SIG_4408_UTM",
{536150.6135, 5278474.102, 536150.6135, 5278474.102}},
{"T_SIG_4458_UTM",
{536201.2532, 5278082.970, 536201.2532, 5278082.970}},
{"T_SIG_4459_UTM",
{536191.8691, 5278070.464, 536191.8691, 5278070.464}},
{"T_SIG_4460_UTM",
{536182.6727, 5278076.075, 536182.6727, 5278076.075}},
{"T_SIG_4461_UTM",
{536192.0458, 5278090.360, 536192.0458, 5278090.360}},
/* geo coordinates */
/* id | x-min | y-min | x-max | y-max */
{"T_SIG_4356_GEO", {47.665856, 9.487589, 47.665856, 9.487589}},
{"T_SIG_4357_GEO", {47.665637, 9.487639, 47.665637, 9.487639}},
{"T_SIG_4358_GEO", {47.665623, 9.487302, 47.665623, 9.487302}},
{"T_SIG_4359_GEO", {47.665868, 9.487348, 47.665868, 9.487348}},
{"T_SIG_4405_GEO", {47.658484, 9.481784, 47.658484, 9.481784}},
{"T_SIG_4406_GEO", {47.658374, 9.481575, 47.658374, 9.481575}},
{"T_SIG_4407_GEO", {47.658488, 9.481358, 47.658488, 9.481358}},
{"T_SIG_4408_GEO", {47.658651, 9.481455, 47.658651, 9.481455}},
{"T_SIG_4458_GEO", {47.655129, 9.482097, 47.655129, 9.482097}},
{"T_SIG_4459_GEO", {47.655017, 9.481971, 47.655017, 9.481971}},
{"T_SIG_4460_GEO", {47.655068, 9.481849, 47.655068, 9.481849}},
{"T_SIG_4461_GEO", {47.655196, 9.481975, 47.655196, 9.481975}}};
/* First we will remove all existing data from the database */
delete_data (db);
std::cout << "Inserting data..." << std::endl;
/* Start a transaction */
db.StartUpdate (tablesToLock, 1);
try
{
for (ii = 0; ii < RDM_LEN (row_data); ii++)
{
db.Insert_rtree_table_Row (row_data[ii]);
std::cout << " ** Inserted Row id: " << row_data[ii].id
<< ", rect = ";
printRectangle (row_data[ii].rect);
std::cout << std::endl;
}
db.End ();
} catch (rdm_exception e)
{
db.EndRollback ();
throw;
}
}
A quick look at each row that was added to the database.
/** \brief Print the current for of a cursor based on the RTREE_TABLE
*/
static void printCurrentRtreeTableRow (Cursor_rtree_table cursor)
{
RTREE_TABLE row;
/* Read the value of the current row into a structure */
cursor.ReadRow (row);
/* Print the row that was read */
std::cout << " ** Found Row id: " << row.id << ", rect = ";
printRectangle (row.rect);
std::cout << std::endl;
}
/** \brief Look up rectangles that meet the specified criteria
This function will read create a cursor containing all rectangles in the
r-tree that meet the bounding box criteria. It will then iterate through
the cursor and display the rows.
*/
static void displayRectangles (
Db_rtreeCPP db, /**< [in] database handle */
RDM_RTREE_TYPE type, /**< [in] The query type */
double boundingBox[4] /**< [in] The bounding box */
)
{
Cursor_rtree_table cursor;
RDM_TABLE_ID tablesToLock[] = {TABLE_RTREE_TABLE};
bool found = false;
/* Get a read lock on the RTREE_TABLE table */
db.StartRead (tablesToLock, RDM_LEN (tablesToLock));
try
{
/* Create the cursor using the r-tree */
cursor = db.Get_rtree_table_RowsBy_rect (boundingBox, type);
/* Move to the first resulting row */
cursor.MoveToFirst ();
while (cursor.GetStatus () == CURSOR_AT_ROW)
{
found = true;
/* Print the current cursor row */
printCurrentRtreeTableRow (cursor);
/* Move to the next row */
cursor.MoveToNext ();
}
/* Free the locks */
db.End ();
} catch (rdm_exception e)
{
std::cerr << "Error in displayRectangles";
db.End ();
throw;
}
/* Display a message if we didn't retrieve any rows */
if (found == false)
{
std::cout << " ** No Rows Found" << std::endl;
}
}
Look up coordinates contained by the created bounding box
The two functions that are utilized to look up data are displayContainedRectangles() and displayOverlappingRectangles().
/** \brief Look up rectangles contained by the specified bounding box
*/
static void displayContainedRectangles (
Db_rtreeCPP db, /**< [IN} The database handle */
double boundingBox[4] /**< [IN] The bounding box value */
)
{
displayRectangles (db, RDM_RTREE_CONTAINS, boundingBox);
}
/** \brief Look up rectangles overlapping the specified bounding box
*/
static void displayOverlappingRectangles (
Db_rtreeCPP db, /**< [IN] The database handle */
double boundingBox[4] /**< [IN] The bounding box value */
)
{
displayRectangles (db, RDM_RTREE_OVERLAP, boundingBox);
}
/** \brief The main function
This function will do initialization and cleanup as well as call
the functions that insert/retrieve data
*/
int32_t main_rtreeCPP (int32_t /*argc*/, const char *const * /*argv*/)
{
TFS tfs = NULL;
Db_rtreeCPP db;
double boundingBox[4];
try
{
/* Allocate RDM_TFS handle */
tfs = TFS::Alloc ("");
/* Allocate RDM_DB handle */
db = tfs.AllocDatabase ();
/* Open database */
db.Open ("rtreeCPP");
/* Insert data */
insert_data (db);
/* Do lookups with a bounding box that contains two of the rows in the
table that use utm coordinates. In this case there are tree
candidates for the X value, but only 2 matches for the Y value */
boundingBox[0] = 536100.0000; /* Min X Value */
boundingBox[1] = 5278440.0000; /* Min Y Value */
boundingBox[2] = 536159.0000; /* Max X Value */
boundingBox[3] = 5278475.000; /* Max Y Value */
std::cout << std::endl
<< std::endl
<< "Looking for rows CONTAINED by the bounding box ";
printRectangle (boundingBox);
std::cout << std::endl << "There should be 2 rows found" << std::endl;
displayContainedRectangles (db, boundingBox);
/* Do lookups with a bounding box that contains two of the rows in the
* table that use geo coordinates */
boundingBox[0] = 47.655000; /* Min X Value */
boundingBox[1] = 9.481000; /* Min Y Value */
boundingBox[2] = 47.665600; /* Max X Value */
boundingBox[3] = 9.482000; /* Max Y Value */
std::cout << std::endl
<< std::endl
<< "Looking for rows CONTAINED by the bounding box ";
printRectangle (boundingBox);
std::cout << std::endl << "There should be 7 rows found" << std::endl;
displayContainedRectangles (db, boundingBox);
/* Do lookups with a bounding box that doesn't contain rows from
either of the coordinate systems */
boundingBox[0] = 6; /* Min X Value */
boundingBox[1] = 14; /* Min Y Value */
boundingBox[2] = 19; /* Max X Value */
boundingBox[3] = 25; /* Max Y Value */
std::cout << std::endl
<< std::endl
<< "Looking for rows CONTAINED by the bounding box ";
printRectangle (boundingBox);
std::cout << std::endl << "There should be 0 rows found" << std::endl;
displayContainedRectangles (db, boundingBox);
} catch (rdm_exception e)
{
std::cerr << "Database Error: " << e.GetEnum () << " - "
<< e.GetDescription () << std::endl;
}
return 0;
}