1 // Boost.Polygon library voronoi_visualizer.cpp file
2
3 // Copyright Andrii Sydorchuk 2010-2012.
4 // Distributed under the Boost Software License, Version 1.0.
5 // (See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7
8 // See http://www.boost.org for updates, documentation, and revision history.
9
10 #include <iostream>
11 #include <vector>
12
13 #include <QtOpenGL/QGLWidget>
14 #include <QtGui/QtGui>
15
16 #include <boost/polygon/polygon.hpp>
17 #include <boost/polygon/voronoi.hpp>
18 using namespace boost::polygon;
19
20 #include "voronoi_visual_utils.hpp"
21
22 class GLWidget : public QGLWidget {
23 Q_OBJECT
24
25 public:
GLWidget(QMainWindow * parent=NULL)26 explicit GLWidget(QMainWindow* parent = NULL) :
27 QGLWidget(QGLFormat(QGL::SampleBuffers), parent),
28 primary_edges_only_(false),
29 internal_edges_only_(false) {
30 startTimer(40);
31 }
32
sizeHint() const33 QSize sizeHint() const {
34 return QSize(600, 600);
35 }
36
build(const QString & file_path)37 void build(const QString& file_path) {
38 // Clear all containers.
39 clear();
40
41 // Read data.
42 read_data(file_path);
43
44 // No data, don't proceed.
45 if (!brect_initialized_) {
46 return;
47 }
48
49 // Construct bounding rectangle.
50 construct_brect();
51
52 // Construct voronoi diagram.
53 construct_voronoi(
54 point_data_.begin(), point_data_.end(),
55 segment_data_.begin(), segment_data_.end(),
56 &vd_);
57
58 // Color exterior edges.
59 for (const_edge_iterator it = vd_.edges().begin();
60 it != vd_.edges().end(); ++it) {
61 if (!it->is_finite()) {
62 color_exterior(&(*it));
63 }
64 }
65
66 // Update view port.
67 update_view_port();
68 }
69
show_primary_edges_only()70 void show_primary_edges_only() {
71 primary_edges_only_ ^= true;
72 }
73
show_internal_edges_only()74 void show_internal_edges_only() {
75 internal_edges_only_ ^= true;
76 }
77
78 protected:
initializeGL()79 void initializeGL() {
80 glHint(GL_POINT_SMOOTH_HINT, GL_NICEST);
81 glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
82 glEnable(GL_BLEND);
83 glEnable(GL_POINT_SMOOTH);
84 }
85
paintGL()86 void paintGL() {
87 qglClearColor(QColor::fromRgb(255, 255, 255));
88 glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
89
90 draw_points();
91 draw_segments();
92 draw_vertices();
93 draw_edges();
94 }
95
resizeGL(int width,int height)96 void resizeGL(int width, int height) {
97 int side = qMin(width, height);
98 glViewport((width - side) / 2, (height - side) / 2, side, side);
99 }
100
timerEvent(QTimerEvent * e)101 void timerEvent(QTimerEvent* e) {
102 update();
103 }
104
105 private:
106 typedef double coordinate_type;
107 typedef point_data<coordinate_type> point_type;
108 typedef segment_data<coordinate_type> segment_type;
109 typedef rectangle_data<coordinate_type> rect_type;
110 typedef voronoi_builder<int> VB;
111 typedef voronoi_diagram<coordinate_type> VD;
112 typedef VD::cell_type cell_type;
113 typedef VD::cell_type::source_index_type source_index_type;
114 typedef VD::cell_type::source_category_type source_category_type;
115 typedef VD::edge_type edge_type;
116 typedef VD::cell_container_type cell_container_type;
117 typedef VD::cell_container_type vertex_container_type;
118 typedef VD::edge_container_type edge_container_type;
119 typedef VD::const_cell_iterator const_cell_iterator;
120 typedef VD::const_vertex_iterator const_vertex_iterator;
121 typedef VD::const_edge_iterator const_edge_iterator;
122
123 static const std::size_t EXTERNAL_COLOR = 1;
124
clear()125 void clear() {
126 brect_initialized_ = false;
127 point_data_.clear();
128 segment_data_.clear();
129 vd_.clear();
130 }
131
read_data(const QString & file_path)132 void read_data(const QString& file_path) {
133 QFile data(file_path);
134 if (!data.open(QFile::ReadOnly)) {
135 QMessageBox::warning(
136 this, tr("Voronoi Visualizer"),
137 tr("Disable to open file ") + file_path);
138 }
139 QTextStream in_stream(&data);
140 std::size_t num_points, num_segments;
141 int x1, y1, x2, y2;
142 in_stream >> num_points;
143 for (std::size_t i = 0; i < num_points; ++i) {
144 in_stream >> x1 >> y1;
145 point_type p(x1, y1);
146 update_brect(p);
147 point_data_.push_back(p);
148 }
149 in_stream >> num_segments;
150 for (std::size_t i = 0; i < num_segments; ++i) {
151 in_stream >> x1 >> y1 >> x2 >> y2;
152 point_type lp(x1, y1);
153 point_type hp(x2, y2);
154 update_brect(lp);
155 update_brect(hp);
156 segment_data_.push_back(segment_type(lp, hp));
157 }
158 in_stream.flush();
159 }
160
update_brect(const point_type & point)161 void update_brect(const point_type& point) {
162 if (brect_initialized_) {
163 encompass(brect_, point);
164 } else {
165 set_points(brect_, point, point);
166 brect_initialized_ = true;
167 }
168 }
169
construct_brect()170 void construct_brect() {
171 double side = (std::max)(xh(brect_) - xl(brect_), yh(brect_) - yl(brect_));
172 center(shift_, brect_);
173 set_points(brect_, shift_, shift_);
174 bloat(brect_, side * 1.2);
175 }
176
color_exterior(const VD::edge_type * edge)177 void color_exterior(const VD::edge_type* edge) {
178 if (edge->color() == EXTERNAL_COLOR) {
179 return;
180 }
181 edge->color(EXTERNAL_COLOR);
182 edge->twin()->color(EXTERNAL_COLOR);
183 const VD::vertex_type* v = edge->vertex1();
184 if (v == NULL || !edge->is_primary()) {
185 return;
186 }
187 v->color(EXTERNAL_COLOR);
188 const VD::edge_type* e = v->incident_edge();
189 do {
190 color_exterior(e);
191 e = e->rot_next();
192 } while (e != v->incident_edge());
193 }
194
update_view_port()195 void update_view_port() {
196 glMatrixMode(GL_PROJECTION);
197 glLoadIdentity();
198 rect_type view_rect = brect_;
199 deconvolve(view_rect, shift_);
200 glOrtho(xl(view_rect), xh(view_rect),
201 yl(view_rect), yh(view_rect),
202 -1.0, 1.0);
203 glMatrixMode(GL_MODELVIEW);
204 }
205
draw_points()206 void draw_points() {
207 // Draw input points and endpoints of the input segments.
208 glColor3f(0.0f, 0.5f, 1.0f);
209 glPointSize(9);
210 glBegin(GL_POINTS);
211 for (std::size_t i = 0; i < point_data_.size(); ++i) {
212 point_type point = point_data_[i];
213 deconvolve(point, shift_);
214 glVertex2f(point.x(), point.y());
215 }
216 for (std::size_t i = 0; i < segment_data_.size(); ++i) {
217 point_type lp = low(segment_data_[i]);
218 lp = deconvolve(lp, shift_);
219 glVertex2f(lp.x(), lp.y());
220 point_type hp = high(segment_data_[i]);
221 hp = deconvolve(hp, shift_);
222 glVertex2f(hp.x(), hp.y());
223 }
224 glEnd();
225 }
226
draw_segments()227 void draw_segments() {
228 // Draw input segments.
229 glColor3f(0.0f, 0.5f, 1.0f);
230 glLineWidth(2.7f);
231 glBegin(GL_LINES);
232 for (std::size_t i = 0; i < segment_data_.size(); ++i) {
233 point_type lp = low(segment_data_[i]);
234 lp = deconvolve(lp, shift_);
235 glVertex2f(lp.x(), lp.y());
236 point_type hp = high(segment_data_[i]);
237 hp = deconvolve(hp, shift_);
238 glVertex2f(hp.x(), hp.y());
239 }
240 glEnd();
241 }
242
draw_vertices()243 void draw_vertices() {
244 // Draw voronoi vertices.
245 glColor3f(0.0f, 0.0f, 0.0f);
246 glPointSize(6);
247 glBegin(GL_POINTS);
248 for (const_vertex_iterator it = vd_.vertices().begin();
249 it != vd_.vertices().end(); ++it) {
250 if (internal_edges_only_ && (it->color() == EXTERNAL_COLOR)) {
251 continue;
252 }
253 point_type vertex(it->x(), it->y());
254 vertex = deconvolve(vertex, shift_);
255 glVertex2f(vertex.x(), vertex.y());
256 }
257 glEnd();
258 }
draw_edges()259 void draw_edges() {
260 // Draw voronoi edges.
261 glColor3f(0.0f, 0.0f, 0.0f);
262 glLineWidth(1.7f);
263 for (const_edge_iterator it = vd_.edges().begin();
264 it != vd_.edges().end(); ++it) {
265 if (primary_edges_only_ && !it->is_primary()) {
266 continue;
267 }
268 if (internal_edges_only_ && (it->color() == EXTERNAL_COLOR)) {
269 continue;
270 }
271 std::vector<point_type> samples;
272 if (!it->is_finite()) {
273 clip_infinite_edge(*it, &samples);
274 } else {
275 point_type vertex0(it->vertex0()->x(), it->vertex0()->y());
276 samples.push_back(vertex0);
277 point_type vertex1(it->vertex1()->x(), it->vertex1()->y());
278 samples.push_back(vertex1);
279 if (it->is_curved()) {
280 sample_curved_edge(*it, &samples);
281 }
282 }
283 glBegin(GL_LINE_STRIP);
284 for (std::size_t i = 0; i < samples.size(); ++i) {
285 point_type vertex = deconvolve(samples[i], shift_);
286 glVertex2f(vertex.x(), vertex.y());
287 }
288 glEnd();
289 }
290 }
291
clip_infinite_edge(const edge_type & edge,std::vector<point_type> * clipped_edge)292 void clip_infinite_edge(
293 const edge_type& edge, std::vector<point_type>* clipped_edge) {
294 const cell_type& cell1 = *edge.cell();
295 const cell_type& cell2 = *edge.twin()->cell();
296 point_type origin, direction;
297 // Infinite edges could not be created by two segment sites.
298 if (cell1.contains_point() && cell2.contains_point()) {
299 point_type p1 = retrieve_point(cell1);
300 point_type p2 = retrieve_point(cell2);
301 origin.x((p1.x() + p2.x()) * 0.5);
302 origin.y((p1.y() + p2.y()) * 0.5);
303 direction.x(p1.y() - p2.y());
304 direction.y(p2.x() - p1.x());
305 } else {
306 origin = cell1.contains_segment() ?
307 retrieve_point(cell2) :
308 retrieve_point(cell1);
309 segment_type segment = cell1.contains_segment() ?
310 retrieve_segment(cell1) :
311 retrieve_segment(cell2);
312 coordinate_type dx = high(segment).x() - low(segment).x();
313 coordinate_type dy = high(segment).y() - low(segment).y();
314 if ((low(segment) == origin) ^ cell1.contains_point()) {
315 direction.x(dy);
316 direction.y(-dx);
317 } else {
318 direction.x(-dy);
319 direction.y(dx);
320 }
321 }
322 coordinate_type side = xh(brect_) - xl(brect_);
323 coordinate_type koef =
324 side / (std::max)(fabs(direction.x()), fabs(direction.y()));
325 if (edge.vertex0() == NULL) {
326 clipped_edge->push_back(point_type(
327 origin.x() - direction.x() * koef,
328 origin.y() - direction.y() * koef));
329 } else {
330 clipped_edge->push_back(
331 point_type(edge.vertex0()->x(), edge.vertex0()->y()));
332 }
333 if (edge.vertex1() == NULL) {
334 clipped_edge->push_back(point_type(
335 origin.x() + direction.x() * koef,
336 origin.y() + direction.y() * koef));
337 } else {
338 clipped_edge->push_back(
339 point_type(edge.vertex1()->x(), edge.vertex1()->y()));
340 }
341 }
342
sample_curved_edge(const edge_type & edge,std::vector<point_type> * sampled_edge)343 void sample_curved_edge(
344 const edge_type& edge,
345 std::vector<point_type>* sampled_edge) {
346 coordinate_type max_dist = 1E-3 * (xh(brect_) - xl(brect_));
347 point_type point = edge.cell()->contains_point() ?
348 retrieve_point(*edge.cell()) :
349 retrieve_point(*edge.twin()->cell());
350 segment_type segment = edge.cell()->contains_point() ?
351 retrieve_segment(*edge.twin()->cell()) :
352 retrieve_segment(*edge.cell());
353 voronoi_visual_utils<coordinate_type>::discretize(
354 point, segment, max_dist, sampled_edge);
355 }
356
retrieve_point(const cell_type & cell)357 point_type retrieve_point(const cell_type& cell) {
358 source_index_type index = cell.source_index();
359 source_category_type category = cell.source_category();
360 if (category == SOURCE_CATEGORY_SINGLE_POINT) {
361 return point_data_[index];
362 }
363 index -= point_data_.size();
364 if (category == SOURCE_CATEGORY_SEGMENT_START_POINT) {
365 return low(segment_data_[index]);
366 } else {
367 return high(segment_data_[index]);
368 }
369 }
370
retrieve_segment(const cell_type & cell)371 segment_type retrieve_segment(const cell_type& cell) {
372 source_index_type index = cell.source_index() - point_data_.size();
373 return segment_data_[index];
374 }
375
376 point_type shift_;
377 std::vector<point_type> point_data_;
378 std::vector<segment_type> segment_data_;
379 rect_type brect_;
380 VB vb_;
381 VD vd_;
382 bool brect_initialized_;
383 bool primary_edges_only_;
384 bool internal_edges_only_;
385 };
386
387 class MainWindow : public QWidget {
388 Q_OBJECT
389
390 public:
MainWindow()391 MainWindow() {
392 glWidget_ = new GLWidget();
393 file_dir_ = QDir(QDir::currentPath(), tr("*.txt"));
394 file_name_ = tr("");
395
396 QHBoxLayout* centralLayout = new QHBoxLayout;
397 centralLayout->addWidget(glWidget_);
398 centralLayout->addLayout(create_file_layout());
399 setLayout(centralLayout);
400
401 update_file_list();
402 setWindowTitle(tr("Voronoi Visualizer"));
403 layout()->setSizeConstraint(QLayout::SetFixedSize);
404 }
405
406 private slots:
primary_edges_only()407 void primary_edges_only() {
408 glWidget_->show_primary_edges_only();
409 }
410
internal_edges_only()411 void internal_edges_only() {
412 glWidget_->show_internal_edges_only();
413 }
414
browse()415 void browse() {
416 QString new_path = QFileDialog::getExistingDirectory(
417 0, tr("Choose Directory"), file_dir_.absolutePath());
418 if (new_path.isEmpty()) {
419 return;
420 }
421 file_dir_.setPath(new_path);
422 update_file_list();
423 }
424
build()425 void build() {
426 file_name_ = file_list_->currentItem()->text();
427 QString file_path = file_dir_.filePath(file_name_);
428 message_label_->setText("Building...");
429 glWidget_->build(file_path);
430 message_label_->setText("Double click the item to build voronoi diagram:");
431 setWindowTitle(tr("Voronoi Visualizer - ") + file_path);
432 }
433
print_scr()434 void print_scr() {
435 if (!file_name_.isEmpty()) {
436 QImage screenshot = glWidget_->grabFrameBuffer(true);
437 QString output_file = file_dir_.absolutePath() + tr("/") +
438 file_name_.left(file_name_.indexOf('.')) + tr(".png");
439 screenshot.save(output_file, 0, -1);
440 }
441 }
442
443 private:
create_file_layout()444 QGridLayout* create_file_layout() {
445 QGridLayout* file_layout = new QGridLayout;
446
447 message_label_ = new QLabel("Double click item to build voronoi diagram:");
448
449 file_list_ = new QListWidget();
450 file_list_->connect(file_list_,
451 SIGNAL(itemDoubleClicked(QListWidgetItem*)),
452 this,
453 SLOT(build()));
454
455 QCheckBox* primary_checkbox = new QCheckBox("Show primary edges only.");
456 connect(primary_checkbox, SIGNAL(clicked()),
457 this, SLOT(primary_edges_only()));
458
459 QCheckBox* internal_checkbox = new QCheckBox("Show internal edges only.");
460 connect(internal_checkbox, SIGNAL(clicked()),
461 this, SLOT(internal_edges_only()));
462
463 QPushButton* browse_button =
464 new QPushButton(tr("Browse Input Directory"));
465 connect(browse_button, SIGNAL(clicked()), this, SLOT(browse()));
466 browse_button->setMinimumHeight(50);
467
468 QPushButton* print_scr_button = new QPushButton(tr("Make Screenshot"));
469 connect(print_scr_button, SIGNAL(clicked()), this, SLOT(print_scr()));
470 print_scr_button->setMinimumHeight(50);
471
472 file_layout->addWidget(message_label_, 0, 0);
473 file_layout->addWidget(file_list_, 1, 0);
474 file_layout->addWidget(primary_checkbox, 2, 0);
475 file_layout->addWidget(internal_checkbox, 3, 0);
476 file_layout->addWidget(browse_button, 4, 0);
477 file_layout->addWidget(print_scr_button, 5, 0);
478
479 return file_layout;
480 }
481
update_file_list()482 void update_file_list() {
483 QFileInfoList list = file_dir_.entryInfoList();
484 file_list_->clear();
485 if (file_dir_.count() == 0) {
486 return;
487 }
488 QFileInfoList::const_iterator it;
489 for (it = list.begin(); it != list.end(); it++) {
490 file_list_->addItem(it->fileName());
491 }
492 file_list_->setCurrentRow(0);
493 }
494
495 QDir file_dir_;
496 QString file_name_;
497 GLWidget* glWidget_;
498 QListWidget* file_list_;
499 QLabel* message_label_;
500 };
501
main(int argc,char * argv[])502 int main(int argc, char* argv[]) {
503 QApplication app(argc, argv);
504 MainWindow window;
505 window.show();
506 return app.exec();
507 }
508
509 #include "voronoi_visualizer.moc"
510