| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
| <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en" xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:(null)1="http://www.w3.org/TR/REC-html40"><head><!-- |
| Copyright 2009-2010 Intel Corporation |
| license banner |
| --> |
| <title>Boost Polygon Library: Interval Concept</title> |
| <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1"> |
| <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0"><tbody><tr> |
| <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> |
| <div style="padding: 5px;" align="center"> |
| <img border="0" src="images/boost.png" width="277" height="86"><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;"> |
| </a> |
| </div> |
| <div style="margin: 5px;"> |
| <h3 class="navbar">Contents</h3> |
| <ul> |
| <li><a href="index.htm">Boost.Polygon Main Page</a></li> |
| <li><a href="gtl_design_overview.htm">Design Overview</a></li> |
| <li><a href="gtl_isotropy.htm">Isotropy</a></li> |
| <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li> |
| <li>Interval Concept</li> |
| <li><a href="gtl_point_concept.htm">Point Concept</a></li> |
| <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li> |
| <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li> |
| <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90 With Holes Concept</a></li> |
| <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li> |
| <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45 With Holes Concept</a></li> |
| <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li> |
| <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With Holes Concept</a></li> |
| <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set Concept</a></li> |
| <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set Concept</a></li> |
| <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li> |
| <li><a href="gtl_connectivity_extraction_90.htm">Connectivity Extraction 90</a></li> |
| <li><a href="gtl_connectivity_extraction_45.htm">Connectivity Extraction 45</a></li> |
| <li><a href="gtl_connectivity_extraction.htm">Connectivity Extraction</a></li> |
| <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li> |
| <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li> |
| <li><a href="gtl_property_merge.htm">Property Merge</a></li> |
| </ul> |
| <h3 class="navbar">Other Resources</h3> |
| <ul> |
| <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li> |
| <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009 |
| Presentation</a></li> |
| <li><a href="analysis.htm">Performance Analysis</a></li> |
| <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li> |
| <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li> |
| </ul> |
| </div> |
| <h3 class="navbar">Polygon Sponsor</h3> |
| <div style="padding: 5px;" align="center"> |
| <img border="0" src="images/intlogo.gif" width="127" height="51"> |
| </div> |
| </td> |
| <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"> |
| |
| <!-- End Header --> |
| |
| <br> |
| <p> |
| </p><h1>Interval Concept</h1> |
| |
| <p> |
| <p>The interval concept tag is <font face="Courier New"> |
| interval_concept</font></p> |
| <p> |
| To register a user defined type as a model of interval concept, specialize the |
| geometry concept meta-function for that type. In the example below |
| CInterval is registered as a model of interval concept.<p> |
| <font face="Courier New">template <><br> |
| struct geometry_concept<CInterval> { typedef interval_concept type; };</font><p> |
| <font face="Times New Roman">The semantic of an interval is that it has a low |
| and high coordinate and there is an invariant that low is less than or equal to |
| high. This invariant is enforced by the generic library functions that |
| operate on intervals, and is not expected of the data type itself or the concept |
| mapping of that data type to the interval concept through its traits. In |
| this way a std::pair<int, int>, boost::tuple<int, int> or boost::array<int, 2> |
| could all be made models of interval by simply providing indirect access to their |
| elements through traits.</font><p> |
| <font face="Times New Roman">Below is shown the default interval traits. |
| Specialization of these traits is required for types that don't conform to the |
| default behavior.</font><p> |
| <font face="Courier New">template <typename T><br> |
| struct interval_traits {<br> |
| typedef typename T::coordinate_type coordinate_type;<br> |
| <br> |
| static inline coordinate_type get(const T& interval, direction_1d dir) {<br> |
| return interval.get(dir); <br> |
| }<br> |
| };<br> |
| <br> |
| template <typename T><br> |
| struct interval_mutable_traits {<br> |
| static inline void set(T& interval, direction_1d dir, </font> |
| <br> |
| <font face="Courier New"> typename interval_traits<T>::coordinate_type value) {<br> |
| |
| interval.set(dir, value); <br> |
| |
| }<br> |
| |
| static inline T construct(typename interval_traits<T>::coordinate_type low_value, |
| <br> |
| |
| typename interval_traits<T>::coordinate_type high_value) {<br> |
| |
| return T(low_value, high_value); <br> |
| |
| }<br> |
| };</font><h2>Functions</h2> |
| <table border="1" width="100%" id="table1"> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| coordinate_type <b>get</b>(const T& interval, direction_1d)</font></td> |
| <td><font face="Times New Roman">Expects a model of interval. |
| Returns the low or high coordinate of the interval, depending on the |
| direction_1d value.</font><font face="Courier New"><br> |
| </font></td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T, typename |
| coordinate_type><br> |
| void <b>set</b>(T& interval, direction_1d, coordinate_type)</font></td> |
| <td><font face="Times New Roman">Expects a model of interval. |
| Sets the low or high coordinate of the interval to the coordinate, |
| depending on the direction_1d value. If low would be greater than |
| high after this change then both are set to the input coordinate value.</font></td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T <b>construct</b>(coordinate_type low, coordinate_type high)</font></td> |
| <td>Construct an object that is a model of interval given low and high |
| coordinate values.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>assign</b>(T1& left, const T2& right)</font></td> |
| <td>Copies data from right object that models interval into left object |
| that models interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T, typename |
| T2><br> |
| bool <b>equivalence</b>(const T& interval1, const T2& interval2)</font></td> |
| <td>Given two objects that model interval, compares and returns true if |
| their low and high values are respectively equal to each other.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| bool <b>contains</b>(const T&, coordinate_type, <br> |
| |
| bool consider_touch=true)</font></td> |
| <td>Given an object that models interval and a coordinate, returns true |
| if the interval contains the coordinate. If the consider_touch |
| flag is true will return true if the coordinate is equal to one of the |
| interval ends.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| bool <b>contains</b>(const T1& a, const T2& b, <br> |
| |
| bool consider_touch = true) </font></td> |
| <td>Returns true if model of interval a contains both ends of model of |
| interval b. If the consider_touch flag is true will consider the |
| end of b contained within a even if it is equal to an end of a.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| interval_type><br> |
| coordinate_type <b>low</b>(const interval_type& interval)</font></td> |
| <td>Returns the low end of an object that models interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| interval_type><br> |
| coordinate_type <b>high</b>(const interval_type& interval)</font></td> |
| <td>Returns the high end of an object that models interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">// get the center coordinate<br> |
| template <typename interval_type><br> |
| coordinate_type <b>center</b>(const interval_type& interval)</font></td> |
| <td>Returns the center coordinate of an object that models interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| interval_type><br> |
| void <b>low</b>(interval_type& interval, coordinate_type )</font></td> |
| <td>Sets the low end of the object that models interval to the |
| coordinate value. If the low end would be set to larger than high |
| end then both are set to the coordinate value.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| interval_type><br> |
| void <b>high</b>(interval_type& interval, coordinate_type )</font></td> |
| <td>Sets the high end of the object that models interval to the |
| coordinate value. If the high end would be set to less than low |
| end then both are set to the coordinate value.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| interval_type><br> |
| coordinate_difference <b>delta</b>(const interval_type& interval)</font></td> |
| <td>Returns the distance from low to high end of an object that models |
| interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| interval_type><br> |
| interval_type& <b>flip</b>(interval_type& interval,<br> |
| |
| coordinate_type axis = 0)</font></td> |
| <td>Flips an object that models interval about the axis coordinate. |
| If no axis is provided the interval is flipped across the the origin.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| interval_type><br> |
| interval_type& <b>scale_up</b>(interval_type& interval, <br> |
| |
| unsigned_area_type factor)</font></td> |
| <td>Multiplies low and high ends of an object that models interval by |
| unsigned factor.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| interval_type><br> |
| interval_type& <b>scale_down</b>(interval_type& interval, <br> |
| |
| unsigned_area_type factor)</font></td> |
| <td>Divides low and high ends of an object that models interval by |
| unsigned factor.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| interval_type><br> |
| interval_type& <b>scale</b>(interval_type& interval,<br> |
| |
| double factor) </font></td> |
| <td>Multiplies low and high ends of an object that models interval by |
| floating point value.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| interval_type><br> |
| interval_type& <b>move</b>(interval_type& interval,<br> |
| |
| coordinate_difference displacement)</font></td> |
| <td>Adds displacement value to low and high ends of an object that |
| models interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| interval_type><br> |
| interval_type& <b>convolve</b>(interval_type& interval,<br> |
| |
| coordinate_type b)</font></td> |
| <td>Adds coordinate value to low and high ends of an object that models |
| interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| interval_type><br> |
| interval_type& <b>deconvolve</b>(interval_type& interval,<br> |
| |
| coordinate_type b)</font></td> |
| <td>Subtracts coordinate value from low and high ends of an object that |
| models interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>convolve</b>(T1& a, const T2& b)</font></td> |
| <td>Adds low end of b to low end of a and adds high end of b to high end |
| of a.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>deconvolve</b>(T1& a, const T2& b)</font></td> |
| <td>Subtracts low end of b from low end of a and subtracts high end of b |
| from high end of a. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>reflected_convolve</b>(T1& a, const T2& b)</font></td> |
| <td>Adds high end of b to low end of a and adds low end of b to high end |
| of a.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>reflected_deconvolve</b>(T1& a, const T2& b)</font></td> |
| <td>Subtracts high end of b from low end of a and subtracts low end of b |
| from high end of a.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| coordinate_difference <b>euclidean_distance</b>(const T&,<br> |
| |
| coordinate_type)</font></td> |
| <td>Returns the distance from an object that models interval to a |
| coordinate. Returns zero if the coordinate is equal to an end of |
| the interval or contained within the interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| bool <b>intersects</b>(const T1& interval, const T2& b, <br> |
| |
| bool consider_touch = true)</font></td> |
| <td>Returns true if two objects that model interval overlap. If |
| the consider_touch flag is true touching at the endpoints is considered |
| overlap.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| bool <b>boundaries_intersect</b>(const T1& interval, const T2& b, <br> |
| |
| bool consider_touch = true)</font></td> |
| <td>Returns true is two objects that model interval partially overlap |
| such that one end point of each is contained within the other. If |
| the consider_touch flag is true a coordinate is considered contained |
| even if it is equal to an end.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| bool <b>abuts</b>(const T1& a, const T2& b,<br> |
| direction_1d dir) |
| </font></td> |
| <td>Returns true if interval b abuts but down not overlap interval a on |
| the end of interval a specified by dir.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| bool <b>abuts</b>(const T1& a, const T2& b)</font></td> |
| <td>Returns true if interval b abuts but down not overlap interval a.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| bool <b>intersect</b>(T1& a, const T2& b,<br> |
| |
| bool consider_touch = true) </font></td> |
| <td>Sets interval a to the intersection of interval a and interval b and |
| return true. If the two intervals do not intersect interval a is |
| unchanged and the function returns false. If the flag |
| consider_touch is true intervals that abut are considered to intersect.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T& <b>generalized_intersect</b>(T1& a, const T2& b)</font></td> |
| <td>Same as intersect, but if they do not intersect set a to the |
| interval between a and b.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>bloat</b>(T& interval, coordinate_type)</font></td> |
| <td>Adds the coordinate value to high end of interval and subtracts it |
| from low end of interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>bloat</b>(T& interval, direction_1d, coordinate_type)</font></td> |
| <td>Adds the coordinate value to high end of interval or subtracts it |
| from low end of interval depending on the direction_1d.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>shrink</b>(T& interval, coordinate_type)</font></td> |
| <td>Subtracts the coordinate value from high end of interval and adds it |
| to low end of interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>shrink</b>(T& interval, direction_1d, coordinate_type)</font></td> |
| <td>Subtracts the coordinate value from high end of interval or adds it |
| to low end of interval depending on the direction_1d.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| bool <b>encompass</b>(T1& a, const T2& b)</font></td> |
| <td>Sets low of a to min of low of a and low of b and sets high of a to |
| max of high of a and high of b. Returns true if b was not |
| contained within a to begin with.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| bool <b>encompass</b>(T& a, coordinate_type)</font></td> |
| <td>Sets low of a to min of low of a and coordinate value and sets high |
| of a to max of high of a and coordinate value. Returns true if |
| coordinate value was not contained within a to begin with.</td> |
| </tr> |
| </table> |
| <h1>Interval Data</h1> |
| |
| <p> |
| <p>The library provides a model of interval concept declared |
| <font face="Courier New"> |
| template<typename T> interval_data </font>where T is the coordinate type.</p> |
| <p>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.</p> |
| <h2>Members</h2> |
| <table border="1" width="100%" id="table2"> |
| <tr> |
| <td width="586"><b><font face="Courier New">geometry_type</font></b></td> |
| <td><font face="Times New Roman">interval_concept</font></td> |
| </tr> |
| <tr> |
| <td width="586"><b><font face="Courier New">coordinate_type</font></b></td> |
| <td><font face="Times New Roman">T</font></td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"><b>interval_data</b>()</font></td> |
| <td><font face="Times New Roman">Default constructs the two coordinate |
| values of the interval.</font></td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"><b>interval_data</b>(T low, T |
| high)</font></td> |
| <td><font face="Times New Roman">Constructs an interval with two |
| coordinates.</font></td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"><b>interval_data</b>(const |
| interval_data& that)</font></td> |
| <td><font face="Times New Roman">Copy construct</font></td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">interval_data& <b>operator=</b>(const |
| interval_data& that)</font></td> |
| <td>Assignment operator.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T2><b> |
| <br> </b>interval_data& <b>operator=</b>(const T2& that) const</font></td> |
| <td>Assign from an object that is a model of interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T2><b> |
| <br> </b>bool<b> |
| operator==</b>(const T2& that) const</font></td> |
| <td>Compare equality to an object that is a model of interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T2><b> |
| <br> </b>bool<b> |
| operator!=</b>(const T2& that) const</font></td> |
| <td>Compare inequality to an object that is a model of interval.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T2><b> |
| <br> </b>bool<b> |
| operator<</b>(const T2& that) const</font></td> |
| <td>Compares low coordinates then high coordinates to break ties.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T2><b> |
| <br> </b>bool<b> |
| operator<=</b>(const T2& that) const</font></td> |
| <td>Compares low coordinates then high coordinates to break ties.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T2><b> |
| <br> </b>bool<b> |
| operator></b>(const T2& that) const</font></td> |
| <td>Compares low coordinates then high coordinates to break ties.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T2><b> |
| <br> </b>bool<b> |
| operator>=</b>(const T2& that) const</font></td> |
| <td>Compares low coordinates then high coordinates to break ties.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">T <b>get</b>(direction_1d dir) |
| const</font></td> |
| <td>Get the coordinate in the given direction.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">void <b>set</b>(direction_1d |
| dir, T value)</font></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> |
| <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"> |
| |
| |
| <table class="docinfo" rules="none" frame="void" id="table3"> |
| <colgroup> |
| <col class="docinfo-name"><col class="docinfo-content"> |
| </colgroup> |
| <tbody vAlign="top"> |
| <tr> |
| <th class="docinfo-name">Copyright:</th> |
| <td>Copyright © Intel Corporation 2008-2010.</td> |
| </tr> |
| <tr class="field"> |
| <th class="docinfo-name">License:</th> |
| <td class="field-body">Distributed under the Boost Software License, |
| Version 1.0. (See accompanying file <tt class="literal"> |
| <span class="pre">LICENSE_1_0.txt</span></tt> or copy at |
| <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt"> |
| http://www.boost.org/LICENSE_1_0.txt</a>)</td> |
| </tr> |
| </table> |
| |
| </html> |