Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r54070 - in sandbox/gtl/doc: . images
From: lucanus.j.simonson_at_[hidden]
Date: 2009-06-18 18:55:51

Next message: lucanus.j.simonson_at_[hidden]: "[Boost-commit] svn:boost r54071 - sandbox/gtl/doc/images"
Previous message: jewillco_at_[hidden]: "[Boost-commit] svn:boost r54069 - trunk/boost/graph"

Author: ljsimons
Date: 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
New Revision: 54070
URL: http://svn.boost.org/trac/boost/changeset/54070

Log:
updating documentation
Added:
   sandbox/gtl/doc/images/refinements.png (contents, props changed)
Text files modified:
   sandbox/gtl/doc/gtl_connectivity_extraction_45.htm | 7 +
   sandbox/gtl/doc/gtl_connectivity_extraction_90.htm | 7 +
   sandbox/gtl/doc/gtl_coordinate_concept.htm | 4
   sandbox/gtl/doc/gtl_design_overview.htm | 44 +++++++++++--
   sandbox/gtl/doc/gtl_interval_concept.htm | 97 +++++++++++++++++++++++++++++
   sandbox/gtl/doc/gtl_isotropy.htm | 29 ++++++++
   sandbox/gtl/doc/gtl_point_concept.htm | 121 ++++++++++++++++++++++++++++++++++++-
   sandbox/gtl/doc/gtl_polygon_45_concept.htm | 70 +++++++++++++++++++++
   sandbox/gtl/doc/gtl_polygon_45_set_concept.htm | 34 ++++++++--
   sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm | 100 ++++++++++++++++++++++++++++++
   sandbox/gtl/doc/gtl_polygon_90_concept.htm | 97 +++++++++++++++++++++++++++++
   sandbox/gtl/doc/gtl_polygon_90_set_concept.htm | 34 ++++++++--
   sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm | 127 +++++++++++++++++++++++++++++++++++++++
   sandbox/gtl/doc/gtl_polygon_concept.htm | 74 ++++++++++++++++++++++
   sandbox/gtl/doc/gtl_polygon_set_concept.htm | 30 +++++++--
   sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm | 99 ++++++++++++++++++++++++++++++
   sandbox/gtl/doc/gtl_property_merge.htm | 8 +
   sandbox/gtl/doc/gtl_property_merge_90.htm | 6 +
   sandbox/gtl/doc/gtl_rectangle_concept.htm | 83 +++++++++++++++++++++++++
   sandbox/gtl/doc/index.htm | 30 ++++++--
   20 files changed, 1026 insertions(+), 75 deletions(-)

Modified: sandbox/gtl/doc/gtl_connectivity_extraction_45.htm
==============================================================================
--- sandbox/gtl/doc/gtl_connectivity_extraction_45.htm (original)
+++ sandbox/gtl/doc/gtl_connectivity_extraction_45.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,7 +22,6 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -34,6 +33,7 @@
 <li>Polygon 45 Set Concept</li>
 <li>Polygon Set Concept</li>
 <li>Connectivity Extraction 90</li>
+ <li>Connectivity Extraction 45</li>
 <li>Property Merge 90</li>
 <li>Property Merge</li>
 </ul>
@@ -72,7 +72,10 @@
support more generic graph concepts is deferred to future work.The following
is the declaration of the connectivity extraction algorithm.
template <typename coordinate_type> 
-class connectivity_extraction_45;<h2>Member Functions</h2>
+class connectivity_extraction_45;
+Example code connectivity_extraction_usage.cpp
+ demonstrates using the connectivity extraction algorithm to build a
+connectivity graph on geometry.<h2>Member Functions</h2>
<table border="1" width="100%" id="table1">
 <tr>
 <td width="586">connectivity_extraction_45()</td>

Modified: sandbox/gtl/doc/gtl_connectivity_extraction_90.htm
==============================================================================
--- sandbox/gtl/doc/gtl_connectivity_extraction_90.htm (original)
+++ sandbox/gtl/doc/gtl_connectivity_extraction_90.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,7 +22,6 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -33,6 +32,7 @@
 <li>Polygon 90 Set Concept</li>
 <li>Polygon 45 Set Concept</li>
 <li>Polygon Set Concept</li>
+ <li>Connectivity Extraction 90</li>
 <li>Connectivity Extraction 45</li>
 <li>Property Merge 90</li>
 <li>Property Merge</li>
@@ -72,7 +72,10 @@
support more generic graph concepts is deferred to future work.The following
is the declaration of the connectivity extraction algorithm.
template <typename coordinate_type> 
-class connectivity_extraction_90;<h2>Member Functions</h2>
+class connectivity_extraction_90;
+Example code connectivity_extraction_usage.cpp
+ demonstrates using the connectivity extraction algorithm to build a
+connectivity graph on geometry.<h2>Member Functions</h2>
<table border="1" width="100%" id="table1">
 <tr>
 <td width="586">connectivity_extraction_90()</td>

Modified: sandbox/gtl/doc/gtl_coordinate_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_coordinate_concept.htm (original)
+++ sandbox/gtl/doc/gtl_coordinate_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -19,9 +19,9 @@
 <li><a href="gtl_design_overview.htm">Polygon
 Library Design Overview</a></li>
 <li>Isotropy</li>
+ <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -59,7 +59,7 @@
<h1>Coordinate Concept</h1>


-The coordinate concept type identifier is 
+The coordinate concept tag is 
coordinate_concept
To register a user defined type as a model of coordinate concept, specialize the
geometry concept meta-function for that type.  In the example below

Modified: sandbox/gtl/doc/gtl_design_overview.htm
==============================================================================
--- sandbox/gtl/doc/gtl_design_overview.htm (original)
+++ sandbox/gtl/doc/gtl_design_overview.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -16,13 +16,12 @@
 <h3 class="navbar">Contents</h3>
 <ul>
 <li>Polygon Library Main Page</li>
+ <li>Polygon Library Design Overview</li>
 <li>Isotropy</li>
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>
 <a href="gtl_point_concept.htm">Point Concept</a></li>
- <li>
- Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -62,14 +61,14 @@

The Polygon library uses C++-Concepts inspired template programming to
provide generic library functions overloaded on concept type.  There are
-currently fourteen concepts in the Polygon library type system.  A concept
+currently thirteen concepts in the Polygon library type system.  A concept
object in the Polygon library is just an empty struct similar to a tag that
would be used for tag dispatching.   These concepts are listed with
the names they are given in the library code and abbreviations used for them in
this document in the table below.

