[ceph.git] / ceph / src / boost / libs / polygon / doc / voronoi_main.htm

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>
  <meta http-equiv="Content-Language" content="en-us">
  <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Main</title>
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta http-equiv="content-type" content="text/html; charset=utf-8"></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" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </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><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>Voronoi Main Page </li>
        <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a></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" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
      </td>
      <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br>
      <h1>THE BOOST POLYGON VORONOI EXTENSIONS</h1>
      <img style="width: 900px; height: 300px;" alt="" src="images/voronoi3.png"><br>
The Voronoi extensions of the Boost Polygon library provide functionality to
construct a <a href="voronoi_diagram.htm">Voronoi diagram</a> of a set of points
and linear segments in 2D space with the following set of limitations:<br>
      <ul>
        <li>Coordinates of the input points and endpoints of the input segments should have integral type. The int32 data type is supported by the default implementation. Support for the other data types (e.g. int64) could be achieved through the configuration of the coordinate type traits (<a href="voronoi_advanced_tutorial.htm">Voronoi Advanced tutorial</a>).</li>
        <li>Input points and segments should not overlap except their endpoints. This means that input point should not lie inside the input segment and input segments should not intersect except their endpoints.</li>
      </ul>
While the first restriction is permanent (it
allows to give the exact warranties about the output precision and
algorithm execution flow),
the second one may be resolved using the Boost.Polygon <a href="gtl_segment_concept.htm">segment utils</a>.
The strong sides of the
library and the main benefits comparing to the other implementations are
discussed in the following paragraphs.<br>
<h2>Fully Functional with Segments</h2>
There are just a few implementations of the Voronoi diagram
construction
algorithm that can
handle input data sets that contain linear segments, even considering
the commercial
libraries.
Support of the
segments allows to discretize any input geometry (sampled
floating-point coordinates can be scaled and snapped to the integer
grid): circle, ellipse,
parabola. This functionality allows to compute
the medial axis transform of the arbitrary set of input geometries,
with direct applications in the computer vision
projects.
      <h2>Robustness and Efficiency</h2>
Robustness issues can be divided onto the two main categories: memory
management
issues and numeric stability issues. The implementation avoids the
first type of the issues using pure STL data structures, thus there is
no
presence of the new operator in the code. The second category of
the problems is
resolved using the multiprecision geometric
predicates.
Even for the commercial libraries, usage of such predicates
results in a vast performance slowdown. The library implementation
overcomes this by avoiding the multiprecision
computations in the 95% of the cases by
using the efficient, floating-point based predicates. Such predicates
don't
produce the correct result always, however the library embeds the
relative
error arithmetic apparatus to identify such situations and switch
to the
higher precision predicates when appropriate. As the result, the
implementation has a solid performance comparing to the other known
libraries (more details in the <a href="voronoi_benchmark.htm">benchmarks</a>).<br>
      <h2>Precision of the Output Structures </h2>
The implementation guaranties, that the relative error of the
coordinates of the output
geometries is at most 64 machine epsilons (6
bits of mantissa, for the IEEE-754 floating-point type), while on
average it's slightly lower. This means, that the precision of the
output
geometries can be increased simply by using a floating-point type with
the larger mantissa. The practical point of this statements is
explained in the following table:<br>
      <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td style="vertical-align: top;">Output Coordinate Type </td>
            <td style="vertical-align: top;">Output Coordinate Value </td>
            <td style="vertical-align: top;">Max Absolute Error </td>
            <td style="vertical-align: top;">Precise Value Range </td>
          </tr>
          <tr>
            <td style="vertical-align: top;">double (53 bit mantissa) </td>
            <td style="vertical-align: top;">1 </td>
            <td style="vertical-align: top;">2<sup>-53</sup> * 2<sup>6</sup>
