added useless LASkdtreePoint after four weeks of memoy pain in Samara

Martin Isenburg · Martin Isenburg · commit 3c55459d741a · 2021-06-27T01:21:05.000+02:00
diff --git a/LASlib/inc/laskdtree.hpp b/LASlib/inc/laskdtree.hpp
@@ -5,15 +5,16 @@
   
   CONTENTS:
   
-    Tree structure for fast overlap checks of rectangles with list of rectangles 
+    Tree structure for fast overlap checks of points or rectangles with list
+    of rectangles 
 
   PROGRAMMERS:
 
     martin.isenburg@rapidlasso.com - http://rapidlasso.com
 
   COPYRIGHT:
 
-    (c) 2007-2019, martin isenburg, rapidlasso - fast tools to catch reality
+    (c) 2007-2021, martin isenburg, rapidlasso - fast tools to catch reality
 
     This is free software; you can redistribute and/or modify it under the
     terms of the GNU Lesser General Licence as published by the Free Software
@@ -24,6 +25,7 @@
   
   CHANGE HISTORY:
   
+    26 June 2021 -- new LASkdtreePoint after four weeks of memoy pain in Samara
     26 October 2019 -- created at LoCoworking after three days of rain in Samara
   
 ===============================================================================
@@ -56,6 +58,17 @@ class LASkdtreeRectangle
   LASkdtreeRectangle(F64 min_x, F64 min_y, F64 max_x, F64 max_y, U32 index);
 };
 
+class LASkdtreePoint
+{
+public:
+  F64 pos[2];
+
+  BOOL overlap(const LASkdtreeRectangle &rectangle) const;
+
+  LASkdtreePoint();
+  LASkdtreePoint(F64 x, F64 y);
+};
+
 typedef list<LASkdtreeRectangle> my_rectangle_list;
 
 class LASkdtreeRectanglesNode
@@ -77,7 +90,8 @@ class LASkdtreeRectangles
   void add(F64 min_x, F64 min_y, F64 max_x, F64 max_y);
   BOOL build();
   BOOL was_built() const;
-  BOOL overlap(F64 min_x, F64 min_y, F64 max_x, F64 max_y);
+  BOOL overlap(F64 min_x, F64 min_y, F64 max_x, F64 max_y); // rectangle
+  BOOL overlap(F64 x, F64 y);                               // point
   void print_overlap();
   BOOL has_overlaps();
   BOOL get_overlap(U32& index);
@@ -93,6 +107,7 @@ class LASkdtreeRectangles
 
   void build_recursive(LASkdtreeRectanglesNode* node, I32 plane, LASkdtreeRectangle bb, my_rectangle_list* insertion_list, I32 unchanged);
   void overlap_rectangles(LASkdtreeRectanglesNode* node, I32 plane, LASkdtreeRectangle rectangle, my_index_set* overlap_set);
+  void overlap_rectangles(LASkdtreeRectanglesNode* node, I32 plane, LASkdtreePoint point, my_index_set* overlap_set);
 };
 
 #endif
diff --git a/LASlib/src/laskdtree.cpp b/LASlib/src/laskdtree.cpp
@@ -69,6 +69,27 @@ LASkdtreeRectangle::LASkdtreeRectangle()
   idx = 0;
 }
 
+BOOL LASkdtreePoint::overlap(const LASkdtreeRectangle &rectangle) const
+{
+  if (pos[0] < rectangle.min[0]) return FALSE;
+  if (pos[1] < rectangle.min[1]) return FALSE;
+  if (rectangle.max[0] < pos[0]) return FALSE;
+  if (rectangle.max[1] < pos[1]) return FALSE;
+  return TRUE;
+}
+
+LASkdtreePoint::LASkdtreePoint(F64 x, F64 y)
+{
+  pos[0] = x;
+  pos[1] = y;
+}
+
+LASkdtreePoint::LASkdtreePoint()
+{
+  pos[0] = 0;
+  pos[1] = 0;
+}
+
 LASkdtreeRectanglesNode::LASkdtreeRectanglesNode()
 {
   left = 0;
@@ -164,6 +185,18 @@ BOOL LASkdtreeRectangles::overlap(F64 min_x, F64 min_y, F64 max_x, F64 max_y)
   return TRUE;
 }
 
+BOOL LASkdtreeRectangles::overlap(F64 x, F64 y)
+{
+  if (overlap_set == 0)
+  {
+    return FALSE;
+  }
+  overlap_set->clear();
+  LASkdtreePoint point(x, y);
+  overlap_rectangles(root, 0, point, overlap_set);
+  return TRUE;
+}
+
 BOOL LASkdtreeRectangles::has_overlaps()
 {
   if (overlap_set && overlap_set->size())
@@ -324,6 +357,45 @@ void LASkdtreeRectangles::overlap_rectangles(LASkdtreeRectanglesNode* node, I32
   }
 }
 
+void LASkdtreeRectangles::overlap_rectangles(LASkdtreeRectanglesNode* node, I32 plane, LASkdtreePoint point, my_index_set* overlap_set)
+{
+  if (node->list)
+  {
+    my_rectangle_list::iterator list_element = node->list->begin();
+    while (TRUE)
+    {
+      if (list_element == node->list->end())
+      {
+        break;
+      }
+
+      LASkdtreeRectangle overlap_candidate = (*list_element);
+
+      if (point.overlap(overlap_candidate))
+      {
+        overlap_set->insert(overlap_candidate.idx);
+      }
+      list_element++;
+    }
+  }
+  else
+  {
+    // maybe recurse left
+
+    if (point.pos[plane] < node->split)
+    {
+      overlap_rectangles(node->left, (plane + 1) % 2, point, overlap_set);
+    }
+
+    // maybe recurse right
+    
+    if (node->split <= point.pos[plane])
+    {
+      overlap_rectangles(node->right, (plane + 1) % 2, point, overlap_set);
+    }
+  }
+}
+
 void LASkdtreeRectangles::print_overlap()
 {
   fprintf(stderr, "overlap elements: %u\n", (U32)overlap_set->size());
