[mlpack-svn] r16581 - mlpack/trunk/src/mlpack/core/tree/rectangle_tree

[fastlab-svn at coffeetalk-1.cc.gatech.edu]

Author: andrewmw94
Date: Fri May 30 08:04:44 2014
New Revision: 16581

Log:
more R Tree stuff

Modified:
   mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp
   mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp

Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp	Fri May 30 08:04:44 2014
@@ -36,6 +36,31 @@
  */
 static bool SplitNonLeafNode(const RectangleTree& tree);
 
+/**
+ * Get the seeds for splitting a leaf node.
+ */
+static void GetPointSeeds(const RectangleTree& tree, int &i, int &j);
+
+/**
+ * Get the seeds for splitting a non-leaf node.
+ */
+static void GetBoundSeeds(const RectangleTree& tree, int &i, int &j);
+
+/**
+ * Get the index of the tree 
+ */
+static int GetPointDestNode(
+    const RectangleTree& oldTree,
+    const RectangleTree& treeOne,
+    const RectangleTree& treeTwo,
+    const int index);
+
+static int GetBoundDestNode(
+    const RectangleTree& oldTree,
+    const RectangleTree& treeOne,
+    const RectangleTree& treeTwo,
+    const int index);
+
 };
 
 }; // namespace tree

Modified: mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
==============================================================================
--- mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp	(original)
+++ mlpack/trunk/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp	Fri May 30 08:04:44 2014
@@ -15,7 +15,23 @@
 template<typename MatType>
 bool RTreeSplit<MatType>::SplitLeafNode(const RectangleTree& tree)
 {
+  // Use the quadratic split method from: Guttman "R-Trees: A Dynamic Index Structure for
+  // Spatial Searching"  It is simplified since we don't handle rectangles, only points.
+  // It assumes that the tree uses Euclidean Distance.
+  int i = 0;
+  int j = 0;
+  GetPointSeeds(tree, &i, &j);
 
+  RectangleTree treeOne = new RectangleTree();
+  treeOne.insertPoint(tree.points[i]);
+  RectangleTree treeTwo = new RectangleTree();
+  treeTwo.insertPoint(tree.points[j]);
+
+  int treeOneCount = 1;
+  int treeTwoCount = 1;
+
+  
+  
 }
 
 bool RTreeSplit<MatType>::SplitNonLeafNode(const RectangleTree& tree)
@@ -23,6 +39,39 @@
 
 }
 
+/**
+ * Get the two points that will be used as seeds for the split of a leaf node.
+ * The indices of these points will be stored in iRet and jRet.
+ */
+void RTreeSplit<MatType>::GetPointSeeds(const RectangleTree& tree, int* iRet, int* jRet)
+{
+  // Here we want to find the pair of points that it is worst to place in the same
+  // node.  Because we are just using points, we will simply choose the two that would
+  // create the most voluminous hyperrectangle.
+  double worstPairScore = 0.0;
+  int worstI = 0;
+  int worstJ = 0;
+  for(int i = 0; i < tree.count; i++) {
+    for(int j = i; j < tree.count; j++) {
+      double score = 1.0;
+      for(int k = 0; k < dimensions; k++) {
+	score *= std::abs(tree.points[i][k] - tree.points[j][k]);
+      }
+      if(score > worstPairScore) {
+	worstPairScore = score;
+	worstI = i;
+	worstJ = j;
+      }
+    }
+  }
+
+  *iRet = i;
+  *jRet = j;
+  return;
+}
+
+
+
 }; // namespace tree
 }; // namespace mlpack