bump version to 12.2.2-pve1

[ceph.git] / ceph / src / boost / libs / geometry / doc / index / rtree / query.qbk

[/============================================================================
  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 /]