Subject: [Boost-commit] svn:boost r81907 - in sandbox-branches/geometry/index: doc/html doc/html/geometry_index/r_tree doc/images doc/rtree tests
From: adam.wulkiewicz_at_[hidden]
Date: 2012-12-13 13:39:32
Author: awulkiew
Date: 2012-12-13 13:39:31 EST (Thu, 13 Dec 2012)
New Revision: 81907
URL: http://svn.boost.org/trac/boost/changeset/81907
Log:
Info about spatial predicates using Ring and Polygon added in docs.
Ring and Polygon queries added to GLUT Vis test.
Added:
sandbox-branches/geometry/index/doc/images/intersects_poly.png (contents, props changed)
sandbox-branches/geometry/index/doc/images/intersects_ring.png (contents, props changed)
Text files modified:
sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html | 50 +++++++++--
sandbox-branches/geometry/index/doc/html/index.html | 2
sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk | 15 ++-
sandbox-branches/geometry/index/tests/additional_glut_vis.cpp | 169 +++++++++++++++++++++++++++++++++++++++
4 files changed, 217 insertions(+), 19 deletions(-)
Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html 2012-12-13 13:39:31 EST (Thu, 13 Dec 2012)
@@ -43,8 +43,8 @@
which meets some predicates. For instance it may be used to retrieve Values
intersecting some area or are within some other area. Names of predicates
corresponds to names of Boost.Geometry
- algorithms. The examples of some basic queries may be found in the table
- below. The query region and result <code class="computeroutput"><span class="identifier">Value</span></code>s
+ algorithms. The examples of some basic queries may be found in tables below.
+ The query region and result <code class="computeroutput"><span class="identifier">Value</span></code>s
are orange.
</p>
<div class="informaltable"><table class="table">
@@ -58,27 +58,27 @@
<thead><tr>
<th>
<p>
- intersects (default)
+ intersects(Box) - default
</p>
</th>
<th>
<p>
- covered_by
+ covered_by(Box)
</p>
</th>
<th>
<p>
- disjoint
+ disjoint(Box)
</p>
</th>
<th>
<p>
- overlaps
+ overlaps(Box)
</p>
</th>
<th>
<p>
- within
+ within(Box)
</p>
</th>
</tr></thead>
@@ -110,6 +110,36 @@
</td>
</tr></tbody>
</table></div>
+<div class="informaltable"><table class="table">
+<colgroup>
+<col>
+<col>
+</colgroup>
+<thead><tr>
+<th>
+ <p>
+ intersects(Ring)
+ </p>
+ </th>
+<th>
+ <p>
+ intersects(Polygon)
+ </p>
+ </th>
+</tr></thead>
+<tbody><tr>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/intersects_ring.png" alt="intersects_ring"></span>
+ </p>
+ </td>
+<td>
+ <p>
+ <span class="inlinemediaobject"><img src="../../../images/intersects_poly.png" alt="intersects_poly"></span>
+ </p>
+ </td>
+</tr></tbody>
+</table></div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="geometry_index.r_tree.spatial_queries.basic_queries"></a><a class="link" href="spatial_queries.html#geometry_index.r_tree.spatial_queries.basic_queries" title="Basic queries">Basic
@@ -117,7 +147,7 @@
</h4></div></div></div>
<p>
There are three ways to perform a spatial query. Following queries returns
- <code class="computeroutput">Value</code>s intersecting some box_region.
+ <code class="computeroutput">Value</code>s intersecting some region defined as a box in this example.
</p>
<p>
Method call
@@ -148,7 +178,7 @@
</h4></div></div></div>
<p>
To explicitly define one of the predicates one may pass it to the <code class="computeroutput"><span class="identifier">spatial_query</span><span class="special">()</span></code>
- as the first argument instead of <code class="computeroutput"><span class="identifier">Box</span></code>.
+ as the first argument.
</p>
<pre class="programlisting"><span class="identifier">rt</span><span class="special">.</span><span class="identifier">spatial_query</span><span class="special">(</span><span class="identifier">box</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> <span class="comment">// default case - intersects</span>
<span class="identifier">rt</span><span class="special">.</span><span class="identifier">spatial_query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> <span class="comment">// the same as default</span>
@@ -178,7 +208,7 @@
to construct advanced queries but is also faster than separate calls because
the tree is traversed only once. Traversing is continued and <code class="computeroutput"><span class="identifier">Value</span></code>s are returned only if all predicates
are met. Predicates are checked left-to-right so placing most restictive
- predicates first should accelerate the search even more.
+ predicates first should accelerate the search.
</p>
<pre class="programlisting"><span class="identifier">rt</span><span class="special">.</span><span class="identifier">spatial_query</span><span class="special">(</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">make_pair</span><span class="special">(</span>
Modified: sandbox-branches/geometry/index/doc/html/index.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/index.html (original)
+++ sandbox-branches/geometry/index/doc/html/index.html 2012-12-13 13:39:31 EST (Thu, 13 Dec 2012)
@@ -56,7 +56,7 @@
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left"><p><small>Last revised: November 27, 2012 at 12:09:04 GMT</small></p></td>
+<td align="left"><p><small>Last revised: December 13, 2012 at 18:36:05 GMT</small></p></td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
Added: sandbox-branches/geometry/index/doc/images/intersects_poly.png
==============================================================================
Binary file. No diff available.
Added: sandbox-branches/geometry/index/doc/images/intersects_ring.png
==============================================================================
Binary file. No diff available.
Modified: sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk 2012-12-13 13:39:31 EST (Thu, 13 Dec 2012)
@@ -13,17 +13,22 @@
Spatial queries returns `Value`s which meets some predicates. For instance it may be used to
retrieve Values intersecting some area or are within some other area. Names of predicates
corresponds to names of __boost_geometry__ algorithms. The examples of some
-basic queries may be found in the table below. The query region and result `Value`s are orange.
+basic queries may be found in tables below. The query region and result `Value`s are orange.
[table
-[[intersects (default)] [covered_by] [disjoint] [overlaps] [within]]
+[[intersects(Box) - default] [covered_by(Box)] [disjoint(Box)] [overlaps(Box)] [within(Box)]]
[[[$../images/intersects.png]] [[$../images/within.png]] [[$../images/disjoint.png]] [[$../images/overlaps.png]] [[$../images/within.png]]]
]
+[table
+[[intersects(Ring)] [intersects(Polygon)]]
+[[[$../images/intersects_ring.png]] [[$../images/intersects_poly.png]]]
+]
+
[section Basic queries]
There are three ways to perform a spatial query. Following queries returns
-`__value__`s intersecting some box_region.
+`__value__`s intersecting some region defined as a box in this example.
Method call
@@ -47,7 +52,7 @@
[section Spatial predicates]
To explicitly define one of the predicates one may pass it to the `spatial_query()` as
-the first argument instead of `Box`.
+the first argument.
rt.spatial_query(box, std::back_inserter(result)); // default case - intersects
rt.spatial_query(index::intersects(box), std::back_inserter(result)); // the same as default
@@ -71,7 +76,7 @@
Passing all predicates together not only makes possible to construct advanced queries but is also
faster than separate calls because the tree is traversed only once. Traversing is continued and
`Value`s are returned only if all predicates are met. Predicates are checked left-to-right so placing
-most restictive predicates first should accelerate the search even more.
+most restictive predicates first should accelerate the search.
rt.spatial_query(
std::make_pair(
Modified: sandbox-branches/geometry/index/tests/additional_glut_vis.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_glut_vis.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_glut_vis.cpp 2012-12-13 13:39:31 EST (Thu, 13 Dec 2012)
@@ -11,8 +11,13 @@
#define BOOST_GEOMETRY_INDEX_ENABLE_DEBUG_INTERFACE
+#include <boost/foreach.hpp>
+
#include <boost/geometry/extensions/index/rtree/rtree.hpp>
+#include <boost/geometry/geometries/ring.hpp>
+#include <boost/geometry/geometries/polygon.hpp>
+
#include <boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/print.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp>
@@ -24,6 +29,8 @@
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::ring<P> R;
+typedef bg::model::polygon<P> Poly;
bgi::rtree<
B,
@@ -38,9 +45,11 @@
size_t count = 5;
std::vector<B> nearest_boxes;
B search_box;
+R search_ring;
+Poly search_poly;
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_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
} query_mode = qm_knn;
bool search_valid = false;
@@ -113,6 +122,111 @@
std::cout << "boxes not found\n";
}
+template <typename Predicate>
+void query_ring()
+{
+ float x = ( rand() % 1000 ) / 10.0f;
+ float y = ( rand() % 1000 ) / 10.0f;
+ float w = 10 + ( rand() % 1000 ) / 100.0f;
+ float h = 10 + ( rand() % 1000 ) / 100.0f;
+
+ search_ring.clear();
+ search_ring.push_back(P(x - w, y - h));
+ search_ring.push_back(P(x - w/2, y - h));
+ search_ring.push_back(P(x, y - 3*h/2));
+ search_ring.push_back(P(x + w/2, y - h));
+ search_ring.push_back(P(x + w, y - h));
+ search_ring.push_back(P(x + w, y - h/2));
+ search_ring.push_back(P(x + 3*w/2, y));
+ search_ring.push_back(P(x + w, y + h/2));
+ search_ring.push_back(P(x + w, y + h));
+ search_ring.push_back(P(x + w/2, y + h));
+ search_ring.push_back(P(x, y + 3*h/2));
+ search_ring.push_back(P(x - w/2, y + h));
+ search_ring.push_back(P(x - w, y + h));
+ search_ring.push_back(P(x - w, y + h/2));
+ search_ring.push_back(P(x - 3*w/2, y));
+ search_ring.push_back(P(x - w, y - h/2));
+ search_ring.push_back(P(x - w, y - h));
+
+ nearest_boxes.clear();
+ found_count = t.spatial_query(Predicate(search_ring), std::back_inserter(nearest_boxes) );
+
+ if ( found_count > 0 )
+ {
+ std::cout << "search ring: ";
+ BOOST_FOREACH(P const& p, search_ring)
+ {
+ bgi::detail::rtree::visitors::detail::print_indexable(std::cout, p);
+ std::cout << ' ';
+ }
+ 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 << "boxes not found\n";
+}
+
+template <typename Predicate>
+void query_poly()
+{
+ float x = ( rand() % 1000 ) / 10.0f;
+ float y = ( rand() % 1000 ) / 10.0f;
+ float w = 10 + ( rand() % 1000 ) / 100.0f;
+ float h = 10 + ( rand() % 1000 ) / 100.0f;
+
+ search_poly.clear();
+ search_poly.outer().push_back(P(x - w, y - h));
+ search_poly.outer().push_back(P(x - w/2, y - h));
+ search_poly.outer().push_back(P(x, y - 3*h/2));
+ search_poly.outer().push_back(P(x + w/2, y - h));
+ search_poly.outer().push_back(P(x + w, y - h));
+ search_poly.outer().push_back(P(x + w, y - h/2));
+ search_poly.outer().push_back(P(x + 3*w/2, y));
+ search_poly.outer().push_back(P(x + w, y + h/2));
+ search_poly.outer().push_back(P(x + w, y + h));
+ search_poly.outer().push_back(P(x + w/2, y + h));
+ search_poly.outer().push_back(P(x, y + 3*h/2));
+ search_poly.outer().push_back(P(x - w/2, y + h));
+ search_poly.outer().push_back(P(x - w, y + h));
+ search_poly.outer().push_back(P(x - w, y + h/2));
+ search_poly.outer().push_back(P(x - 3*w/2, y));
+ search_poly.outer().push_back(P(x - w, y - h/2));
+ search_poly.outer().push_back(P(x - w, y - h));
+
+ search_poly.inners().push_back(Poly::ring_type());
+ search_poly.inners()[0].push_back(P(x - w/2, y - h/2));
+ search_poly.inners()[0].push_back(P(x + w/2, y - h/2));
+ search_poly.inners()[0].push_back(P(x + w/2, y + h/2));
+ search_poly.inners()[0].push_back(P(x - w/2, y + h/2));
+ search_poly.inners()[0].push_back(P(x - w/2, y - h/2));
+
+ nearest_boxes.clear();
+ found_count = t.spatial_query(Predicate(search_poly), std::back_inserter(nearest_boxes) );
+
+ if ( found_count > 0 )
+ {
+ std::cout << "search poly outer: ";
+ BOOST_FOREACH(P const& p, search_poly.outer())
+ {
+ bgi::detail::rtree::visitors::detail::print_indexable(std::cout, p);
+ std::cout << ' ';
+ }
+ 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 << "boxes not found\n";
+}
+
void search()
{
if ( query_mode == qm_knn )
@@ -139,6 +253,10 @@
query< bgi::detail::not_within<B> >();
else if ( query_mode == qm_all )
query< bgi::detail::intersects<B> >();
+ else if ( query_mode == qm_ri )
+ query_ring< bgi::detail::intersects<R> >();
+ else if ( query_mode == qm_pi )
+ query_poly< bgi::detail::intersects<Poly> >();
search_valid = true;
}
@@ -171,7 +289,7 @@
glEnd();
}
-void draw_query_area()
+void draw_query_box_area()
{
float x1 = boost::geometry::get<bg::min_corner, 0>(search_box);
float y1 = boost::geometry::get<bg::min_corner, 1>(search_box);
@@ -188,6 +306,36 @@
glEnd();
}
+template <typename Range>
+void draw_ring_area(Range const& range)
+{
+ float z = t.depth();
+
+ // search box
+ glBegin(GL_LINE_LOOP);
+
+ BOOST_FOREACH(P const& p, range)
+ {
+ float x = boost::geometry::get<0>(p);
+ float y = boost::geometry::get<1>(p);
+
+ glVertex3f(x, y, z);
+ }
+ glEnd();
+}
+
+void draw_query_ring_area()
+{
+ draw_ring_area(search_ring);
+}
+
+void draw_query_poly_area()
+{
+ draw_ring_area(search_poly.outer());
+ BOOST_FOREACH(Poly::ring_type const& r, search_poly.inners())
+ draw_ring_area(r);
+}
+
void render_scene(void)
{
glClear(GL_COLOR_BUFFER_BIT);
@@ -200,8 +348,12 @@
if ( query_mode == qm_knn )
draw_knn_area();
+ else if ( query_mode == qm_ri )
+ draw_query_ring_area();
+ else if ( query_mode == qm_pi )
+ draw_query_poly_area();
else
- draw_query_area();
+ draw_query_box_area();
for ( size_t i = 0 ; i < nearest_boxes.size() ; ++i )
boost::geometry::index::detail::rtree::visitors::detail::gl_draw_indexable(nearest_boxes[i], t.depth());
@@ -357,6 +509,10 @@
query_mode = qm_nw;
else if ( current_line == "all" )
query_mode = qm_all;
+ else if ( current_line == "ri" )
+ query_mode = qm_ri;
+ else if ( current_line == "pi" )
+ query_mode = qm_pi;
search();
glutPostRedisplay();
@@ -372,8 +528,15 @@
}
}
+#include <boost/geometry/geometries/segment.hpp>
+#include <boost/geometry/geometries/linestring.hpp>
+
int main(int argc, char **argv)
{
+ bg::model::linestring<P> s;
+ B b;
+ bg::intersects(s, b);
+
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_DEPTH | GLUT_SINGLE | GLUT_RGBA);
glutInitWindowPosition(100,100);