Boost-Commit :

Date view	Thread view	Subject view	Author view

From: mariano.consoni_at_[hidden]
Date: 2008-06-04 16:05:13

Next message: troy_at_[hidden]: "[Boost-commit] svn:boost r46142 - branches/CMake/release/libs"
Previous message: mariano.consoni_at_[hidden]: "[Boost-commit] svn:boost r46140 - in sandbox/SOC/2008/spacial_indexing/geometry/doc: . doxygen doxygen/html"

Author: mconsoni
Date: 2008-06-04 16:05:13 EDT (Wed, 04 Jun 2008)
New Revision: 46141
URL: http://svn.boost.org/trac/boost/changeset/46141

Log:
- Initial Geometry Library integration.
-> we add the current code
-> the quadtree code was modificated to adapt to the new point and box classes.
-> simple_test was adapted to the new style (the other tests are pending)

Added:
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/algorithms.html (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/classes.html (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/examples.html (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/clip_polygon_example.png (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/clip_polygon_example.svg (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/geometries.svg (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/intersection_linestring_example.png (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/linestring.png (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/linestring_example.svg (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/linestring_intersection_example.svg (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/multi_polygon.png (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/polygon.png (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/polygon_example1.svg (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/simplify_example.png (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/simplify_example.svg (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/within_polygon_example.png (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/within_polygon_example.svg (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/rationale.html (contents, props changed)

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/algorithms.html
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/algorithms.html 2008-06-04 16:05:13 EDT (Wed, 04 Jun 2008)
@@ -0,0 +1,775 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head>
+<meta content="text/html; charset=ISO-8859-1" http-equiv="Content-Type"><title>Algorithms</title>
+
+<link type="text/css" href="../boostbook.css" rel="stylesheet"></head>
+<body style="color: black; background-color: white; background-image: url(../images/draft.png);" alink="#0000ff" link="#0000ff" vlink="#840084">
+<table cellpadding="2" width="100%">
+<tbody>
+<tr>
+<td valign="top"><img alt="Boost C++ Libraries" src="../proposed_boost.png" height="86" width="277"></td>
+</tr>
+</tbody>
+</table>
+<hr>
+<div class="spirit-nav"><a accesskey="p" href="classes.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/prev.png" alt="Prev"></a><a accesskey="u" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/up.png" alt="Up"></a><a accesskey="h" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/home.png" alt="Home"></a><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/next_disabled.png" alt="Next"></div>
+<div class="section" lang="en">
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.concept"></a>Algorithms</h2>
+</div>
+</div>
+<p>The Geometry Library contains geometry classes and algorithms,
+which
+are separated from each other. This page describes the geometry
+algorithms.
+</p>
+<p>Most geometry algorithms are templatized in two ways. This is described in the rationale.
+</p><p>OGC made standards on geometries, called <i>simple
+features</i>, and defines operations on geometries.
+In OGC all operations are class methods. The Geometry Library is a
+template library and defines the operations as standalone algorithms.
+The Geometry Library follows the OGC names for the naming of
+the algorithms.</p>
+<p>The Geometry Library implements the following OGC algorithms,
+which are
+applicable to most or all geometries
+</p>
+<table class="table" summary="Notation">
+<tbody>
+<tr>
+<td align="left"><code class="computeroutput">within</code></td>
+<td align="left">
+<p>Returns true if one geometry falls
+completely within another geometry</p>
+</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">distance</code></td>
+<td align="left">
+<p>Returns the distance between two
+geometries</p>
+</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">intersection</code></td>
+<td align="left">
+<p>Returns a geometry containing the
+intersection between two geometries</p>
+</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">envelope</code></td>
+<td align="left">
+<p>Returns the bounding box of a
+geometry
+</p>
+</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">as_text</code></td>
+<td align="left">
+<p>Represents the geometry as a Well
+Known Text</p>
+</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">area</code></td>
+<td align="left">
+<p>Returns the area of
+surface-geometries</p>
+</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">length</code></td>
+<td align="left">
+<p>Returns the length of curve-type
+geometries</p>
+</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">centroid</code></td>
+<td align="left">
+<p>Returns a point geometry: the
+centroid on surface-geometries</p>
+</td>
+</tr><tr><td><code class="computeroutput">is_simple</code></td><td><p>Returns true if the geometry is simple (doesn't intersect itself)</p></td></tr>
+</tbody>
+</table>
+<br>
+<p>Apart from OGC, the following algorithms are provided:
+</p>
+<table class="table" summary="Notation">
+<colgroup><col><col></colgroup>
+<tbody>
+<tr>
+<td align="left"><code class="computeroutput">simplify</code></td>
+<td align="left">
+<p>Returns a simplified (or
+"generalized") linestring or polygon using the Douglas Peucker algorithm</p>
+</td>
+</tr>
+</tbody>
+</table>
+<br>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.within"></a>Within</h2>
+</div>
+</div>
+<p>The within algorithm checks if one geometry is located
+completely within another geometry. A well-known example is
+point-in-polygon, returning true if a point falls within a polygon. Many
+point-in-polygon algorithms ignore boundary cases (point is situated on
+boundary of polygon), however the within_point_in_polygon method should
+return true if a point is completely within the boundary of the
+polygon, and not on the boundary.</p>
+<p>
+There are many possibilities and the matrix below gives some details about implementation.</p>
+<table class="table">
+<tbody>
+<tr>
+<td>
+<p></p>
+</td>
+<td>
+<p>linear ring</p>
+</td>
+<td>
+<p>polygon</p>
+</td>
+<td>
+<p>multi_polygon</p>
+</td>
+<td>
+<p>box</p>
+</td>
+<td>
+<p>circle</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>point</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>linestring</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p><br>
+</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>polygon</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p><br>
+</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>multi_point</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p><br>
+</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>multi_linestring</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p><br>
+</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>multi_polygon</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p><br>
+</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+</tr>
+</tbody>
+</table>
+<p>All these algorithms are called <span style="font-weight: bold;">within</span>. As
+described in the rationale, all algorithms have a <span style="font-style: italic;">primary</span> version called within_<span style="font-style: italic;">GEOMETRY</span>_in_<span style="font-style: italic;">GEOMETRY</span>, where <span style="font-style: italic;">GEOMETRY</span> <span style="font-weight: bold;"> </span>is
+replaced by the name of the geometry. So there is an algorithm <span style="font-weight: bold;">within_point_in_polygon</span>.</p>
+<p><br>
+Examples:</p>
+<code class="computeroutput">typedef
+geometry::point<float> P;<br>
+geometry::polygon<P> poly;<br>
+<span style="color: rgb(102, 102, 102);">// polygon is
+filled with points somehow</span><br style="color: rgb(102, 102, 102);">
+P p;<br>
+std::cout << p << ((</code><code class="computeroutput">geometry::</code><code class="computeroutput">within(p, poly) ? "within" : "not
+within") << poly << std::endl;<br>
+<br>
+<span style="color: rgb(102, 102, 102);">// or, for
+example if you have your own polygon or a derived polygon, the primary
+version:</span><br style="color: rgb(102, 102, 102);">
+</code><code class="computeroutput">std::cout
+<< p << ((</code><code class="computeroutput">geometry::</code><code class="computeroutput">within_point_in_polygon(p, poly) ?
+"within" : "not within") << poly <<
+std::endl;<br>
+</code>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.geometry_traits"></a>Distance</h2>
+</div>
+</div>
+<p><code class="computeroutput"></code>The
+distance
+algorithm returns the distance between two geometries. The distance is
+always returned as a <span style="font-weight: bold;">double</span>
+type, regardless of the input type, because the distance between
+integer coordinates is a square root and might be a double.<br>
+<br>
+The generic versions are called <span style="font-weight: bold;">distance</span>
+and are defined for the following combinations:</p>
+<table class="table">
+<tbody>
+<tr>
+<td>
+<p></p>
+</td>
+<td>
+<p>point</p>
+</td>
+<td>
+<p>segment</p>
+</td>
+<td>
+<p>linestring</p>
+</td>
+<td>
+<p>polygon</p>
+</td>
+<td>
+<p>multi_point</p>
+</td>
+<td>
+<p>multi_linestring</p>
+</td>
+<td>
+<p>multi_polygon</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>point</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p><br>
+</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>segment</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+</tr>
+<tr>
+<td>
+<p>linestring</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+</tr>
+<tr>
+<td>
+<p>polygon</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+</tr>
+<tr>
+<td>
+<p>multi_point</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+</tr>
+<tr>
+<td>
+<p>multi_linestring</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+</tr>
+<tr>
+<td>
+<p>multi_polygon</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+</tr>
+</tbody>
+</table>
+<p>The primary versions are, for performance reasons, slightly
+different:
+they don't do the square root, they deliver the square
+distance. So there is a <span style="font-weight: bold;">square_distance_point_to_linestring</span></p>
+<p>Examples:</p>
+<code class="computeroutput">typedef
+geometry::point<float> P;<br>
+P p1(1,1), p2(3,4);<br>
+std::cout << "distance " << p1
+<< " - " << p2 << ": "
+<< geometry::distance(p1, p2);<br>
+<br>
+geometry::linestring<P> ls;<br>
+</code><code class="computeroutput">std::cout
+<< "distance " << p1 << " - "
+<< ls << ": " <<
+geometry::distance(p1, ls);<br>
+<br>
+<span style="color: rgb(102, 102, 102);">// or, also
+possible:</span><br style="color: rgb(102, 102, 102);">
+</code><code class="computeroutput">std::cout
+<< "distance " << p1 << " - "
+<< ls << ":
+" <<
+sqrt(geometry::square_distance_point_to_linestring(p1, ls));</code><code class="computeroutput"></code><br>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.linestring"></a>Intersection</h2>
+</div>
+</div>
+<p><code class="computeroutput"></code>The intersection algorithm
+intersects two geometries, resulting in a third geometry. Intersection
+can be implemented for OGC geometries. Besides that an often used
+intersection is the intersection of a linestring or a polygon with a
+box. This is normally called a <span style="font-weight: bold;">clip</span>.</p>
+<p>The matrix below gives some details about implementation.</p>
+<table class="table">
+<tbody>
+<tr>
+<td>
+<p></p>
+</td>
+<td>
+<p>linear ring</p>
+</td>
+<td>
+<p>polygon</p>
+</td>
+<td>
+<p>multi_polygon</p>
+</td>
+<td>
+<p>box</p>
+</td>
+
+</tr>
+<tr>
+<td>
+<p>point</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+<td>
+<p>implemented</p>
+</td>
+
+</tr>
+<tr>
+<td>
+<p>linestring</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p>implemented
+</p>
+</td>
+
+</tr>
+<tr>
+<td>
+<p>polygon</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p>implemented<br>
+</p>
+</td>
+
+</tr>
+<tr>
+<td>
+<p>multi_point</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p><br>
+</p>
+</td>
+
+</tr>
+<tr>
+<td>
+<p>multi_linestring</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p><br>
+</p>
+</td>
+
+</tr>
+<tr>
+<td>
+<p>multi_polygon</p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p></p>
+</td>
+<td>
+<p><br>
+</p>
+</td>
+
+</tr>
+</tbody>
+</table>
+<p>All these algorithms are called <span style="font-weight: bold;">intersection</span>. All algorithms have, again, a <span style="font-style: italic;">primary</span> version called intersection_<span style="font-style: italic;">GEOMETRY</span>_with_<span style="font-style: italic;">GEOMETRY</span>, where <span style="font-style: italic;">GEOMETRY</span> <span style="font-weight: bold;"> </span>is
+replaced by the name of the geometry. So there is an algorithm <span style="font-weight: bold;">intersection_polygon_with_box</span><br>
+</p><div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.polygon"></a>Envelope</h2>
+</div>
+</div>
+<p>The envelope algorithm calculates the bounding box, or envelope, of a geometry. It is defined for all geometries.</p><p>The envelope of a point is a box with zero area, the maximum and the minimum point of the box are set to the point itself.</p><p>The
+envelope of a linestring is the smalles box that contains all points of
+the specified linestring. If the linestring is empty, the envelope is
+the inverse infinite box, that is, the minimum point is very large (max
+infinite) and the maximum point is very small (min infinite).</p><p>The envelope for polygon, and for all multi geometries, are defined as the envelope of the linestring described above. </p><code class="computeroutput">
+
+</code>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.multi_point"></a>Area</h2>
+</div>
+</div>
+<p><code class="computeroutput"></code>The area of a geometry
+calculates the surface area of all geometries having a surface: box,
+circle, polygon, multi_polygon. The units are the square of the units
+used for the points defining the surface. If the polygon is defined in
+meters, the area is in square meters.<br>
+</p><code class="computeroutput"></code>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.multi_linestring"></a>Centroid</h2>
+</div>
+</div>
+<p>The centroid of a surface geometry returns a point which is the centroid the geometry.</p><code class="computeroutput">
+</code>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.multi_polygon"></a>Length</h2>
+</div>
+</div>
+
+<p><code class="computeroutput"></code>The length algorithm is
+implemented for the linestring and the multi_linestring geometry and
+results in the length of the linestring. If the points of a linestring
+have coordinates expressed in kilometers, the length of the line is
+expressed in kilometers as well.<br>
+</p><code class="computeroutput"></code>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.box"></a>As text</h2>
+</div>
+</div>
+<p><code class="computeroutput"></code>The as_text function streams the
+specified geometry as OGC Well Known Text. It is defined for OGC
+geometries. So it is not defined for <span style="font-weight: bold;">box</span> and <span style="font-weight: bold;">circle</span>.<br>
+</p><div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.circle"></a>Simplify</h2>
+</div>
+</div>
+<p><code class="computeroutput"></code>The simplify algorithm
+implementes the Douglas Peucker algorithm to simplify linestrings. It
+is implemented for linestrings, multi_linestrings, linear rings,
+polygons and multi_polygons. Note, however, that simplifying a valid
+simple polygon (which never intersects itself) might result in an
+invalid polygon, where the simplified rings intersect themselves or
+one of the other outer or inner rings.</p>
+</div>
+<table width="100%">
+<tbody>
+<tr>
+<td align="left"><small>
+<p>February 1, 2008</p>
+</small></td>
+<td align="right"><small>Copyright © 1995-2008 Barend Gehrels, Geodan Holding B.V. Amsterdam, the Netherlands</small></td>
+</tr>
+</tbody>
+</table>
+<hr>
+<div class="spirit-nav"><a accesskey="p" href="classes.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/prev.png" alt="Prev"></a><a accesskey="u" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/up.png" alt="Up"></a><a accesskey="h" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/home.png" alt="Home"></a><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/next_disabled.png" alt="Next"></div>
+</body></html>
\ No newline at end of file

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/classes.html
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/classes.html 2008-06-04 16:05:13 EDT (Wed, 04 Jun 2008)
@@ -0,0 +1,475 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head>
+<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Classes</title>
+
+<link rel="stylesheet" href="../boostbook.css" type="text/css"></head>
+<body style="color: black; background-color: white; background-image: url(../images/draft.png);" alink="#0000ff" link="#0000ff" vlink="#840084">
+<table cellpadding="2" width="100%">
+<tbody>
+<tr>
+<td valign="top"><img alt="Boost C++ Libraries" src="../proposed_boost.png" height="86" width="277"></td>
+</tr>
+</tbody>
+</table>
+<hr>
+<div class="spirit-nav"><a accesskey="p" href="rationale.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/prev.png" alt="Prev"></a><a accesskey="u" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/up.png" alt="Up"></a><a accesskey="h" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/home.png" alt="Home"></a><a accesskey="n" href="algorithms.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/next.png" alt="Next"></a></div>
+<div class="section" lang="en">
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.concept"></a>Classes</h2>
+</div>
+</div>
+The Geometry Library contains geometry classes and algorithms, which
+are separated from each other. This page describes the geometry
+classes.
+<br>
+<br>
+Geometry classes are templatized in many ways:
+point coordinate values can be defined using numeric types as <b>double</b>, <b>float</b> or <b>int</b>.
+Linestrings can have points of the type above,
+types derived from these point types or point types defined  by the library user. Points are contained in containers of
+type std::vector or another std:: container type.
+<br>
+<br>
+OGC made standards on those geometries, and called them <i>simple
+features</i>.
+ The Geometry Library follows the OGC names for the naming of
+the classes.<br>
+<br>
+The Geometry Library defines the following OGC geometries:
+<table class="table" summary="Notation">
+<colgroup><col><col></colgroup>
+<tbody>
+<tr>
+<td align="left"><code class="computeroutput">point</code></td>
+<td align="left">A point, having coordinates of type T <i>Currently x() and y(), will be changed based on boost list discussions!</i></td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">linestring</code></td>
+<td align="left">An ordered series of points of type
+P. The linestring is default a std::vector of points, but can also
+be a std::list or std::deque of points</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">linear_ring</code></td>
+<td align="left">An ordered and closed series of
+points of type P. As with the linestring, it is default but not always
+a std::vector</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">polygon</code></td>
+<td align="left">An outer ring and zero, one or more
+inner
+rings (holes).
+</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">multi_point</code></td>
+<td align="left">A collection of points
+</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">multi_linestring</code></td>
+<td align="left">A collection of linestrings (for
+example: the output of the clipping of one linestring can result in a
+multi_linestring)
+</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">multi_polygon</code></td>
+<td align="left">A collection of polygons
+</td>
+</tr>
+</tbody>
+</table>
+<br>
+The following geometry types are used in the Geometry Library, but not
+defined by OGC:
+<table class="table" summary="Notation">
+<colgroup><col><col></colgroup>
+<tbody>
+<tr>
+<td align="left"><code class="computeroutput">circle</code></td>
+<td align="left">A circle (consisting of a center
+and a radius, used for selections (within) )</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">box</code></td>
+<td align="left">A box (consisting of a minimum
+point and a maximum point, used for selections and clipping)</td>
+</tr>
+<tr>
+<td align="left"><code class="computeroutput">segment</code></td>
+<td align="left">A line from point "first" to point
+"second", used in some algorithms</td>
+</tr>
+</tbody>
+</table>
+<br>
+There is one traits class:
+<table class="table" summary="Notation">
+<colgroup><col><col></colgroup>
+<tbody>
+<tr>
+<td align="left"><code class="computeroutput">geometry_traits</code></td>
+
+
+<td align="left">Defines the type used as
+coordinates, and the type used for the points, with their names
+<code class="computeroutput">coordinate_type</code>
+and <code class="computeroutput">point_type</code></td>
+</tr>
+</tbody>
+</table>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.point"></a>Point</h2>
+</div>
+</div><span style="font-style: italic;"><span style="font-weight: bold;">WILL BE CHANGED! THERE WILL BE MORE GENERIC POINT CONCEPT/BASECLASS and specializations for x/y and lat/lon or other<br><br></span></span>The point is defined like this:
+<br>
+<br>
+<code class="computeroutput"> template <typename
+T><br>
+class point<br>
+{<br>
+    public :<br>
+        typedef T
+coordinate_type;<br>
+        // rest omitted, will be changed<br>
+<span style="color: rgb(102, 102, 102);"> </span></code><code class="computeroutput">};<br>
+</code><br>
+The point that is defined by the Geometry Library contains methods to
+access and modify coordinates, which can be doubles, floats,
+ints or another numeric type. Furthermore there are some constructors
+available and there are some operators to compare points. Basically
+that's everything there is.<br>
+<br>
+However, that doesn't mean that other points are not possible. A user can
+derive points from this point to add for example an SRID
+(spatial reference  ID), a property map, or anything
+ else. Or  a user can implement point class with, for
+example, latitude and longitude. Those classes are accepted by the
+algorithms which are in the library, as long as they support
+ the methods above. In fact they don't need to support them
+all: if only algorithms are used which access coordinate values, such
+as <span style="font-weight: bold;">within</span>,
+then the two methods which modify coordinate values are not necessary.
+If there are no algorithms used which sort the points, they don't have
+to be defined. The compiler will tell if the class fits the algorithm.<br>
+<br>
+The usage of points is trivial:<br>
+<br>
+<code class="computeroutput">geometry::point<double>
+p1;<br>
+</code><code class="computeroutput">geometry::point<double>
+p2(3.14, 8.2);<br>
+</code><code class="computeroutput">geometry::point<char>
+p3(5, 8);</code><br>
+<code class="computeroutput"><br>// will be changed!<br>
+</code><code class="computeroutput">geometry::point<double>::coordinate_type
+x = p1.x();<br>
+</code>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.geometry_traits"></a>Geometry Traits</h2>
+</div>
+</div>
+The geometry traits class is a small class defining two member
+types. All geometry classes, but point, are derived from the geometry
+traits class. <br>
+<br>
+<code class="computeroutput">   
+template <typename P><br>
+    class geometry_traits<br>
+    {<br>
+        public :<br>
+      
+     typedef P point_type;<br>
+      
+     typedef typename
+P::coordinate_type coordinate_type;<br>
+    };</code><br>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.linestring"></a>Linestring</h2>
+</div>
+</div>
+A linestring is an ordered series of points. Here is an example of a
+linestring with 5 points.<br>
+<img style="width: 399px; height: 182px;" alt="" src="images/linestring.png"><br>
+You might expect a
+shorter name <span style="font-weight: bold;">line</span>
+here, but the name <span style="font-weight: bold;">linestring</span>
+is defined by OGC and the Geometry Library follows this definition.<br>
+<br>
+The Geometry Library defines a linestring, by design, as small as
+possible, it is a container of points and for the rest an empty class:<br>
+<br>
+<code class="computeroutput">
+    template <typename P, template
+<typename,typename> class V = std::vector,
+template<typename> class A = std::allocator><br>
+    class linestring : public V<P,
+A<P> >, public geometry_traits<P><br>
+    {<br>
+    };<br>
+<br>
+</code>The definition might seem somewhat cryptic, therefore it can be seen as this definition, its default:<br>
+<br style="color: rgb(51, 255, 51);">
+<code class="computeroutput"><span style="color: rgb(153, 153, 153);">   
+template <typename P></span><br style="color: rgb(153, 153, 153);"><span style="color: rgb(153, 153, 153);">
+    class linestring : public
+std::vector<P></span><br style="color: rgb(153, 153, 153);"><span style="color: rgb(153, 153, 153);">
+    {</span><br style="color: rgb(153, 153, 153);"><span style="color: rgb(153, 153, 153);">
+    };</span><br>
+</code><br>
+It is just a vector or another container of points, and
+contains the two member types point_type
+and coordinate_type
+defined by the geometry traits class.<br>
+<br>
+A linestring can be used like this:<br>
+<br>
+<code class="computeroutput">geometry::linestring<geometry::point<double>
+> ls;<br>
+ls.push_back(geometry::point<double>(1.2,
+5.8));<br>
+<br>
+</code><code class="computeroutput"><br>
+</code>Because a linestring is a container, you can call the
+std:: algorithms on containers.<br>
+<br>
+In most cases you will first do a typedef of the point type
+you want to use:<br>
+<br>
+<code class="computeroutput">typedef
+MyPoint<double> P;<br>
+geometry::linestring<P> ls;<br>
+</code><br>
+If you prefer other container types you can use a linestring like this:<br>
+<code class="computeroutput">geometry::linestring<P,
+std::deque> ls1;<br>
+</code><code class="computeroutput">geometry::linestring<P,
+std::list> ls2;</code><br>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.polygon"></a>Polygon</h2>
+</div>
+</div>
+A polygon contains an outer ring and zero, one or more inner rings.
+Inner
+rings are, in general, also called holes, donuts, or interior
+of in the polygon. The outer
+ring
+is the exterior boundary. The example below shows a polygon with one
+inner ring.<br>
+<img style="width: 400px; height: 240px;" alt="" src="images/polygon.png"><br>
+<br>
+Rings in polygons are normally directed:
+the outer ring is clockwise, the inner rings are counterclockwise.
+Some algorithms depend on this order and there is an algorithm to
+ensure that a polygon has the right order.<br>
+<br>
+The interface is the following:<br>
+<br>
+<code class="computeroutput">   
+template <typename P, template <typename,typename>
+class V = std::vector, template<typename> class A =
+std::allocator><br>
+    class polygon : public
+geometry_traits<P><br>
+    {<br>
+        public :<br>
+<span style="color: rgb(102, 102, 102);">   
+   
+    // Member types</span><br style="color: rgb(102, 102, 102);">
+       
+    typedef linear_ring<P, V,
+A> ring_type;<br>
+       
+    typedef V<ring_type ,
+A<ring_type > > inner_container_type;<br>
+<br>
+       
+    const ring_type& outer() const;<br>
+       
+    const inner_container_type &
+inners() const;<br>
+<br>
+       
+    ring_type& outer();<br>
+       
+    inner_container_type & inners();<br>
+<br>
+       
+    void clear();<br>
+    };<br>
+<br>
+</code><br>
+A polygon can be used like this:<br>
+<br>
+<code class="computeroutput">geometry::polygon<geometry::point<double>
+>
+polygon;<br>
+polygon.outer().push_back(geometry::point<double>(1.2,
+5.8));<br>
+</code><code class="computeroutput"><br>
+<br>
+</code>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.multi_point"></a>Multi point</h2>
+</div>
+</div>
+A multi point is a set of points, for example a constellation. As a
+linestring, it is empty.<br>
+<br>
+<code class="computeroutput">   
+template <typename P, template <typename,typename>
+class V = std::vector, template<typename> class A =
+std::allocator><br>
+    class multi_point : public V<P,
+A<P> >, public geometry_traits<P><br>
+    {<br>
+    };<br>
+<br>
+</code><br>
+However, it is not the same as a linestring: you can not calculate the length, for example.<code class="computeroutput"></code><br>
+<code class="computeroutput"><br>
+</code>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.multi_linestring"></a>Multi linestring</h2>
+</div>
+</div>
+A multi linestring is a set of linestrings, for example a road.<br>
+<br>
+<code class="computeroutput">   
+template <typename L, template <typename,typename>
+class V = std::vector, template<typename> class A =
+std::allocator><br>
+    class multi_linestring : public
+V<L, A<L> >, public
+geometry_traits<typename L::point_type><br>
+    {<br>
+        public:<br>
+      
+     typedef L linestring_type;<br>
+    };<br>
+</code><br>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.multi_polygon"></a>Multi polygon</h2>
+</div>
+</div>
+A multi polygons is a set of polygons, for example the state Hawaii.
+This is a multi polygon, containing two polygons:<br>
+<img src="images/multi_polygon.png"><br>
+<br>
+A multi polygon is defined as follows:<br>
+<br>
+<code class="computeroutput">   
+template <typename Y, template <typename,typename>
+class V = std::vector, template<typename> class A =
+std::allocator><br>
+    class multi_polygon : public V<Y,
+A<Y> >, public geometry_traits<typename
+Y::point_type><br>
+    {<br>
+        public :<br>
+      
+     typedef Y polygon_type;<br>
+    };</code><br>
+<code class="computeroutput"><br>
+<br>
+</code>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.box"></a>Box</h2>
+</div>
+</div>
+A box is not defined as such by OGC but useful in many algorithms. The
+Geometry Library defines a box by a minimum point and a maximum point.<br>
+<br>
+<code class="computeroutput">   
+template <typename P><br>
+    class box : public
+geometry_traits<P><br>
+    {<br>
+      
+     box();<br>
+      
+     box(const P& min,
+const P& max)<br><span style="color: rgb(102, 102, 102);">   
+        //
+Constructor with an option, for example geometry::init_inverse</span><br style="color: rgb(102, 102, 102);">
+      
+     box(init option);<br>
+<br>
+      
+     const P& min() const;<br>
+      
+     const P& max() const;<br>
+<br>
+      
+     P& min();<br>
+      
+     P& max();<br>
+    };</code><br>
+<br>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.circle"></a>Circle</h2>
+</div>
+</div>
+The main purpose of a circle is to be able to select, for example,
+points or lines with a circle. There is no full support on circle in
+most algorithms, you cannot intersect polygons with circles for example.<br>
+<br>
+A circle consists a point and a radius.<br>
+<br>
+<code class="computeroutput">   
+template <typename P, typename T><br>
+    class circle :
+geometry_traits<P><br>
+    {<br>
+        public :<br>
+      
+     typedef T radius_type;<br>
+<br>
+      
+     circle();<br>
+      
+     circle(const P&
+center, const T& radius);<br>
+      
+     circle(const
+coordinate_type& x, const coordinate_type& y, const
+T& radius);<br>
+<br>
+      
+     const P& center()
+const;<br>
+      
+     const T radius() const;<br>
+<br>
+      
+     void radius(const T&
+r);<br>
+      
+     P& center();<br>
+    };</code><br>
+</div>
+<table width="100%">
+<tbody>
+<tr>
+<td align="left"><small>
+<p>February 1, 2008</p>
+</small></td>
+<td align="right"><small>Copyright © 1995-2008 Barend Gehrels, Geodan Holding B.V. Amsterdam, the Netherlands</small></td>
+</tr>
+</tbody>
+</table>
+<hr>
+<div class="spirit-nav"><a accesskey="p" href="rationale.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/prev.png" alt="Prev"></a><a accesskey="u" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/up.png" alt="Up"></a><a accesskey="h" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/home.png" alt="Home"></a><a accesskey="n" href="algorithms.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/next.png" alt="Next"></a></div>
+</body></html>
\ No newline at end of file

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/examples.html
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/examples.html 2008-06-04 16:05:13 EDT (Wed, 04 Jun 2008)
@@ -0,0 +1,167 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head>
+<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Examples</title>
+
+<link rel="stylesheet" href="../boostbook.css" type="text/css"></head>
+<body style="color: black; background-color: white; background-image: url(../images/draft.png);" alink="#0000ff" link="#0000ff" vlink="#840084">
+<table cellpadding="2" width="100%">
+<tbody>
+<tr>
+<td valign="top"><img alt="Boost C++ Libraries" src="../proposed_boost.png" height="86" width="277"></td>
+</tr>
+</tbody>
+</table>
+<hr>
+<div class="spirit-nav"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/prev_disabled.png" alt="Prev"><a accesskey="u" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/up.png" alt="Up"></a><a accesskey="h" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/home.png" alt="Home"></a><a accesskey="n" href="rationale.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/next.png" alt="Next"></a></div>
+<div class="section" lang="en">
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.usage"></a>Examples</h2>
+</div>
+</div>
+<p>There are four example programs, which are described shortly
+below.
+</p>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="point"></a>Point Example</h2>
+</div>
+</div>
+<p>The point example (point_example.cpp) is a short example
+giving the
+first idea of how to use the library. It shows </p>
+<ul>
+<li>the usage of include files</li>
+<li>how to declare points, using different coordinate types</li>
+<li>how to construct points, specifying coordinates,
+initializing to zero or to infinite</li>
+<li>how to compare points to each other</li>
+<li>how points can be streamed as OGC text</li>
+<li>calculating the distance from point to point</li>
+</ul>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="other_point"></a>Other point Example</h2>
+</div>
+</div>
+<p>The "other point" example illustrates how derived classes can
+be used as well as the default implemented classes in the Geometry
+Library.</p>
+<div>
+<h2 class="title" style="clear: both;"><a name="linestring"></a>Linestring Example</h2>
+</div>
+<p>The linestring example (linestring_example.cpp) shows how
+linestrings can be declared and used and shows some more algorithms.
+One of the important concepts of the geometry library is that it is
+totally built upon the standard library, using the standard containers
+such as std::vector. </p>
+<p>A linestring is, as explained elsewhere in this documentation,
+nothing more than a vector of points. Therefore the first line of the
+main function of this example lists:</p>
+<code class="computeroutput"><span style="color: rgb(102, 102, 102);">
+    // Define a linestring, which is a
+vector of points, and add some points</span><br style="color: rgb(102, 102, 102);">
+
+   
+geometry::linestring<geometry::point<double>
+> ls;<br>
+   
+ls.push_back(geometry::point<double>(1.1, 1.1));<br>
+<br>
+</code>
+<p>Besides this, and besides that all algorithms on std::vector
+can be used on geometry::linestring, the sample elucidates the library
+showing some algorithms:</p>
+<ul>
+<li>geometry::evelope</li>
+<li>geometry::length</li>
+<li>geometry::distance</li>
+<li>geometry::simplify</li>
+<li>geometry::for_each</li>
+<li>geometry::intersection</li>
+</ul>
+<p>This documentation illustrates the <span style="font-weight: bold;">simplify</span> algorithm
+and the <span style="font-weight: bold;">intersection</span>
+algorithm with some pictures.</p>
+<p>The <span style="font-weight: bold;">simplify</span>
+algorithm simplifies a linestring. Simplification means that the less
+important points are removed from the line and that the points that are
+most important for the shape of a line are kept. Simplification is done
+using the well known Douglas Peucker algorithm. The library user can
+specify the <span style="font-style: italic;">distance</span>
+or <span style="font-style: italic;">tolerance</span>,
+which indicates how much the linestring should be simplified. </p>
+<p>The image below shows the linestring used in the example:</p>
+<img style="width: 400px; height: 212px;" alt="" src="images/simplify_example.png"><br>
+<p>The red line is the original linestring; the blue
+line is the simplified line which has one point less. In geographical
+applications simplification can reduce a linestring to its basic form
+containing only 10% of its original points.<br>
+<br>
+The intersection algorithm intersects two geometries which each other,
+delivering a third geometry. In the case of the example a linestring is
+intersected with a box. Intersection with a box is often called a <span style="font-weight: bold;">clip</span>. The image
+below illustrates the intersection.</p>
+<img style="width: 401px; height: 213px;" alt="" src="images/intersection_linestring_example.png"><br>
+<br>
+<p>The red line is intersected with the blue box. The
+intersection result, painted in black, is a multi_linestring containing
+three linestrings.</p>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="polygon"></a>Polygon Example</h2>
+</div>
+</div>
+<p>The polygon example (polygon_example.cpp) shows some examples of what can be done
+with polygons in the Geometry Library:</p>
+<ul>
+<li>the outer ring and the inner rings</li>
+<li>how to calculate the area of a polygon</li>
+<li>how to get the centroid, and how to get an often more
+interesting label point</li>
+<li>how to correct the polygon such that it is clockwise and
+closed</li>
+<li><span style="font-weight: bold;">within</span>:
+the well-known <span style="font-weight: bold;">point in
+polygon</span> algorithm</li>
+<li>how to use polygons which use another container, or which
+use different containers for points and for inner rings</li>
+<li>how polygons can be intersected, or clipped, using a
+clipping box</li>
+</ul>
+<p>
+The illustrations below show the usage of the <span style="font-weight: bold;">within </span>algorithm
+and the <span style="font-weight: bold;">intersection</span>
+algorithm.<br>
+<br>
+The within algorithm results in <span style="font-weight: bold;">true</span>
+if a point lies completly within a polygon. If it lies exactly on a
+border it is not<span style="font-weight: bold;"><span style="font-weight: bold;"> </span></span>considered
+as within and if it is inside a hole it is also not within the polygon.
+This is illustrated below, where only the point in the middle is within the
+polygon.</p>
+<img src="images/within_polygon_example.png"><br>
+<br>
+<br>
+<p>The clipping algorithm, called <span style="font-weight: bold;">intersection</span>,
+is illustrated below:</p>
+<img src="images/clip_polygon_example.png"><br>
+<br>
+<p>The yellow polygon, containing a hole, is clipped with the
+blue
+rectangle, resulting in a multi_polygon of three polygons, drawn in
+red. The hole is vanished.</p>
+</div>
+<table width="100%">
+<tbody>
+<tr>
+<td align="left"><small>
+<p>February 1, 2008</p>
+</small></td>
+<td align="right"><small>Copyright © 1995-2008 Barend Gehrels, Geodan Holding B.V. Amsterdam, the Netherlands</small></td>
+</tr>
+</tbody>
+</table>
+<hr>
+<div class="spirit-nav"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/prev_disabled.png" alt="Prev"><a accesskey="u" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/up.png" alt="Up"></a><a accesskey="h" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/home.png" alt="Home"></a><a accesskey="n" href="rationale.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/next.png" alt="Next"></a></div>
+</body></html>
\ No newline at end of file

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/clip_polygon_example.png
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/clip_polygon_example.svg
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/geometries.svg
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/intersection_linestring_example.png
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/linestring.png
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/linestring_example.svg
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/linestring_intersection_example.svg
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/multi_polygon.png
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/polygon.png
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/polygon_example1.svg
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/simplify_example.png
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/simplify_example.svg
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/within_polygon_example.png
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/images/within_polygon_example.svg
==============================================================================
Binary file. No diff available.

Added: sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/rationale.html
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/spacial_indexing/geometry/doc/geometry/rationale.html 2008-06-04 16:05:13 EDT (Wed, 04 Jun 2008)
@@ -0,0 +1,413 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head>
+<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Rationale</title>
+
+<link rel="stylesheet" href="../boostbook.css" type="text/css"></head>
+<body style="color: black; background-color: white; background-image: url(../images/draft.png);" alink="#0000ff" link="#0000ff" vlink="#840084">
+<table cellpadding="2" width="100%">
+<tbody>
+<tr>
+<td valign="top"><img alt="Boost C++ Libraries" src="../proposed_boost.png" height="86" width="277"></td>
+</tr>
+</tbody>
+</table>
+<hr>
+<div class="spirit-nav"><a accesskey="p" href="examples.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/prev.png" alt="Prev"></a><a accesskey="u" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/up.png" alt="Up"></a><a accesskey="h" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/home.png" alt="Home"></a><a accesskey="n" href="classes.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/next.png" alt="Next"></a></div>
+<div class="section" lang="en">
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="rationale"></a>Rationale</h2>
+</div>
+</div>
+<p>The Geometry Library is implemented like the std:: library and
+most of the boost:: libraries are implemented.</p>
+<p>Data and algorithms are separated.</p>
+<p>The library contains only header files.</p>
+<p>Besides that the Geometry Library uses OGC <span style="font-style: italic;">conventions</span> for
+names and definitions of geometries and algorithms. The library
+implements the OGC geometries <span style="font-weight: bold;">point</span>,
+<span style="font-weight: bold;">linestring</span>, <span style="font-weight: bold;">polygon, multi_point, multi_</span><span style="font-weight: bold;">linestring</span> and <span style="font-weight: bold;">multi_polygon</span>. The
+library implements OGC  algorithms as <span style="font-weight: bold;">within</span>, <span style="font-weight: bold;">intersection</span>, <span style="font-weight: bold;">distance</span>,
+and more, but not all of them are currently implemented, and not all of
+them are implemented for all possible geometry combinations.</p>
+<p>The Geometry Library is not an OGC <span style="font-style: italic;">implementation</span>. OGC specifies a base geometry class and derived classes for
+point, linestring, etc, where all algorithms are implemented
+as class methods. This conflicts with std:: and boost::
+conventions and C++ generic program in general, and results in sometimes poor
+implementations where all algorithms need typecasts to see
+with
+which geometry they handle.</p>
+<p>So this library defines the algorithms separated from the
+geometry classes and strict OGC compliancy is dropped.</p>
+<p>This library has no calls to new or delete. There are no casts. There are no virtual
+member functions. There is no inheritance, besides type traits
+inheritance. There are hardly any exceptions.</p>
+<p>The Geometry Library does <span style="font-weight: bold;">not</span>
+implement vector or matrix classes. Vector and matrix calculations are
+used in some geometry algorithms, and are essential for
+transformations. However, the concepts vector and matrix are more
+generic than geometry and could be used in other scopes than in
+geometry scope. So they should be defined in a separate library. Boost
+UBlas is an example of such a library and the Geometry Library could be
+used in combination with Boost UBlas.</p>
+<p>Although lat long classes
+and projections could fit in the projects where the Geometry Library is
+used, they are not implemented
+in the Geometry Library.</p>
+<p>In summary, the Geometry Library provides some often used
+algorithms such as <span style="font-weight: bold;">point
+in polygon</span>, <span style="font-weight: bold;">area,
+clip</span>, <span style="font-weight: bold;">distance</span>
+in the most generic way as possible.</p>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="rationale"></a>Templatization</h2>
+</div>
+</div>
+<p><span style="font-weight: bold;"></span>The
+Geometry Library uses templates for all class definitions and
+algorithms.</p>
+<p>In
+all geometries the coordinate type is templatized. Points can
+be
+created using double, float, int, char or whatever.</p>
+<p><code>geometry::point<double> p;</code><br>
+</p>
+<p>In
+all geometries consisting of points, the point type itself is
+templatized. So linestrings can be linestrings built of
+point<double>, but also other points can be used. That
+means that
+you can specify your own point-type for a linestring, as long as the
+point-type implements the basic point interface (or concept).</p>
+<p><code>geometry::linestring<my_point> line;</code><br>
+</p>
+<p>In
+all geometries consisting of points, the container type is templatized,
+and default to std::vector. So a linestring is default defined
+as a std::vector of points, but the library user can take a
+std::list of points as well, or a std::deque of points.</p>
+<p><code>geometry::linestring<my_point,
+std::deque> line2;</code><br>
+</p>
+<p>In
+all multi-geometries the container containing the single type is
+templatized and defaults to std::vector. A multi-linestring can be a
+std::deque of linestrings.</p>
+<p>In a polygon the container containing
+the inner rings is templatized. To illustrate this, a multi_polygon can
+be a std::vector of polygons, where polygons have a std::list of inner
+rings and all rings are a std::deque of points, where points have float
+coordinates.</p>
+<p>So far the geometries classes. The algorithms are designed
+with the following requirements in mind:</p>
+<ul>
+<li>they all should have the same name</li>
+<li>they
+all should work on the provided geometry classes, but also on derived
+classes, and also on other geometry classes (having the specified
+interface)</li>
+</ul>
+<p>These requirements conflict in a way. The first
+requirement is necessary because you might use the geometry as a
+template in, for example, a layer of those geometries. The <span style="font-weight: bold;">within</span> algorithm or
+the <span style="font-weight: bold;">label_point</span>
+algorithm should work on all geometries. The second requirement is
+useful because many libraries define their own points, and library
+users might have additional needs for points such as a Z-value or an
+SRID.</p>
+<p>Suppose the <span style="font-style: italic;">within</span>
+function for point in polygon is defined as following:</p>
+<p><span class="computeroutput"><code>   
+template<typename P1, typename P2, <br>
+       
+   
+template<typename,typename> class VP, <br>
+       
+   
+template<typename,typename> class VR, <br>
+       
+    template<typename> class
+AP,<br>
+       
+    template<typename> class
+AR><br>
+    bool within(const P1&
+pnt, const polygon<P2, VP, VR, AP, AR>& poly)</code><br>
+</span><span class="computeroutput"></span><br>
+</p>
+<p>(The
+template template parameters are necessary for flexibel containers).
+With this definition the second requirement is not met, library users
+cannot add their own polygons, they should use the geometry::polygon.</p>
+<p>If the <span style="font-style: italic;">within</span>
+function would have been defined as following:</p>
+<p><code>   
+template<typename POI, typename POL><br>
+    bool within(const POI& pnt,
+const POL& poly)</code><br>
+the
+second requirement is met, but the first is not. Because, what if you
+have the within function for point in box, or for point in multi-polygon:</p>
+<p><code>   
+template<typename POI, typename B><br>
+    bool within(const POI& pnt,
+const B& b)</code></p>
+<p>The compiler cannot make the difference, these two definitions
+are ambiguous.</p>
+<p>Therefore,
+the Geometry Library design contains both approaches to fulfill both
+requirements. The algorithms implemented per geometry class add the
+name of the geometry classes. So we have:</p>
+<p><code>   
+template<typename P, typename POL><br>
+    bool
+within_point_in_polygon(const P& p, const POL& poly)</code><br>
+and</p>
+<p><code>   
+template<typename P, typename B><br>
+    inline bool within_point_in_box(const
+P& p, const B& b)</code><br>
+</p>
+<p>Besides this there are within algorithms defined as described
+above, which are just wrappers</p>
+<p><code>   
+template<typename P1, typename P2><br>
+    bool within(const P1&
+p, const box<P2>& b) { return
+within_point_in_box(p, b); }</code><br>
+<br>
+and</p>
+<code>    template<typename P1,
+typename P2, <br class="author">
+       
+   
+template<typename,typename> class VP, <br class="author">
+       
+   
+template<typename,typename> class VR, <br class="author">
+       
+    template<typename> class
+AP,<br class="author">
+       
+    template<typename> class
+AR><br class="author">
+   
+inline bool within(const P1& p, const polygon<P2, VP,
+VR, AP,
+AR>& poly) { return
+within_point_in_polygon(p,
+poly); }</code><br>
+<p>So, in summary, all algorithms have two forms. There is the <span style="font-style: italic;">primary</span> form, such as <span style="font-weight: bold;">within_point_in_polygon</span>,
+defined for all types including the user defined types. And there is
+the generic form <span style="font-weight: bold;">within</span>,
+defined for the supplied classes (and for derived classes as well).</p>
+<p>Besides
+this, algorithms also work for mixed types. Point in polygon works
+for point-type in polygon-of-same-point-type, but it also
+works
+for point-type in a polygon-of-different-point-type.</p>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.other_libraries"></a>Other libraries</h2>
+</div>
+</div>
+<p>There are many other Open Source libraries on geometry. This
+Geometry Library is a template library, following std::, boost:: and
+OGC conventions. There are <span style="font-weight: bold;">not</span>
+many Open Source libraries like this.</p>
+<p>The
+found Open Source geometry libraries are listed here shortly.</p>
+<p></p>
+<table style="text-align: left; width: 100%;" border="0" cellpadding="2" cellspacing="2">
+<tbody>
+<tr>
+<td>
+<p>Library</p>
+</td>
+<td>
+<p>License</p>
+</td>
+<td>
+<p>C++ object type</p>
+</td>
+<td>
+<p>Typical geometries</p>
+</td>
+<td><p>Typical algorithms</p></td><td>
+<p>Remarks</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>CGAL
+(computational geometry algorithms library)</p>
+</td>
+<td>
+<p>QPL</p>
+</td>
+<td>
+<p>template</p>
+</td>
+<td>
+<p>many, a.o. lines, polygons </p>
+<p>E.g. General_polygon_with_holes_2</p>
+</td>
+<td><p>many</p></td><td>
+<p>Often used. License is not compatible. More
+geometry than GIS.</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>GDAL
+(Geospatial Data Abstraction Library)</p>
+</td>
+<td>
+<p>MIT/X style</p>
+</td>
+<td>
+<p>virtual</p>
+</td>
+<td>
+<p>OGC*</p>
+<p>class CPL_DLL OGRPolygon : public OGRSurface </p>
+</td>
+<td><p>OGC* (?)</p></td><td>
+<p>Often used. OGC compliant. C++, C-styled</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>GEOS (Geometry Engine - Open
+Source)</p>
+</td>
+<td>
+<p>LGPL</p>
+</td>
+<td>
+<p>virtual</p>
+</td>
+<td>
+<p>OGC*</p>
+<p>class Point : public Geometry</p>
+</td>
+<td><p>OGC*</p></td><td>
+<p>Documentation states: If you prefer troubles you can use
+the C++ interface.</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>GFC (Geometry Foundation Classes)</p>
+</td>
+<td>
+<p>GPL</p>
+</td>
+<td>
+<p>virtual</p>
+</td>
+<td>
+<p>polygons, holes</p>
+</td>
+<td><p>area, centroid, intersection, within</p></td><td>
+<p>Status unknown, original ibrary is gone.</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>GTL (geometric template library)</p>
+</td>
+<td>
+<p>Not Open Source</p>
+</td>
+<td>
+<p>template</p>
+</td>
+<td>
+<p>Point, Segment, Rectangle, Polygon, PolygonSet
+</p>
+</td>
+<td><p></p></td><td>
+<p>Not published.</p>
+</td>
+</tr>
+<tr>
+<td>
+<p>TGL (templatized geometry library)</p>
+</td>
+<td>
+<p>GPL</p>
+</td>
+<td>
+<p>template</p>
+</td>
+<td>
+<p>box, curve, plane, sphere</p>
+</td>
+<td><p></p></td><td>
+<p></p>
+<p></p></td>
+</tr>
+<tr>
+<td>
+<p>CPAF GMath (CPAF - C++ Cross
+Platform Application)</p>
+</td>
+<td>
+<p>?</p>
+</td>
+<td>
+<p>template</p>
+</td>
+<td>
+
+<p>box, circle, ellipse, rectangle, triangle, <br>vector, matrix</p>
+</td>
+<td><p></p><p></p></td><td>
+<p> <br>
+</p>
+</td>
+</tr><tr><td><p>GPC (General Polygon Clipping Library)</p></td><td><p>Not Open Source</p></td><td><p>n.a., C</p></td><td><p>gpc_polygon</p></td><td><p>clip</p></td><td><p>Not C++, not Open Source</p></td></tr>
+</tbody>
+</table>
+
+<p><span style="font-weight: bold;"></span></p>
+<div class="titlepage">
+<div>
+<h2 class="title" style="clear: both;"><a name="geometry.other_libraries"></a>Performance</h2>
+</div>
+</div><p>A geometry library could be built in many ways. This Geometry
+Library follows std:: conventions and defines a linestring as a
+std::vector of points and nothing more.</p><p>Therefore, the linestring class has no bounding box.</p><p>In
+many algorithms, such as intersecting a linestring with a clipping box,
+it is useful to first compare if the bounding box overlaps with the
+clipping box. If there is no overlap, there is no intersection and the
+clipping process  doesn't need to be started. The same applies for
+within (point-in-polygon), etc.</p><p>The library user could make a
+derived linestring or polygon containing its bounding box. That
+bounding box could be calculated after the geometry is filled using <span style="font-weight: bold;">geometry::envelope</span>. Before
+the relevant algorithms there could be checked if the bounding box
+overlaps with the clipping box, or if the point is in the polygon
+bounding box.</p><p>Alternately, the library user could have a table
+structure where a geometry is one column of the table, and its bounding
+box is another column of the table. That bounding box could be read
+from file or from the database, it doesn't need to be calculated. Or
+the library user could make a wrapper class containing the geometry as
+well as its bounding box.</p><p>The library user is free how to
+implement this, if necessary. However, often it is necessary and it
+makes sense to first compare bounding boxes.</p>
+</div>
+<table width="100%">
+<tbody>
+<tr>
+<td align="left"><small>
+<p>February 1, 2008</p>
+</small></td>
+<td align="right"><small>Copyright © 1995-2008 Barend Gehrels, Geodan Holding B.V. Amsterdam, the Netherlands</small></td>
+</tr>
+</tbody>
+</table>
+<hr>
+<div class="spirit-nav"><a accesskey="p" href="examples.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/prev.png" alt="Prev"></a><a accesskey="u" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/up.png" alt="Up"></a><a accesskey="h" href="../geometry.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/home.png" alt="Home"></a><a accesskey="n" href="classes.html"><img style="border: 0px solid ; width: 19px; height: 19px;" src="../images/next.png" alt="Next"></a></div>
+</body></html>
\ No newline at end of file

Next message: troy_at_[hidden]: "[Boost-commit] svn:boost r46142 - branches/CMake/release/libs"
Previous message: mariano.consoni_at_[hidden]: "[Boost-commit] svn:boost r46140 - in sandbox/SOC/2008/spacial_indexing/geometry/doc: . doxygen doxygen/html"

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