-</body><img border="0" src="images/concept_table.png" width="322" height="453">
+</body><img border="0" src="images/refinements.png" width="554" height="474">
The arrows between diagram bubbles show concept refinement relationships.  This is
similar, but not identical to, inheritance relationships between normal classes. 
A refinement of a concept narrows down the definition of a more general concept. 
@@ -85,14 +84,41 @@
general case.  This allows the compiler to choose between the three
implementations of algorithms to select the best algorithm for the conceptual
data types passed to an overload of a function including heterogeneous
-combinations of 90, 45 and general case geometry.
+combinations of 90, 45 and general case geometry.  To provide the
+operator& that performs the intersection on any
+pair of objects from the ten conceptual types related to each other through
+refinement in the diagraph above fully one hundred distinct combinations of
+conceptual types are supported by the library, but only three overloads are
+required to implement the operator (one for 90, one for 45 and one for arbitrary
+angle version of the intersection operation) because refinement generalizes the
+implementation of the interface.  In this way a fully symmetric, complete
+and internally consistent API is implemented to provide meaningful and correct
+behaviors for all combinations of argument types in all APIs where those types
+make sense.  For example, it doesn't make sense to copy data from a polygon
+into a rectangle, so attempting to do so yields a syntax error, while copying a
+rectangle into a polygon does make sense.  The 
+assign() function that is used to copy geometry data between concepts
+instantiates for the 49 combinations of concepts that make sense, but not for
+the 51 combinations that are illegal.  The syntax error you will see when
+attempting an illegal assign operation is simple and clear because use of SFINAE
+by the library to overload generic functions means no matching function is found
+by the compiler in cases where no overload is provided.
+
+error: no matching function for call to 'gtl::assign(gtl::rectangle_data<int>&,
+gtl::polygon_data<int>&)'
Associated with each concept is a traits struct that generally must be
specialized for a given data type to provide the concept mapping between the
interfaces of the data type and the expected behaviors of an object of that type
required by the library.  The library also provides its own data types for
-each concept that conform to the default traits definition.  When a data
-type has been mapped to a concept through traits it also needs to be registered
-as that conceptual type with the library.  This is accomplished by
+each concept that conform to the default traits definition.  These library
+provided data types are no more than dumb containers that provide access to
+their data and rely on the generic library functions to enforce invariants and
+provide useful behaviors specific to their type of geometry that would normally
+be member functions of the data type in an OO design.  The library data
+types conform to the default traits associated with their related geometry
+concept and are registered as models of that concept.  When a data
+type has been mapped to a concept through traits it needs to be registered
+as that conceptual type with the library by
specializing the geometry_concept meta-function.  Once mapped and
registered, a user data type can be used interchangeably with library data types
in the generic free functions that are overloaded on concept.Traits for
@@ -105,7 +131,7 @@
object is used with that type.  For example, a triangle type could be
registered as a polygon_concept and the read only traits but not the mutable
traits defined for that triangle type.  This would allow the triangle type
-to be passed into any API that expects a cost reference to an object that models
+to be passed into any API that expects a const reference to an object that models
polygon.  <tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  </td>

Modified: sandbox/gtl/doc/gtl_interval_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_interval_concept.htm (original)
+++ sandbox/gtl/doc/gtl_interval_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -20,8 +20,8 @@
 Library Design Overview</a></li>
 <li>Isotropy</li>
 <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -59,7 +59,7 @@
<h1>Interval Concept</h1>


-The interval concept type identifier is 
+The interval concept tag is 
interval_concept

To register a user defined type as a model of interval concept, specialize the
@@ -399,6 +399,99 @@
 coordinate value was not contained within a to begin with.</td>
 </tr>
</table>
+ <h1>Interval Data</h1>
+
+
+The library provides a model of interval concept declared
+
+template<typename T> interval_data where T is the coordinate type.
+This data type is used internally when an interval is needed and is available
+to the library user who finds it convenient to use a library interval data type
+instead of providing their own.  The data type is implemented to be
+convenient to use with the library traits.
+<h2>Members</h2>
+<table border="1" width="100%" id="table2">
+ <tr>
+ <td width="586">geometry_type</td>
+ <td>interval_concept</td>
+ </tr>
+ <tr>
+ <td width="586">coordinate_type</td>
+ <td>T</td>
+ </tr>
+ <tr>
+ <td width="586">interval_data()</td>
+ <td>Default constructs the two coordinate
+ values of the interval.</td>
+ </tr>
+ <tr>
+ <td width="586">interval_data(T low, T
+ high)</td>
+ <td>Constructs an interval with two
+ coordinates.</td>
+ </tr>
+ <tr>
+ <td width="586">interval_data(const
+ interval_data* that)</td>
+ <td>Copy construct</td>
+ </tr>
+ <tr>
+ <td width="586">interval_data& operator=(const
+ interval_data& that)</td>
+ <td>Assignment operator.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2> 
+ interval_data& operator=(const T2& that) const</td>
+ <td>Assign from an object that is a model of interval.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator==(const T2& that) const</td>
+ <td>Compare equality to an object that is a model of interval.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator!=(const T2& that) const</td>
+ <td>Compare inequality to an object that is a model of interval.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator<(const T2& that) const</td>
+ <td>Compares low coordinates then high coordinates to break ties.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator<=(const T2& that) const</td>
+ <td>Compares low coordinates then high coordinates to break ties.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator>(const T2& that) const</td>
+ <td>Compares low coordinates then high coordinates to break ties.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator>=(const T2& that) const</td>
+ <td>Compares low coordinates then high coordinates to break ties.</td>
+ </tr>
+ <tr>
+ <td width="586">T get(direction_1d dir)
+ const</td>
+ <td>Get the coordinate in the given direction.</td>
+ </tr>
+ <tr>
+ <td width="586">void set(direction_1d
+ dir, T value)</td>
+ <td>Sets the coordinate in the given direction to the value.</td>
+ </tr>
+ </table>
 <tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  </td>

Modified: sandbox/gtl/doc/gtl_isotropy.htm
==============================================================================
--- sandbox/gtl/doc/gtl_isotropy.htm (original)
+++ sandbox/gtl/doc/gtl_isotropy.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -18,10 +18,10 @@
 <li>Polygon Library Main Page</li>
 <li><a href="gtl_design_overview.htm">Polygon
 Library Design Overview</a></li>
+ <li>Isotropy</li>
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -73,7 +73,7 @@
In computational geometry things are often symmetric and
invariant to direction and orientation.  This invariance to direction is
called isotropy.  In such situations it is convenient to parameterize
-direction or orientation and write code that is invariant to direction or
+direction or orientation and write code that is invariant to the direction or
orientation in which it is applied.  To do this effectively we provide an
internally consistent set of isotropic data types in GTL to represent program
data that describes orientations and directions.  These data types are:
@@ -97,12 +97,35 @@
orientation_2d orient = HORIZONTAL; 
direction_2d dir = orient.get_direction(direction_1d(HIGH)); 
assert(dir == EAST);
+The motivation for providing isotropic data types is to
+encourage programming at a higher level of abstraction where program behavior is
+controlled by program data passed into function calls rather than flow control
+syntax.  Isotropic programming style is particularly applicable to working
+with points, intervals and rectangles.  Often times the implementation of
+such logic is identical when implemented for the x or y coordinates, except that
+the names of functions and data members are changed in a mechanical way leading
+to code duplication and bloat that results in copy-paste programming errors and
+maintenance problems where changes made to a given code block relating to x
+coordiantes are not duplicated to the code block that refers to y. 
+Isotropy therefore represents an opportunity to refactor and improve the quality
+of low level geometry code especially in regard to inter-relating coordinates,
+points, intervals and rectangles.
<h2>direction_1d</h2>


