123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250 |
- [/============================================================================
- Boost.Geometry Index
- Copyright (c) 2011-2017 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 queries]
- 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(Segment)] [intersects(Box)] [disjoint(Box)] [intersects(Box)] [disjoint(Box)]]
- [[[$img/index/rtree/intersects_segment.png]] [[$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]]]
- ]
- [/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));
- [note In case of k-NN queries performed with `query()` function it's not guaranteed that the returned values will be sorted according to the distance.
- It's different in case of k-NN queries performed with query iterator returned by `qbegin()` function which guarantees the iteration over the closest `__value__`s first. ]
- [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 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));
- 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;
- }
- [warning The modification of the `rtree`, e.g. insertion or removal of `__value__`s may invalidate the iterators. ]
- [h4 Inserting query results into another R-tree]
- There are several ways of inserting Values returned by a query into another 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 other 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));
- You may also pass the resulting Range directly into the constructor or `insert()` member function using Boost.Range adaptor syntax.
- RTree rt4(rt1 | bgi::adaptors::queried(bgi::intersects(Box(/*...*/)))));
- [endsect] [/ Queries /]
|