| [/============================================================================ |
| Boost.Geometry Index |
| |
| Copyright (c) 2011-2013 Adam Wulkiewicz. |
| |
| Use, modification and distribution is subject to the Boost Software License, |
| Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| =============================================================================/] |
| |
| [section Queries] |
| |
| Queries returns `__value__`s which meets some predicates. Currently supported are three types of predicates: |
| |
| * spatial predicates - spatial conditions that must be met by stored Value and some Geometry, |
| * distance predicates - distance conditions that must be met by stored Value and some Geometry, |
| * user-defined unary predicate - function, function object or lambda expression checking user-defined condition. |
| |
| For example queries may be used to retrieve Values: |
| |
| * intersecting some area but not within other area, |
| * are nearest to some point, |
| * overlapping a box and has user-defined property. |
| |
| [h4 Performing a query] |
| |
| There are various ways to perform a query. They are presented below. |
| All of them returns `__value__`s intersecting some region defined as a `__box__`. |
| |
| Member function call |
| |
| std::vector<__value__> returned_values; |
| __box__ box_region(...); |
| rt.query(bgi::intersects(box_region), std::back_inserter(returned_values)); |
| |
| Free function call |
| |
| std::vector<__value__> returned_values; |
| __box__ box_region(...); |
| bgi::query(rt, bgi::intersects(box_region), std::back_inserter(returned_values)); |
| |
| Range generated by `operator|` |
| |
| __box__ box_region(...); |
| BOOST_FOREACH(__value__ & v, rt | bgi::adaptors::queried(bgi::intersects(box_region))) |
| ; // do something with v |
| |
| Query iterators returned by member functions |
| |
| std::vector<__value__> returned_values; |
| __box__ box_region(...); |
| std::copy(rt.qbegin(bgi::intersects(box_region)), rt.qend(), std::back_inserter(returned_values)); |
| |
| Query iterators returned by free functions |
| |
| std::vector<__value__> returned_values; |
| __box__ box_region(...); |
| std::copy(bgi::qbegin(rt, bgi::intersects(box_region)), bgi::qend(rt), std::back_inserter(returned_values)); |
| |
| [h4 Spatial predicates] |
| |
| Queries using spatial predicates returns `__value__`s which are related somehow to some Geometry - box, polygon, etc. |
| Names of spatial predicates correspond to names of __boost_geometry__ algorithms (boolean operations). |
| Examples of some basic queries may be found in the tables below. The query region and result `Value`s are orange. |
| |
| [table |
| [[intersects(Box)] [covered_by(Box)] [disjoint(Box)] [overlaps(Box)] [within(Box)]] |
| [[[$img/index/rtree/intersects.png]] [[$img/index/rtree/within.png]] [[$img/index/rtree/disjoint.png]] [[$img/index/rtree/overlaps.png]] [[$img/index/rtree/within.png]]] |
| ] |
| |
| [table |
| [[intersects(Ring)] [intersects(Polygon)] [intersects(MultiPolygon)] [intersects(Segment)] [intersects(Linestring)]] |
| [[[$img/index/rtree/intersects_ring.png]] [[$img/index/rtree/intersects_poly.png]] [[$img/index/rtree/intersects_mpoly.png]] [[$img/index/rtree/intersects_segment.png]] [[$img/index/rtree/intersects_linestring.png]]] |
| ] |
| |
| [table |
| [[intersects(Box)] [disjoint(Box)] [intersects(Box)] [disjoint(Box)]] |
| [[[$img/index/rtree/rtree_pt_intersects_box.png]] [[$img/index/rtree/rtree_pt_disjoint_box.png]] [[$img/index/rtree/rtree_seg_intersects_box.png]] [[$img/index/rtree/rtree_seg_disjoint_box.png]]] |
| ] |
| |
| Spatial predicates are generated by functions defined in `boost::geometry::index` namespace. |
| |
| rt.query(index::contains(box), std::back_inserter(result)); |
| rt.query(index::covered_by(box), std::back_inserter(result)); |
| rt.query(index::covers(box), std::back_inserter(result)); |
| rt.query(index::disjont(box), std::back_inserter(result)); |
| rt.query(index::intersects(box), std::back_inserter(result)); |
| rt.query(index::overlaps(box), std::back_inserter(result)); |
| rt.query(index::within(box), std::back_inserter(result)); |
| |
| All spatial predicates may be negated, e.g.: |
| |
| rt.query(!index::intersects(box), std::back_inserter(result)); |
| // the same as |
| rt.query(index::disjoint(box), std::back_inserter(result)); |
| |
| [h4 Nearest neighbours queries] |
| |
| Nearest neighbours queries returns `__value__`s which are closest to some Geometry. |
| The examples of k-NN queries are presented below. 5 `__value__`s nearest to the Geometry are orange. |
| |
| [table |
| [[nearest(Point, k)] [nearest(Box, k)] [nearest(Point, k)] [nearest(Box, k)]] |
| [[[$img/index/rtree/knn_pt_box.png]] [[$img/index/rtree/knn_box_box.png]] [[$img/index/rtree/rtree_pt_knn_pt.png]] [[$img/index/rtree/rtree_pt_knn_box.png]]] |
| ] |
| [table |
| [[nearest(Segment, k)] |
| [nearest(Point, k)] [nearest(Box, k)] [nearest(Segment, k)] |
| [nearest(Segment, k)]] |
| [[[$img/index/rtree/knn_seg_box.png]] |
| [[$img/index/rtree/rtree_seg_knn_pt.png]] [[$img/index/rtree/rtree_seg_knn_box.png]] [[$img/index/rtree/rtree_seg_knn_seg.png]] |
| [[$img/index/rtree/rtree_pt_knn_seg.png]]] |
| ] |
| |
| To perform the knn query one must pass the nearest predicate generated by the |
| `nearest()` function defined in `boost::geometry::index` namespace. |
| For non-point `__indexable__`s the shortest distance is calculated using `bg::comparable_distance()` function. |
| The following query returns `k` `__value__`s closest to some Point in space. |
| |
| std::vector<__value__> returned_values; |
| __point__ pt(/*...*/); |
| rt.query(bgi::nearest(pt, k), std::back_inserter(returned_values)); |
| |
| The same way different query Geometries can be used: |
| |
| __box__ box(/*...*/); |
| rt.query(bgi::nearest(box, k), std::back_inserter(returned_values)); |
| |
| Segment seg(/*...*/); |
| rt.query(bgi::nearest(seg, k), std::back_inserter(returned_values)); |
| |
| [h4 User-defined unary predicate] |
| |
| The user may pass a `UnaryPredicate` - function, function object or lambda expression taking const reference to Value and returning bool. |
| This object may be passed to the query in order to check if `__value__` should be returned by the query. To do it one |
| may use `index::satisfies()` function like on the example below: |
| |
| bool is_red(__value__ const& v) |
| { |
| return v.is_red(); |
| } |
| |
| struct is_red_o |
| { |
| template <typename Value> |
| bool operator()(__value__ const& v) |
| { |
| return v.is_red(); |
| } |
| } |
| |
| // ... |
| |
| rt.query(index::intersects(box) && index::satisfies(is_red), |
| std::back_inserter(result)); |
| |
| rt.query(index::intersects(box) && index::satisfies(is_red_o()), |
| std::back_inserter(result)); |
| |
| #ifndef BOOST_NO_CXX11_LAMBDAS |
| rt.query(index::intersects(box) && index::satisfies([](__value__ const& v) { return v.is_red(); }), |
| std::back_inserter(result)); |
| #endif |
| |
| `satisfies()` may be negated, e.g.: |
| |
| bool is_red(__value__ const& v) { return v.is_red(); } |
| bool is_not_red(__value__ const& v) { return !v.is_red(); } |
| |
| // ... |
| |
| rt.query(index::intersects(box) && index::satisfies(is_red), |
| std::back_inserter(result)); |
| // the same as |
| rt.query(index::intersects(box) && !index::satisfies(is_not_red), |
| std::back_inserter(result)); |
| |
| [h4 Passing a set of predicates] |
| |
| It's possible to use some number of predicates in one query by connecting them with `operator&&` e.g. `Pred1 && Pred2 && Pred3 && ...`. |
| |
| These predicates are connected by logical AND. 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 restrictive predicates first should accelerate the search. |
| |
| rt.query(index::intersects(box1) && !index::within(box2), |
| std::back_inserter(result)); |
| |
| rt.query(index::intersects(box1) && !index::within(box2) && index::overlaps(box3), |
| std::back_inserter(result)); |
| |
| Of course it's possible to connect different types of predicates together. |
| |
| index::query(rt, index::nearest(pt, k) && index::within(b), std::back_inserter(returned_values)); |
| |
| BOOST_FOREACH(Value & v, rt | index::adaptors::queried(index::nearest(pt, k) && index::covered_by(b))) |
| ; // do something with v |
| |
| [h4 Iterative queries] |
| |
| The query performed using query iterators may be paused and resumed if needed, e.g. when the query takes too long, |
| or may be stopped at some point, when all interesting values were gathered. The query iterator is returned by |
| `qbegin()` member function which requires passing predicates, like `query()` member function. |
| |
| for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ; |
| it != tree.qend() ; ++it ) |
| { |
| // do something with value |
| if ( has_enough_nearest_values() ) |
| break; |
| } |
| |
| [note In the case of iterative k-NN queries it's guaranteed to iterate over the closest `__value__`s first. ] |
| |
| [warning The modification of the `rtree`, e.g. insertion or removal of `__value__`s may invalidate the iterators. ] |
| |
| [h4 Inserting query results into the other R-tree] |
| |
| There are several ways of inserting Values returned by a query to the other R-tree container. |
| The most basic way is creating a temporary container for Values and insert them later. |
| |
| namespace bgi = boost::geometry::index; |
| typedef std::pair<Box, int> __value__; |
| typedef bgi::rtree< __value__, bgi::linear<32, 8> > RTree; |
| |
| RTree rt1; |
| /* some inserting into the tree */ |
| |
| std::vector<Value> result; |
| rt1.query(bgi::intersects(Box(/*...*/)), std::back_inserter(result)); |
| RTree rt2(result.begin(), result.end()); |
| |
| However there are better ways. One of these methods is mentioned in the "Creation and modification" section. |
| The insert iterator may be passed directly into the query. |
| |
| RTree rt3; |
| rt1.query(bgi::intersects(Box(/*...*/))), bgi::inserter(rt3)); |
| |
| If you're a user of Boost.Range you'll appreciate the third option. You may pass the result Range directly into the |
| constructor or `insert()` member function. |
| |
| RTree rt4(rt1 | bgi::adaptors::queried(bgi::intersects(Box(/*...*/))))); |
| |
| [endsect] [/ Queries /] |