The direction_1d data type has two possible states.  These
are the positive and negative directions on a continuum such as the number line.  
-These states can be described by one of several direction_1d_enum values:
+These states can be described by one of several direction_1d_enum values: 
+We make clockwise and counterclockwise winding orientation of polygons a
+direction 1d value instead of providing a separate winding_orientation data
+type.  This is because winding orientation can be thought of as positive
+and negative directions in a 1d (although cyclic) space.  We assign
+counterclockwise to be the positive direction of travel in the 1d cyclic space
+to conform with the mathematical convention frequently described as the "right
+hand rule" which assigns positive normal value to counterclockwise and negative
+normal value to clockwise as well as the common convention that counterclockwise
+polygon winding corresponds to positive polygonal regions where as clockwise
+polygon winding corresponds to hole (negative) polygonal regions.
enum direction_1d_enum {LOW = 0, HIGH =
1,

Modified: sandbox/gtl/doc/gtl_point_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_point_concept.htm (original)
+++ sandbox/gtl/doc/gtl_point_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -21,7 +21,7 @@
 <li>Isotropy</li>
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
- <li>Point 3D Concept</li>
+ <li>Point Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -60,7 +60,7 @@



-The point concept type identifier is 
+The point concept tag is 
point_concept
To register a user defined type as a model of point concept, specialize the
geometry concept meta-function for that type.  In the example below CPoint is registered as a model of
@@ -101,7 +101,10 @@
          return T(x_value, y_value);
 
     } 
-};<h2>Functions</h2>
+};
+Example code custom_point.cpp demonstrates
+how to map a
+ user defined point class to the library point_concept<h2>Functions</h2>
<table border="1" width="100%" id="table1">
 <tr>
 <td width="586">template <typename T> 
@@ -255,7 +258,117 @@
 models point.</td>
 </tr>
</table>
- <tr>
+<h1>Point Data</h1>
+
+
+The library provides a model of point concept declared
+
+template<typename T> point_data where T is the coordinate type.
+This data type is used internally when a point is needed and is available to
+the library user who finds it convenient to use a library point data type
+instead of providing their own.  The data type is implemented to be
+convenient to use with the library traits.
+Example code point_usage.cpp demonstrates using the
+ library provided point data type and functions
+<h2>Members</h2>
+<table border="1" width="100%" id="table2">
+ <tr>
+ <td width="586">geometry_type</td>
+ <td>point_concept</td>
+ </tr>
+ <tr>
+ <td width="586">coordinate_type</td>
+ <td>T</td>
+ </tr>
+ <tr>
+ <td width="586">point_data()</td>
+ <td>Default constructs the two coordinate
+ values of the point.</td>
+ </tr>
+ <tr>
+ <td width="586">point_data(T x, T y)</td>
+ <td>Constructs an interval with two
+ coordinates.</td>
+ </tr>
+ <tr>
+ <td width="586">point_data(const point_data*
+ that)</td>
+ <td>Copy construct</td>
+ </tr>
+ <tr>
+ <td width="586">point_data& operator=(const
+ point_data& that)</td>
+ <td>Assignment operator.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2> 
+ point_data& operator=(const T2& that) const</td>
+ <td>Assign from an object that is a model of point.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator==(const T2& that) const</td>
+ <td>Compare equality to an object that is a model of point.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator!=(const T2& that) const</td>
+ <td>Compare inequality to an object that is a model of point.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator<(const T2& that) const</td>
+ <td>Compares y coordinates then x coordinates to break ties.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator<=(const T2& that) const</td>
+ <td>Compares y coordinates then x coordinates to break ties.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator>(const T2& that) const</td>
+ <td>Compares low coordinates then high coordinates to break ties.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator>=(const T2& that) const</td>
+ <td>Compares low coordinates then high coordinates to break ties.</td>
+ </tr>
+ <tr>
+ <td width="586">T get(orientation_2d
+ orient) const</td>
+ <td>Get the coordinate in the given orientation.</td>
+ </tr>
+ <tr>
+ <td width="586">T x() const</td>
+ <td>Get the coordinate in the horizontal orientation.</td>
+ </tr>
+ <tr>
+ <td width="586">T y() const</td>
+ <td>Get the coordinate in the vertical orientation.</td>
+ </tr>
+ <tr>
+ <td width="586">void set(orientation_2d
+ orient, T value)</td>
+ <td>Sets the coordinate in the given orientation to the value.</td>
+ </tr>
+ <tr>
+ <td width="586">void x(T value)</td>
+ <td>Sets the coordinate in the horizontal orientation to the value.</td>
+ </tr>
+ <tr>
+ <td width="586">void y(T value)</td>
+ <td>Sets the coordinate in the vertical orientation to the value.</td>
+ </tr>
+ </table>
+ <tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  </td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">

Modified: sandbox/gtl/doc/gtl_polygon_45_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_45_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_45_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,10 +22,10 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
+ <li>Polygon 45 Concept</li>
 <li>Polygon 45 With Holes Concept</li>
 <li>Polygon Concept</li>
 <li>Polygon With Holes Concept</li>
@@ -59,7 +59,7 @@
<h1>Polygon 45 Concept</h1>


-The polygon_45 concept type identifier is 
+The polygon_45 concept tag is 
polygon_45_concept

To register a user defined type as a model of
@@ -250,6 +250,72 @@
 object that models polygon_45.</td>
 </tr>
 </table>
+ <h1>Polygon 45 Data</h1>
+
+
+The library provides a model of polygon 45 concept declared
+
+template<typename T> poolygon_45_data where T is the coordinate type.
+This data type is used internally when a 45-degree polygon is needed and is
+available to the library user who finds it convenient to use a library polygon
+data type instead of providing their own.  The data type is implemented to
+be convenient to use with the library traits.
+<h2>Members</h2>
+<table border="1" width="100%" id="table2">
+ <tr>
+ <td width="586">geometry_type</td>
+ <td>polygon_45_concept</td>
+ </tr>
+ <tr>
+ <td width="586">coordinate_type</td>
+ <td>T</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type</td>
+ <td>Iterator over vertices point_data<T> vertices of polygon</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_45_data()</td>
+ <td>Default constructs the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_45_data(const
+ poolygon_45_data* that)</td>
+ <td>Copy construct</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_45_data& operator=(const
+ poolygon_45_data& that)</td>
+ <td>Assignment operator.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2> 
+ polygon_45_data& operator=(const T2& that) const</td>
+ <td>Assign from an object that is a model of polygon 45.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type begin()
+ const</td>
+ <td>Get the begin iterator over vertices of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type end()
+ const</td>
+ <td>Get the end iterator over vertices of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">std::size_t size() const</td>
+ <td>Get the number of elements in the sequence stored to the polygon,
+ usually equal to the number of edges of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename iT> 
+ void set(iT begin_points, iT end_points)</td>
+ <td>Sets the polygon to the iterator range of points.  No check is
+ performed to ensure the points describe corners that are multiples of 45
+ degrees relative to the coordinate axis.</td>
+ </tr>
+</table>
 <tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  </td>

