188 lines
8.7 KiB
HTML
188 lines
8.7 KiB
HTML
<!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 <20> 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>
|