[mlpack-git] master,mlpack-1.0.x: more R Tree stuff (245182b)

[gitdub at big.cc.gt.atl.ga.us]

Repository : https://github.com/mlpack/mlpack

On branches: master,mlpack-1.0.x
Link       : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40

>---------------------------------------------------------------

commit 245182b6532adbcda97f05ee7e068e3a0630b65c
Author: andrewmw94 <andrewmw94 at gmail.com>
Date:   Fri May 30 12:04:44 2014 +0000

    more R Tree stuff


>---------------------------------------------------------------

245182b6532adbcda97f05ee7e068e3a0630b65c
 .../core/tree/rectangle_tree/r_tree_split.hpp      | 25 +++++++++++
 .../core/tree/rectangle_tree/r_tree_split_impl.hpp | 49 ++++++++++++++++++++++
 2 files changed, 74 insertions(+)

diff --git a/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp b/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp
index e2786fb..85a3687 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_tree_split.hpp
@@ -36,6 +36,31 @@ private:
  */
 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
diff --git a/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp b/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
index 389553a..d182fec 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_tree_split_impl.hpp
@@ -15,6 +15,22 @@ namespace tree {
 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;
+
+  
   
 }
 
@@ -23,6 +39,39 @@ bool RTreeSplit<MatType>::SplitNonLeafNode(const RectangleTree& tree)
 
 }
 
+/**
+ * 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