Modified: sandbox/gtl/doc/gtl_polygon_45_set_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_45_set_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_45_set_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,7 +22,6 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -31,6 +30,7 @@
 <li>Polygon Concept</li>
 <li>Polygon With Holes Concept</li>
 <li>Polygon 90 Set Concept</li>
+ <li>Polygon 45 Set Concept</li>
 <li>Polygon Set Concept</li>
 <li>Connectivity Extraction 90</li>
 <li>Connectivity Extraction 45</li>
@@ -59,10 +59,10 @@
<h1>Polygon 45 Set Concept</h1>


-The polygon 45 set concept type identifier is 
+The polygon 45 set concept tag is 
polygon_45_set_concept

-The semantic of a polygon_45_set is a zero or more
+The semantic of a polygon_45_set is zero or more
geometry regions which have angles at the vertices that are multiples of
45-degrees relative to the coordinate axis.  A Polygon 45 Set Concept makes
no sense in floating point, but currently does not provide a static assert to
@@ -73,12 +73,25 @@
intersection point.  In the case that data represented contains no
45-degree angles and is Manhattan a runtime check will default to the Manhattan
algorithm.  The results of which are identical to what the 45-degree
-algorithm would do, but obtained more efficiently.Mapping type traits for a user defined
-polygon 45 set object is an advanced topic and covered by example code. 
-Users are recommended to use std::vector and std::list of user defined polygons
+algorithm would do, but obtained more efficiently.
+The motivation for providing the polygon 45 set is
+to extend the special case of Manhattan geometry capability of the library to
+encompass the slightly less common, but still important special case of geometry
+that is described by angles that are multiples of 45-degress with respect to the
+coordinate axis.  This simplifies the implementation of geometry algorithms
+and affords many opportunities for optimization.  45-degree algorithms can
+be 50X faster than arbitrary angle algorithms and are required to provide a
+complete feature set that meets the performance requirements of application
+domains in which Manhattan and 45-degree geometry are a common special case.Users are recommended to use std::vector and std::list of user defined polygons
or library provided polygon_45_set_data<coordinate_type> objects.  Lists
and vectors of models of polygon_45_concept or polygon_45_with_holes_concept are automatically models of polygon_45_set_concept.
<h2>Operators</h2>
+The return type of some operators is the polygon_45_set_view
+operator template type.  This type is itself a model of the polygon 90 set
+concept, but furthermore can be used as an argument to the polygon_45_set_data
+constructor and assignment operator.  The operator template exists to
+eliminate temp copies of intermediate results when Boolean operators are chained
+together.
<table border="1" width="100%" id="table5">
 <tr>
 <td width="586">template <typename T1, typename
@@ -457,7 +470,11 @@
void get(output_container& output) const</td>
 <td>Expects a standard container of geometry objects.  Will scan
 and eliminate overlaps.  Converts polygon set geometry to objects
- of that type and appends them to the container.</td>
+ of that type and appends them to the container.  Polygons will be
+ output with counterclockwise winding, hole polygons will be output with
+ clockwise winding.  The last vertex of an output polygon is the
+ duplicate of the first, and the number of points is equal to the number
+ of edges plus 1.</td>
 </tr>
 <tr>
 <td width="586">
@@ -465,7 +482,8 @@
void get_polygons(output_container& output) const</td>
 <td>Expects a standard container of polygon objects.  Will scan and
 eliminate overlaps.  Converts polygon set geometry to polygons and
- appends them to the container.</td>
+ appends them to the container.  Polygons will have holes fractured
+ out to the outer boundary along the positive y direction.</td>
 </tr>
 <tr>
 <td width="586">

Modified: sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,11 +22,11 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
 <li>Polygon 45 Concept</li>
+ <li>Polygon 45 With Holes Concept</li>
 <li>Polygon Concept</li>
 <li>Polygon With Holes Concept</li>
 <li>Polygon 90 Set Concept</li>
@@ -59,7 +59,7 @@
<h1>Polygon 45 With Holes Concept</h1>


-The polygon_45 concept type identifier is 
+The polygon_45 concept tag is 
polygon_45_with_holes_concept

To register a user defined type as a model of
@@ -259,6 +259,102 @@
 object that models polygon_45_with_holes.</td>
 </tr>
 </table>
+ <h1>Polygon 45 With Holes Data</h1>
+
+
+The library provides a model of polygon 45 with holes concept declared
+
+template<typename T> poolygon_45_with_holes_data where T is the
+coordinate type.
+This data type is used internally when a 45 degree polygon with holes is
+needed and is available to the library user who finds it convenient to use a
+library polygon data type instead of providing their own.  The data type is
+implemented to be convenient to use with the library traits.
+<h2>Members</h2>
+<table border="1" width="100%" id="table2">
+ <tr>
+ <td width="586">geometry_type</td>
+ <td>polygon_45_with_holes_concept</td>
+ </tr>
+ <tr>
+ <td width="586">coordinate_type</td>
+ <td>T</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type</td>
+ <td>Iterator over vertices point_data<T> vertices of polygon</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_holes_type</td>
+ <td>Iterator over hole polygons of type
+ polygon_45_data<T>.</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_45_with_holes_data()</td>
+ <td>Default constructs the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_45_with_holes_data(const
+ poolygon_45_with_holes_data* that)</td>
+ <td>Copy construct</td>
+ </tr>
+ <tr>
+ <td width="586">poolygon_45_with_holes_data& 
+ operator=(const poolygon_45_with_holes_data& that)</td>
+ <td>Assignment operator.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2> 
+ polygon_45_with_holes_data& 
+ operator=(const T2& that) const</td>
+ <td>Assign from an object that is a model of polygon 45 with holes.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type begin()
+ const</td>
+ <td>Get the begin iterator over vertices of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type end()
+ const</td>
+ <td>Get the end iterator over vertices of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_hole_type begin_holes()
+ const</td>
+ <td>Get the begin compact iterator over non-redundant coordinates of the
+ polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_hole_type end_holes()
+ const</td>
+ <td>Get the end compact iterator over non-redundant coordinates of the
+ polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">std::size_t size() const</td>
+ <td>Get the number of elements in the sequence stored to the polygon,
+ usually equal to the number of edges of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">std::size_t size_holes() const</td>
+ <td>Get the number of holes in the polygon</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename iT> 
+ void set(iT begin_points, iT end_points)</td>
+ <td>Sets the polygon to the iterator range of points.  No check is
+ performed to ensure the points describe a 45 degree figure.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename iT> 
+ void set_holes(iT begin_holes, iT end_choless)</td>
+ <td>Sets the polygon holes the iterator range of hole polygons.  These
+ polygons in the input range may be either polygon_45_data or
+ polygon_45_with_holes_data or any type that provides begin and end
+ member functions to iterate over point_data<T>.</td>
+ </tr>
+</table>
 <tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  </td>

