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;
152 bool remove(
const te::gm::Envelope& mbr,
const DATATYPE& data, NodeType** root);
170 const DATATYPE& data,
180 std::vector<DATATYPE>& report,
181 int& foundObjs)
const;
199 NodeType** newNode)
const;
209 void splitNode(NodeType* node, BranchType* branch, NodeType** newNode)
const;
211 void getBranches(NodeType* n, BranchType* b, PartitionVarsType& p)
const;
215 void pickSeeds(PartitionVarsType& p)
const;
217 void classify(
int i,
int group, PartitionVarsType& p)
const;
221 void loadNodes(NodeType* n, NodeType* q, PartitionVarsType& p)
const;
230 void erase(NodeType* node);
260 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 269 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 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 298 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 312 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 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 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 356 if(
chooseLeaf(mbr, data, *root, &newNode, level))
364 newRoot->
m_level = (*root)->m_level + 1;
384 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 389 std::vector<NodeType*> reInsertList;
391 if(
remove2(mbr, data, *root, reInsertList))
396 while(!reInsertList.empty())
400 for(i = 0; i < t->
m_count; ++i)
404 reInsertList.erase(reInsertList.begin());
412 if(((*root)->m_count == 1) && ((*root)->isInternalNode()))
428 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 435 for(i = 0; i < n->
m_count; ++i)
459 for(i = 0; i < n->
m_count; ++i)
472 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
481 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
510 else if (node->
m_level == level)
529 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
536 for(i = 0; i < node->
m_count; ++i)
545 for(i = 0; i < node->
m_count; ++i)
551 report.push_back(
id);
561 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
568 for(
int i = 0; i < n->
m_count; ++i)
582 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 590 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 606 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 611 double bestIncr = -1.0;
612 double bestArea = 0.;
615 for(
int i = 0; i < node->
m_count; ++i)
622 double increase = rr.
getArea() - area;
624 if((increase < bestIncr) || flag)
631 else if((increase == bestIncr) && (area < bestArea))
642 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 659 (*newNode)->m_level = node->
m_level = level;
664 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 668 for(
int i = 0; i < MAXNODES; ++i)
678 for(
int i = 1; i <= MAXNODES; ++i)
684 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 692 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 700 int greatestLower[2];
706 greatestLower[0] = leastUpper[0] = 0;
708 for(i = 1; i <= MAXNODES; ++i)
713 greatestLower[0] = i;
725 greatestLower[1] = leastUpper[1] = 0;
727 for(i = 1; i <= MAXNODES; ++i)
732 greatestLower[1] = i;
757 seed0 = leastUpper[0];
758 seed1 = greatestLower[0];
774 if(separation > bestSep)
776 seed0 = leastUpper[1];
777 seed1 = greatestLower[1];
779 bestSep = separation;
789 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 805 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 813 for(
int i = 0; i <= MAXNODES; ++i)
818 if(p.
m_count[0] >= (MAXNODES + 1 - MINNODES))
823 else if(p.
m_count[1] >= (MAXNODES + 1 - MINNODES))
830 for(
int group = 0; group < 2; ++group)
841 newArea[group] = newCover[group].
getArea();
842 increase[group] = newArea[group] - p.
m_area[group];
846 if(increase[0] < increase[1])
848 else if(increase[1] < increase[0])
864 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 867 for(
int i = 0; i <= MAXNODES; ++i)
878 template<
class DATATYPE,
int MAXNODES,
int MINNODES>
inline 887 for(
int i = 0u; i < node->
m_count; ++i)
899 #endif // __TERRALIB_SAM_RTREE_INTERNAL_INDEX_H bool remove(const te::gm::Envelope &mbr, const DATATYPE &data)
It removes an item from the tree.
int m_partition[MAXNODES+1]
Auxiliary partition vector.
void pickSeeds(PartitionVarsType &p) const
NodeType * m_root
Pointer to the root node.
bool intersects(const Envelope &rhs) const
It returns true if the envelopes "spatially intersects".
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 classify(int i, int group, PartitionVarsType &p) const
void disconBranch(NodeType *n, int i)
It disconnects a dependent node.
A class that represents an R-tree.
NodeType::BranchType BranchType
void loadNodes(NodeType *n, NodeType *q, PartitionVarsType &p) const
A class that represents an R-tree node.
te::gm::Envelope nodeCover(NodeType *n) const
Find the smallest rectangle that includes all rectangles in branches of a node.
te::gm::Envelope m_coverSplit
Auxiliary box covering branchBuf.
te::gm::Envelope m_mbr
Bounding box of the tree.
double m_urx
Upper right corner x-coordinate.
void init()
Initializes partition vars.
DATATYPE m_data
An object-identifier (oid).
void init()
This method is used during split when a node retained and used again (beeing re-filled).
te::gm::Envelope combineRect(const te::gm::Envelope &mbrA, const te::gm::Envelope &mbrB) const
Combine two rectangles into larger one containing both.
bool isInternalNode() const
It returns true if this is a internal node.
int m_level
Leaf is zero, others positive.
void Union(const Envelope &rhs)
It updates the envelop with coordinates of another envelope.
double m_area[2]
Auxiliary area of each new page.
void pigeonhole(PartitionVarsType &p) const
int m_count
The number of elements in the node (count).
bool isEmpty(void) const
It returns true if the tree is empty.
double m_llx
Lower left corner x-coordinate.
An Envelope defines a 2D rectangular region.
void setMBR(const te::gm::Envelope &mbr)
It sets the bounding box of all elements in the tree.
double getArea() const
It returns the area of this envelope as measured in the spatial reference system of it...
void methodZero(PartitionVarsType &p) const
BRANCH m_branchBuf[MAXNODES+1]
Auxiliary branch buffer.
te::sam::rtree::PartitionVars< BranchType, MAXNODES > PartitionVarsType
BranchType m_branch[MAXNODES]
Branches.
int search(const te::gm::Envelope &mbr, std::vector< DATATYPE > &report) const
Range search query.
std::size_t m_size
The size of R-Tree (number of nodes).
bool isLeaf() const
It returns true if this is a leaf node.
te::gm::Envelope m_mbr
Bounding box containing all the objects under the branch or an object bounding box.
Index & operator=(const Index &rhs)
No assignment operator allowed.
bool addBranch(BranchType *branch, NodeType *node, NodeType **newNode) const
Add a branch to a node.
double m_lly
Lower left corner y-coordinate.
void erase(NodeType *node)
Erases a node from the tree and all nodes below it.
const te::gm::Envelope & getMBR(void) const
It returns the bounding box of all elements in the tree.
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.
std::size_t size(void) const
It returns the number of elements in the tree.
int m_count[2]
Number of entries in each new page.
int pickBranch(const te::gm::Envelope &mbr, NodeType *node) const
Pick a branch.
void getBranches(NodeType *n, BranchType *b, PartitionVarsType &p) const
te::gm::Envelope m_cover[2]
Auxiliary box of each new page.
int m_taken[MAXNODES+1]
Flag to indicate that entry is ok.
NODE * m_child
A pointer to the child node.
Auxiliary structure when searching for a split partition.
Node< DATATYPE, MAXNODES, MINNODES > NodeType
bool isValid() const
It tells if the rectangle is valid or not.
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.