projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
| 2 | <html><head> | |
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 | ||
| 9 | ||
| 10 | ||
| 11 | ||
| 12 | ||
| 13 | ||
| 14 | ||
| 15 | <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> | |
| 16 | <h1>Voronoi Basic Tutorial<br> | |
| 17 | </h1> | |
| 18 | ||
| 19 | <p>In this tutorial we will cover the basic usage of the Boost.Polygon | |
| 20 | Voronoi library that should be enough for the 95% of cases. Below we will | |
| 21 | discuss the following topics:<br> | |
| 22 | </p> | |
| 23 | ||
| 24 | <ul> | |
| 25 | ||
| 26 | <li>preparing input geometries<br> | |
| 27 | </li> | |
| 28 | <li>Voronoi diagram construction</li> | |
| 29 | ||
| 30 | <li>Voronoi graph traversal<br> | |
| 31 | </li> | |
| 32 | ||
| 33 | <li>associating the user data with the Voronoi primitives</li> | |
| 34 | <li>accessing input site inside the Voronoi cell</li> | |
| 35 | <li>Voronoi diagram rendering<br> | |
| 36 | </li> | |
| 37 | ||
| 38 | ||
| 39 | </ul> | |
| 40 | ||
| 41 | In the example that goes through this tutorial (<a href="../example/voronoi_basic_tutorial.cpp">voronoi_basic_tutorial.cpp</a>) | |
| 42 | we | |
| 43 | are going to construct the Voronoi diagram of a few points and | |
| 44 | segments. | |
| 45 | On the image below one may see the corresponding rendered Voronoi | |
| 46 | graph. The primary Voronoi edges | |
| 47 | are marked with | |
| 48 | the black color, non-primary with green, input geometries have blue | |
| 49 | color. We split each input segment onto three sites (segment | |
| 50 | itself and both endpoints), edges that go between the sites corresponding to the same segment are | |
| 51 | considered to be non-primary.<br> | |
| 52 | ||
| 53 | <br> | |
| 54 | ||
| 55 | <img style="border: 2px solid ; width: 300px; height: 300px;" alt="" src="images/voronoi4.png"><br> | |
| 56 | ||
| 57 | <br> | |
| 58 | ||
| 59 | And before you proceed don't forget to:<span style="font-family: Courier New,Courier,monospace;"><br> | |
| 60 | </span><span style="font-family: Courier New,Courier,monospace;"></span><br> | |
| 61 | <span style="font-family: Courier New,Courier,monospace;">#include "boost/polygon/voronoi.hpp"<br> | |
| 62 | using boost::polygon::voronoi_builder;<br> | |
| 63 | using boost::polygon::voronoi_diagram;<br> | |
| 64 | </span> | |
| 65 | ||
| 66 | <h2>Preparing Input Geometries</h2>Below is the example of how the user provided point and segment classes might look like:<br> | |
| 67 | <br><span style="font-family: Courier New,Courier,monospace;">struct Point {<br> int a;<br> | |
| 68 | int b;<br> | |
| 69 | Point (int x, int y) : a(x), b(y) {}<br> | |
| 70 | ||
| 71 | };</span><span style="font-family: Courier New,Courier,monospace;"><br> | |
| 72 | <br>struct Segment {</span><span style="font-family: Courier New,Courier,monospace;"></span><br> | |
| 73 | <span style="font-family: Courier New,Courier,monospace;"> | |
| 74 | Point p0;<br> | |
| 75 | Point p1;<br> | |
| 76 | Segment (int x1, int y1, int x2, int y2) : p0(x1, y1), p1(x2, y2) {}<br> | |
| 77 | </span><span style="font-family: Courier New,Courier,monospace;"></span> | |
| 78 | ||
| 79 | <span style="font-family: Courier New,Courier,monospace;">};<br> | |
| 80 | <br> | |
| 81 | </span>As we are going to use the default routines defined in the | |
| 82 | voronoi.hpp header to construct the Voronoi diagram, we are required to map | |
| 83 | our point and segment classes to the corresponding Boost.Polygon concepts:<br> | |
| 84 | <br> | |
| 85 | <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> | |
| 86 | 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> | |
| 87 | <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> | |
| 88 | 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> | |
| 89 | };</span><br> | |
| 90 | <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;"> | |
| 91 | <br> | |
| 92 | template <><br> | |
| 93 | </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> | |
| 94 | <br> | |
| 95 | </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;"> | |
| 96 | <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;"> | |
| 97 | <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> | |
| 98 | 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;"> | |
| 99 | </span> | |
| 100 | <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;"> | |
| 101 | <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> | |
| 102 | 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;"> | |
| 103 | <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> | |
| 104 | <br> | |
| 105 | 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> | |
| 106 | <br> | |
| 107 | So once we are done we can create the sample input:<br> | |
| 108 | ||
| 109 | <br> | |
| 110 | ||
| 111 | <span style="font-family: Courier New,Courier,monospace;">std::vector<Point> | |
| 112 | points;<br> | |
| 113 | points.push_back(Point(0, 0));<br> | |
| 114 | points.push_back(Point(1, 6));<br> | |
| 115 | std::vector<Segment> segments;<br> | |
| 116 | segments.push_back(Segment(-4, 5, 5, -1));<br> | |
| 117 | segments.push_back(Segment(3, -11, 13, -1));</span><span style="font-family: Courier New,Courier,monospace;"><br> | |
| 118 | </span> | |
| 119 | <h2>Construction of the Voronoi Diagram<br> | |
| 120 | </h2>At this point we are ready to construct the Voronoi diagram:<br> | |
| 121 | <span style="font-family: Courier New,Courier,monospace;"><br> | |
| 122 | </span><span style="font-family: Courier New,Courier,monospace;"> | |
| 123 | voronoi_diagram<double> vd;<br> | |
| 124 | construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &vd);</span><br> | |
| 125 | ||
| 126 | <h2>Traversing Voronoi Graph</h2> | |
| 127 | ||
| 128 | Voronoi graph traversal is the basic | |
| 129 | operation one would like to do once the Voronoi diagram is constructed. | |
| 130 | There are three ways to do that and we are going to cover all of them:<br> | |
| 131 | ||
| 132 | <ul> | |
| 133 | ||
| 134 | <li>simply iterating over the Voronoi edges (counts each edge twice):<br> | |
| 135 | <span style="font-family: Courier New,Courier,monospace;"><br> | |
| 136 | int iterate_primary_edges1(const voronoi_diagram<double> &vd) | |
| 137 | {<br> | |
| 138 | int result = 0;<br> | |
| 139 | for (voronoi_diagram<double>::const_edge_iterator it = | |
| 140 | vd.edges().begin();<br> | |
| 141 | it != vd.edges().end(); ++it) {<br> | |
| 142 | if (it->is_primary())<br> | |
| 143 | ++result;<br> | |
| 144 | }<br> | |
| 145 | return result;<br> | |
| 146 | }</span><br> | |
| 147 | <span style="font-family: Courier New,Courier,monospace;"> </span><br> | |
| 148 | </li> | |
| 149 | <li>iterating over the Voronoi cells and then traversing edges around | |
| 150 | each cell (counts each edge twice):<br> | |
| 151 | <br> | |
| 152 | <span style="font-family: Courier New,Courier,monospace;">int | |
| 153 | iterate_primary_edges2(const voronoi_diagram<double> &vd) {<br> | |
| 154 | int result = 0;<br> | |
| 155 | for (voronoi_diagram<double>::const_cell_iterator it = | |
| 156 | vd.cells().begin();<br> | |
| 157 | it != vd.cells().end(); ++it) {<br> | |
| 158 | const voronoi_diagram<double>::cell_type | |
| 159 | &cell = *it;<br> | |
| 160 | const voronoi_diagram<double>::edge_type *edge | |
| 161 | = cell.incident_edge();<br> | |
| 162 | // This is convenient way to iterate edges around | |
| 163 | Voronoi cell.<br> | |
| 164 | do {<br> | |
| 165 | if (edge->is_primary())<br> | |
| 166 | ++result;<br> | |
| 167 | edge = edge->next();<br> | |
| 168 | } while (edge != cell.incident_edge());<br> | |
| 169 | }<br> | |
| 170 | return result;<br> | |
| 171 | }</span><br> | |
| 172 | <br> | |
| 173 | </li> | |
| 174 | <li>iterating over the Voronoi | |
| 175 | vertices and then traversing edges around each vertex (the number of the | |
| 176 | iterations through each edge is equal to the number of finite endpoints | |
| 177 | of the edge):<span style="font-family: Courier New,Courier,monospace;"></span><br> | |
| 178 | <span style="font-family: Courier New,Courier,monospace;">int | |
| 179 | iterate_primary_edges3(const voronoi_diagram<double> &vd) {<br> | |
| 180 | int result = 0;<br> | |
| 181 | for (voronoi_diagram<double>::const_vertex_iterator it = | |
| 182 | vd.vertices().begin();<br> | |
| 183 | it != vd.vertices().end(); ++it) {<br> | |
| 184 | const voronoi_diagram<double>::vertex_type | |
| 185 | &vertex = *it;<br> | |
| 186 | const voronoi_diagram<double>::edge_type *edge | |
| 187 | = vertex.incident_edge();<br> | |
| 188 | // This is convenient way to iterate edges around | |
| 189 | Voronoi vertex.<br> | |
| 190 | do {<br> | |
| 191 | if (edge->is_primary())<br> | |
| 192 | ++result;<br> | |
| 193 | edge = edge->rot_next();<br> | |
| 194 | } while (edge != vertex.incident_edge());<br> | |
| 195 | }<br> | |
| 196 | return result;<br> | |
| 197 | }</span></li> | |
| 198 | </ul> | |
| 199 | ||
| 200 | This should give a very nice idea on how to do the Voronoi | |
| 201 | diagram traversal. Notice that while the output from the first two methods should | |
| 202 | be the same, it wouldn't for the third one. The reason is that in the | |
| 203 | last case we will iterate only once through the edges with a single | |
| 204 | finite endpoint and will skip all the edges with no finite endpoints.<br> | |
| 205 | ||
| 206 | <h2>Associating User Data with Voronoi Primitives</h2> | |
| 207 | ||
| 208 | A few simple cases of associating the user data with the Voronoi primitives are | |
| 209 | following:<br> | |
| 210 | ||
| 211 | <ul> | |
| 212 | ||
| 213 | <li>associating number of incident edges with each cell, vertex;</li> | |
| 214 | <li>associating color information with each edge;</li> | |
| 215 | <li>using DFS or BFS on the Voronoi graph requires to mark visited | |
| 216 | edges/vertices/cells.</li> | |
| 217 | </ul> | |
| 218 | ||
| 219 | We will consider the first example and will associate the total number | |
| 220 | of incident edges with each cell.<br> | |
| 221 | ||
| 222 | Note: Each Voronoi primitive contains mutable color member, | |
| 223 | that allows to use it for the graph algorithms or associate user data via array indices.<br> | |
| 224 | ||
| 225 | <br style="font-family: Courier New,Courier,monospace;"> | |
| 226 | ||
| 227 | <span style="font-family: Courier New,Courier,monospace;">// Using color member of the Voronoi primitives to store the average number<br> | |
| 228 | // of edges around each cell (including secondary edges).<br> | |
| 229 | {<br> | |
| 230 | printf("Number of edges (including secondary) around the Voronoi cells:\n");<br> | |
| 231 | for (voronoi_diagram<double>::const_edge_iterator it = vd.edges().begin();<br> | |
| 232 | it != vd.edges().end(); ++it) {<br> | |
| 233 | std::size_t cnt = it->cell()->color();<br> | |
| 234 | it->cell()->color(cnt + 1);<br> | |
| 235 | }<br> | |
| 236 | for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin();<br> | |
| 237 | it != vd.cells().end(); ++it) {<br> | |
| 238 | printf("%lu ", it->color());<br> | |
| 239 | }<br> | |
| 240 | printf("\n");<br> | |
| 241 | printf("\n");<br> | |
| 242 | }</span><span style="font-family: Courier New,Courier,monospace;"></span><br> | |
| 243 | ||
| 244 | <h2>Accessing Input Site inside the Voronoi Cell</h2> | |
| 245 | As explained in the <a href="voronoi_diagram.htm">Voronoi diagram</a> | |
| 246 | section, Voronoi cells don't contain coordinates of the input | |
| 247 | geometries directly. Instead they contains source index and source | |
| 248 | category that uniquely identify input site. The below routines | |
| 249 | traverses over the all Voronoi cells, fetches input geometry | |
| 250 | corresponding to the Voronoi cell and prints coordinates of the input | |
| 251 | site.<br> | |
| 252 | <br> | |
| 253 | <span style="font-family: Courier New,Courier,monospace;">unsigned int cell_index = 0;</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 254 | <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;"> | |
| 255 | <span style="font-family: Courier New,Courier,monospace;"> it != vd.cells().end(); ++it) {</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 256 | <span style="font-family: Courier New,Courier,monospace;"> if (it->contains_point()) {</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 257 | <span style="font-family: Courier New,Courier,monospace;"> std::size_t index = it->source_index();</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 258 | <span style="font-family: Courier New,Courier,monospace;"> Point p = points[index];</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 259 | <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;"> | |
| 260 | <span style="font-family: Courier New,Courier,monospace;"> cell_index, x(p), y(p));</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 261 | <span style="font-family: Courier New,Courier,monospace;"> } else {</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 262 | <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;"> | |
| 263 | <span style="font-family: Courier New,Courier,monospace;"> Point p0 = low(segments[index]);</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 264 | <span style="font-family: Courier New,Courier,monospace;"> Point p1 = high(segments[index]);</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 265 | <span style="font-family: Courier New,Courier,monospace;"> if (it->source_category() ==</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 266 | <span style="font-family: Courier New,Courier,monospace;"> boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT) {</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 267 | <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;"> | |
| 268 | <span style="font-family: Courier New,Courier,monospace;"> cell_index, x(p0), y(p0));</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 269 | <span style="font-family: Courier New,Courier,monospace;"> } else if (it->source_category() ==</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 270 | <span style="font-family: Courier New,Courier,monospace;"> | |
| 271 | boost::polygon::SOURCE_CATEGORY_SEGMENT_END_POINT) {</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 272 | <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;"> | |
| 273 | <span style="font-family: Courier New,Courier,monospace;"> cell_index, x(p0), y(p0));</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 274 | <span style="font-family: Courier New,Courier,monospace;"> } else {</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 275 | <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;"> | |
| 276 | <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;"> | |
| 277 | <span style="font-family: Courier New,Courier,monospace;"> }</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 278 | <span style="font-family: Courier New,Courier,monospace;"> }</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 279 | <span style="font-family: Courier New,Courier,monospace;"> ++cell_index;</span><br style="font-family: Courier New,Courier,monospace;"> | |
| 280 | }<br> | |
| 281 | <h2>Voronoi Diagram Rendering<br> | |
| 282 | </h2> | |
| 283 | ||
| 284 | ||
| 285 | There are two main issues that don't allow to strictly render the resulting | |
| 286 | Voronoi diagram using such rendering tools as OpenGL or DirectX. | |
| 287 | Those are:<br> | |
| 288 | ||
| 289 | <ul> | |
| 290 | ||
| 291 | <li>Some of the Voronoi edges are infinite, so should be clipped;</li> | |
| 292 | <li>Some of the Voronoi edge are parabolic arcs, so should be | |
| 293 | discretized.</li> | |
| 294 | </ul> | |
| 295 | ||
| 296 | Note: This would be the issues not only for rendering tools. | |
| 297 | Basically every task that requires diagram to be represented as a set | |
| 298 | of finite segments will fall into this category.<a href="../example/voronoi_visualizer.cpp"> voronoi_visualizer.cpp</a> | |
| 299 | contains a simple fully featured implementation of the Voronoi diagram | |
| 300 | renderer using the Qt libraries. It was used to generate all the .png | |
| 301 | drawings under the boost/libs/polygon/example directory.<span style="text-decoration: underline;"></span><span style="font-family: Courier New,Courier,monospace;"><br> | |
| 302 | </span> | |
| 303 | <h2>Summary<br> | |
| 304 | </h2> | |
| 305 | <span style="font-family: Courier New,Courier,monospace;"> | |
| 306 | </span>I hope the reader managed to get to this point and found the | |
| 307 | basic tutorial to be useful (in the end it's not so basic). Worth | |
| 308 | to notice that construction of the Voronoi diagram takes only two lines | |
| 309 | of code, everything else is about initializing input data structures, | |
| 310 | traversing Voronoi graph, associating data with the diagram primitives. In the | |
| 311 | default mode the Voronoi diagram operates with the signed int (32-bit) input | |
| 312 | coordinate type and double (64-bit) output coordinate type. In the <a href="voronoi_advanced_tutorial.htm">advanced Voronoi tutorial</a> we | |
| 313 | explain why this is enough for the 95% of cases and how to expand the | |
| 314 | algorithm coordinate types for the other 5%.<br> | |
| 315 | ||
| 316 | <span style="font-family: Courier New,Courier,monospace;"></span><br> | |
| 317 | ||
| 318 | <table class="docinfo" id="table1" frame="void" rules="none"> | |
| 319 | ||
| 320 | <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> | |
| 321 | <tbody valign="top"> | |
| 322 | <tr> | |
| 323 | <th class="docinfo-name">Copyright:</th> | |
| 324 |