Subject: [Boost-commit] svn:boost r63792 - in sandbox/SOC/2010/sweepline: . boost/sweepline boost/sweepline/detail libs/sweepline/example libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-07-09 16:25:15
Author: asydorchuk
Date: 2010-07-09 16:25:13 EDT (Fri, 09 Jul 2010)
New Revision: 63792
URL: http://svn.boost.org/trac/boost/changeset/63792
Log:
Added voronoi visualizer.
Made clipping update.
Added:
sandbox/SOC/2010/sweepline/libs/sweepline/example/Jamfile.v2 (contents, props changed)
sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 81 +++++++++++++++++----------------------
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp | 2
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp | 31 ++++++++------
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 4
sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp | 6 +-
sandbox/SOC/2010/sweepline/project-root.jam | 1
6 files changed, 59 insertions(+), 66 deletions(-)
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp 2010-07-09 16:25:13 EDT (Fri, 09 Jul 2010)
@@ -457,7 +457,7 @@
// Returns x coordinate of the rightmost site.
coordinate_type get_sweepline_coord() const {
- return std::max(left_site_.x(), right_site_.x());
+ return (std::max)(left_site_.x(), right_site_.x());
}
// Returns the rightmost site.
@@ -1093,8 +1093,30 @@
void find_intersections(const Point2D &origin, const Point2D &direction,
kEdgeType edge_type, const BRect<Point2D> &brect,
std::vector<Point2D> &intersections) const {
- // Do intersection test.
- if (!test_intersection(origin, direction, brect))
+ coordinate_type half = static_cast<coordinate_type>(0.5);
+
+ // Find rectangle center.
+ coordinate_type center_x = (brect.x_min + brect.x_max) * half;
+ coordinate_type center_y = (brect.y_min + brect.y_max) * half;
+
+ // Find rectangle half-diagonal vector.
+ coordinate_type len_x = brect.x_max - center_x;
+ coordinate_type len_y = brect.y_max - center_y;
+
+ // Find distance between origin and center of rectangle.
+ coordinate_type diff_x = origin.x() - center_x;
+ coordinate_type diff_y = origin.y() - center_y;
+
+ // Find direction perpendicular to the current.
+ coordinate_type perp_x = direction.y();
+ coordinate_type perp_y = -direction.x();
+
+ // Compare projections of distances.
+ coordinate_type lexpr = magnitude(perp_x * diff_x + perp_y * diff_y);
+ coordinate_type rexpr = magnitude(perp_x * len_x) + magnitude(perp_y * len_y);
+
+ // Intersection check.
+ if (lexpr > rexpr)
return;
// Intersection parameters:
@@ -1104,23 +1126,18 @@
coordinate_type fT0 = static_cast<coordinate_type>(0);
coordinate_type fT1 = static_cast<coordinate_type>(0);
- // Half lengths of sides of a bounding rectangle.
- coordinate_type half = static_cast<coordinate_type>(0.5);
- coordinate_type x_len = (brect.x_max - brect.x_min) * half;
- coordinate_type y_len = (brect.y_max - brect.y_min) * half;
-
- // Find intersections with lines going through sides of a bounding recntagle.
- clip(+direction.x(), -origin.x() - x_len, fT0_used, fT1_used, fT0, fT1);
- clip(-direction.x(), +origin.x() - x_len, fT0_used, fT1_used, fT0, fT1);
- clip(+direction.y(), -origin.y() - y_len, fT0_used, fT1_used, fT0, fT1);
- clip(-direction.y(), +origin.y() - y_len, fT0_used, fT1_used, fT0, fT1);
+ // Find intersections with lines going through sides of a bounding rectangle.
+ clip(+direction.x(), -diff_x - len_x, fT0_used, fT1_used, fT0, fT1);
+ clip(-direction.x(), +diff_x - len_x, fT0_used, fT1_used, fT0, fT1);
+ clip(+direction.y(), -diff_y - len_y, fT0_used, fT1_used, fT0, fT1);
+ clip(-direction.y(), +diff_y - len_y, fT0_used, fT1_used, fT0, fT1);
if (fT0_used && check_extent(fT0, edge_type))
- intersections.push_back(make_point_2d(origin.x() + fT0_used * direction.x(),
- origin.y() + fT0_used * direction.y()));
+ intersections.push_back(make_point_2d(origin.x() + fT0 * direction.x(),
+ origin.y() + fT0 * direction.y()));
if (fT1_used && check_extent(fT1, edge_type))
- intersections.push_back(make_point_2d(origin.x() + fT1_used * direction.x(),
- origin.y() + fT1_used * direction.y()));
+ intersections.push_back(make_point_2d(origin.x() + fT1 * direction.x(),
+ origin.y() + fT1 * direction.y()));
}
private:
@@ -1186,36 +1203,8 @@
return -value;
}
- // Check line rectangle intersection.
- bool test_intersection(const Point2D &origin, const Point2D &direction,
- const BRect<Point2D> &brect) const {
- coordinate_type half = static_cast<coordinate_type>(0.5);
-
- // Find rectangle center.
- coordinate_type center_x = (brect.x_min + brect.x_max) * half;
- coordinate_type center_y = (brect.y_min + brect.y_max) * half;
-
- // Find rectangle half-diagonal vector.
- coordinate_type len_x = brect.x_max - center_x;
- coordinate_type len_y = brect.y_max - center_y;
-
- // Find distance between origin and center of rectangle.
- coordinate_type diff_x = origin.x() - center_x;
- coordinate_type diff_y = origin.y() - center_y;
-
- // Find direction perpendicular to the current.
- coordinate_type perp_x = direction.y();
- coordinate_type perp_y = -direction.x();
-
- // Compare projections of distances.
- coordinate_type lexpr = magnitude(perp_x * diff_x + perp_y * diff_y);
- coordinate_type rexpr = magnitude(perp_x * len_x) + magnitude(perp_y * len_y);
-
- return lexpr <= rexpr;
- }
-
bool clip(coordinate_type denom, coordinate_type numer, bool &fT0_used, bool &fT1_used,
- coordinate_type &fT0, coordinate_type fT1) const {
+ coordinate_type &fT0, coordinate_type &fT1) const {
if (denom > static_cast<coordinate_type>(0)) {
if (fT1_used && numer > denom * fT1)
return false;
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp 2010-07-09 16:25:13 EDT (Fri, 09 Jul 2010)
@@ -34,6 +34,8 @@
// vertical line, we init beach line with all of them.
// In other case just use the first two sites for the initialization.
void init(std::vector<Point2D> &sites) {
+ reset();
+
// Sort all sites.
sort(sites.begin(), sites.end());
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp 2010-07-09 16:25:13 EDT (Fri, 09 Jul 2010)
@@ -90,6 +90,7 @@
// Bounding rectangle data structure.
template <typename Point2D>
struct BRect {
+ public:
typedef typename Point2D::coordinate_type coordinate_type;
coordinate_type x_min;
@@ -100,25 +101,25 @@
BRect() {}
BRect(const Point2D &p1, const Point2D &p2) {
- x_min = std::min(p1.x(), p2.x());
- y_min = std::min(p1.y(), p2.y());
- x_max = std::max(p1.x(), p2.x());
- y_max = std::max(p1.y(), p2.y());
+ x_min = (std::min)(p1.x(), p2.x());
+ y_min = (std::min)(p1.y(), p2.y());
+ x_max = (std::max)(p1.x(), p2.x());
+ y_max = (std::max)(p1.y(), p2.y());
}
BRect(coordinate_type x_mn, coordinate_type y_mn,
coordinate_type x_mx, coordinate_type y_mx) {
- x_min = std::min(x_mn, x_mx);
- y_min = std::min(y_mn, y_mx);
- x_max = std::max(x_mn, x_mx);
- y_max = std::max(y_mn, y_mx);
+ x_min = (std::min)(x_mn, x_mx);
+ y_min = (std::min)(y_mn, y_mx);
+ x_max = (std::max)(x_mn, x_mx);
+ y_max = (std::max)(y_mn, y_mx);
}
void update(const Point2D &p) {
- x_min = std::min(x_min, p.x());
- y_min = std::min(y_min, p.y());
- x_max = std::max(x_max, p.x());
- y_max = std::max(y_max, p.y());
+ x_min = (std::min)(x_min, p.x());
+ y_min = (std::min)(y_min, p.y());
+ x_max = (std::max)(x_max, p.x());
+ y_max = (std::max)(y_max, p.y());
}
bool contains(const Point2D &p) const {
@@ -187,9 +188,11 @@
typedef voronoi_record_clipped<Point2D> voronoi_record_type;
typedef half_edge_clipped<Point2D> edge_type;
typedef std::list<voronoi_record_type> voronoi_records_type;
- typedef std::list<edge_type> voronoi_edges_type;
typedef typename voronoi_records_type::iterator voronoi_iterator_type;
typedef typename voronoi_records_type::const_iterator voronoi_const_iterator_type;
+ typedef std::list<edge_type> voronoi_edges_type;
+ typedef typename voronoi_edges_type::iterator edges_iterator_type;
+ typedef typename voronoi_edges_type::const_iterator edges_const_iterator_type;
voronoi_output_clipped() {
num_cell_records_ = 0;
@@ -243,7 +246,7 @@
num_cell_records_--;
}
- const voronoi_records_type &get_cell_records() const {
+ const voronoi_records_type &get_voronoi_cells() const {
return cell_records_;
}
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/Jamfile.v2
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/Jamfile.v2 2010-07-09 16:25:13 EDT (Fri, 09 Jul 2010)
@@ -0,0 +1,17 @@
+# Copyright Andrii Sydorchuk 2010.
+# Distributed under the Boost Software License, Version 1.0.
+# (See accompanying file LICENSE_1_0.txt or copy at
+# http://www.boost.org/LICENSE_1_0.txt)
+
+import cast ;
+
+lib opengl : : <name>opengl32 ;
+lib glu : : <name>glu32 ;
+exe voronoi_visualizer : voronoi_visualizer.cpp
+ [ cast _ moccable-cpp : voronoi_visualizer.cpp ]
+ /qt//QtCore
+ /qt//QtGui
+ /qt//QtOpenGL
+ opengl
+ glu
+ ;
\ No newline at end of file
Added: sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp 2010-07-09 16:25:13 EDT (Fri, 09 Jul 2010)
@@ -0,0 +1,205 @@
+// Boost sweepline library visualizer_main.cpp file
+
+// Copyright Andrii Sydorchuk 2010.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org for updates, documentation, and revision history.
+
+#include <QtOpenGL/QGLWidget>
+#include <QtGui/QtGui>
+
+#include "boost/sweepline/voronoi_sweepline.hpp"
+
+class GLWidget : public QGLWidget {
+ Q_OBJECT
+public:
+ GLWidget(QMainWindow *parent = NULL) : QGLWidget(QGLFormat(QGL::SampleBuffers), parent) {}
+
+ QSize sizeHint() const {
+ return QSize(600, 600);
+ }
+
+ void build(QString file_path) {
+ std::vector<Point2D> sites;
+
+ // Open file.
+ QFile data(file_path);
+ if (!data.open(QFile::ReadOnly))
+ QMessageBox::warning(this, tr("Voronoi Visualizer"),
+ tr("Disable to open file ") + file_path);
+
+ // Read points from the file.
+ QTextStream in_stream(&data);
+ int num_sites;
+ in_stream >> num_sites;
+ double x, y;
+ for (int i = 0; i < num_sites; i++) {
+ in_stream >> x >> y;
+ sites.push_back(boost::sweepline::make_point_2d(x, y));
+ }
+ in_stream.flush();
+
+ // Build voronoi diagram.
+ voronoi_builder_.init(sites);
+ voronoi_builder_.run_sweepline();
+ voronoi_builder_.clip(voronoi_output_);
+ brect_ = voronoi_output_.get_bounding_rectangle();
+
+ // Update view.
+ update_view_port();
+ updateGL();
+ }
+
+protected:
+ void initializeGL() {
+ glPointSize(9);
+ }
+
+ void paintGL() {
+ qglClearColor(QColor::fromRgb(0, 0, 0));
+ glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
+
+ // Draw voronoi sites.
+ voronoi_records_type cells = voronoi_output_.get_voronoi_cells();
+ voronoi_const_iterator_type it;
+ glColor3f(0.0f, 0.0f, 1.0f);
+ glBegin(GL_POINTS);
+ for (it = cells.begin(); it != cells.end(); it++)
+ glVertex2f(it->voronoi_point.x(), it->voronoi_point.y());
+ glEnd();
+
+ // Draw voronoi vertices.
+ voronoi_records_type vertices = voronoi_output_.get_voronoi_vertices();
+ glColor3f(0.0f, 1.0f, 0.0f);
+ glBegin(GL_POINTS);
+ for (it = vertices.begin(); it != vertices.end(); it++)
+ glVertex2f(it->voronoi_point.x(), it->voronoi_point.y());
+ glEnd();
+
+ // Draw voronoi edges.
+ voronoi_edges_type edges = voronoi_output_.get_voronoi_edges();
+ edges_const_iterator_type edge_it;
+ glColor3f(0.0f, 1.0f, 0.0f);
+ glBegin(GL_LINES);
+ for (edge_it = edges.begin(); edge_it != edges.end(); edge_it++) {
+ glVertex2f(edge_it->start_point->voronoi_point.x(),
+ edge_it->start_point->voronoi_point.y());
+ glVertex2f(edge_it->end_point->voronoi_point.x(),
+ edge_it->end_point->voronoi_point.y());
+ }
+ glEnd();
+ }
+
+ void resizeGL(int width, int height) {
+ int side = qMin(width, height);
+ glViewport((width - side) / 2, (height - side) / 2, side, side);
+ }
+
+private:
+ void update_view_port() {
+ glMatrixMode(GL_PROJECTION);
+ glLoadIdentity();
+ glOrtho(brect_.x_min, brect_.x_max, brect_.y_min, brect_.y_max, -1.0, 1.0);
+ glMatrixMode(GL_MODELVIEW);
+ }
+
+ typedef boost::sweepline::point_2d<double> Point2D;
+ typedef boost::sweepline::voronoi_output_clipped<Point2D>::voronoi_records_type
+ voronoi_records_type;
+ typedef boost::sweepline::voronoi_output_clipped<Point2D>::voronoi_edges_type
+ voronoi_edges_type;
+ typedef boost::sweepline::voronoi_output_clipped<Point2D>::voronoi_const_iterator_type
+ voronoi_const_iterator_type;
+ typedef boost::sweepline::voronoi_output_clipped<Point2D>::edges_const_iterator_type
+ edges_const_iterator_type;
+ boost::sweepline::voronoi_builder<double> voronoi_builder_;
+ boost::sweepline::BRect<Point2D> brect_;
+ boost::sweepline::voronoi_output_clipped<Point2D> voronoi_output_;
+};
+
+class MainWindow : public QWidget {
+ Q_OBJECT
+public:
+ MainWindow() {
+ glWidget_ = new GLWidget();
+ file_dir_ = QDir(QDir::currentPath(), tr("*.pts"));
+
+ QHBoxLayout *centralLayout = new QHBoxLayout;
+ centralLayout->addWidget(glWidget_);
+ centralLayout->addLayout(create_file_layout());
+ setLayout(centralLayout);
+
+ update_file_list_();
+ setWindowTitle(tr("Voronoi Visualizer"));
+ layout()->setSizeConstraint( QLayout::SetFixedSize );
+ }
+
+private slots:
+ void browse() {
+ QString new_path = QFileDialog::getExistingDirectory(0, tr("Choose Directory"),
+ file_dir_.absolutePath());
+ if (new_path.isEmpty())
+ return;
+ file_dir_.setPath(new_path);
+ update_file_list_();
+ }
+
+ void build() {
+ QString file_name = file_list_->currentItem()->text();
+ QString file_path = file_dir_.filePath(file_name);
+ message_label_->setText("Building...");
+ glWidget_->build(file_path);
+ message_label_->setText("Double click item to build voronoi diagram:");
+ setWindowTitle(tr("Voronoi Visualizer - ") + file_path);
+ }
+
+private:
+ QGridLayout *create_file_layout() {
+ QGridLayout *file_layout = new QGridLayout;
+
+ message_label_ = new QLabel("Double click item to build voronoi diagram:");
+
+ file_list_ = new QListWidget();
+ file_list_->connect(file_list_, SIGNAL(itemDoubleClicked(QListWidgetItem*)),
+ this, SLOT(build()));
+
+ QPushButton *browse_button = new QPushButton(tr("Browse"));
+ browse_button->connect(browse_button, SIGNAL(clicked()), this, SLOT(browse()));
+ browse_button->setMinimumHeight(50);
+
+ file_layout->addWidget(message_label_, 0, 0);
+ file_layout->addWidget(file_list_, 1, 0);
+ file_layout->addWidget(browse_button, 2, 0);
+
+ return file_layout;
+ }
+
+ void update_file_list_() {
+ QFileInfoList list = file_dir_.entryInfoList();
+ file_list_->clear();
+ if (file_dir_.count() == 0)
+ return;
+
+ QFileInfoList::const_iterator it;
+ for (it = list.begin(); it != list.end(); it++)
+ file_list_->addItem(it->fileName());
+ file_list_->setCurrentRow(0);
+ }
+
+ QDir file_dir_;
+ GLWidget *glWidget_;
+ QListWidget *file_list_;
+ QLabel *message_label_;
+};
+
+int main(int argc, char *argv[])
+{
+ QApplication app(argc, argv);
+ MainWindow window;
+ window.show();
+ return app.exec();
+}
+
+#include "voronoi_visualizer.moc"
\ No newline at end of file
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp 2010-07-09 16:25:13 EDT (Fri, 09 Jul 2010)
@@ -1,10 +1,10 @@
// Boost sweepline library event_queue_test.cpp file
-//
+
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-//
+
// See http://www.boost.org for updates, documentation, and revision history.
#include <cmath>
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp 2010-07-09 16:25:13 EDT (Fri, 09 Jul 2010)
@@ -45,7 +45,7 @@
bounding_rectangle.x_max == static_cast<T>(2) &&
bounding_rectangle.y_max == static_cast<T>(4), true);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_cell_records().size()), 3);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_cells().size()), 3);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 4);
voronoi_const_iterator_type it = test_output.get_voronoi_vertices().begin();
@@ -107,7 +107,7 @@
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_cell_records().size()), 3);
+ BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_cells().size()), 3);
BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 4);
voronoi_const_iterator_type it = test_output.get_voronoi_vertices().begin();
@@ -166,7 +166,7 @@
test_beach_line.clip(test_output);
BOOST_CHECK_EQUAL(test_output.check(), true);
- BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_cell_records().size()), 4);
+ BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_voronoi_cells().size()), 4);
BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_voronoi_vertices().size()), 5);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 4);
BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 1);
Modified: sandbox/SOC/2010/sweepline/project-root.jam
==============================================================================
--- sandbox/SOC/2010/sweepline/project-root.jam (original)
+++ sandbox/SOC/2010/sweepline/project-root.jam 2010-07-09 16:25:13 EDT (Fri, 09 Jul 2010)
@@ -3,7 +3,6 @@
# (See accompanying file LICENSE_1_0.txt or copy at
# http://www.boost.org/LICENSE_1_0.txt)
-
import os ;
path-constant BOOST_ROOT : [ os.environ BOOST_ROOT ] ;