[Boost-commit] svn:boost r84210 - in trunk/libs/geometry: doc/html/img/index/rtree doc/index/rtree index/example

Subject: [Boost-commit] svn:boost r84210 - in trunk/libs/geometry: doc/html/img/index/rtree doc/index/rtree index/example
From: adam.wulkiewicz_at_[hidden]
Date: 2013-05-09 14:25:29

Author: awulkiew
Date: 2013-05-09 14:25:28 EDT (Thu, 09 May 2013)
New Revision: 84210
URL: http://svn.boost.org/trac/boost/changeset/84210

Log:
geometry.index docs, example: Added path query description in 'Experimental features' section. Added path query to benchmark_experimental and glut_vis.
Added:
   trunk/libs/geometry/doc/html/img/index/rtree/path.png   (contents, props changed)
Text files modified: 
   trunk/libs/geometry/doc/index/rtree/experimental.qbk         |    16 ++++++++                                
   trunk/libs/geometry/index/example/benchmark_experimental.cpp |    33 +++++++++++++++++-                      
   trunk/libs/geometry/index/example/glut_vis.cpp               |    67 ++++++++++++++++++++++++++++++++++++++- 
   3 files changed, 109 insertions(+), 7 deletions(-)

Added: trunk/libs/geometry/doc/html/img/index/rtree/path.png
==============================================================================
Binary file. No diff available.

Modified: trunk/libs/geometry/doc/index/rtree/experimental.qbk
==============================================================================
--- trunk/libs/geometry/doc/index/rtree/experimental.qbk	(original)
+++ trunk/libs/geometry/doc/index/rtree/experimental.qbk	2013-05-09 14:25:28 EDT (Thu, 09 May 2013)
@@ -31,12 +31,26 @@
  /* caluclate distance to the Indexables' furthest points */
  rtree.query(index::nearest(index::to_furthest(pt), k), std::back_inserter(returned_values));
 
+[heading Path query]
+
+Path query returns `k` first `__value__`s intersecting a path defined by a `Linestring`. Query returning first 5
+values intersecting a path is presented below. Path's flow is denoted by blue arrows, returned values are orange.
+
+[$img/index/rtree/path.png]
+ 
+To perform this query one may pass a `path()` predicate taking a `Linestring` and maximum number of `__value__`s which
+should be returned:
+
+ rtree.query(index::path(linestring, k), std::back_inserter(returned_values));
+
+[warning Only one distance predicate may be used in a query. This means that there can be only one `nearest()` or `path()` predicate passed. Passing more of them will result in compile-time error.]
+
 [heading Incremental queries]
 
 Sometimes there is a need to brake querying at some desired point because it depends on objects already
 returned or to pause it in order to resume later. For this purpose iterators may be used.
 
-In this library incremental queries are implemented as input (single pass) const iterators, relatively
+Currently incremental queries are implemented as input (single pass) const iterators, relatively
 big fat-iterators storing stack used in the tree-traversing process. Because the type of predicates passed
 to the query varies, the type of the iterator varies as well.
 

Modified: trunk/libs/geometry/index/example/benchmark_experimental.cpp
==============================================================================
--- trunk/libs/geometry/index/example/benchmark_experimental.cpp	(original)
+++ trunk/libs/geometry/index/example/benchmark_experimental.cpp	2013-05-09 14:25:28 EDT (Thu, 09 May 2013)
@@ -17,12 +17,14 @@
 #include <boost/random.hpp>
 
 #include <boost/geometry/index/rtree.hpp>
+#include <boost/geometry/geometries/linestring.hpp>
 
 namespace bg = boost::geometry;
 namespace bgi = bg::index;
 
 typedef bg::model::point<double, 2, bg::cs::cartesian> P;
 typedef bg::model::box<P> B;
+typedef bg::model::linestring<P> LS;
 
 template <typename I1, typename I2, typename O>
 void mycopy(I1 first, I2 last, O o)
@@ -40,14 +42,16 @@
     size_t queries_count = 100000;
     size_t nearest_queries_count = 10000;
     unsigned neighbours_count = 10;
+    size_t path_queries_count = 1000;
+    unsigned path_values_count = 10;
 
