336 lines
31 KiB
HTML
336 lines
31 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
||
<html><head>
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Basic Tutorial</title><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
|
||
<h1>Voronoi Basic Tutorial<br>
|
||
</h1>
|
||
|
||
<p>In this tutorial we will cover the basic usage of the Boost.Polygon
|
||
Voronoi library that should be enough for the 95% of cases. Below we will
|
||
discuss the following topics:<br>
|
||
</p>
|
||
|
||
<ul>
|
||
|
||
<li>preparing input geometries<br>
|
||
</li>
|
||
<li>Voronoi diagram construction</li>
|
||
|
||
<li>Voronoi graph traversal<br>
|
||
</li>
|
||
|
||
<li>associating the user data with the Voronoi primitives</li>
|
||
<li>accessing input site inside the Voronoi cell</li>
|
||
<li>Voronoi diagram rendering<br>
|
||
</li>
|
||
|
||
|
||
</ul>
|
||
|
||
In the example that goes through this tutorial (<a href="../example/voronoi_basic_tutorial.cpp">voronoi_basic_tutorial.cpp</a>)
|
||
we
|
||
are going to construct the Voronoi diagram of a few points and
|
||
segments.
|
||
On the image below one may see the corresponding rendered Voronoi
|
||
graph. The primary Voronoi edges
|
||
are marked with
|
||
the black color, non-primary with green, input geometries have blue
|
||
color. We split each input segment onto three sites (segment
|
||
itself and both endpoints), edges that go between the sites corresponding to the same segment are
|
||
considered to be non-primary.<br>
|
||
|
||
<br>
|
||
|
||
<img style="border: 2px solid ; width: 300px; height: 300px;" alt="" src="images/voronoi4.png"><br>
|
||
|
||
<br>
|
||
|
||
And before you proceed don't forget to:<span style="font-family: Courier New,Courier,monospace;"><br>
|
||
</span><span style="font-family: Courier New,Courier,monospace;"></span><br>
|
||
<span style="font-family: Courier New,Courier,monospace;">#include "boost/polygon/voronoi.hpp"<br>
|
||
using boost::polygon::voronoi_builder;<br>
|
||
using boost::polygon::voronoi_diagram;<br>
|
||
</span>
|
||
|
||
<h2>Preparing Input Geometries</h2>Below is the example of how the user provided point and segment classes might look like:<br>
|
||
<br><span style="font-family: Courier New,Courier,monospace;">struct Point {<br> int a;<br>
|
||
int b;<br>
|
||
Point (int x, int y) : a(x), b(y) {}<br>
|
||
|
||
};</span><span style="font-family: Courier New,Courier,monospace;"><br>
|
||
<br>struct Segment {</span><span style="font-family: Courier New,Courier,monospace;"></span><br>
|
||
<span style="font-family: Courier New,Courier,monospace;">
|
||
Point p0;<br>
|
||
Point p1;<br>
|
||
Segment (int x1, int y1, int x2, int y2) : p0(x1, y1), p1(x2, y2) {}<br>
|
||
</span><span style="font-family: Courier New,Courier,monospace;"></span>
|
||
|
||
<span style="font-family: Courier New,Courier,monospace;">};<br>
|
||
<br>
|
||
</span>As we are going to use the default routines defined in the
|
||
voronoi.hpp header to construct the Voronoi diagram, we are required to map
|
||
our point and segment classes to the corresponding Boost.Polygon concepts:<br>
|
||
<br>
|
||
<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">template <></span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"><br>
|
||
struct geometry_concept<Point> { typedef point_concept type; };</span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;"><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"></span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> <span class="Apple-converted-space"></span></span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;"><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">template <></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;"><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">struct point_traits<</span><span style="font-family: Courier New,Courier,monospace;">Point</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">> {</span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;"><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> typedef int coordinate_type;</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"><br>
|
||
<span class="Apple-converted-space"> </span></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;"><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> static inline coordinate_type get(const </span><span style="font-family: Courier New,Courier,monospace;">Point</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">& point,<span class="Apple-converted-space"> </span></span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">orientation_2d orient) {<br>
|
||
return </span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">(orient == HORIZONTAL) ? point.a : point.b;</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;"><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> }<br>
|
||
};</span><br>
|
||
<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">
|
||
<br>
|
||
template <><br>
|
||
</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">struct geometry_concept<Segment> { typedef segment_concept type; };<br>
|
||
<br>
|
||
</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">template <></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;">
|
||
<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">struct point_traits<</span><span style="font-family: Courier New,Courier,monospace;">Segment</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">> {</span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;">
|
||
<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> typedef int coordinate_type;<br>
|
||
typedef Point point_type;<br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;">
|
||
</span>
|
||
<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> <span class="Apple-converted-space"> </span></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;">
|
||
<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> static inline coordinate_type get(const </span><span style="font-family: Courier New,Courier,monospace;">Segment</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">& segment,<span class="Apple-converted-space"> direction_1d dir</span></span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">) {<br>
|
||
return </span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">dir.to_int() ? segment.p1() : segment.p0();</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;">
|
||
<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> }<br>};</span><br>
|
||
<br>
|
||
It's also possible to use the native Boost.Polygon types as <a href="../../../boost/polygon/point_data.hpp">point_data</a> and <a href="../../../boost/polygon/segment_data.hpp">segment_data</a>, that won't require the above mapping.<br>
|
||
<br>
|
||
So once we are done we can create the sample input:<br>
|
||
|
||
<br>
|
||
|
||
<span style="font-family: Courier New,Courier,monospace;">std::vector<Point>
|
||
points;<br>
|
||
points.push_back(Point(0, 0));<br>
|
||
points.push_back(Point(1, 6));<br>
|
||
std::vector<Segment> segments;<br>
|
||
segments.push_back(Segment(-4, 5, 5, -1));<br>
|
||
segments.push_back(Segment(3, -11, 13, -1));</span><span style="font-family: Courier New,Courier,monospace;"><br>
|
||
</span>
|
||
<h2>Construction of the Voronoi Diagram<br>
|
||
</h2>At this point we are ready to construct the Voronoi diagram:<br>
|
||
<span style="font-family: Courier New,Courier,monospace;"><br>
|
||
</span><span style="font-family: Courier New,Courier,monospace;">
|
||
voronoi_diagram<double> vd;<br>
|
||
construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &vd);</span><br>
|
||
|
||
<h2>Traversing Voronoi Graph</h2>
|
||
|
||
Voronoi graph traversal is the basic
|
||
operation one would like to do once the Voronoi diagram is constructed.
|
||
There are three ways to do that and we are going to cover all of them:<br>
|
||
|
||
<ul>
|
||
|
||
<li>simply iterating over the Voronoi edges (counts each edge twice):<br>
|
||
<span style="font-family: Courier New,Courier,monospace;"><br>
|
||
int iterate_primary_edges1(const voronoi_diagram<double> &vd)
|
||
{<br>
|
||
int result = 0;<br>
|
||
for (voronoi_diagram<double>::const_edge_iterator it =
|
||
vd.edges().begin();<br>
|
||
it != vd.edges().end(); ++it) {<br>
|
||
if (it->is_primary())<br>
|
||
++result;<br>
|
||
}<br>
|
||
return result;<br>
|
||
}</span><br>
|
||
<span style="font-family: Courier New,Courier,monospace;"> </span><br>
|
||
</li>
|
||
<li>iterating over the Voronoi cells and then traversing edges around
|
||
each cell (counts each edge twice):<br>
|
||
<br>
|
||
<span style="font-family: Courier New,Courier,monospace;">int
|
||
iterate_primary_edges2(const voronoi_diagram<double> &vd) {<br>
|
||
int result = 0;<br>
|
||
for (voronoi_diagram<double>::const_cell_iterator it =
|
||
vd.cells().begin();<br>
|
||
it != vd.cells().end(); ++it) {<br>
|
||
const voronoi_diagram<double>::cell_type
|
||
&cell = *it;<br>
|
||
const voronoi_diagram<double>::edge_type *edge
|
||
= cell.incident_edge();<br>
|
||
// This is convenient way to iterate edges around
|
||
Voronoi cell.<br>
|
||
do {<br>
|
||
if (edge->is_primary())<br>
|
||
++result;<br>
|
||
edge = edge->next();<br>
|
||
} while (edge != cell.incident_edge());<br>
|
||
}<br>
|
||
return result;<br>
|
||
}</span><br>
|
||
<br>
|
||
</li>
|
||
<li>iterating over the Voronoi
|
||
vertices and then traversing edges around each vertex (the number of the
|
||
iterations through each edge is equal to the number of finite endpoints
|
||
of the edge):<span style="font-family: Courier New,Courier,monospace;"></span><br>
|
||
<span style="font-family: Courier New,Courier,monospace;">int
|
||
iterate_primary_edges3(const voronoi_diagram<double> &vd) {<br>
|
||
int result = 0;<br>
|
||
for (voronoi_diagram<double>::const_vertex_iterator it =
|
||
vd.vertices().begin();<br>
|
||
it != vd.vertices().end(); ++it) {<br>
|
||
const voronoi_diagram<double>::vertex_type
|
||
&vertex = *it;<br>
|
||
const voronoi_diagram<double>::edge_type *edge
|
||
= vertex.incident_edge();<br>
|
||
// This is convenient way to iterate edges around
|
||
Voronoi vertex.<br>
|
||
do {<br>
|
||
if (edge->is_primary())<br>
|
||
++result;<br>
|
||
edge = edge->rot_next();<br>
|
||
} while (edge != vertex.incident_edge());<br>
|
||
}<br>
|
||
return result;<br>
|
||
}</span></li>
|
||
</ul>
|
||
|
||
This should give a very nice idea on how to do the Voronoi
|
||
diagram traversal. Notice that while the output from the first two methods should
|
||
be the same, it wouldn't for the third one. The reason is that in the
|
||
last case we will iterate only once through the edges with a single
|
||
finite endpoint and will skip all the edges with no finite endpoints.<br>
|
||
|
||
<h2>Associating User Data with Voronoi Primitives</h2>
|
||
|
||
A few simple cases of associating the user data with the Voronoi primitives are
|
||
following:<br>
|
||
|
||
<ul>
|
||
|
||
<li>associating number of incident edges with each cell, vertex;</li>
|
||
<li>associating color information with each edge;</li>
|
||
<li>using DFS or BFS on the Voronoi graph requires to mark visited
|
||
edges/vertices/cells.</li>
|
||
</ul>
|
||
|
||
We will consider the first example and will associate the total number
|
||
of incident edges with each cell.<br>
|
||
|
||
Note: Each Voronoi primitive contains mutable color member,
|
||
that allows to use it for the graph algorithms or associate user data via array indices.<br>
|
||
|
||
<br style="font-family: Courier New,Courier,monospace;">
|
||
|
||
<span style="font-family: Courier New,Courier,monospace;">// Using color member of the Voronoi primitives to store the average number<br>
|
||
// of edges around each cell (including secondary edges).<br>
|
||
{<br>
|
||
printf("Number of edges (including secondary) around the Voronoi cells:\n");<br>
|
||
for (voronoi_diagram<double>::const_edge_iterator it = vd.edges().begin();<br>
|
||
it != vd.edges().end(); ++it) {<br>
|
||
std::size_t cnt = it->cell()->color();<br>
|
||
it->cell()->color(cnt + 1);<br>
|
||
}<br>
|
||
for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin();<br>
|
||
it != vd.cells().end(); ++it) {<br>
|
||
printf("%lu ", it->color());<br>
|
||
}<br>
|
||
printf("\n");<br>
|
||
printf("\n");<br>
|
||
}</span><span style="font-family: Courier New,Courier,monospace;"></span><br>
|
||
|
||
<h2>Accessing Input Site inside the Voronoi Cell</h2>
|
||
As explained in the <a href="voronoi_diagram.htm">Voronoi diagram</a>
|
||
section, Voronoi cells don't contain coordinates of the input
|
||
geometries directly. Instead they contains source index and source
|
||
category that uniquely identify input site. The below routines
|
||
traverses over the all Voronoi cells, fetches input geometry
|
||
corresponding to the Voronoi cell and prints coordinates of the input
|
||
site.<br>
|
||
<br>
|
||
<span style="font-family: Courier New,Courier,monospace;">unsigned int cell_index = 0;</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;">for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin();</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> it != vd.cells().end(); ++it) {</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> if (it->contains_point()) {</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> std::size_t index = it->source_index();</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> Point p = points[index];</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> printf("Cell #%ud contains a point: (%d, %d).\n",</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> cell_index, x(p), y(p));</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> } else {</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> std::size_t index = it->source_index() - points.size();</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> Point p0 = low(segments[index]);</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> Point p1 = high(segments[index]);</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> if (it->source_category() ==</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT) {</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> printf("Cell #%ud contains segment start point: (%d, %d).\n",</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> cell_index, x(p0), y(p0));</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> } else if (it->source_category() ==</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;">
|
||
boost::polygon::SOURCE_CATEGORY_SEGMENT_END_POINT) {</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> printf("Cell #%ud contains segment end point: (%d, %d).\n",</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> cell_index, x(p0), y(p0));</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> } else {</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> printf("Cell #%ud contains a segment: ((%d, %d), (%d, %d)). \n",</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> cell_index, x(p0), y(p0), x(p1), y(p1));</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> }</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> }</span><br style="font-family: Courier New,Courier,monospace;">
|
||
<span style="font-family: Courier New,Courier,monospace;"> ++cell_index;</span><br style="font-family: Courier New,Courier,monospace;">
|
||
}<br>
|
||
<h2>Voronoi Diagram Rendering<br>
|
||
</h2>
|
||
|
||
|
||
There are two main issues that don't allow to strictly render the resulting
|
||
Voronoi diagram using such rendering tools as OpenGL or DirectX.
|
||
Those are:<br>
|
||
|
||
<ul>
|
||
|
||
<li>Some of the Voronoi edges are infinite, so should be clipped;</li>
|
||
<li>Some of the Voronoi edge are parabolic arcs, so should be
|
||
discretized.</li>
|
||
</ul>
|
||
|
||
Note: This would be the issues not only for rendering tools.
|
||
Basically every task that requires diagram to be represented as a set
|
||
of finite segments will fall into this category.<a href="../example/voronoi_visualizer.cpp"> voronoi_visualizer.cpp</a>
|
||
contains a simple fully featured implementation of the Voronoi diagram
|
||
renderer using the Qt libraries. It was used to generate all the .png
|
||
drawings under the boost/libs/polygon/example directory.<span style="text-decoration: underline;"></span><span style="font-family: Courier New,Courier,monospace;"><br>
|
||
</span>
|
||
<h2>Summary<br>
|
||
</h2>
|
||
<span style="font-family: Courier New,Courier,monospace;">
|
||
</span>I hope the reader managed to get to this point and found the
|
||
basic tutorial to be useful (in the end it's not so basic). Worth
|
||
to notice that construction of the Voronoi diagram takes only two lines
|
||
of code, everything else is about initializing input data structures,
|
||
traversing Voronoi graph, associating data with the diagram primitives. In the
|
||
default mode the Voronoi diagram operates with the signed int (32-bit) input
|
||
coordinate type and double (64-bit) output coordinate type. In the <a href="voronoi_advanced_tutorial.htm">advanced Voronoi tutorial</a> we
|
||
explain why this is enough for the 95% of cases and how to expand the
|
||
algorithm coordinate types for the other 5%.<br>
|
||
|
||
<span style="font-family: Courier New,Courier,monospace;"></span><br>
|
||
|
||
<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> Andrii Sydorchuk 2010-2012.</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>
|
||
|
||
|
||
</body></html> |