= 2<sup>-47</sup></td>
Commit	Line	Data
7c673cae FG	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
	2	<html><head>
	3	<meta http-equiv="Content-Language" content="en-us">
	4	<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Main</title>
	5	<meta http-equiv="content-type" content="text/html; charset=utf-8">
	6	<meta http-equiv="content-type" content="text/html; charset=utf-8">
	7	<meta http-equiv="content-type" content="text/html; charset=utf-8">
	8	<meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
	9	<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
	10	<tbody>
	11	<tr>
	12	<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
	13	<div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
	14	<div style="margin: 5px;">
	15	<h3 class="navbar">Contents</h3>
	16	<ul>
	17	<li><a href="index.htm">Boost.Polygon Main Page</a></li>
	18	<li><a href="gtl_design_overview.htm">Design Overview</a></li>
	19	<li><a href="gtl_isotropy.htm">Isotropy</a></li>
	20	<li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
	21	<li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
	22	<li><a href="gtl_point_concept.htm">Point Concept</a></li>
	23	<li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
	24	<li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
	25	<li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
	26	<li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90 With Holes Concept</a></li>
	27	<li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
	28	<li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45 With Holes Concept</a></li>
	29	<li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
	30	<li><a href="gtl_polygon_with_holes_concept.htm">Polygon With Holes Concept</a></li>
	31	<li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set Concept</a></li>
	32	<li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set Concept</a></li>
	33	<li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
	34	<li><a href="gtl_connectivity_extraction_90.htm">Connectivity Extraction 90</a></li>
	35	<li><a href="gtl_connectivity_extraction_45.htm">Connectivity Extraction 45</a></li>
	36	<li><a href="gtl_connectivity_extraction.htm">Connectivity Extraction</a></li>
	37	<li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
	38	<li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
	39	<li><a href="gtl_property_merge.htm">Property Merge</a></li>
	40	<li>Voronoi Main Page </li>
	41	<li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a></li>
	42	<li><a href="voronoi_builder.htm">Voronoi Builder</a> </li>
	43	<li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
	44	</ul>
	45	<h3 class="navbar">Other Resources</h3>
	46	<ul>
	47	<li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
	48	<li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009 Presentation</a></li>
	49	<li><a href="analysis.htm">Performance Analysis</a></li>
	50	<li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
	51	<li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
	52	<li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
	53	<li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced Tutorial</a></li>
	54	</ul>
	55	</div>
	56	<h3 class="navbar">Polygon Sponsor</h3>
	57	<div style="padding: 5px;" align="center"> <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
	58	</td>
	59	<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br>
	60	<h1>THE BOOST POLYGON VORONOI EXTENSIONS</h1>
	61	<img style="width: 900px; height: 300px;" alt="" src="images/voronoi3.png"><br>
	62	The Voronoi extensions of the Boost Polygon library provide functionality to
	63	construct a <a href="voronoi_diagram.htm">Voronoi diagram</a> of a set of points
	64	and linear segments in 2D space with the following set of limitations:<br>
65	<ul>
66	<li>Coordinates of the input points and endpoints of the input segments should have integral type. The int32 data type is supported by the default implementation. Support for the other data types (e.g. int64) could be achieved through the configuration of the coordinate type traits (<a href="voronoi_advanced_tutorial.htm">Voronoi Advanced tutorial</a>).</li>
67	<li>Input points and segments should not overlap except their endpoints. This means that input point should not lie inside the input segment and input segments should not intersect except their endpoints.</li>
68	</ul>
69	While the first restriction is permanent (it
70	allows to give the exact warranties about the output precision and
71	algorithm execution flow),
72	the second one may be resolved using the Boost.Polygon <a href="gtl_segment_concept.htm">segment utils</a>.
73	The strong sides of the
74	library and the main benefits comparing to the other implementations are
75	discussed in the following paragraphs.<br>
76	<h2>Fully Functional with Segments</h2>
77	There are just a few implementations of the Voronoi diagram
78	construction
79	algorithm that can
80	handle input data sets that contain linear segments, even considering
81	the commercial
82	libraries.
83	Support of the
84	segments allows to discretize any input geometry (sampled
85	floating-point coordinates can be scaled and snapped to the integer
86	grid): circle, ellipse,
87	parabola. This functionality allows to compute
88	the medial axis transform of the arbitrary set of input geometries,
89	with direct applications in the computer vision
90	projects.
91	<h2>Robustness and Efficiency</h2>
92	Robustness issues can be divided onto the two main categories: memory
93	management
94	issues and numeric stability issues. The implementation avoids the
95	first type of the issues using pure STL data structures, thus there is
96	no
97	presence of the new operator in the code. The second category of
98	the problems is
99	resolved using the multiprecision geometric
100	predicates.
101	Even for the commercial libraries, usage of such predicates
102	results in a vast performance slowdown. The library implementation
103	overcomes this by avoiding the multiprecision
104	computations in the 95% of the cases by
105	using the efficient, floating-point based predicates. Such predicates
106	don't
107	produce the correct result always, however the library embeds the
108	relative
109	error arithmetic apparatus to identify such situations and switch
110	to the
111	higher precision predicates when appropriate. As the result, the
112	implementation has a solid performance comparing to the other known
113	libraries (more details in the <a href="voronoi_benchmark.htm">benchmarks</a>).<br>
114	<h2>Precision of the Output Structures </h2>
115	The implementation guaranties, that the relative error of the
116	coordinates of the output
117	geometries is at most 64 machine epsilons (6
118	bits of mantissa, for the IEEE-754 floating-point type), while on
119	average it's slightly lower. This means, that the precision of the
120	output
121	geometries can be increased simply by using a floating-point type with
122	the larger mantissa. The practical point of this statements is
123	explained in the following table:<br>
124	<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
125	<tbody>
126	<tr>
127	<td style="vertical-align: top;">Output Coordinate Type </td>
128	<td style="vertical-align: top;">Output Coordinate Value </td>
129	<td style="vertical-align: top;">Max Absolute Error </td>
130	<td style="vertical-align: top;">Precise Value Range </td>
131	</tr>
132	<tr>
133	<td style="vertical-align: top;">double (53 bit mantissa) </td>
134	<td style="vertical-align: top;">1 </td>
135	<td style="vertical-align: top;">2<sup>-53</sup> * 2<sup>6</sup>
136	= 2<sup>-47</sup></td>
137