Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r75740 - in sandbox-branches/geometry/index/doc: . html html/geometry_index html/index
From: adam.wulkiewicz_at_[hidden]
Date: 2011-11-29 22:22:16

Author: awulkiew
Date: 2011-11-29 22:22:14 EST (Tue, 29 Nov 2011)
New Revision: 75740
URL: http://svn.boost.org/trac/boost/changeset/75740

Log:
changed docs format - from BoostBook to QuickBook
Added:
   sandbox-branches/geometry/index/doc/html/geometry_index/
   sandbox-branches/geometry/index/doc/html/geometry_index/introduction.html (contents, props changed)
   sandbox-branches/geometry/index/doc/html/geometry_index/r_tree.html (contents, props changed)
   sandbox-branches/geometry/index/doc/index.qbk (contents, props changed)
   sandbox-branches/geometry/index/doc/introduction.qbk (contents, props changed)
   sandbox-branches/geometry/index/doc/rtree.qbk (contents, props changed)
Removed:
   sandbox-branches/geometry/index/doc/html/index/
   sandbox-branches/geometry/index/doc/index.xml
Text files modified:
   sandbox-branches/geometry/index/doc/Jamfile.v2 | 29 ++++++++++++++------
   sandbox-branches/geometry/index/doc/html/index.html | 54 +++++++++++++++++----------------------
   2 files changed, 43 insertions(+), 40 deletions(-)

Modified: sandbox-branches/geometry/index/doc/Jamfile.v2
==============================================================================
--- sandbox-branches/geometry/index/doc/Jamfile.v2 (original)
+++ sandbox-branches/geometry/index/doc/Jamfile.v2 2011-11-29 22:22:14 EST (Tue, 29 Nov 2011)
@@ -1,4 +1,4 @@
-# Boost.Geometry.Index (Spatial Indexes Library)
+# Boost.Geometry Index (Spatial Indexes)
#
# Copyright (c) 2008 Federico J. Fernandez.
# Copyright (c) 2011 Adam Wulkiewicz.
@@ -7,14 +7,25 @@
# Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
# http://www.boost.org/LICENSE_1_0.txt)

-project boost/doc ;
-import boostbook : boostbook ;
+project geometry_index/doc ;

-boostbook geometry-index-doc
- :
- index.xml
+import boostbook ;
+import quickbook ;
+
+boostbook geometry_index-doc
:
- <xsl:param>boost.root=http://www.boost.org/doc/libs/release
- <format>pdf:<xsl:param>boost.url.prefix=http://www.boost.org/doc/libs/release/doc/html
+ index.qbk
+ :
+# <auto-index>off
+# <auto-index-internal>on
+# <auto-index-verbose>off
+# <xsl:param>index.on.type=1
+ <format>html
+ <format>pdf:<xsl:param>boost.url.prefix=http://www.boost.org/doc/libs/release/doc/html
+ <xsl:param>chunk.first.sections=1
+ <xsl:param>toc.section.depth=3
+ <xsl:param>toc.max.depth=2
+ <xsl:param>generate.section.toc.level=4
+ <xsl:param>boost.root=http://www.boost.org/doc/libs/release
+ <quickbook-define>enable_index
;
-

Added: sandbox-branches/geometry/index/doc/html/geometry_index/introduction.html
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/introduction.html 2011-11-29 22:22:14 EST (Tue, 29 Nov 2011)
@@ -0,0 +1,53 @@
+<html>
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
+<title>Introduction</title>
+<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
+<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<link rel="home" href="../index.html" title="Chapter 1. Geometry Index 0.7">
+<link rel="up" href="../index.html" title="Chapter 1. Geometry Index 0.7">
+<link rel="prev" href="../index.html" title="Chapter 1. Geometry Index 0.7">
+<link rel="next" href="r_tree.html" title="R-tree">
+</head>
+<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
+<table cellpadding="2" width="100%"><tr>
+<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="http://www.boost.org/doc/libs/release/boost.png"></td>
+<td align="center">Home</td>
+<td align="center">Libraries</td>
+<td align="center">People</td>
+<td align="center">FAQ</td>
+<td align="center">More</td>
+</tr></table>
+<hr>
+<div class="spirit-nav">
+<a accesskey="p" href="../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h2 class="title" style="clear: both">
+<a name="geometry_index.introduction"></a><a class="link" href="introduction.html" title="Introduction">Introduction</a>
+</h2></div></div></div>
+
+ The Boost.Geometry Index is intetended to gather containers (spatial indexes)
+ used for speeding spatial queries up. It is a part of the Boost.Geometry
+ library. In general, spatial indexes stores geometric objects' representations
+ and allows searching for objects occupying some space or close to some point
+ in space.
+ 
+
+ Currently, only one spatial index is implemented - R-tree.
+ 
+</div>
+<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
+<td align="left"></td>
+<td align="right"><div class="copyright-footer">Copyright © 2011 Adam Wulkiewicz, Federico J. Fernandez
+ Distributed under 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)
+ 
+</div></td>
+</tr></table>
+<hr>
+<div class="spirit-nav">
+<a accesskey="p" href="../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a>
+</div>
+</body>
+</html>

