Go to the documentation of this file.
26 #ifndef __TERRALIB_SAM_RTREE_INTERNAL_INDEX_H
27 #define __TERRALIB_SAM_RTREE_INTERNAL_INDEX_H
56 template<
class DATATYPE,
int MAXNODES = 8,
int MINNODES = MAXNODES / 2>
class Index
84 std::size_t
size(
void)
const;
170 const DATATYPE& data,
180 std::vector<DATATYPE>& report,
181 int& foundObjs)
const;
260 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
262 : m_root(0), m_size(0)
269 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
271 : m_root(0), m_mbr(mbr), m_size(0)
279 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
286 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
292 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
295 return (m_root->m_count == 0);
298 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
312 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
315 insert(mbr, data, &m_root, 0);
319 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
322 return remove(mbr, data, &m_root);
325 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
331 search(mbr, m_root, report, foundObjs);
336 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
342 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
348 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
354 if(chooseLeaf(mbr, data, *root, &newNode, level))
362 newRoot->
m_level = (*root)->m_level + 1;
366 branch.
m_mbr = nodeCover(*root);
368 addBranch(&branch, newRoot, 0);
371 branch.
m_mbr = nodeCover(newNode);
373 addBranch(&branch, newRoot, 0);
383 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
387 std::vector<NodeType*> reInsertList;
389 if(remove2(mbr, data, *root, reInsertList))
394 while(!reInsertList.empty())
398 for(
int i = 0; i < t->
m_count; ++i)
402 reInsertList.erase(reInsertList.begin());
410 if(((*root)->m_count == 1) && ((*root)->isInternalNode()))
426 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
433 for(i = 0; i < n->
m_count; ++i)
457 for(i = 0; i < n->
m_count; ++i)
470 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
479 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
485 int i = pickBranch(mbr, node);
502 b.
m_mbr = nodeCover(n2);
504 return addBranch(&b, node, newNode);
507 else if (node->
m_level == level)
516 return addBranch(&b, node, newNode);
526 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
533 for(i = 0; i < node->
m_count; ++i)
542 for(i = 0; i < node->
m_count; ++i)
547 report.push_back(
id);
557 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
564 for(
int i = 0; i < n->
m_count; ++i)
578 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
586 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
597 splitNode(node, branch, newNode);
602 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
607 double bestIncr = -1.0;
608 double bestArea = 0.;
611 for(
int i = 0; i < node->
m_count; ++i)
616 rr = combineRect(mbr, rr);
618 double increase = rr.
getArea() - area;
620 if((increase < bestIncr) || flag)
627 else if((increase == bestIncr) && (area < bestArea))
638 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
646 getBranches(node, branch, partitions);
649 methodZero(partitions);
655 (*newNode)->m_level = node->
m_level = level;
657 loadNodes(node, *newNode, partitions);
660 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
664 for(
int i = 0; i < MAXNODES; ++i)
674 for(
int i = 1; i <= MAXNODES; ++i)
680 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
688 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
696 int greatestLower[2];
702 greatestLower[0] = leastUpper[0] = 0;
704 for(i = 1; i <= MAXNODES; ++i)
709 greatestLower[0] = i;
721 greatestLower[1] = leastUpper[1] = 0;
723 for(i = 1; i <= MAXNODES; ++i)
728 greatestLower[1] = i;
753 seed0 = leastUpper[0];
754 seed1 = greatestLower[0];
770 if(separation > bestSep)
772 seed0 = leastUpper[1];
773 seed1 = greatestLower[1];
775 bestSep = separation;
780 classify(seed0, 0, p);
781 classify(seed1, 1, p);
785 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
801 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
809 for(
int i = 0; i <= MAXNODES; ++i)
814 if(p.
m_count[0] >= (MAXNODES + 1 - MINNODES))
819 else if(p.
m_count[1] >= (MAXNODES + 1 - MINNODES))
826 for(
int group = 0; group < 2; ++group)
837 newArea[group] = newCover[group].
getArea();
838 increase[group] = newArea[group] - p.
m_area[group];
842 if(increase[0] < increase[1])
844 else if(increase[1] < increase[0])
860 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
863 for(
int i = 0; i <= MAXNODES; ++i)
874 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline
883 for(
int i = 0u; i < node->
m_count; ++i)
895 #endif // __TERRALIB_SAM_RTREE_INTERNAL_INDEX_H
An Envelope defines a 2D rectangular region.
const te::gm::Envelope & getMBR(void) const
It returns the bounding box of all elements in the tree.
bool isValid() const
It tells if the rectangle is valid or not.
void splitNode(NodeType *node, BranchType *branch, NodeType **newNode) const
Split a node.
bool chooseLeaf(const te::gm::Envelope &mbr, const DATATYPE &data, NodeType *node, NodeType **newNode, int level)
It inserts a new data rectangle into the index structure.
void pigeonhole(PartitionVarsType &p) const
A class that represents an R-tree.
int m_count
The number of elements in the node (count).
double getArea() const
It returns the area of this envelope as measured in the spatial reference system of it.
bool isInternalNode() const
It returns true if this is a internal node.
void disconBranch(NodeType *n, int i)
It disconnects a dependent node.
int m_level
Leaf is zero, others positive.
te::gm::Envelope combineRect(const te::gm::Envelope &mbrA, const te::gm::Envelope &mbrB) const
Combine two rectangles into larger one containing both.
Node< DATATYPE, MAXNODES, MINNODES > NodeType
void methodZero(PartitionVarsType &p) const
double m_llx
Lower left corner x-coordinate.
std::size_t size(void) const
It returns the number of elements in the tree.
void init()
This method is used during split when a node retained and used again (beeing re-filled).
Index & operator=(const Index &rhs)
No assignment operator allowed.
void Union(const Envelope &rhs)
It updates the envelop with coordinates of another envelope.
bool insert(const te::gm::Envelope &mbr, const DATATYPE &data, NodeType **root, int level)
It inserts a data rectangle into an index structure.
Auxiliary structure when searching for a split partition.
DATATYPE m_data
An object-identifier (oid).
te::sam::rtree::PartitionVars< BranchType, MAXNODES > PartitionVarsType
double m_area[2]
Auxiliary area of each new page.
void pickSeeds(PartitionVarsType &p) const
A class that represents an R-tree node.
bool remove(const te::gm::Envelope &mbr, const DATATYPE &data)
It removes an item from the tree.
double m_urx
Upper right corner x-coordinate.
void search(const te::gm::Envelope &mbr, NodeType *node, std::vector< DATATYPE > &report, int &foundObjs) const
Recursive range query.
NodeType * m_root
Pointer to the root node.
bool remove2(const te::gm::Envelope &mbr, const DATATYPE &data, NodeType *n, std::vector< NodeType * > &ee)
It deletes a rectangle from non-root part of an index structure.
bool remove(const te::gm::Envelope &mbr, const DATATYPE &data, NodeType **root)
It deletes a data rectangle from an index structure.
NodeType
The type of node read by XML reader.
mydialect insert("+", new te::da::BinaryOpEncoder("+"))
void erase(NodeType *node)
Erases a node from the tree and all nodes below it.
Index(const te::gm::Envelope &mbr)
Constructor.
A class that represents an R-tree node.
double m_lly
Lower left corner y-coordinate.
te::gm::Envelope nodeCover(NodeType *n) const
Find the smallest rectangle that includes all rectangles in branches of a node.
bool addBranch(BranchType *branch, NodeType *node, NodeType **newNode) const
Add a branch to a node.
int search(const te::gm::Envelope &mbr, std::vector< DATATYPE > &report) const
Range search query.
te::gm::Envelope m_mbr
Bounding box containing all the objects under the branch or an object bounding box.
NodeType::BranchType BranchType
bool isLeaf() const
It returns true if this is a leaf node.
void getBranches(NodeType *n, BranchType *b, PartitionVarsType &p) const
te::gm::Envelope m_coverSplit
Auxiliary box covering branchBuf.
bool isEmpty(void) const
It returns true if the tree is empty.
te::gm::Envelope m_mbr
Bounding box of the tree.
void classify(int i, int group, PartitionVarsType &p) const
te::gm::Envelope m_cover[2]
Auxiliary box of each new page.
BranchType m_branch[MAXNODES]
Branches.
int m_count[2]
Number of entries in each new page.
int m_taken[MAXNODES+1]
Flag to indicate that entry is ok.
void insert(const te::gm::Envelope &mbr, const DATATYPE &data)
It inserts an item into the tree.
double m_ury
Upper right corner y-coordinate.
bool intersects(const Envelope &rhs) const
It returns true if the envelopes "spatially intersects".
Index(const Index &rhs)
No copy constructor allowed.
int pickBranch(const te::gm::Envelope &mbr, NodeType *node) const
Pick a branch.
NODE * m_child
A pointer to the child node.
void init()
Initializes partition vars.
BRANCH m_branchBuf[MAXNODES+1]
Auxiliary branch buffer.
void setMBR(const te::gm::Envelope &mbr)
It sets the bounding box of all elements in the tree.
std::size_t m_size
The size of R-Tree (number of nodes).
int m_partition[MAXNODES+1]
Auxiliary partition vector.
void loadNodes(NodeType *n, NodeType *q, PartitionVarsType &p) const