Modified: sandbox/gtl/doc/gtl_polygon_90_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_90_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_90_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,8 +22,8 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
 <li>Polygon 45 Concept</li>
 <li>Polygon 45 With Holes Concept</li>
@@ -59,7 +59,7 @@
<h1>Polygon 90 Concept</h1>


-The polygon_90 concept type identifier is 
+The polygon_90 concept tag is 
polygon_90_concept

To register a user defined type as a model of
@@ -259,6 +259,99 @@
 object that models polygon_90.</td>
 </tr>
 </table>
+ <h1>Polygon 90 Data</h1>
+
+
+The library provides a model of polygon 90 concept declared
+
+template<typename T> poolygon_90_data where T is the coordinate type.
+This data type is used internally when a Manhattan polygon is needed and is
+available to the library user who finds it convenient to use a library polygon
+data type instead of providing their own.  The data type is implemented to
+be convenient to use with the library traits.
+<h2>Members</h2>
+<table border="1" width="100%" id="table2">
+ <tr>
+ <td width="586">geometry_type</td>
+ <td>polygon_90_concept</td>
+ </tr>
+ <tr>
+ <td width="586">coordinate_type</td>
+ <td>T</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type</td>
+ <td>Iterator over vertices point_data<T> vertices of polygon</td>
+ </tr>
+ <tr>
+ <td width="586">compact_iterator_type</td>
+ <td>Iterator over non-redundant coordinates
+ of the polygon, alternating x, y, x, y starting with an x, where each x
+ corresponds to a vertical edge and each y corresponds to a horizontal
+ edge.</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_90_data()</td>
+ <td>Default constructs the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_90_data(const
+ poolygon_90_data* that)</td>
+ <td>Copy construct</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_90_data& operator=(const
+ poolygon_90_data& that)</td>
+ <td>Assignment operator.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2> 
+ polygon_90_data& operator=(const T2& that) const</td>
+ <td>Assign from an object that is a model of polygon 90.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type begin()
+ const</td>
+ <td>Get the begin iterator over vertices of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type end()
+ const</td>
+ <td>Get the end iterator over vertices of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">compact_iterator_type 
+ begin_compact() const</td>
+ <td>Get the begin compact iterator over non-redundant coordinates of the
+ polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">compact_iterator_type 
+ end_compact() const</td>
+ <td>Get the end compact iterator over non-redundant coordinates of the
+ polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">std::size_t size() const</td>
+ <td>Get the number of elements in the sequence stored to the polygon,
+ usually equal to the number of edges of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename iT> 
+ void set(iT begin_points, iT end_points)</td>
+ <td>Sets the polygon to the iterator range of points.  No check is
+ performed to ensure the points describe a Manhattan figure, every other
+ x and y value of the points is used to initialize the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename iT> 
+ void set_compact(iT begin_coords, iT end_coords)</td>
+ <td>Sets the polygon to the iterator range of coordinates.  These
+ coordinates correspond to the x values of vertical edges and y values of
+ horizontal edges.  It is expected that the sequence start with an x
+ value and proceed x then y then x then y.</td>
+ </tr>
+</table>
 <tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  </td>

Modified: sandbox/gtl/doc/gtl_polygon_90_set_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_90_set_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_90_set_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,7 +22,6 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -30,6 +29,7 @@
 <li>Polygon 45 With Holes Concept</li>
 <li>Polygon Concept</li>
 <li>Polygon With Holes Concept</li>
+ <li>Polygon 90 Set Concept</li>
 <li>Polygon 45 Set Concept</li>
 <li>Polygon Set Concept</li>
 <li>Connectivity Extraction 90</li>
@@ -59,17 +59,29 @@
<h1>Polygon 90 Set Concept</h1>


-The polygon 90 set concept type identifier is 
+The polygon 90 set concept tag is 
polygon_90_set_concept

-The semantic of a polygon_90_set is a zero or more
-Manhattan geometry regions.Mapping type traits for a user defined
-polygon 90 set object is an advanced topic and covered by example code. 
-Users are recommended to use std::vector and std::list of user defined polygons
+The semantic of a polygon 90 set is zero or more
+Manhattan geometry regions.
+The motivation for providing the
+polygon_90_set_concept is that it is a very common special case of planar
+geometry which afford the implementation of a variety of optimizations on the
+general planar geometry algorithms.  Manhattan geometry processing by the
+polygon_90_set_concept can be 100X faster than arbitrary angle polygon
+manipulation.  Because the performance benefits are so large and the
+special case is important enough, the library provides these performance
+benefits for those application domains that require them.Users are recommended to use std::vector and std::list of user defined polygons
or library provided polygon_90_set_data<coordinate_type> objects.  Lists
and vectors of models of polygon_90_concept or polygon_90_with_holes_concept or
rectangle_concept are automatically models of polygon_90_set_concept.
<h2>Operators</h2>
+The return type of some operators is the polygon_90_set_view
+operator template type.  This type is itself a model of the polygon 90 set
+concept, but furthermore can be used as an argument to the polygon_90_set_data
+constructor and assignment operator.  The operator template exists to
+eliminate temp copies of intermediate results when Boolean operators are chained
+together.
<table border="1" width="100%" id="table3">
 <tr>
 <td width="586">template <typename T1, typename
@@ -588,7 +600,11 @@
void get(output_container& output) const</td>
 <td>Expects a standard container of geometry objects.  Will scan
 and eliminate overlaps.  Converts polygon set geometry to objects
- of that type and appends them to the container.</td>
+ of that type and appends them to the container.  Polygons will be
+ output with counterclockwise winding, hole polygons will be output with
+ clockwise winding.  The last vertex of an output polygon is not the
+ duplicate of the first, and the number of points is equal to the number
+ of edges.</td>
 </tr>
 <tr>
 <td width="586">
@@ -596,7 +612,9 @@
void get_polygons(output_container& output) const</td>
 <td>Expects a standard container of polygon objects.  Will scan and
 eliminate overlaps.  Converts polygon set geometry to polygons and
- appends them to the container.</td>
+ appends them to the container.  Polygons will have holes fractured
+ out to the outer boundary along the positive direction of the scanline
+ orientation of the polygon set.</td>
 </tr>
 <tr>
 <td width="586">

Modified: sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,9 +22,9 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
+ <li>Polygon 90 With Holes Concept</li>
 <li>Polygon 45 Concept</li>
 <li>Polygon 45 With Holes Concept</li>
 <li>Polygon Concept</li>
@@ -59,7 +59,7 @@
<h1>Polygon 90 With Holes Concept</h1>


-The polygon_90 concept type identifier is 
+The polygon_90 concept tag is 
polygon_90_with_holes_concept

To register a user defined type as a model of
@@ -283,6 +283,129 @@
 object that models polygon_90_with_holes.</td>
 </tr>
 </table>