Added: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree.html
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree.html 2011-11-29 22:22:14 EST (Tue, 29 Nov 2011)
@@ -0,0 +1,502 @@
+<html>
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
+<title>R-tree</title>
+<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
+<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<link rel="home" href="../index.html" title="Chapter 1. Geometry Index 0.7">
+<link rel="up" href="../index.html" title="Chapter 1. Geometry Index 0.7">
+<link rel="prev" href="introduction.html" title="Introduction">
+</head>
+<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
+<table cellpadding="2" width="100%"><tr>
+<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="http://www.boost.org/doc/libs/release/boost.png"></td>
+<td align="center">Home</td>
+<td align="center">Libraries</td>
+<td align="center">People</td>
+<td align="center">FAQ</td>
+<td align="center">More</td>
+</tr></table>
+<hr>
+<div class="spirit-nav">
+<a accesskey="p" href="introduction.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h2 class="title" style="clear: both">
+<a name="geometry_index.r_tree"></a><a class="link" href="r_tree.html" title="R-tree">R-tree</a>
+</h2></div></div></div>
+<div class="toc"><dl>
+<dt>Introduction</dt>
+<dt>R-tree creation</dt>
+<dd><dl>
+<dt><a href="r_tree.html#geometry_index.r_tree.r_tree_creation.quick_start">Quick
+ start</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.r_tree_creation.r_tree_template_parameters">R-tree
+ template parameters</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.r_tree_creation.values__indexables_and_default_translator">Values,
+ Indexables and default Translator</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.r_tree_creation.inserting_and_splitting_algorithms">Inserting
+ and splitting algorithms</a></dt>
+</dl></dd>
+<dt><a href="r_tree.html#geometry_index.r_tree.inserting_and_removing_values">Inserting
+ and removing Values</a></dt>
+<dt>Spatial queries</dt>
+<dd><dl>
+<dt><a href="r_tree.html#geometry_index.r_tree.spatial_queries.basic_queries">Basic
+ queries</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.spatial_queries.spatial_predicates">Spatial
+ predicates</a></dt>
+</dl></dd>
+<dt><a href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries">Nearest
+ neighbors queries</a></dt>
+<dd><dl>
+<dt><a href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries.k_nearest_neighbors">k
+ nearest neighbors</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries.one_nearest_neighbor">One
+ nearest neighbor</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries.distances_predicates">Distances
+ predicates</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries.using_spatial_predicates">Using
+ spatial predicates</a></dt>
+</dl></dd>
+</dl></div>
+<div class="section">
+<div class="titlepage"><div><div><h3 class="title">
+<a name="geometry_index.r_tree.introduction"></a><a class="link" href="r_tree.html#geometry_index.r_tree.introduction" title="Introduction">Introduction</a>
+</h3></div></div></div>
+
+ R-tree is a self-balancing search tree with nodes stored with their axis
+ aligned bounding boxes. Each node's box describes the space occupied by children
+ nodes. At the bottom of the structure, there are leaf-nodes which contains
+ values (geometric objects representations). Minimal and maximal numbers of
+ values/children which may be stored inside the node are user defined.
+ 
+
+ In order to use the R-tree one must include folowing file.
+ 
+<pre class="programlisting">#include <boost/geometry/extensions/index/rtree/rtree.hpp>
+</pre>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h3 class="title">
+<a name="geometry_index.r_tree.r_tree_creation"></a><a class="link" href="r_tree.html#geometry_index.r_tree.r_tree_creation" title="R-tree creation">R-tree creation</a>
+</h3></div></div></div>
+<div class="toc"><dl>
+<dt><a href="r_tree.html#geometry_index.r_tree.r_tree_creation.quick_start">Quick
+ start</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.r_tree_creation.r_tree_template_parameters">R-tree
+ template parameters</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.r_tree_creation.values__indexables_and_default_translator">Values,
+ Indexables and default Translator</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.r_tree_creation.inserting_and_splitting_algorithms">Inserting
+ and splitting algorithms</a></dt>
+</dl></div>
+<div class="section">
+<div class="titlepage"><div><div><h4 class="title">
+<a name="geometry_index.r_tree.r_tree_creation.quick_start"></a><a class="link" href="r_tree.html#geometry_index.r_tree.r_tree_creation.quick_start" title="Quick start">Quick
+ start</a>
+</h4></div></div></div>
+
+ In order to create a R-tree object storing values of type <code class="computeroutput">std::pair<Box, size_t></code> one may use the following code:
+ 
+<pre class="programlisting">using namespace boost::geometry;
+typedef std::pair<Box, size_t> Value;
+index::rtree< Value, index::quadratic<32, 8> > rt;
+</pre>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h4 class="title">
+<a name="geometry_index.r_tree.r_tree_creation.r_tree_template_parameters"></a><a class="link" href="r_tree.html#geometry_index.r_tree.r_tree_creation.r_tree_template_parameters" title="R-tree template parameters">R-tree
+ template parameters</a>
+</h4></div></div></div>
+
+ R-tree has 4 parameters:
+ 
+<pre class="programlisting">rtree<Value, Parameters, Translator, Allocator>
+</pre>
+<div class="itemizedlist"><ul class="itemizedlist" type="disc">
+<li class="listitem">
+ <code class="computeroutput">Value</code> - type of object
+ which will be stored in the container.
+ </li>
+<li class="listitem">
+ <code class="computeroutput">Parameters</code> - compile-time
+ parameters, e.g. inserting/splitting algorithm with min and max nodes'
+ elements numbers.
+ </li>
+<li class="listitem">
+ <code class="computeroutput">Translator</code> - type of
+ object translating <code class="computeroutput">Value</code>
+ objects to <code class="computeroutput">Indexable</code>
+ objects (<code class="computeroutput">Point</code>
+ or <code class="computeroutput">Box</code>)
+ which R-tree can handle.
+ </li>
+<li class="listitem">
+ <code class="computeroutput">Allocator</code> - the allocator.
+ </li>
+</ul></div>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h4 class="title">
+<a name="geometry_index.r_tree.r_tree_creation.values__indexables_and_default_translator"></a><a class="link" href="r_tree.html#geometry_index.r_tree.r_tree_creation.values__indexables_and_default_translator" title="Values, Indexables and default Translator">Values,
+ Indexables and default Translator</a>
+</h4></div></div></div>
+
+ R-tree may store <code class="computeroutput">Value</code>s of any type as long as there is passed
+ the <code class="computeroutput">Translator</code> which knows how to interpret those <code class="computeroutput">Value</code>s
+ and extract an object understandable by the R-tree. Those objects are called
+ <code class="computeroutput">Indexable</code>s and they are simply of type adapted to <code class="computeroutput">Point</code>
+ or <code class="computeroutput">Box</code>
+ concept. Default <code class="computeroutput">Translator</code> <code class="computeroutput">index::translator::def<Value></code> is able to handle <code class="computeroutput">Point</code>,
+ <code class="computeroutput">Box</code>,
+ <code class="computeroutput">std::pair<...></code>,
+ pointer, iterator or smart pointer.
+ 
+<div class="itemizedlist"><ul class="itemizedlist" type="disc">
+<li class="listitem">
+ <code class="computeroutput">Indexable = Point
+ | Box</code>
+ </li>
+<li class="listitem">
+ <code class="computeroutput">BasicValue =
+ Indexable |
+ std::pair<Indexable, T> | std::pair<T, Indexable></code>
+ </li>
+<li class="listitem">
+ <code class="computeroutput">Value = BasicValue
+ | BasicValue* | Iterator<BasicValue>
+ | SmartPtr<BasicValue></code>
+ </li>
+</ul></div>
+
+ Examples of <code class="computeroutput">Value</code> types:
+ 
+<pre class="programlisting">geometry::model::point<...>
+geometry::model::point_xy<...>
+geometry::model::box<...>
+std::pair<geometry::model::box<...>, size_t>
+</pre>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h4 class="title">
+<a name="geometry_index.r_tree.r_tree_creation.inserting_and_splitting_algorithms"></a><a class="link" href="r_tree.html#geometry_index.r_tree.r_tree_creation.inserting_and_splitting_algorithms" title="Inserting and splitting algorithms">Inserting
+ and splitting algorithms</a>
+</h4></div></div></div>
+
+ <code class="computeroutput">Value</code>s may be inserted to the R-tree in many various ways.
+ Final structure of nodes depends on algorithms used in the process, especially
+ nodes' splitting algorithm. Currently, three well-known types of R-trees
+ may be created.
+ 
+
+ Linear - classic R-tree using splitting algorithm of linear complexity
+ 
+<pre class="programlisting">index::rtree< Value, index::linear<32, 8> > rt;
+</pre>
+
+ Quadratic - classic R-tree using splitting algorithm of quadratic complexity
+ 
+<pre class="programlisting">index::rtree< Value, index::quadratic<32, 8> > rt;
+</pre>
+
+ R*-tree - splitting algorithm minimizing nodes' overlap with forced reinsertions
+ 
+<pre class="programlisting">index::rtree< Value, index::rstar<32, 8> > rt;
+</pre>
+</div>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h3 class="title">
+<a name="geometry_index.r_tree.inserting_and_removing_values"></a><a class="link" href="r_tree.html#geometry_index.r_tree.inserting_and_removing_values" title="Inserting and removing Values">Inserting
+ and removing Values</a>
+</h3></div></div></div>
+
+ Create
+ 
+<pre class="programlisting">using namespace boost::geometry;
+typedef std::pair<Box, int> Value;
+index::rtree< Value, index::quadratic<32, 8> > rt;
+</pre>
+
+ Insert and remove by method call
+ 
+<pre class="programlisting">Value v = std::make_pair(Box(...), 0);
+rt.insert(v);
+rt.remove(v);
+</pre>
+
+ or by function call
+ 
+<pre class="programlisting">Value v = std::make_pair(Box(...), 0);
+index::insert(rt, v);
+index::remove(rt, v);
+</pre>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h3 class="title">
+<a name="geometry_index.r_tree.spatial_queries"></a><a class="link" href="r_tree.html#geometry_index.r_tree.spatial_queries" title="Spatial queries">Spatial queries</a>
+</h3></div></div></div>
+<div class="toc"><dl>
+<dt><a href="r_tree.html#geometry_index.r_tree.spatial_queries.basic_queries">Basic
+ queries</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.spatial_queries.spatial_predicates">Spatial
+ predicates</a></dt>
+</dl></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="r_tree.html#geometry_index.r_tree.spatial_queries.basic_queries" title="Basic queries">Basic
+ queries</a>
+</h4></div></div></div>
+
+ There are three ways to perform a spatial query. Following queries returns
+ <code class="computeroutput">Value</code>s intersecting some box_region.
+ 
+
+ Method call
+ 
+<pre class="programlisting">std::vector<Value> returned_values;
+Box box_region(...);
+rt.query(box_region, std::back_inserter(returned_values));
+</pre>
+
+ Function call
+ 
+<pre class="programlisting">std::vector<Value> returned_values;
+Box box_region(...);
+index::query(rt, box_region, std::back_inserter(returned_values));
+</pre>
+
+ Use of <code class="computeroutput">operator |</code>
+ (as with ranges)
+ 
+<pre class="programlisting">Box box_region(...);
+BOOST_FOREACH(Value & v, rt | index::query_filtered(box_region))
+ ; // do something with v
+</pre>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h4 class="title">
+<a name="geometry_index.r_tree.spatial_queries.spatial_predicates"></a><a class="link" href="r_tree.html#geometry_index.r_tree.spatial_queries.spatial_predicates" title="Spatial predicates">Spatial
+ predicates</a>
+</h4></div></div></div>
+
+ It is possible to define other relations between queried <code class="computeroutput">Value</code>s
+ and region/regions of interest. Names of predicates corresponds to names
+ of Boost.Geometry
+ algorithms.
+ 
+<pre class="programlisting">rt.query(box, std::back_inserter(result)); // default case - intersects
+rt.query(index::intersects(box), std::back_inserter(result)); // same as default
+rt.query(index::covered_by(box), std::back_inserter(result));
+rt.query(index::disjont(box), std::back_inserter(result));
+rt.query(index::overlaps(box), std::back_inserter(result));
+rt.query(index::within(box), std::back_inserter(result));
+</pre>
+
+ All predicates may be negated, e.g.:
+ 
+<pre class="programlisting">rt.query(index::not_intersects(box), std::back_inserter(result));
+// or
+rt.query(!index::intersects(box), std::back_inserter(result));
+// the same as
+rt.query(index::disjoint(box), std::back_inserter(result));
+</pre>
+
+ It's possible to use some number of predicates by passing <code class="computeroutput">std::pair<Pred1, Pred2></code>
+ 
+<pre class="programlisting">rt.query(
+ std::make_pair(index::intersects(box1), !index::within(box2))
+ , std::back_inserter(result));
+</pre>
+
+ or <code class="computeroutput">boost::tuple<Pred1, Pred2, Pred3, ...></code>
+ 
+<pre class="programlisting">rt.query(
+ boost::make_tuple(
+ index::intersects(box1), !index::within(box2), index::overlaps(box3))
+ , std::back_inserter(result));
+</pre>
+
+ There is also a unique predicate <code class="computeroutput">index::value(...)</code> taking user-defined function/functor
+ which checks if <code class="computeroutput">Value</code> should be returned by the query.
+ 
+<pre class="programlisting">bool fun(__value const& v)
+{
+ return v.is_red();
+}
+
+// ...
+
+rt.query(
+ boost::make_pair(index::intersects(box), index::value(fun))
+ , std::back_inserter(result));
+</pre>
+</div>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h3 class="title">
+<a name="geometry_index.r_tree.nearest_neighbors_queries"></a><a class="link" href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries" title="Nearest neighbors queries">Nearest
+ neighbors queries</a>
+</h3></div></div></div>
+<div class="toc"><dl>
+<dt><a href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries.k_nearest_neighbors">k
+ nearest neighbors</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries.one_nearest_neighbor">One
+ nearest neighbor</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries.distances_predicates">Distances
+ predicates</a></dt>
+<dt><a href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries.using_spatial_predicates">Using
+ spatial predicates</a></dt>
+</dl></div>
+<div class="section">
+<div class="titlepage"><div><div><h4 class="title">
+<a name="geometry_index.r_tree.nearest_neighbors_queries.k_nearest_neighbors"></a><a class="link" href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries.k_nearest_neighbors" title="k nearest neighbors">k
+ nearest neighbors</a>
+</h4></div></div></div>
+
+ There are three ways of performing knn queries. Following queries returns
+ k <code class="computeroutput">Value</code>s closest to some point in space. For <code class="computeroutput">Box</code>es
+ <code class="computeroutput">Indexable</code>s closest point of a <code class="computeroutput">Box</code>
+ is taken into account by default.
+ 
+
+ Method call
+ 
+<pre class="programlisting">std::vector<Value> returned_values;
+Point pt(...);
+rt.nearest(pt, k, std::back_inserter(returned_values));
+</pre>
+
+ Function call
+ 
+<pre class="programlisting">std::vector<Value> returned_values;
+Point pt(...);
+index::nearest(rt, pt, k, std::back_inserter(returned_values));
+</pre>
+
+ Use of <code class="computeroutput">operator |</code>
+ 
+<pre class="programlisting">Point pt(...);
+BOOST_FOREACH(Value & v, rt | index::nearest_filtered(pt, k))
+ ; // do something with v
+</pre>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h4 class="title">
+<a name="geometry_index.r_tree.nearest_neighbors_queries.one_nearest_neighbor"></a><a class="link" href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries.one_nearest_neighbor" title="One nearest neighbor">One
+ nearest neighbor</a>
+</h4></div></div></div>
+
+ Another type of nearest neighbor query is searching for the one closest
+ <code class="computeroutput">Value</code>. If it is found, 1 is returned by the method or function.
+ This kind of query has only two forms.
+ 
+
+ Method call
+ 
+<pre class="programlisting">Value returned_value;
+Point pt(...);
+size_t n = rt.nearest(pt, returned_value);
+</pre>
+
+ Function call
+ 
+<pre class="programlisting">Value Value returned_value;
+Point pt(...);
+size_t n = index::nearest(rt, pt, returned_value);
+</pre>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h4 class="title">
+<a name="geometry_index.r_tree.nearest_neighbors_queries.distances_predicates"></a><a class="link" href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries.distances_predicates" title="Distances predicates">Distances
+ predicates</a>
+</h4></div></div></div>
+
+ It is possible to define if calculated distance between query point and
+ <code class="computeroutput">Value</code> should be greater, lesser or between some other distances.
+ Those are called <code class="computeroutput">DistancesPredicate</code>s
+ and may be defined as follows.
+ 
+<pre class="programlisting">std::vector<__Value__> returned_values;
+Point pt(...);
+
+/* default - without bounds */
+index::nearest(rt, pt, k, std::back_inserter(returned_values));
+
+/* same as default */
+index::nearest(rt, index::unbounded(pt), k, std::back_inserter(returned_values));
+
+/* distance must be greater than or equal to 10 */
+index::nearest(rt, index::min_bounded(pt, 10), k, std::back_inserter(returned_values));
+
+/* distance must be lesser than or equal to 500 */
+index::nearest(rt, index::max_bounded(pt, 500), k, std::back_inserter(returned_values));
+
+/* distance must be between 10 and 500 */
+index::nearest(rt, index::bounded(pt, 10, 500), k, std::back_inserter(returned_values));
+</pre>
+
+ Furthermore, it's possible to define if the closest, furthest or centroidal
+ point of the non-point <code class="computeroutput">__Indexable__</code>
+ should be taken into account in the routine calculating distance.
+ 
+<pre class="programlisting">std::vector<Value> returned_values;
+Point pt(...);
+
+/* default - distance between __indexable__'s closest point and a query point
+must be greater than 10 */
+index::nearest(rt, index::min_bounded(pt, 10), k, std::back_inserter(returned_values));
+
+/* same as default - distance between __indexable__'s closest point and a query point
+must be greater than 10 */
+index::nearest(rt, index::min_bounded(pt, index::near(10)), k, std::back_inserter(returned_values));
+
+/* distance between __indexable__'s furthest point and a query point
+must be greater than 10 */
+index::nearest(rt, index::min_bounded(pt, index::far(10)), k, std::back_inserter(returned_values));
+
+/* distance between __indexable__'s centroid and a query point
+must be greater than 10 */
+index::nearest(rt, index::min_bounded(pt, index::centroid(10)), k, std::back_inserter(returned_values));
+</pre>
+</div>
+<div class="section">
+<div class="titlepage"><div><div><h4 class="title">
+<a name="geometry_index.r_tree.nearest_neighbors_queries.using_spatial_predicates"></a><a class="link" href="r_tree.html#geometry_index.r_tree.nearest_neighbors_queries.using_spatial_predicates" title="Using spatial predicates">Using
+ spatial predicates</a>
+</h4></div></div></div>
+
+ It is possible to use spatial predicates described before in nearest neighbors
+ queries.
+ 
+<pre class="programlisting">Value returned_value;
+std::vector<Value> returned_values;
+
+Point pt(...);
+Box b(...);
+
+size_t n1 = rt.nearest(index::bounded(pt, index::far(1), 10), index::intersects(b), returned_value);
+
+size_t n2 = index::nearest(rt, pt, k, index::within(b), std::back_inserter(returned_values));
+
+BOOST_FOREACH(Value & v, rt | index::nearest_filtered(pt, k, index::covered_by(b)))
+ ; // do something with v
+</pre>
+</div>
+</div>
+</div>
+<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
+<td align="left"></td>
+<td align="right"><div class="copyright-footer">Copyright © 2011 Adam Wulkiewicz, Federico J. Fernandez
+ Distributed under 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)
+ 
+</div></td>
+</tr></table>
+<hr>
+<div class="spirit-nav">
+<a accesskey="p" href="introduction.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a>
+</div>
+</body>
+</html>

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 2011-11-29 22:22:14 EST (Tue, 29 Nov 2011)
@@ -1,11 +1,11 @@
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
-<title>Chapter 1. Boost.Geometry.Index</title>
+<title>Chapter 1. Geometry Index 0.7</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
-<link rel="home" href="index.html" title="Chapter 1. Boost.Geometry.Index">
-<link rel="next" href="index/rtree.html" title="R-tree">
+<link rel="home" href="index.html" title="Chapter 1. Geometry Index 0.7">
+<link rel="next" href="geometry_index/introduction.html" title="Introduction">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
@@ -17,55 +17,47 @@
<td align="center">More</td>
</tr></table>
<hr>
-<div class="spirit-nav"><a accesskey="n" href="index/rtree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a></div>
+<div class="spirit-nav"><a accesskey="n" href="geometry_index/introduction.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a></div>
<div class="chapter">
<div class="titlepage"><div>
<div><h2 class="title">
-<a name="index"></a>Chapter 1. Boost.Geometry.Index</h2></div>
+<a name="geometry"></a>Chapter 1. Geometry Index 0.7</h2></div>
<div><div class="author"><h3 class="author">
-Federico J. Fernandez
+Adam Wulkiewicz
</h3></div></div>
<div><div class="author"><h3 class="author">
-Adam Wulkiewicz
+Federico J. Fernandez
</h3></div></div>
-<div>Copyright © 2008 Federico J. Fernandez</div>
-<div>Copyright © 2011 Adam Wulkiewicz</div>
+<div>Copyright © 2011 Adam Wulkiewicz, Federico J. Fernandez</div>
<div><div class="legalnotice">
-<a name="id821289"></a>Use, modification and distribution is subject to the Boost
- Software License, Version 1.0. (See accompanying file
- <code class="filename">LICENSE_1_0.txt</code> or copy at http://www.boost.org/LICENSE_1_0.txt)
+<a name="id783458"></a>
+ Distributed under 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)
+ 
</div></div>
</div></div>
<div class="toc">
Table of Contents
<dl>
-<dt>Introduction</dt>
-<dt>R-tree</dt>
+<dt>Introduction</dt>
+<dt>R-tree</dt>
<dd><dl>
-<dt>Introduction</dt>
-<dt>R-tree creation</dt>
-<dt>Inserting and removing Values</dt>
-<dt>Spatial queries</dt>
-<dt>Nearest neighbors queries</dt>
+<dt>Introduction</dt>
+<dt>R-tree creation</dt>
+<dt><a href="geometry_index/r_tree.html#geometry_index.r_tree.inserting_and_removing_values">Inserting
+ and removing Values</a></dt>
+<dt>Spatial queries</dt>
+<dt><a href="geometry_index/r_tree.html#geometry_index.r_tree.nearest_neighbors_queries">Nearest
+ neighbors queries</a></dt>
</dl></dd>
</dl>
</div>
-<div class="section">
-<div class="titlepage"><div><div><h2 class="title" style="clear: both">
-<a name="index.intro"></a>Introduction</h2></div></div></div>
-The Boost.Geometry.Index library is intetended to gather containers
-(spatial indexes) used for speeding spatial queries up. In general, indexes
-stores geometric objects' representations and allows searching for objects
-occupying some space or close to some point in space.
-
-Currently, only one spatial index is implemented - the R-tree.
-</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left"></td>
+<td align="left">Last revised: November 30, 2011 at 03:13:32 GMT</td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
-<div class="spirit-nav"><a accesskey="n" href="index/rtree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a></div>
+<div class="spirit-nav"><a accesskey="n" href="geometry_index/introduction.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a></div>
</body>
</html>

