123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336 |
- <!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 © 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>
|