+ <h1>Polygon 90 With Holes Data</h1>
+
+
+The library provides a model of polygon 90 with holes concept declared
+
+template<typename T> poolygon_90_with_holes_data where T is the
+coordinate type.
+This data type is used internally when a Manhattan polygon with holes is
+needed and is available to the library user who finds it convenient to use a
+library polygon data type instead of providing their own.  The data type is
+implemented to be convenient to use with the library traits.
+<h2>Members</h2>
+<table border="1" width="100%" id="table2">
+ <tr>
+ <td width="586">geometry_type</td>
+ <td>polygon_90_with_holes_concept</td>
+ </tr>
+ <tr>
+ <td width="586">coordinate_type</td>
+ <td>T</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type</td>
+ <td>Iterator over vertices point_data<T> vertices of polygon</td>
+ </tr>
+ <tr>
+ <td width="586">compact_iterator_type</td>
+ <td>Iterator over non-redundant coordinates
+ of the polygon, alternating x, y, x, y starting with an x, where each x
+ corresponds to a vertical edge and each y corresponds to a horizontal
+ edge.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_holes_type</td>
+ <td>Iterator over hole polygons of type
+ polygon_90_data<T>.</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_90_with_holes_data()</td>
+ <td>Default constructs the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_90_with_holes_data(const
+ poolygon_90_with_holes_data* that)</td>
+ <td>Copy construct</td>
+ </tr>
+ <tr>
+ <td width="586">poolygon_90_with_holes_data& 
+ operator=(const poolygon_90_with_holes_data& that)</td>
+ <td>Assignment operator.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2> polygon_90_with_holes_data& 
+ operator=(const T2& that) const</td>
+ <td>Assign from an object that is a model of polygon 90 with holes.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type begin()
+ const</td>
+ <td>Get the begin iterator over vertices of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type end()
+ const</td>
+ <td>Get the end iterator over vertices of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">compact_iterator_type begin_compact()
+ const</td>
+ <td>Get the begin compact iterator over non-redundant coordinates of the
+ polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">compact_iterator_type end_compact()
+ const</td>
+ <td>Get the end compact iterator over non-redundant coordinates of the
+ polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_hole_type begin_holes()
+ const</td>
+ <td>Get the begin compact iterator over non-redundant coordinates of the
+ polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_hole_type end_holes()
+ const</td>
+ <td>Get the end compact iterator over non-redundant coordinates of the
+ polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">std::size_t size() const</td>
+ <td>Get the number of elements in the sequence stored to the polygon,
+ usually equal to the number of edges of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">std::size_t size_holes() const</td>
+ <td>Get the number of holes in the polygon</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename iT> 
+ void set(iT begin_points, iT end_points)</td>
+ <td>Sets the polygon to the iterator range of points.  No check is
+ performed to ensure the points describe a Manhattan figure, every other
+ x and y value of the points is used to initialize the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename iT> 
+ void set_compact(iT begin_coords, iT end_coords)</td>
+ <td>Sets the polygon to the iterator range of coordinates.  These
+ coordinates correspond to the x values of vertical edges and y values of
+ horizontal edges.  It is expected that the sequence start with an x
+ value and proceed x then y then x then y.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename iT> 
+ void set_holes(iT begin_holes, iT end_choless)</td>
+ <td>Sets the polygon holes the iterator range of hole polygons.  These
+ polygons in the input range may be either polygon_90_data or
+ polygon_90_with_holes_data or any type that provides begin_compact and
+ end_compact member functions.</td>
+ </tr>
+</table>
 <tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  </td>

Modified: sandbox/gtl/doc/gtl_polygon_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,12 +22,12 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
 <li>Polygon 45 Concept</li>
 <li>Polygon 45 With Holes Concept</li>
+ <li>Polygon Concept</li>
 <li>Polygon With Holes Concept</li>
 <li>Polygon 90 Set Concept</li>
 <li>Polygon 45 Set Concept</li>
@@ -59,7 +59,7 @@
<h1>Polygon Concept</h1>


-The polygon concept type identifier is 
+The polygon concept tag is 
polygon_concept

To register a user defined type as a model of
@@ -125,6 +125,9 @@
          return t; 
     } 
};
+Example code custom_polygon.cpp
+demonstrates mapping a
+ user defined polygon class to the library polygon_concept
<h2>Functions</h2>
<table border="1" width="100%" id="table1">
 <tr>
@@ -248,6 +251,73 @@
 object that models polygon.</td>
 </tr>
 </table>
+ <h1>Polygon Data</h1>
+
+
+The library provides a model of polygon concept declared
+
+template<typename T> poolygon_data where T is the coordinate type.
+This data type is used internally when a polygon is needed and is available
+to the library user who finds it convenient to use a library polygon data type
+instead of providing their own.  The data type is implemented to be
+convenient to use with the library traits.
+Example code polygon_usage.cpp
+demonstrates using
+ the library provided polygon data types and functions
+<h2>Members</h2>
+<table border="1" width="100%" id="table2">
+ <tr>
+ <td width="586">geometry_type</td>
+ <td>polygon_concept</td>
+ </tr>
+ <tr>
+ <td width="586">coordinate_type</td>
+ <td>T</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type</td>
+ <td>Iterator over vertices point_data<T> vertices of polygon</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_data()</td>
+ <td>Default constructs the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_data(const
+ poolygon_data* that)</td>
+ <td>Copy construct</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_data& operator=(const
+ poolygon_data& that)</td>
+ <td>Assignment operator.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2> 
+ polygon_data& operator=(const T2& that) const</td>
+ <td>Assign from an object that is a model of polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type begin()
+ const</td>
+ <td>Get the begin iterator over vertices of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type end()
+ const</td>
+ <td>Get the end iterator over vertices of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">std::size_t size() const</td>
+ <td>Get the number of elements in the sequence stored to the polygon,
+ usually equal to the number of edges of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename iT> 
+ void set(iT begin_points, iT end_points)</td>
+ <td>Sets the polygon to the iterator range of points.  </td>
+ </tr>
+</table>
 <tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  </td>

Modified: sandbox/gtl/doc/gtl_polygon_set_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_set_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_set_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,7 +22,6 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -32,6 +31,7 @@
 <li>Polygon With Holes Concept</li>
 <li>Polygon 90 Set Concept</li>
 <li>Polygon 45 Set Concept</li>
+ <li>Polygon Set Concept</li>
 <li>Connectivity Extraction 90</li>
 <li>Connectivity Extraction 45</li>
 <li>Property Merge 90</li>
@@ -59,10 +59,10 @@
<h1>Polygon Set Concept</h1>


-The polygon set concept type identifier is 
+The polygon set concept tag is 
polygon_set_concept