Added: sandbox-branches/geometry/index/doc/index.qbk
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/doc/index.qbk 2011-11-29 22:22:14 EST (Tue, 29 Nov 2011)
@@ -0,0 +1,47 @@
+[/============================================================================
+ Boost.Geometry Index (Spatial Indexes)
+
+ Copyright (c) 2008 Federico J. Fernandez.
+ Copyright (c) 2011 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)
+=============================================================================/]
+
+[library Geometry Index
+ [quickbook 1.5]
+ [version 0.7]
+ [authors [Wulkiewicz, Adam], [Fernandez, Federico J.]]
+ [copyright 2011 Adam Wulkiewicz, Federico J. Fernandez]
+ [purpose Documentation of Boost.Geometry Index library]
+ [license
+ Distributed under 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])
+ ]
+ [id geometry]
+ [category geometry]
+]
+
+[def __box__ [@http://www.boost.org/libs/geometry/doc/html/geometry/reference/concepts/concept_box.html Box]]
+[def __point__ [@http://www.boost.org/libs/geometry/doc/html/geometry/reference/concepts/concept_point.html Point]]
+
+[def __boost__ [@http://www.boost.org/libs/libraries.htm Boost]]
+[def __boost_geometry__ [@http://www.boost.org/libs/geometry/doc/html/index.html Boost.Geometry]]
+[def __boost_geometry_index__ Boost.Geometry Index]
+
+[def __rtree__ R-tree]
+
+[def __value__ Value]
+[def __parameters__ Parameters]
+[def __translator__ Translator]
+[def __allocator__ Allocator]
+[def __indexable__ Indexable]
+
+[def __cgeometry__ [@http://www.boost.org/libs/geometry/doc/html/index.html geometry]]
+[def __cboost__ [@http://www.boost.org/libs/libraries.htm boost]]
+
+[include introduction.qbk]
+
+[include rtree.qbk]

Deleted: sandbox-branches/geometry/index/doc/index.xml
==============================================================================
--- sandbox-branches/geometry/index/doc/index.xml 2011-11-29 22:22:14 EST (Tue, 29 Nov 2011)
+++ (empty file)
@@ -1,428 +0,0 @@
-<?xml version="1.0" encoding="utf-8"?>
-<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
- "http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
-<library name="Geometry.Index" dirname="index" id="index"
- xmlns:xi="http://www.w3.org/2001/XInclude">
-<libraryinfo>
- <author>
- <firstname>Federico J.</firstname>
- <surname>Fernandez</surname>
- </author>
- <author>
- <firstname>Adam</firstname>
- <surname>Wulkiewicz</surname>
- </author>
-
- <copyright>
- <year>2008</year>
- <holder>Federico J. Fernandez</holder>
- </copyright>
- <copyright>
- <year>2011</year>
- <holder>Adam Wulkiewicz</holder>
- </copyright>
-
- <legalnotice>
- <para>Use, modification and distribution is subject to the Boost
- Software License, Version 1.0. (See accompanying file
- <filename>LICENSE_1_0.txt</filename> or copy at <ulink
- url="http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt>)</para>
- </legalnotice>
-
- <librarypurpose>Spatial indexes for faster spatial and knn queries.</librarypurpose>
- <librarycategory name="category:data-structures"/>
-</libraryinfo>
-
-<title>Boost.Geometry.Index</title>
-
-<section id="index.intro">
-<title>Introduction</title>
-<para>The Boost.Geometry.Index library is intetended to gather containers
-(spatial indexes) used for speeding spatial queries up. In general, indexes
-stores geometric objects' representations and allows searching for objects
-occupying some space or close to some point in space.
-</para>
-
-<para>Currently, only one spatial index is implemented - the R-tree.</para>
-</section>
-
-<section id="index.rtree">
-<title>R-tree</title>
-
-<section>
-<title>Introduction</title>
-<para>
-R-tree is a self-balancing search tree with nodes stored with their axis aligned
-bounding boxes. Each node's box describes the space occupied by children nodes.
-At the bottom of the structure, there are leaf-nodes which contains values
-(geometric objects representations). Minimal and maximal numbers of values/children
-which may be stored inside the node are user defined.
-</para>
-
-<para>
-In order to use the R-tree one must include folowing file.
-<programlisting>
-#include <boost/geometry/extensions/index/rtree/rtree.hpp>
-</programlisting>
-</para>
-</section>
-
-<section>
-<title>R-tree creation</title>
-
-<section>
-<title>Quick start</title>
-<para>
-In order to create a R-tree object storing values of type
-<code>std::pair<Box, int></code> one may use the following code
-<programlisting>
-using namespace boost::geometry;
-typedef std::pair<Box, int> Value;
-index::rtree< Value, index::quadratic<32, 8> > rt;
-</programlisting>
-</para>
-</section>
-
-<section>
-<title>R-tree template parameters</title>
-<para>
-R-tree has 4 parameters:
-<programlisting>
-rtree<Value, Parameters, Translator, Allocator>
-</programlisting>
-<itemizedlist>
-<listitem>
-<code>Value</code> - type of object which will be stored in the container.
-</listitem>
-<listitem>
-<code>Parameters</code> - compile-time parameters, e.g. inserting/splitting
-algorithm with min and max nodes' elements numbers.
-</listitem>
-<listitem>
-<code>Translator</code> - type of object translating <code>Value</code> objects
-to <code>Indexable</code> objects (<code>Point</code> or <code>Box</code>) which
-R-tree can handle.
-</listitem>
-<listitem>
-<code>Allocator</code> - the allocator.
-</listitem>
-</itemizedlist>
-</para>
-</section>
-
-<section>
-<title>Values, Indexables and default Translator</title>
-<para>
-R-tree may store <code>Value</code>s of any type as long as there is passed
-the <code>Translator</code> which knows how to interpret those <code>Value</code>s
-and extract an object understandable by the R-tree. Those objects are called
-<code>Indexables</code> and they are simply of type adapted to <code>Point</code>
-or <code>Box</code> concept. Default translator <code>index::translator::def<Value></code>
-is able to handle <code>Point</code>, <code>Box</code>, <code>std::pair<...></code>,
-pointer, iterator or smart pointer.
-<itemizedlist>
-<listitem><code>Indexable = Point | Box</code></listitem>
-<listitem><code>BasicValue = Indexable | std::pair<Indexable, T> | std::pair<T, Indexable></code></listitem>
-<listitem><code>Value = BasicValue | BasicValue* | Iterator<BasicValue> | SmartPtr<BasicValue></code></listitem>
-</itemizedlist>
-Examples of <code>Value</code> types:
-<itemizedlist>
-<listitem><code>geometry::model::point<...></code></listitem>
-<listitem><code>geometry::model::point_xy<...></code></listitem>
-<listitem><code>geometry::model::box<...></code></listitem>
-<listitem><code>std::pair<geometry::model::box<...>, size_t></code></listitem>
-</itemizedlist>
-</para>
-</section>
-
-<section>
-<title>Inserting and splitting algorithms</title>
-<para>
-<code>Value</code>s may be inserted to the R-tree in many various ways. Final structure of nodes depends
-on algorithms used in the process, especially nodes' splitting algorithm. Currently, three
-well-known types of R-trees may be created.
-<itemizedlist>
-<listitem>
-Linear - classic R-tree using splitting algorithm of linear complexity
-<programlisting>
-index::rtree< Value, index::linear<32, 8> > rt;
-</programlisting>
-</listitem>
-<listitem>
-Quadratic - classic R-tree using splitting algorithm of quadratic complexity
-<programlisting>
-index::rtree< Value, index::quadratic<32, 8> > rt;
-</programlisting>
-</listitem>
-<listitem>
-R*-tree - splitting algorithm minimizing nodes' overlap with forced reinsertions
-<programlisting>
-index::rtree< Value, index::rstar<32, 8> > rt;
-</programlisting>
-</listitem>
-</itemizedlist>
-</para>
-</section>
-
-</section>
-
-<section>
-<title>Inserting and removing Values</title>
-<para>
-Create
-<programlisting>
-using namespace boost::geometry;
-typedef std::pair<Box, int> Value;
-index::rtree< Value, index::quadratic<32, 8> > rt;
-</programlisting>
-Insert and remove by method call
-<programlisting>
-Value v = std::make_pair(Box(...), 0);
-rt.insert(v);
-rt.remove(v);
-</programlisting>
-or by function call
-<programlisting>
-Value v = std::make_pair(Box(...), 0);
-index::insert(rt, v);
-index::remove(rt, v);
-</programlisting>
-</para>
-</section>
-
-<section>
-<title>Spatial queries</title>
-
-<section>
-<title>Basic queries</title>
-<para>
-There are three ways to perform a spatial query. Following queries returns
-<code>Value</code>s intersecting some box_region.
-<itemizedlist>
-<listitem>
-Method call
-<programlisting>
-std::vector<Value> returned_values;
-Box box_region(...);
-rt.query(box_region, std::back_inserter(returned_values));
-</programlisting>
-</listitem>
-<listitem>
-Function call
-<programlisting>
-std::vector<Value> returned_values;
-Box box_region(...);
-index::query(rt, box_region, std::back_inserter(returned_values));
-</programlisting>
-</listitem>
-<listitem>
-Use of <code>operator |</code> (as with ranges)
-<programlisting>
-Box box_region(...);
-BOOST_FOREACH(Value &v, rt | index::query_filtered(box_region))
- ;// do something with v
-</programlisting>
-</listitem>
-</itemizedlist>
-</para>
-</section>
-
-<section>
-<title>Spatial predicates</title>
-<para>
-It is possible to define other relations between queried <code>Value</code>s and region/regions
-of interest. Names of predicates corresponds to names of Boost.Geometry algorithms.
-<programlisting>
-rt.query(box, std::back_inserter(result)); // default case - intersects
-rt.query(index::intersects(box), std::back_inserter(result)); // same as default
-rt.query(index::covered_by(box), std::back_inserter(result));
-rt.query(index::disjont(box), std::back_inserter(result));
-rt.query(index::overlaps(box), std::back_inserter(result));
-rt.query(index::within(box), std::back_inserter(result));
-</programlisting>
-All predicates may be negated, e.g.:
-<programlisting>
-rt.query(index::not_intersects(box), std::back_inserter(result));
-// or
-rt.query(!index::intersects(box), std::back_inserter(result));
-// the same as
-rt.query(index::disjoint(box), std::back_inserter(result));
-</programlisting>
-It's possible to use some number of predicates by passing <code>std::pair<Pred1, Pred2></code>
-<programlisting>
-rt.query(
- std::make_pair(index::intersects(box1), !index::within(box2))
- , std::back_inserter(result));
-</programlisting>
-or <code>boost::tuple<Pred1, Pred2, Pred3, ...></code>
-<programlisting>
-rt.query(
- boost::make_tuple(index::intersects(box1), !index::within(box2), index::overlaps(box3))
- , std::back_inserter(result));
-</programlisting>
-There is special predicate <code>index::value(Fun)</code> taking user-defined function/functor
-which checks if <code>Value</code> should be returned by the query.
-<programlisting>
-bool fun(Value const& v)
-{
- return v.is_red();
-}
-
-// ...
-
-rt.query(
- boost::make_pair(index::intersects(box), index::value(fun))
- , std::back_inserter(result));
-</programlisting>
-</para>
-</section>
-
-</section>
-
-<section>
-<title>Nearest neighbors queries</title>
-
-<section>
-<title>k nearest neighbors</title>
-<para>
-There are three ways of performing knn queries. Following queries returns
-k <code>Value</code>s closest to some point in space. For <code>Box</code>es
-<code>Indexable</code>s closest point of a <code>Box</code> is taken into
-account by default.
-<itemizedlist>
-<listitem>
-Method call
-<programlisting>
-std::vector<Value> returned_values;
-Point pt(...);
-rt.nearest(pt, k, std::back_inserter(returned_values));
-</programlisting>
-</listitem>
-<listitem>
-Function call
-<programlisting>
-std::vector<Value> returned_values;
-Point pt(...);
-index::nearest(rt, pt, k, std::back_inserter(returned_values));
-</programlisting>
-</listitem>
-<listitem>
-Use of <code>operator |</code>
-<programlisting>
-Point pt(...);
-BOOST_FOREACH(Value &v, rt | index::nearest_filtered(pt, k))
- ;// do something with v
-</programlisting>
-</listitem>
-</itemizedlist>
-</para>
-</section>
-
-<section>
-<title>One nearest neighbor</title>
-<para>
-Another type of nearest neighbor query is searching for the one closest <code>Value</code>.
-If it is found, 1 is returned by the method or function. This kind of query
-has only two forms.
-<itemizedlist>
-<listitem>
-Method call
-<programlisting>
-Value returned_value;
-Point pt(...);
-size_t n = rt.nearest(pt, returned_value);
-</programlisting>
-</listitem>
-<listitem>
-Function call
-<programlisting>
-Value returned_value;
-Point pt(...);
-size_t n = index::nearest(rt, pt, returned_value);
-</programlisting>
-</listitem>
-</itemizedlist>
-</para>
-</section>
-
-<section>
-<title>Distances predicates</title>
-<para>
-It is possible to define if calculated distance between query point and <code>Value</code> should be
-greater, lesser or between some other distances. Those are called <code>DistancesPredicate</code>s and
-may be defined as follows.
-<programlisting>
-std::vector<Value> returned_values;
-Point pt(...);
-
-/* default - without bounds */
-index::nearest(rt, pt, k, std::back_inserter(returned_values));
-
-/* same as default */
-index::nearest(rt, index::unbounded(pt), k, std::back_inserter(returned_values));
-
-/* distance must be greater than or equal to 10 */
-index::nearest(rt, index::min_bounded(pt, 10), k, std::back_inserter(returned_values));
-
-/* distance must be lesser than or equal to 500 */
-index::nearest(rt, index::max_bounded(pt, 500), k, std::back_inserter(returned_values));
-
-/* distance must be between 10 and 500 */
-index::nearest(rt, index::bounded(pt, 10, 500), k, std::back_inserter(returned_values));
-
-</programlisting>
-</para>
-
-<para>
-Furthermore, it's possible to define if the closest, furthest or centroidal point of the
-non-point <code>Indexable</code> should be taken into account in the routine calculating distance.
-<programlisting>
-std::vector<Value> returned_values;
-Point pt(...);
-
-/* default - distance between Indexable's closest point and a query point
-must be greater than 10 */
-index::nearest(rt, index::min_bounded(pt, 10), k, std::back_inserter(returned_values));
-
-/* same as default - distance between Indexable's closest point and a query point
-must be greater than 10 */
-index::nearest(rt, index::min_bounded(pt, index::near(10)), k, std::back_inserter(returned_values));
-
-/* distance between Indexable's furthest point and a query point
-must be greater than 10 */
-index::nearest(rt, index::min_bounded(pt, index::far(10)), k, std::back_inserter(returned_values));
-
-/* distance between Indexable's centroid and a query point
-must be greater than 10 */
-index::nearest(rt, index::min_bounded(pt, index::centroid(10)), k, std::back_inserter(returned_values));
-</programlisting>
-</para>
-
-</section>
-
-<section>
-<title>Using spatial predicates</title>
-<para>
-It is possible to use spatial predicates described before in nearest neighbors queries.
-<programlisting>
-Value returned_value;
-std::vector<Value> returned_values;
-
-Point pt(...);
-Box b(...);
-
-size_t n1 = rt.nearest(index::bounded(pt, index::far(1), 10), index::intersects(b), returned_value);
-
-size_t n2 = index::nearest(rt, pt, k, index::within(b), std::back_inserter(returned_values));
-
-BOOST_FOREACH(Value &v, rt | index::nearest_filtered(pt, k, index::covered_by(b)))
- ;// do something with v
-</programlisting>
-</para>
-</section>
-
-</section>
-
-</section>
-
-</library>

Added: sandbox-branches/geometry/index/doc/rtree.qbk
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/doc/rtree.qbk 2011-11-29 22:22:14 EST (Tue, 29 Nov 2011)
@@ -0,0 +1,317 @@
+[/============================================================================
+ Boost.Geometry Index (Spatial Indexes)
+
+ Copyright (c) 2008 Federico J. Fernandez.
+ Copyright (c) 2011 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 R-tree]
+
+[section Introduction]
+
+__rtree__ is a self-balancing search tree with nodes stored with their axis aligned
+bounding boxes. Each node's box describes the space occupied by children nodes.
+At the bottom of the structure, there are leaf-nodes which contains values
+(geometric objects representations). Minimal and maximal numbers of values/children
+which may be stored inside the node are user defined.
+
+In order to use the __rtree__ one must include folowing file.
+
+ #include <boost/geometry/extensions/index/rtree/rtree.hpp>
+
+[endsect]
+
+[section R-tree creation]
+
+[section Quick start]
+
+In order to create a __rtree__ object storing values of type `std::pair<__box__, size_t>`
+one may use the following code:
+
+ using namespace __cboost__::__cgeometry__;
+ typedef std::pair<__box__, size_t> Value;
+ index::rtree< Value, index::quadratic<32, 8> > rt;
+
+[endsect]
+
+[section R-tree template parameters]
+
+__rtree__ has 4 parameters:
+
+ rtree<Value, Parameters, Translator, Allocator>
+
+* `Value` - type of object which will be stored in the container.
+* `Parameters` - compile-time parameters, e.g. inserting/splitting
+ algorithm with min and max nodes' elements numbers.
+* `Translator` - type of object translating `Value` objects to
+ `Indexable` objects (`__point__` or `__box__`) which __rtree__ can handle.
+* `Allocator` - the allocator.
+
+[endsect]
+
+[section Values, Indexables and default Translator]
+
+__rtree__ may store `__value__`s of any type as long as there is passed
+the `__translator__` which knows how to interpret those `__value__`s
+and extract an object understandable by the __rtree__. Those objects are called
+`__indexable__`s and they are simply of type adapted to `__point__`
+or `__box__` concept. Default `__translator__` `index::translator::def<Value>`
+is able to handle `__point__`, `__box__`, `std::pair<...>`, pointer, iterator
+or smart pointer.
+
+* `__indexable__ = __point__ | __box__`
+* `BasicValue = Indexable | std::pair<__indexable__, T> | std::pair<T, __indexable__>`
+* `__value__ = BasicValue | BasicValue* | Iterator<BasicValue> | SmartPtr<BasicValue>`
+
+Examples of `__value__` types:
+
+ geometry::model::point<...>
+ geometry::model::point_xy<...>
+ geometry::model::box<...>
+ std::pair<geometry::model::box<...>, size_t>
+
+[endsect]
+
+[section Inserting and splitting algorithms]
+
+`__value__`s may be inserted to the __rtree__ in many various ways. Final structure of nodes depends
+on algorithms used in the process, especially nodes' splitting algorithm. Currently, three
+well-known types of R-trees may be created.
+
+Linear - classic __rtree__ using splitting algorithm of linear complexity
+
+ index::rtree< __value__, index::linear<32, 8> > rt;
+
+Quadratic - classic __rtree__ using splitting algorithm of quadratic complexity
+
+ index::rtree< __value__, index::quadratic<32, 8> > rt;
+
+R*-tree - splitting algorithm minimizing nodes' overlap with forced reinsertions
+
+ index::rtree< __value__, index::rstar<32, 8> > rt;
+
+[endsect]
+
+[endsect] [/ R-tree creation /]
+
+[section Inserting and removing Values]
+
+Create
+
+ using namespace boost::geometry;
+ typedef std::pair<Box, int> __value__;
+ index::rtree< __value__, index::quadratic<32, 8> > rt;
+
+Insert and remove by method call
+
+ __value__ v = std::make_pair(__box__(...), 0);
+ rt.insert(v);
+ rt.remove(v);
+
+or by function call
+
+ __value__ v = std::make_pair(__box__(...), 0);
+ index::insert(rt, v);
+ index::remove(rt, v);
+
+[endsect]
+
+[section Spatial queries]
+
+[section Basic queries]
+
+There are three ways to perform a spatial query. Following queries returns
+`__value__`s intersecting some box_region.
+
+Method call
+
+ std::vector<__value__> returned_values;
+ __box__ box_region(...);
+ rt.query(box_region, std::back_inserter(returned_values));
+
+Function call
+
+ std::vector<__value__> returned_values;
+ __box__ box_region(...);
+ index::query(rt, box_region, std::back_inserter(returned_values));
+
+Use of `operator |` (as with ranges)
+
+ __box__ box_region(...);
+ BOOST_FOREACH(__value__ & v, rt | index::query_filtered(box_region))
+ ; // do something with v
+[endsect]
+
+[section Spatial predicates]
+
+It is possible to define other relations between queried `__value__`s and region/regions
+of interest. Names of predicates corresponds to names of __boost_geometry__ algorithms.
+
+ rt.query(box, std::back_inserter(result)); // default case - intersects
+ rt.query(index::intersects(box), std::back_inserter(result)); // same as default
+ rt.query(index::covered_by(box), std::back_inserter(result));
+ rt.query(index::disjont(box), std::back_inserter(result));
+ rt.query(index::overlaps(box), std::back_inserter(result));
+ rt.query(index::within(box), std::back_inserter(result));
+
+All predicates may be negated, e.g.:
+
+ rt.query(index::not_intersects(box), std::back_inserter(result));
+ // or
+ rt.query(!index::intersects(box), std::back_inserter(result));
+ // the same as
+ rt.query(index::disjoint(box), std::back_inserter(result));
+
+It's possible to use some number of predicates by passing `std::pair<Pred1, Pred2>`
+
+ rt.query(
+ std::make_pair(index::intersects(box1), !index::within(box2))
+ , std::back_inserter(result));
+
+or `boost::tuple<Pred1, Pred2, Pred3, ...>`
+
+ rt.query(
+ boost::make_tuple(
+ index::intersects(box1), !index::within(box2), index::overlaps(box3))
+ , std::back_inserter(result));
+
+There is also a unique predicate `index::value(...)` taking user-defined function/functor
+which checks if `__value__` should be returned by the query.
+
+ bool fun(__value const& v)
+ {
+ return v.is_red();
+ }
+
+ // ...
+
+ rt.query(
+ boost::make_pair(index::intersects(box), index::value(fun))
+ , std::back_inserter(result));
+
+[endsect]
+
+[endsect] [/ Spatial queries /]
+
+[section Nearest neighbors queries]
+
+[section k nearest neighbors]
+
+There are three ways of performing knn queries. Following queries returns
+k `__value__`s closest to some point in space. For `__box__`es
+`__indexable__`s closest point of a `__box__` is taken into account by default.
+
+Method call
+
+ std::vector<__value__> returned_values;
+ __point__ pt(...);
+ rt.nearest(pt, k, std::back_inserter(returned_values));
+
+Function call
+
+ std::vector<__value__> returned_values;
+ __point__ pt(...);
+ index::nearest(rt, pt, k, std::back_inserter(returned_values));
+
+Use of `operator |`
+
+ __point__ pt(...);
+ BOOST_FOREACH(__value__ & v, rt | index::nearest_filtered(pt, k))
+ ; // do something with v
+
+[endsect]
+
+[section One nearest neighbor]
+
+Another type of nearest neighbor query is searching for the one closest `__value__`.
+If it is found, 1 is returned by the method or function. This kind of query
+has only two forms.
+
+Method call
+
+ __value__ returned_value;
+ __point__ pt(...);
+ size_t n = rt.nearest(pt, returned_value);
+
+Function call
+
+ __value__ Value returned_value;
+ __point__ pt(...);
+ size_t n = index::nearest(rt, pt, returned_value);
+
+[endsect]
+
+[section Distances predicates]
+
+It is possible to define if calculated distance between query point and `__value__` should be
+greater, lesser or between some other distances. Those are called `DistancesPredicate`s and
+may be defined as follows.
+
+ std::vector<__Value__> returned_values;
+ __point__ pt(...);
+
+ /* default - without bounds */
+ index::nearest(rt, pt, k, std::back_inserter(returned_values));
+
+ /* same as default */
+ index::nearest(rt, index::unbounded(pt), k, std::back_inserter(returned_values));
+
+ /* distance must be greater than or equal to 10 */
+ index::nearest(rt, index::min_bounded(pt, 10), k, std::back_inserter(returned_values));
+
+ /* distance must be lesser than or equal to 500 */
+ index::nearest(rt, index::max_bounded(pt, 500), k, std::back_inserter(returned_values));
+
+ /* distance must be between 10 and 500 */
+ index::nearest(rt, index::bounded(pt, 10, 500), k, std::back_inserter(returned_values));
+
+Furthermore, it's possible to define if the closest, furthest or centroidal point of the
+non-point `__Indexable__` should be taken into account in the routine calculating distance.
+
+ std::vector<__value__> returned_values;
+ __point__ pt(...);
+
+ /* default - distance between __indexable__'s closest point and a query point
+ must be greater than 10 */
+ index::nearest(rt, index::min_bounded(pt, 10), k, std::back_inserter(returned_values));
+
+ /* same as default - distance between __indexable__'s closest point and a query point
+ must be greater than 10 */
+ index::nearest(rt, index::min_bounded(pt, index::near(10)), k, std::back_inserter(returned_values));
+
+ /* distance between __indexable__'s furthest point and a query point
+ must be greater than 10 */
+ index::nearest(rt, index::min_bounded(pt, index::far(10)), k, std::back_inserter(returned_values));
+
+ /* distance between __indexable__'s centroid and a query point
+ must be greater than 10 */
+ index::nearest(rt, index::min_bounded(pt, index::centroid(10)), k, std::back_inserter(returned_values));
+
+[endsect]
+
+[section Using spatial predicates]
+
+It is possible to use spatial predicates described before in nearest neighbors queries.
+
+ __value__ returned_value;
+ std::vector<__value__> returned_values;
+
+ __point__ pt(...);
+ __box__ b(...);
+
+ size_t n1 = rt.nearest(index::bounded(pt, index::far(1), 10), index::intersects(b), returned_value);
+
+ size_t n2 = index::nearest(rt, pt, k, index::within(b), std::back_inserter(returned_values));
+
+ BOOST_FOREACH(Value & v, rt | index::nearest_filtered(pt, k, index::covered_by(b)))
+ ; // do something with v
+
+[endsect]
+
+[endsect] [/ Nearest neighbors queries /]
+
+[endsect] [/ R-tree /]

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk