From 658708520d88e48f914a28e86748821974b0b09d Mon Sep 17 00:00:00 2001
From: Peter Clifton <pcjc2@cam.ac.uk>
Date: Mon, 13 Oct 2008 19:21:19 +0000
Subject: [PATCH] Check all r-tree node children for fit before working out
 penalties

Working out the penalty involves multiplications which produce a
"long long" result, and is seen to be appear in profiling.

Make a pass at testing all children for the fast case of the child
node containing the desired box, before working out size penalties
to expanding each child.
---
 src/rtree.c | 76 ++++++++++++++++++++++++++++++++++---------------------------
 1 file changed, 43 insertions(+), 33 deletions(-)

diff --git a/src/rtree.c b/src/rtree.c
index fec72bc1..1f205855 100644
--- a/src/rtree.c
+++ b/src/rtree.c
@@ -868,27 +868,32 @@ split_node (struct rtree_node *node)
   split_node (node->parent);
 }
 
-static inline bigun
-penalty (struct rtree_node *node, const BoxType * query)
+static inline int
+contained (struct rtree_node *node, const BoxType * query)
 {
   if (node->box.X1 > query->X1 || node->box.X2 < query->X2 ||
       node->box.Y1 > query->Y1 || node->box.Y2 < query->Y2)
-    {
-      long long score;
-      /* We're not already contained at this node, so compute
-       * the area penalty for inserting here and return.
-       * The penalty is the increase in area necessary
-       * to include the query->
-       */
-      score = (MAX (node->box.X2, query->X2) - MIN (node->box.X1, query->X1));
-      score *=
-        (MAX (node->box.Y2, query->Y2) - MIN (node->box.Y1, query->Y1));
-      score -=
-        ((long long) node->box.X2 -
-         node->box.X1) * ((long long) node->box.Y2 - node->box.Y1);
-      return score;
-    }
-  return 0;
+    return 0;
+  return 1;
+}
+
+
+static inline bigun
+penalty (struct rtree_node *node, const BoxType * query)
+{
+  long long score;
+
+  /* Compute the area penalty for inserting here and return.
+   * The penalty is the increase in area necessary
+   * to include the query->
+   */
+  score = (MAX (node->box.X2, query->X2) - MIN (node->box.X1, query->X1));
+  score *=
+    (MAX (node->box.Y2, query->Y2) - MIN (node->box.Y1, query->Y1));
+  score -=
+    ((long long) node->box.X2 -
+     node->box.X1) * ((long long) node->box.Y2 - node->box.Y1);
+  return score;
 }
 
 static void
@@ -961,31 +966,23 @@ __r_insert_node (struct rtree_node *node, const BoxType * query,
           MAKEMIN (node->box.Y1, query->Y1);
           MAKEMAX (node->box.Y2, query->Y2);
         }
+
       /* this node encloses it, but it's not a leaf, so descend the tree */
+
+      /* First check if any children actually encloses it */
       assert (node->u.kids[0]);
-      if ((best_score = penalty (node->u.kids[0], query)) == 0)
-        {
-          __r_insert_node (node->u.kids[0], query, manage, False);
-          sort_node (node);
-          return;
-        }
-      best_node = node->u.kids[0];
-      for (i = 1; i < M_SIZE; i++)
+      for (i = 0; i < M_SIZE; i++)
         {
           if (!node->u.kids[i])
             break;
-          if ((score = penalty (node->u.kids[i], query)) == 0)
+          if (contained (node->u.kids[i], query))
             {
               __r_insert_node (node->u.kids[i], query, manage, False);
               sort_node (node);
               return;
             }
-          else if (score < best_score)
-            {
-              best_score = score;
-              best_node = node->u.kids[i];
-            }
         }
+
       /* see if there is room for a new leaf node */
       if (node->u.kids[0]->flags.is_leaf && i < M_SIZE)
         {
@@ -1003,7 +1000,20 @@ __r_insert_node (struct rtree_node *node, const BoxType * query,
           return;
         }
 
-      /* didn't find an enclosure, so use the best one */
+      /* Ok, so we're still here - look for the best child to push it into */
+      best_score = penalty (node->u.kids[0], query);
+      best_node = node->u.kids[0];
+      for (i = 1; i < M_SIZE; i++)
+        {
+          if (!node->u.kids[i])
+            break;
+          score = penalty (node->u.kids[i], query);
+          if (score < best_score)
+            {
+              best_score = score;
+              best_node = node->u.kids[i];
+            }
+        }
       __r_insert_node (best_node, query, manage, True);
       sort_node (node);
       return;
-- 
2.11.4.GIT