-The semantic of a polygon_set is a zero or more
+The semantic of a polygon_set is zero or more
geometry regions.  A Polygon Set Concept may be defined with floating point
coordinates, but a snap rounding distance of one integer unit will still be
applied, furthermore, geometry outside the domain where one integer unit is
@@ -74,12 +74,18 @@
case that the data represented contains only Manhattan and 45-degree geometry a
runtime check will default to the faster 45-degree algorithm.  The results
of which may differ slight from what the general algorithm would do because
-non-integer intersections will be handled differently.Mapping type traits for a user defined
-polygon set object is an advanced topic and covered by example code. 
-Users are recommended to use std::vector and std::list of user defined polygons
+non-integer intersections will be handled differently.Users are recommended to use std::vector and std::list of user defined polygons
or library provided polygon_set_data<coordinate_type> objects.  Lists
and vectors of models of polygon_concept or polygon_with_holes_concept are automatically models of polygon_set_concept.
+Example code custom_polygon_set.cpp
+ demonstrates mapping a user defined class to the library polygon_set_concept
<h2>Operators</h2>
+The return type of some operators is the polygon_set_view
+operator template type.  This type is itself a model of the polygon 90 set
+concept, but furthermore can be used as an argument to the polygon_set_data
+constructor and assignment operator.  The operator template exists to
+eliminate temp copies of intermediate results when Boolean operators are chained
+together.
<table border="1" width="100%" id="table5">
 <tr>
 <td width="586">template <typename T1, typename
@@ -268,6 +274,9 @@
benefit from knowledge of the invariants enforced by the class are implemented
as member functions to provide them access to information about those
invariants.  
+Example code polygon_set_usage.cpp
+demonstrates using
+ the library provided polygon set data types and functions
<h2>Member Functions</h2>
<table border="1" width="100%" id="table7">
 <tr>
@@ -339,7 +348,14 @@
void get(output_container& output) const</td>
 <td>Expects a standard container of polygons objects.  Will scan
 and eliminate overlaps.  Converts polygon set geometry to objects
- of the polygon type and appends them to the container.</td>
+ of the polygon type and appends them to the container.  Polygons
+ will be output with counterclockwise winding, hole polygons will be
+ output with clockwise winding.  The last vertex of an output
+ polygon is the duplicate of the first, and the number of points is equal
+ to the number of edges plus 1.  If required by the output data
+ type, polygons will have holes fractured out to the outer boundary along
+ the positive y direction and off grid intersections on the outer
+ boundary introduced by this fracture will be truncated downward.</td>
 </tr>
 <tr>
 <td width="586">

Modified: sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,13 +22,13 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
 <li>Polygon 45 Concept</li>
 <li>Polygon 45 With Holes Concept</li>
 <li>Polygon Concept</li>
+ <li>Polygon With Holes Concept</li>
 <li>Polygon 90 Set Concept</li>
 <li>Polygon 45 Set Concept</li>
 <li>Polygon Set Concept</li>
@@ -59,7 +59,7 @@
<h1>Polygon With Holes Concept</h1>


-The polygon concept type identifier is 
+The polygon concept tag is 
polygon_with_holes_concept

To register a user defined type as a model of
@@ -254,6 +254,101 @@
 object that models polygon_with_holes.</td>
 </tr>
 </table>
+ <h1>Polygon With Holes Data</h1>
+
+
+The library provides a model of polygon with holes concept declared
+
+template<typename T> poolygon_with_holes_data where T is the
+coordinate type.
+This data type is used internally when a polygon with holes is
+needed and is available to the library user who finds it convenient to use a
+library polygon data type instead of providing their own.  The data type is
+implemented to be convenient to use with the library traits.
+<h2>Members</h2>
+<table border="1" width="100%" id="table2">
+ <tr>
+ <td width="586">geometry_type</td>
+ <td>polygon_with_holes_concept</td>
+ </tr>
+ <tr>
+ <td width="586">coordinate_type</td>
+ <td>T</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type</td>
+ <td>Iterator over vertices point_data<T> vertices of polygon</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_holes_type</td>
+ <td>Iterator over hole polygons of type
+ polygon_data<T>.</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_with_holes_data()</td>
+ <td>Default constructs the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">polygon_with_holes_data(const
+ poolygon_with_holes_data* that)</td>
+ <td>Copy construct</td>
+ </tr>
+ <tr>
+ <td width="586">poolygon_with_holes_data& 
+ operator=(const poolygon_with_holes_data& that)</td>
+ <td>Assignment operator.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2> 
+ polygon_with_holes_data& 
+ operator=(const T2& that) const</td>
+ <td>Assign from an object that is a model of polygon with holes.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type begin()
+ const</td>
+ <td>Get the begin iterator over vertices of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_type end()
+ const</td>
+ <td>Get the end iterator over vertices of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_hole_type begin_holes()
+ const</td>
+ <td>Get the begin compact iterator over non-redundant coordinates of the
+ polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">iterator_hole_type end_holes()
+ const</td>
+ <td>Get the end compact iterator over non-redundant coordinates of the
+ polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">std::size_t size() const</td>
+ <td>Get the number of elements in the sequence stored to the polygon,
+ usually equal to the number of edges of the polygon.</td>
+ </tr>
+ <tr>
+ <td width="586">std::size_t size_holes() const</td>
+ <td>Get the number of holes in the polygon</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename iT> 
+ void set(iT begin_points, iT end_points)</td>
+ <td>Sets the polygon to the iterator range of points. </td>
+ </tr>
+ <tr>
+ <td width="586">template <typename iT> 
+ void set_holes(iT begin_holes, iT end_choless)</td>
+ <td>Sets the polygon holes the iterator range of hole polygons.  These
+ polygons in the input range may be either polygon_data or
+ polygon_with_holes_data or any type that provides begin and end member
+ functions to iterate over point_data<T>.</td>
+ </tr>
+</table>
 <tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  </td>

Modified: sandbox/gtl/doc/gtl_property_merge.htm
==============================================================================
--- sandbox/gtl/doc/gtl_property_merge.htm (original)
+++ sandbox/gtl/doc/gtl_property_merge.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,7 +22,6 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -36,6 +35,7 @@
 <li>Connectivity Extraction 90</li>
 <li>Connectivity Extraction 45</li>
 <li>Property Merge 90</li>
+ <li>Property Merge</li>
 </ul>
 <h3 class="navbar">Other Resources</h3>
 <ul>
@@ -70,9 +70,11 @@
operation a fairly complex container is required.  Resulting geometries are
associated with unique subsets of property values of the input geometry. 
Two suitable containers for storing the result of a property merge operation
-are: std::map<std::set<property_type>, polygon_set_data<coordiante_type>
+are:std::map<std::set<property_type>, polygon_set_data<coordiante_type>
> 
-std::map<std::vector<property_type>, polygon_set_data<coordiante_type> ><h2>Member Functions</h2>
+std::map<std::vector<property_type>, polygon_set_data<coordiante_type> >
+Example code property_merge_usage.cpp
+ demonstrates using the n-layer map-overlay algorithm on polygon data.<h2>Member Functions</h2>
<table border="1" width="100%" id="table1">
 <tr>
 <td width="586">property_merge()</td>

Modified: sandbox/gtl/doc/gtl_property_merge_90.htm
==============================================================================
--- sandbox/gtl/doc/gtl_property_merge_90.htm (original)
+++ sandbox/gtl/doc/gtl_property_merge_90.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,7 +22,6 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -35,6 +34,7 @@
 <li>Polygon Set Concept</li>
 <li>Connectivity Extraction 90</li>
 <li>Connectivity Extraction 45</li>