+    float max_val = static_cast<float>(values_count / 2);
     std::vector< std::pair<float, float> > coords;
 
     //randomize values
     {
         boost::mt19937 rng;
         //rng.seed(static_cast<unsigned int>(std::time(0)));
-        float max_val = static_cast<float>(values_count / 2);
         boost::uniform_real<float> range(-max_val, max_val);
         boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
 
@@ -242,7 +246,7 @@
         {
             clock_t::time_point start = clock_t::now();
             size_t temp = 0;
-            for (size_t i = 0 ; i < queries_count ; ++i )
+            for (size_t i = 0 ; i < nearest_queries_count ; ++i )
             {
                 float x = coords[i].first;
                 float y = coords[i].second;
@@ -256,9 +260,32 @@
             std::cout << time << " - type-erased qbegin(nearest(P, " << neighbours_count << ")) qend(n) " << nearest_queries_count << " found " << temp << '\n';
         }
 #endif
-#endif
 
         {
+            LS ls;
+            ls.resize(6);
+            
+            clock_t::time_point start = clock_t::now();
+            size_t temp = 0;
+            for (size_t i = 0 ; i < path_queries_count ; ++i )
+            {
+                float x = coords[i].first;
+                float y = coords[i].second;
+                for ( int i = 0 ; i < 3 ; ++i )
+                {
+                    float foo = i*max_val/300;
+                    ls[2*i] = P(x, y+foo);
+                    ls[2*i+1] = P(x+max_val/100, y+foo);
+                }                
+                result.clear();
+                t.query(bgi::path(ls, path_values_count), std::back_inserter(result));
+                temp += result.size();
+            }
+            dur_t time = clock_t::now() - start;
+            std::cout << time << " - query(path(LS, " << path_values_count << ")) " << path_queries_count << " found " << temp << '\n';
+        }
+#endif
+        {
             clock_t::time_point start = clock_t::now();
             for (size_t i = 0 ; i < values_count / 10 ; ++i )
             {

Modified: trunk/libs/geometry/index/example/glut_vis.cpp
==============================================================================
--- trunk/libs/geometry/index/example/glut_vis.cpp	(original)
+++ trunk/libs/geometry/index/example/glut_vis.cpp	2013-05-09 14:25:28 EDT (Thu, 09 May 2013)
@@ -15,6 +15,7 @@
 
 #include <boost/geometry/index/rtree.hpp>
 
+#include <boost/geometry/geometries/linestring.hpp>
 #include <boost/geometry/geometries/ring.hpp>
 #include <boost/geometry/geometries/polygon.hpp>
 #include <boost/geometry/multi/geometries/multi_polygon.hpp>
@@ -30,6 +31,7 @@
 typedef bg::model::point<float, 2, boost::geometry::cs::cartesian> P;
 typedef bg::model::box<P> B;
 //bgi::rtree<B> t(2, 1);
+typedef bg::model::linestring<P> LS;
 typedef bg::model::ring<P> R;
 typedef bg::model::polygon<P> Poly;
 typedef bg::model::multi_polygon<Poly> MPoly;
@@ -48,14 +50,15 @@
 R search_ring;
 Poly search_poly;
 MPoly search_multi_poly;
+LS search_path;
 
 enum query_mode_type {
-    qm_knn, qm_c, qm_d, qm_i, qm_o, qm_w, qm_nc, qm_nd, qm_ni, qm_no, qm_nw, qm_all, qm_ri, qm_pi, qm_mpi
+    qm_knn, qm_c, qm_d, qm_i, qm_o, qm_w, qm_nc, qm_nd, qm_ni, qm_no, qm_nw, qm_all, qm_ri, qm_pi, qm_mpi, qm_path
 } query_mode = qm_knn;
 
 bool search_valid = false;
 
-void knn()
+void query_knn()
 {
     float x = ( rand() % 1000 ) / 10.0f;
     float y = ( rand() % 1000 ) / 10.0f;
@@ -82,6 +85,43 @@
         std::cout << "nearest not found\n";
 }
 
+void query_path()
+{
+    float x = ( rand() % 1000 ) / 10.0f;
+    float y = ( rand() % 1000 ) / 10.0f;
+    float w = 20 + ( rand() % 1000 ) / 100.0f;
+    float h = 20 + ( rand() % 1000 ) / 100.0f;
+
+    search_path.resize(10);
+    float yy = y-h;
+    for ( int i = 0 ; i < 5 ; ++i, yy += h / 2 )
+    {
+        search_path[2 * i] = P(x-w, yy);
+        search_path[2 * i + 1] = P(x+w, yy);
+    }
+        
+    nearest_boxes.clear();
+    found_count = t.query(
+        bgi::detail::path<LS>(search_path, count),
+        std::back_inserter(nearest_boxes)
+        );
+
+    if ( found_count > 0 )
+    {
+        std::cout << "search path: ";
+        BOOST_FOREACH(P const& p, search_path)
+            bgi::detail::rtree::visitors::detail::print_indexable(std::cout, p);
+        std::cout << "\nfound: ";
+        for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
+        {
+            bgi::detail::rtree::visitors::detail::print_indexable(std::cout, nearest_boxes[i]);
+            std::cout << '\n';
+        }
+    }
+    else
+        std::cout << "values on path not found\n";
+}
+
 template <typename Predicate>
 void query()
 {
@@ -298,7 +338,7 @@
 void search()
 {
     if ( query_mode == qm_knn )
-        knn();
+        query_knn();
     else if ( query_mode == qm_c )
         query< bgi::detail::covered_by<B> >();
     else if ( query_mode == qm_d )
@@ -327,6 +367,8 @@
         query_poly< bgi::detail::intersects<Poly> >();
     else if ( query_mode == qm_mpi )
         query_multi_poly< bgi::detail::intersects<MPoly> >();
+    else if ( query_mode == qm_path )
+        query_path();
 
     search_valid = true;
 }
@@ -359,6 +401,21 @@
     glEnd();
 }
 
+void draw_path(LS const& ls)
+{
+    glBegin(GL_LINE_STRIP);
+
+    BOOST_FOREACH(P const& p, ls)
+    {
+        float x = boost::geometry::get<0>(p);
+        float y = boost::geometry::get<1>(p);
+        float z = t.depth();
+        glVertex3f(x, y, z);
+    }
+
+    glEnd();
+}
+
 template <typename Box>
 void draw_box(Box const& box)
 {
@@ -428,6 +485,8 @@
             draw_polygon(search_poly);
         else if ( query_mode == qm_mpi )
             draw_multi_polygon(search_multi_poly);
+        else if ( query_mode == qm_path )
+            draw_path(search_path);
         else
             draw_box(search_box);
 
@@ -591,6 +650,8 @@
                 query_mode = qm_pi;
             else if ( current_line == "mpi" )
                 query_mode = qm_mpi;
+            else if ( current_line == "path" )
+                query_mode = qm_path;
             
             search();
             glutPostRedisplay();