123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187 |
- <!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"
- 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" lang="en">
- <head>
- <!--
- Copyright 2009-2010 Intel Corporation
- license banner
- -->
- <title>Boost Polygon Library: Coordinate Concept</title>
- <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" />
- <!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> -->
- </head>
- <body>
- <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
- src="images/boost.png" border="0" height="86" width="277" /><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>Coordinate Concept</li>
- <li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
- <li><a href="gtl_point_concept.htm">Point Concept</a></li>
- <li><a href="gtl_segment_concept.htm">Segment 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>
- <li><a href="voronoi_main.htm">Voronoi Main Page<br />
- </a></li>
- <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br />
- </li>
- <li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
- <li><a href="voronoi_diagram.htm">Voronoi Diagram</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>
- <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
- <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
- Tutorial</a></li>
- </ul>
- </div>
- <h3 class="navbar">Polygon Sponsor</h3>
- <div style="padding: 5px;" align="center"> <img
- src="images/intlogo.gif" border="0" height="51" width="127" /><a
- title="www.adobe.com home page" href="http://www.adobe.com/"
- tabindex="2" style="border: medium none ;"> </a> </div>
- </td>
- <td
- style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
- valign="top" width="100%">
- <!-- End Header --><br />
- <p>
- </p>
- <h1>Coordinate Concept</h1>
- <p> The coordinate concept tag is <font face="Courier New">
- coordinate_concept</font></p>
- <p> 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 CCoordinate is registered as a model
- of coordinate concept.</p>
- <p> <font face="Courier New">template <><br />
- struct geometry_concept<CCoordinate> { typedef coordinate_concept
- type; };</font></p>
- <p> The coordinate type is expected to be integral and built-in
- numerical data types such as float and int already have concept type
- traits specializations in the library. In the coordinate traits
- are type definitions for related types are provided to allow the
- library to choose the best type to cast to under various
- circumstances. The definition of coordinate_traits and its
- specialization for int are shown below.</p>
- <p> <font face="Courier New">template <typename T><br />
- struct coordinate_traits {};<br />
- <br />
- template <><br />
- struct coordinate_traits<int> {<br />
- typedef int coordinate_type;<br />
- typedef long double area_type;<br />
- typedef long long manhattan_area_type;<br />
- typedef unsigned long long unsigned_area_type;<br />
- typedef long long coordinate_difference;<br />
- typedef long double coordinate_distance;<br />
- };</font></p>
- <p> By making use of the coordinate traits of int the library is
- able to avoid overflow and handle the normal issues encountered when
- programming integer geometry. For the out of the ordinary issues
- there is a special meta-function that provides the library with a
- numerical type suitable for exact numerical calculations. It
- defaults to the highest precision data type available in most
- compilers, long double, but can be overridden by specializing for a
- particular coordinate type. Use of gmp multi-precision rational
- or similar data type is recommended for numerically robust calculations
- in the general polygon algorithms.</p>
- <p> <font face="Courier New">template <typename T><br />
- struct high_precision_type {<br />
- typedef long double type;<br />
- };</font></p>
- <p> There is only one generic function on coordinate concepts,
- Euclidean distance.</p>
- <p> <font face="Courier New">template <typename
- coordinate_type_1, typename coordinate_type_2><br />
- coordinate_difference euclidean_distance(coordinate_type_1,
- coordinate_type_2)</font></p>
- <p> This function returns the absolution value of the difference
- between the two coordinates.</p>
- <p> Note: older versions of the stl define a fully generic
- distance(T, T) function for computing the difference between two
- iterators. We were forced to name our distance function
- euclidean_distance to avoid name collision.</p>
- <p> The
- <a
- href="http://www.mentor.com/products/esl/high_level_synthesis/ac_datatypes">
- Algorithmic C</a> ac_int<128> is an example of a user defined
- coordinate data type that satisfies the coordinate concept. In
- general a data type should define std::numeric_limits and be
- integer-like. Floating point coordinate types are not supported
- by all the algorithms and generally not suitable for use with the
- library at present.</p>
- </td>
- </tr>
- <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" id="table1" frame="void" rules="none">
- <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>
- </tbody>
- </table>
- </td>
- </tr>
- </tbody>
- </table>
- </body>
- </html>
|