+ <li>Property Merge 90</li>
 <li>Property Merge</li>
 </ul>
 <h3 class="navbar">Other Resources</h3>
@@ -72,7 +72,9 @@
Two suitable containers for storing the result of a property merge operation
are: std::map<std::set<property_type>, polygon_90_set_data<coordiante_type>
> 
-std::map<std::vector<property_type>, polygon_90_set_data<coordiante_type> ><h2>Member Functions</h2>
+std::map<std::vector<property_type>, polygon_90_set_data<coordiante_type> >
+Example code property_merge_usage.cpp
+ demonstrates using the n-layer map-overlay algorithm on polygon 90 data.<h2>Member Functions</h2>
<table border="1" width="100%" id="table1">
 <tr>
 <td width="586">property_merge_90()</td>

Modified: sandbox/gtl/doc/gtl_rectangle_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_rectangle_concept.htm (original)
+++ sandbox/gtl/doc/gtl_rectangle_concept.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -22,7 +22,7 @@
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>Point Concept</li>
- <li>Point 3D Concept</li>
+ <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
 <li>Polygon 45 Concept</li>
@@ -59,7 +59,7 @@
<h1>Rectangle Concept</h1>


-The rectangle concept type identifier is 
+The rectangle concept tag is 
rectangle_concept

To register a user defined type as a model of
@@ -641,6 +641,85 @@
 returns true.</td>
 </tr>
</table>
+ <h1>Rectangle Data</h1>
+
+
+The library provides a model of rectangle concept declared
+
+template<typename T> rectangle_data where T is the coordinate type.
+This data type is used internally when a rectangle is needed and is available
+to the library user who finds it convenient to use a library rectangle data type
+instead of providing their own.  The data type is implemented to be
+convenient to use with the library traits.
+<h2>Members</h2>
+<table border="1" width="100%" id="table2">
+ <tr>
+ <td width="586">geometry_type</td>
+ <td>rectangle_concept</td>
+ </tr>
+ <tr>
+ <td width="586">coordinate_type</td>
+ <td>T</td>
+ </tr>
+ <tr>
+ <td width="586">interval_type</td>
+ <td>interval_data<T></td>
+ </tr>
+ <tr>
+ <td width="586">rectangle_data(T xl, T
+ yl, T xh, T yh)</td>
+ <td>Constructs a rectangle with four
+ coordinates.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T1, typename
+ T2> 
+ rectangle_data(const T1& horizontal_interval, 
+              
+ const T2& vertical_interval)</td>
+ <td>Constructs a rectangle with two objects
+ that model interval.</td>
+ </tr>
+ <tr>
+ <td width="586">rectangle_data(const
+ rectangle_data* that)</td>
+ <td>Copy construct</td>
+ </tr>
+ <tr>
+ <td width="586">rectangle_data& operator=(const
+ rectangle_data& that)</td>
+ <td>Assignment operator.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ rectangle_data& 
+ operator=(const T2& that) const</td>
+ <td>Assign from an object that is a model of rectangle.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator==(const T2& that) const</td>
+ <td>Compare equality to an object that is a model of rectangle.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2>
+ bool
+ operator!=(const T2& that) const</td>
+ <td>Compare inequality to an object that is a model of rectangle.</td>
+ </tr>
+ <tr>
+ <td width="586">interval_data<T> get(orientation_2d
+ orient) const</td>
+ <td>Get the interval in the given orientation.</td>
+ </tr>
+ <tr>
+ <td width="586">template <typename T2> 
+ void set(orientation_2d orient, const T2& value)</td>
+ <td>Sets the interval in the given orientation to the value of an object
+ that models interval.</td>
+ </tr>
+ </table>
 <tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  </td>

Added: sandbox/gtl/doc/images/refinements.png
==============================================================================
Binary file. No diff available.

Modified: sandbox/gtl/doc/index.htm
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2009-06-18 18:55:48 EDT (Thu, 18 Jun 2009)
@@ -15,15 +15,14 @@
 <div style="margin: 5px;">
 <h3 class="navbar">Contents</h3>
 <ul>
- <li><a href="gtl_design_overview.htm">Polygon
+ <li>Polygon Library Main Page</li>
+ <li><a href="gtl_design_overview.htm">Polygon
 Library Design Overview</a></li>
 <li>Isotropy</li>
 <li>Coordinate Concept</li>
 <li>Interval Concept</li>
 <li>
 <a href="gtl_point_concept.htm">Point Concept</a></li>
- <li>
- Point 3D Concept</li>
 <li>Rectangle Concept</li>
 <li>Polygon 90 Concept</li>
 <li>Polygon 90 With Holes Concept</li>
@@ -64,12 +63,25 @@
The boost polygon library provides algorithms focused on manipulating planar
polygon geometry data.  Specific algorithms provided are the polygon set
operations (intersection, union, difference, disjoint-union) and related
-algorithms such as polygon connectivity graph extraction and map-overlay. 
-These algorithms are of significant interest in GIS (Geospatial Information
+algorithms such as polygon connectivity graph extraction, offsetting and map-overlay. 
+An example of the disjoint-union (XOR) of figure a and figure b is shown below
+in figure c. 
+These so-called Boolean algorithms are of significant interest in GIS (Geospatial Information
Systems), VLSI CAD as well al other fields of CAD, and many more application
-areas.
-The design philosophy behind the Polygon Library was to create an API for
-invoking these library algorithms on user geometry data types that is maximally
+areas, and providing them is the primary focus of this library.  The
+polygon library is not intended to cover all of computational geometry in its
+scope, and provides a set of capabilities for working with coordinates, points,
+intervals and rectangles that are needed to support implementing and interacting
+with polygon data structures and algorithms.  Specifically, 3d and
+non-Cartesian/non-planar geometry is outside of the scope of the polygon
+library.<img border="0" src="images/hand.png" width="837" height="277">
+For additional detailed discussion of the library and its implementation
+including benchmark comparisons with other open source alternatives please see
+the paper and
+presentation from
+boostcon 2009. 
+The design philosophy behind the polygon library was to create an API for
+invoking the library algorithms it provides on user geometry data types that is maximally
intuitive, minimally error-prone and easy to integrate into pre-existing
applications.  C++-concepts based template meta-programming combined with
generic operator overloading meets these design goals without sacrificing the
@@ -119,7 +131,7 @@
The end result is accumulated into a list of polygons with a union operation. 
It is considerably more typing to describe this usage of the API than to code
it, and the description is not much clearer than the code itself. 
-Functions are named for what they do, or overloads of C++ operators that make it
+Functions are named for what they do, or are overloads of C++ operators that make it
easy to infer from reading the code what to expect from it.  Following the
principle of least astonishment, the inferred behavior should generally match
the actual behavior.  Conventions such as argument ordering (output

Next message: lucanus.j.simonson_at_[hidden]: "[Boost-commit] svn:boost r54071 - sandbox/gtl/doc/images"
Previous message: jewillco_at_[hidden]: "[Boost-commit] svn:boost r54069 - trunk/boost/graph"

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