Subject: [Boost-commit] svn:boost r77365 - in sandbox/gtl: boost/polygon libs/polygon/test libs/polygon/voronoi_example
From: sydorchuk.andriy_at_[hidden]
Date: 2012-03-18 07:22:04
Author: asydorchuk
Date: 2012-03-18 07:22:03 EDT (Sun, 18 Mar 2012)
New Revision: 77365
URL: http://svn.boost.org/trac/boost/changeset/77365
Log:
Updating voronoi utils class.
Removed:
sandbox/gtl/libs/polygon/test/voronoi_clipping_test.cpp
Text files modified:
sandbox/gtl/boost/polygon/voronoi_builder.hpp | 2
sandbox/gtl/boost/polygon/voronoi_diagram.hpp | 13 +
sandbox/gtl/boost/polygon/voronoi_utils.hpp | 302 +++++++++++++++++++--------------------
sandbox/gtl/libs/polygon/test/Jamfile.v2 | 3
sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp | 4
sandbox/gtl/libs/polygon/voronoi_example/voronoi_visualizer.cpp | 9
6 files changed, 169 insertions(+), 164 deletions(-)
Modified: sandbox/gtl/boost/polygon/voronoi_builder.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_builder.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_builder.hpp 2012-03-18 07:22:03 EDT (Sun, 18 Mar 2012)
@@ -163,7 +163,7 @@
}
beach_line_.clear();
- // Clean the output (remove zero-length edges).
+ // Finish construction.
output->builder()->build();
}
Modified: sandbox/gtl/boost/polygon/voronoi_diagram.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_diagram.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_diagram.hpp 2012-03-18 07:22:03 EDT (Sun, 18 Mar 2012)
@@ -48,6 +48,9 @@
incident_edge_(edge),
data_(NULL) {}
+ // Returns true if the cell contains point site, false else.
+ bool contains_point() const { return point0_ == point1_; }
+
// Returns true if the cell contains segment site, false else.
bool contains_segment() const { return point0_ != point1_; }
@@ -183,17 +186,21 @@
// Return true if the edge is finite (segment, parabolic arc).
// Return false if the edge is infinite (ray, line).
- bool is_bounded() const { return vertex0() && vertex1(); }
+ bool is_finite() const { return vertex0() && vertex1(); }
- // Return true if the edge is linear.
+ // Return true if the edge is linear (segment, ray, line).
// Return false if the edge is curved (parabolic arc).
bool is_linear() const {
+ if (!is_primary())
+ return true;
return !(cell()->contains_segment() ^ twin()->cell()->contains_segment());
}
// Returns true if the edge is curved (parabolic arc).
- // Returns false if the edge is linear.
+ // Returns false if the edge is linear (segment, ray, line).
bool is_curved() const {
+ if (!is_primary())
+ return false;
return (cell()->contains_segment() ^ twin()->cell()->contains_segment());
}
Modified: sandbox/gtl/boost/polygon/voronoi_utils.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_utils.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_utils.hpp 2012-03-18 07:22:03 EDT (Sun, 18 Mar 2012)
@@ -36,6 +36,7 @@
y_max_ = (std::max)(y1, y2);
}
+ // Update bounding rectangle.
void update(coordinate_type x, coordinate_type y) {
if (x_min_ > x_max_) {
x_min_ = x_max_ = x;
@@ -57,7 +58,6 @@
x_max_ = 0;
}
- // Update bounding rectangle.
bool contains(coordinate_type x, coordinate_type y) const {
return x > x_min_ && x < x_max_ && y > y_min_ && y < y_max_;
}
@@ -116,20 +116,10 @@
typedef typename TRAITS::brect_type brect_type;
typedef typename TRAITS::ctype_converter_type ctype_converter_type;
- // There are three different types of linear primitive:
- // 1) SEGMENT - has two finite endpoints;
- // 2) RAY - has one finite and one infinite endpoint;
- // 3) LINE - has two infinite endpoints.
- enum EdgeType {
- SEGMENT = 0,
- RAY = 1,
- LINE = 2
- };
-
// Get scaled by a factor bounding rectangle.
template <typename CT>
- static brect_type scale(const bounding_rectangle<CT> &brect,
- coordinate_type factor = 1.0) {
+ static brect_type scale(const bounding_rectangle<CT> &brect,
+ coordinate_type factor) {
coordinate_type x_len = to_fpt(brect.x_max()) - to_fpt(brect.x_min());
coordinate_type y_len = to_fpt(brect.y_max()) - to_fpt(brect.y_min());
coordinate_type x_mid = to_fpt(brect.x_max()) + to_fpt(brect.x_min());
@@ -142,16 +132,15 @@
return new_brect;
}
- // Discretize voronoi edge. Infinite edges are clipped by the input
- // rectangle. Finite edges are not clipped at all.
- // Max_error is the maximum distance (relative to the minor of two
- // rectangle sides) allowed between the parabola and line segments
- // that discretize it.
+ // Discretizes finite voronoi edge.
+ // Disretization absolute error is defined by max_error value.
template <typename CT>
- static void discretize(const voronoi_edge<CT> &edge,
- const bounding_rectangle<CT> &brect,
- coordinate_type max_error,
- point_set_type &discretization) {
+ static void discretize(const voronoi_edge<CT> &edge,
+ coordinate_type max_error, point_set_type &discretization) {
+ // Don't process infinite edges.
+ if (!edge.is_finite())
+ return;
+
// Retrieve the cell to the left of the current edge.
const typename voronoi_edge<CT>::voronoi_cell_type *cell1 = edge.cell();
@@ -159,82 +148,117 @@
const typename voronoi_edge<CT>::voronoi_cell_type *cell2 =
edge.twin()->cell();
- if (!(cell1->contains_segment() ^ cell2->contains_segment())) {
- // Edge is a segment, ray, or line.
- if (edge.vertex0() != NULL && edge.vertex1() != NULL) {
- // Edge is a segment. No further processing is required.
- discretization.push_back(get_point(edge.vertex0()->vertex()));
- discretization.push_back(get_point(edge.vertex1()->vertex()));
- } else {
- // Edge is a ray or line.
- // Clip it with the bounding rectangle.
- const point_type &site1 = get_point(cell1->point0());
- const point_type &site2 = get_point(cell2->point0());
- point_type origin((site1.x() + site2.x()) * to_fpt(0.5),
- (site1.y() + site2.y()) * to_fpt(0.5));
- point_type direction(site1.y() - site2.y(), site2.x() - site1.x());
-
- // Find intersection points.
- intersect(origin, direction, LINE, get_brect(brect), discretization);
-
- // Update endpoints in case edge is a ray.
- if (edge.vertex1() != NULL)
- discretization[1] = get_point(edge.vertex1()->vertex());
- if (edge.vertex0() != NULL)
- discretization[0] = get_point(edge.vertex0()->vertex());
- }
- } else {
+ discretization.push_back(get_point(edge.vertex0()->vertex()));
+ discretization.push_back(get_point(edge.vertex1()->vertex()));
+ if (edge.is_curved()) {
// point1 - site point;
- const point_type &point1 = (cell1->contains_segment()) ?
+ point_type point1 = (cell1->contains_segment()) ?
get_point(cell2->point0()) : get_point(cell1->point0());
// point2 - start-point of the segment site;
- const point_type &point2 = (cell1->contains_segment()) ?
+ point_type point2 = (cell1->contains_segment()) ?
get_point(cell1->point0()) : get_point(cell2->point0());
// point3 - endpoint of the segment site;
- const point_type &point3 = (cell1->contains_segment()) ?
+ point_type point3 = (cell1->contains_segment()) ?
get_point(cell1->point1()) : get_point(cell2->point1());
- if (edge.vertex0() != NULL && edge.vertex1() != NULL) {
- // Edge is a segment or parabolic arc.
- discretization.push_back(get_point(edge.vertex0()->vertex()));
- discretization.push_back(get_point(edge.vertex1()->vertex()));
- coordinate_type x_len = to_fpt(brect.x_max()) - to_fpt(brect.x_min());
- coordinate_type y_len = to_fpt(brect.y_max()) - to_fpt(brect.y_min());
- coordinate_type max_dist = max_error * (std::min)(x_len, y_len);
- fill_intermediate_points(point1, point2, point3,
- discretization, max_dist);
+ fill_intermediate_points(
+ point1, point2, point3, max_error, discretization);
+ }
+ }
+
+ // Clip a linear voronoi edge with a given rectangle.
+ template <typename CT>
+ static void clip(const voronoi_edge<CT> &edge,
+ const brect_type &brect, point_set_type &clipped_edge) {
+ // Don't process curved edges.
+ if (edge.is_curved())
+ return;
+
+ if (edge.is_finite()) {
+ clip(edge.vertex0()->vertex(), edge.vertex1()->vertex(),
+ brect, clipped_edge);
+ } else {
+ const typename voronoi_edge<CT>::voronoi_cell_type *cell1 = edge.cell();
+ const typename voronoi_edge<CT>::voronoi_cell_type *cell2 =
+ edge.twin()->cell();
+ point_type point1 = get_point(cell1->point0());
+ point_type point2 = get_point(cell2->point0());
+ if (point1 == point2) {
+ if (cell1->contains_segment())
+ point1 = get_point(cell1->point1());
+ else
+ point2 = get_point(cell2->point1());
+ }
+
+ if (edge.vertex0()) {
+ // Ray edge.
+ point_type origin = get_point(edge.vertex0()->vertex());
+ point_type direction(point1.y() - point2.y(), point2.x() - point1.x());
+ if (brect.contains(origin.x(), origin.y()))
+ clipped_edge.push_back(origin);
+ intersect(origin, direction, RAY, brect, clipped_edge);
+ } else if (edge.vertex1()) {
+ // Ray edge.
+ point_type origin = get_point(edge.vertex1()->vertex());
+ point_type direction(point2.y() - point1.y(), point1.x() - point2.x());
+ if (brect.contains(origin.x(), origin.y()))
+ clipped_edge.push_back(origin);
+ intersect(origin, direction, RAY, brect, clipped_edge);
+ // Keep correct ordering.
+ (std::reverse)(clipped_edge.begin(), clipped_edge.end());
+ } else if (cell1->contains_point() && cell2->contains_point()) {
+ // Primary line edge.
+ point_type origin((point1.x() + point2.x()) * 0.5, (point1.y() + point2.y()) * 0.5);
+ point_type direction(point1.y() - point2.y(), point2.x() - point1.x());
+ intersect(origin, direction, LINE, brect, clipped_edge);
} else {
- // Edge is a ray or line.
- // Clip it with the bounding rectangle.
- coordinate_type dir_x =
- (cell1->contains_segment() ^ (point1 == point3)) ?
- point3.y() - point2.y() : point2.y() - point3.y();
- coordinate_type dir_y =
- (cell1->contains_segment() ^ (point1 == point3)) ?
- point2.x() - point3.x() : point3.x() - point2.x();
- point_type direction(dir_x, dir_y);
-
- // Find intersection points.
- intersect(point1, direction, LINE, brect, discretization);
-
- // Update endpoints in case edge is a ray.
- if (edge.vertex1() != NULL)
- discretization[1] = get_point(edge.vertex1()->vertex());
- if (edge.vertex0() != NULL)
- discretization[0] = get_point(edge.vertex0()->vertex());
+ point_type origin = cell1->contains_point() ? point1 : point2;
+ point_type direction(point1.y() - point2.y(), point2.x() - point1.x());
+ intersect(origin, direction, LINE, brect, clipped_edge);
}
}
}
- // Find edge-rectangle intersection points.
- // Edge is represented by its origin, direction and type.
- static void intersect(const point_type &origin,
- const point_type &direction,
- EdgeType edge_type,
- const brect_type &brect,
- point_set_type &intersections) {
+ // Clip an edge with the given rectangle.
+ template <typename PointType>
+ static void clip(const PointType &p1, const PointType &p2,
+ const brect_type &brect, point_set_type &clipped_edge) {
+ point_type start = get_point(p1);
+ point_type end = get_point(p2);
+ point_type direction(end.x() - start.x(), end.y() - start.y());
+ if (brect.contains(start.x(), start.y()))
+ clipped_edge.push_back(start);
+ intersect(start, direction, SEGMENT, brect, clipped_edge);
+ if (brect.contains(end.x(), end.y()))
+ clipped_edge.push_back(end);
+ }
+
+private:
+ voronoi_utils();
+
+ // There are three different types of linear primitive:
+ // 1) SEGMENT - has two finite endpoints;
+ // 2) RAY - has one finite and one infinite endpoint;
+ // 3) LINE - has two infinite endpoints.
+ enum EdgeType {
+ SEGMENT = 0,
+ RAY = 1,
+ LINE = 2
+ };
+
+ template <typename P>
+ static point_type get_point(const P &point) {
+ coordinate_type x = to_fpt(point.x());
+ coordinate_type y = to_fpt(point.y());
+ return point_type(x, y);
+ }
+
+ static void intersect(
+ const point_type &origin, const point_type &direction,
+ EdgeType edge_type, const brect_type &brect,
+ point_set_type &clipped_edge) {
// Find the center of the rectangle.
coordinate_type center_x = (brect.x_min() + brect.x_max()) * to_fpt(0.5);
coordinate_type center_y = (brect.y_min() + brect.y_max()) * to_fpt(0.5);
@@ -258,8 +282,8 @@
// Maximum projection among any of the half-diagonals of the
// rectangle on the line perpendicular to the direction vector.
- coordinate_type rexpr = magnitude(perp_x * len_x) +
- magnitude(perp_y * len_y);
+ coordinate_type rexpr =
+ magnitude(perp_x * len_x) + magnitude(perp_y * len_y);
// Intersection check. Compare projections.
if (lexpr > rexpr)
@@ -285,30 +309,11 @@
// Update intersections vector.
if (fT0_used && check_extent(fT0, edge_type))
- intersections.push_back(point_type(origin.x() + fT0 * direction.x(),
- origin.y() + fT0 * direction.y()));
+ clipped_edge.push_back(point_type(
+ origin.x() + fT0 * direction.x(), origin.y() + fT0 * direction.y()));
if (fT1_used && fT0 != fT1 && check_extent(fT1, edge_type))
- intersections.push_back(point_type(origin.x() + fT1 * direction.x(),
- origin.y() + fT1 * direction.y()));
- }
-
-private:
- voronoi_utils();
-
- template <typename P>
- static point_type get_point(const P &point) {
- coordinate_type x = to_fpt(point.x());
- coordinate_type y = to_fpt(point.y());
- return point_type(x, y);
- }
-
- template <typename CT>
- static brect_type get_brect(const bounding_rectangle<CT> &rect) {
- coordinate_type x1 = to_fpt(rect.x_min());
- coordinate_type y1 = to_fpt(rect.y_min());
- coordinate_type x2 = to_fpt(rect.x_max());
- coordinate_type y2 = to_fpt(rect.y_max());
- return brect_type(x1, y1, x2, y2);
+ clipped_edge.push_back(point_type(
+ origin.x() + fT1 * direction.x(), origin.y() + fT1 * direction.y()));
}
// Find intermediate points of the parabola.
@@ -318,46 +323,38 @@
// between the given two endpoints.
// Max_dist is the maximum distance allowed between parabola and line
// segments that discretize it.
- static void fill_intermediate_points(point_type point_site,
- point_type segment_site_start,
- point_type segment_site_end,
- point_set_type &intermediate_points,
- coordinate_type max_dist) {
- // Check if bisector is a segment.
- if (point_site == segment_site_start ||
- point_site == segment_site_end)
- return;
-
+ static void fill_intermediate_points(
+ point_type point_site, point_type segment_site_start,
+ point_type segment_site_end, coordinate_type max_dist,
+ point_set_type &intermediate_points) {
// Apply the linear transformation to move start point of the
// segment to the point with coordinates (0, 0) and the direction
// of the segment to coincide the positive direction of the x-axis.
- coordinate_type segm_vec_x = segment_site_end.x() -
- segment_site_start.x();
- coordinate_type segm_vec_y = segment_site_end.y() -
- segment_site_start.y();
- coordinate_type sqr_segment_length = segm_vec_x * segm_vec_x +
- segm_vec_y * segm_vec_y;
+ coordinate_type segm_vec_x =
+ segment_site_end.x() - segment_site_start.x();
+ coordinate_type segm_vec_y =
+ segment_site_end.y() - segment_site_start.y();
+ coordinate_type sqr_segment_length =
+ segm_vec_x * segm_vec_x + segm_vec_y * segm_vec_y;
// Compute x-coordinates of the endpoints of the edge
// in the transformed space.
coordinate_type projection_start = sqr_segment_length *
- get_point_projection(intermediate_points[0],
- segment_site_start,
- segment_site_end);
+ get_point_projection(
+ intermediate_points[0], segment_site_start, segment_site_end);
coordinate_type projection_end = sqr_segment_length *
- get_point_projection(intermediate_points[1],
- segment_site_start,
- segment_site_end);
+ get_point_projection(
+ intermediate_points[1], segment_site_start, segment_site_end);
// Compute parabola parameters in the transformed space.
// Parabola has next representation:
// f(x) = ((x-rot_x)^2 + rot_y^2) / (2.0*rot_y).
coordinate_type point_vec_x = point_site.x() - segment_site_start.x();
coordinate_type point_vec_y = point_site.y() - segment_site_start.y();
- coordinate_type rot_x = segm_vec_x * point_vec_x +
- segm_vec_y * point_vec_y;
- coordinate_type rot_y = segm_vec_x * point_vec_y -
- segm_vec_y * point_vec_x;
+ coordinate_type rot_x =
+ segm_vec_x * point_vec_x + segm_vec_y * point_vec_y;
+ coordinate_type rot_y =
+ segm_vec_x * point_vec_y - segm_vec_y * point_vec_x;
// Save the last point.
point_type last_point = intermediate_points[1];
@@ -378,24 +375,24 @@
// Compute coordinates of the point of the parabola that is
// furthest from the current line segment.
- coordinate_type mid_x = (new_y - cur_y) / (new_x - cur_x) * rot_y +
- rot_x;
+ coordinate_type mid_x =
+ (new_y - cur_y) / (new_x - cur_x) * rot_y + rot_x;
coordinate_type mid_y = parabola_y(mid_x, rot_x, rot_y);
// Compute maximum distance between the given parabolic arc
// and line segment that discretize it.
coordinate_type dist = (new_y - cur_y) * (mid_x - cur_x) -
- (new_x - cur_x) * (mid_y - cur_y);
+ (new_x - cur_x) * (mid_y - cur_y);
dist = dist * dist / ((new_y - cur_y) * (new_y - cur_y) +
- (new_x - cur_x) * (new_x - cur_x));
+ (new_x - cur_x) * (new_x - cur_x));
if (dist <= max_dist) {
// Distance between parabola and line segment is
// not greater than max_dist.
point_stack.pop();
coordinate_type inter_x = (segm_vec_x * new_x - segm_vec_y * new_y) /
- sqr_segment_length + segment_site_start.x();
+ sqr_segment_length + segment_site_start.x();
coordinate_type inter_y = (segm_vec_x * new_y + segm_vec_y * new_x) /
- sqr_segment_length + segment_site_start.y();
+ sqr_segment_length + segment_site_start.y();
intermediate_points.push_back(point_type(inter_x, inter_y));
cur_x = new_x;
cur_y = new_y;
@@ -409,9 +406,8 @@
}
// Compute y(x) = ((x - a) * (x - a) + b * b) / (2 * b).
- static coordinate_type parabola_y(coordinate_type x,
- coordinate_type a,
- coordinate_type b) {
+ static coordinate_type parabola_y(
+ coordinate_type x, coordinate_type a, coordinate_type b) {
return ((x - a) * (x - a) + b * b) / (to_fpt(2.0) * b);
}
@@ -431,12 +427,10 @@
}
// Find fT min and max values: fT = numer / denom.
- static void clip_line(coordinate_type denom,
- coordinate_type numer,
- bool &fT0_used,
- bool &fT1_used,
- coordinate_type &fT0,
- coordinate_type &fT1) {
+ static void clip_line(
+ coordinate_type denom, coordinate_type numer,
+ bool &fT0_used, bool &fT1_used,
+ coordinate_type &fT0, coordinate_type &fT1) {
if (denom > to_fpt(0.0)) {
if (fT1_used && numer > denom * fT1)
return;
@@ -470,10 +464,10 @@
coordinate_type segment_vec_y = segment_end.y() - segment_start.y();
coordinate_type point_vec_x = point.x() - segment_start.x();
coordinate_type point_vec_y = point.y() - segment_start.y();
- coordinate_type sqr_segment_length = segment_vec_x * segment_vec_x +
- segment_vec_y * segment_vec_y;
- coordinate_type vec_dot = segment_vec_x * point_vec_x +
- segment_vec_y * point_vec_y;
+ coordinate_type sqr_segment_length =
+ segment_vec_x * segment_vec_x + segment_vec_y * segment_vec_y;
+ coordinate_type vec_dot =
+ segment_vec_x * point_vec_x + segment_vec_y * point_vec_y;
return vec_dot / sqr_segment_length;
}
Modified: sandbox/gtl/libs/polygon/test/Jamfile.v2
==============================================================================
--- sandbox/gtl/libs/polygon/test/Jamfile.v2 (original)
+++ sandbox/gtl/libs/polygon/test/Jamfile.v2 2012-03-18 07:22:03 EDT (Sun, 18 Mar 2012)
@@ -29,9 +29,8 @@
alias "voronoi-unit"
:
[ run voronoi_builder_test.cpp ]
- [ run voronoi_clipping_test.cpp ]
[ run voronoi_ctypes_test.cpp ]
- [ run voronoi_predicates_test.cpp ]
+ [ run voronoi_predicates_test.cpp ]
[ run voronoi_robust_fpt_test.cpp ]
[ run voronoi_structures_test.cpp ]
;
Deleted: sandbox/gtl/libs/polygon/test/voronoi_clipping_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_clipping_test.cpp 2012-03-18 07:22:03 EDT (Sun, 18 Mar 2012)
+++ (empty file)
@@ -1,217 +0,0 @@
-// Boost.Polygon library voronoi_clipping_test.cpp file
-
-// Copyright Andrii Sydorchuk 2010-2012.
-// 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.
-
-#define BOOST_TEST_MODULE voronoi_clipping_test
-#include <boost/test/test_case_template.hpp>
-
-#include "boost/polygon/voronoi_utils.hpp"
-using namespace boost::polygon;
-
-typedef voronoi_utils<double> VU;
-typedef VU::brect_type rect_type;
-typedef VU::point_type point_type;
-
-#define SZ(st) static_cast<int>(st.size())
-
-// Test segment clipping.
-BOOST_AUTO_TEST_CASE(segment_clipping_test1) {
- rect_type rect(0, -1, 4, 2);
- point_type origin(-1, 3);
- point_type direction1_1(8, -8);
- point_type direction1_2(2, -2);
- point_type direction1_3(0.5, -0.5);
- point_type direction2(2, -4);
- point_type direction3(2, -1);
- point_type direction4(1, -4);
- point_type direction5(5, -1);
- std::vector<point_type> intersections;
-
- VU::intersect(origin, direction1_1, VU::SEGMENT, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 2);
- BOOST_CHECK_EQUAL(intersections[0].x() == 0 && intersections[0].y() == 2, true);
- BOOST_CHECK_EQUAL(intersections[1].x() == 3 && intersections[1].y() == -1, true);
- intersections.clear();
-
- VU::intersect(origin, direction1_2, VU::SEGMENT, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 1);
- BOOST_CHECK_EQUAL(intersections[0].x() == 0 && intersections[0].y() == 2, true);
- intersections.clear();
-
- VU::intersect(origin, direction1_3, VU::SEGMENT, rect, intersections);
- BOOST_CHECK_EQUAL(intersections.empty(), true);
- intersections.clear();
-
- VU::intersect(origin, direction2, VU::SEGMENT, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 2);
- BOOST_CHECK_EQUAL(intersections[0].x() == 0 && intersections[0].y() == 1, true);
- BOOST_CHECK_EQUAL(intersections[1].x() == 1 && intersections[1].y() == -1, true);
- intersections.clear();
-
- VU::intersect(origin, direction3, VU::SEGMENT, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 1);
- BOOST_CHECK_EQUAL(intersections[0].x() == 1 && intersections[0].y() == 2, true);
- intersections.clear();
-
- VU::intersect(origin, direction4, VU::SEGMENT, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 1);
- BOOST_CHECK_EQUAL(intersections[0].x() == 0 && intersections[0].y() == -1, true);
- intersections.clear();
-
- VU::intersect(origin, direction5, VU::SEGMENT, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 1);
- BOOST_CHECK_EQUAL(intersections[0].x() == 4 && intersections[0].y() == 2, true);
- intersections.clear();
-}
-
-BOOST_AUTO_TEST_CASE(segment_clipping_test2) {
- rect_type rect(0, -1, 4, 3);
- std::vector<point_type> intersections;
- point_type origin(2, 1);
-
- for (int i = -50; i <= 50; i++)
- for (int j = -50; j <= 50; j++) {
- intersections.clear();
- point_type direction(i, j);
- VU::intersect(origin, direction, VU::SEGMENT, rect, intersections);
- if (abs(i) >= 2 || abs(j) >= 2)
- BOOST_CHECK_EQUAL(SZ(intersections), 1);
- else
- BOOST_CHECK_EQUAL(SZ(intersections), 0);
- }
-}
-
-BOOST_AUTO_TEST_CASE(segment_clipping_test3) {
- rect_type rect(0, -1, 4, 3);
- std::vector<point_type> intersections;
- point_type origin(2, 1);
-
- for (int i = -50; i <= 50; i++)
- for (int j = -50; j <= 50; j++) {
- intersections.clear();
- double x = 1.0 * i / 26;
- double y = 1.0 * j / 26;
- point_type direction(x, y);
- VU::intersect(origin, direction, VU::SEGMENT, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 0);
- }
-}
-
-// Test ray clipping.
-BOOST_AUTO_TEST_CASE(ray_clipping_test1) {
- rect_type rect(0, -1, 4, 2);
- point_type origin(-1, 3);
- point_type direction1(2, -2);
- point_type direction2(2, -4);
- point_type direction3(2, -1);
- point_type direction4(1, -4);
- point_type direction5(5, -1);
- std::vector<point_type> intersections;
-
- VU::intersect(origin, direction1, VU::RAY, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 2);
- BOOST_CHECK_EQUAL(intersections[0].x() == 0 && intersections[0].y() == 2, true);
- BOOST_CHECK_EQUAL(intersections[1].x() == 3 && intersections[1].y() == -1, true);
- intersections.clear();
-
- VU::intersect(origin, direction2, VU::RAY, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 2);
- BOOST_CHECK_EQUAL(intersections[0].x() == 0 && intersections[0].y() == 1, true);
- BOOST_CHECK_EQUAL(intersections[1].x() == 1 && intersections[1].y() == -1, true);
- intersections.clear();
-
- VU::intersect(origin, direction3, VU::RAY, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 2);
- BOOST_CHECK_EQUAL(intersections[0].x() == 1 && intersections[0].y() == 2, true);
- BOOST_CHECK_EQUAL(intersections[1].x() == 4 && intersections[1].y() == 0.5, true);
- intersections.clear();
-
- VU::intersect(origin, direction4, VU::RAY, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 1);
- BOOST_CHECK_EQUAL(intersections[0].x() == 0 && intersections[0].y() == -1, true);
- intersections.clear();
-
- VU::intersect(origin, direction5, VU::RAY, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 1);
- BOOST_CHECK_EQUAL(intersections[0].x() == 4 && intersections[0].y() == 2, true);
- intersections.clear();
-}
-
-BOOST_AUTO_TEST_CASE(ray_clipping_test2) {
- rect_type rect(0, -1, 4, 3);
- std::vector<point_type> intersections;
- point_type origin(2, 1);
-
- for (int i = -50; i <= 50; i++)
- for (int j = -50; j <= 50; j++) {
- if (!i && !j) continue;
- intersections.clear();
- double x = 1.0 * i / 26;
- double y = 1.0 * j / 26;
- point_type direction(x, y);
- VU::intersect(origin, direction, VU::RAY, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 1);
- }
-}
-
-// Test line clipping.
-BOOST_AUTO_TEST_CASE(line_clipping_test1) {
- rect_type rect(0, -1, 4, 2);
- point_type origin(-1, 3);
- point_type direction1(-1, 1);
- point_type direction2(-1, 2);
- point_type direction3(-2, 1);
- point_type direction4(-1, 4);
- point_type direction5(-5, 1);
- std::vector<point_type> intersections;
-
- VU::intersect(origin, direction1, VU::LINE, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 2);
- BOOST_CHECK_EQUAL(intersections[0].x() == 3 && intersections[0].y() == -1, true);
- BOOST_CHECK_EQUAL(intersections[1].x() == 0 && intersections[1].y() == 2, true);
- intersections.clear();
-
- VU::intersect(origin, direction2, VU::LINE, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 2);
- BOOST_CHECK_EQUAL(intersections[0].x() == 1 && intersections[0].y() == -1, true);
- BOOST_CHECK_EQUAL(intersections[1].x() == 0 && intersections[1].y() == 1, true);
- intersections.clear();
-
- VU::intersect(origin, direction3, VU::LINE, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 2);
- BOOST_CHECK_EQUAL(intersections[0].x() == 4 && intersections[0].y() == 0.5, true);
- BOOST_CHECK_EQUAL(intersections[1].x() == 1 && intersections[1].y() == 2, true);
- intersections.clear();
-
- VU::intersect(origin, direction4, VU::LINE, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 1);
- BOOST_CHECK_EQUAL(intersections[0].x() == 0 && intersections[0].y() == -1, true);
- intersections.clear();
-
- VU::intersect(origin, direction5, VU::LINE, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 1);
- BOOST_CHECK_EQUAL(intersections[0].x() == 4 && intersections[0].y() == 2, true);
- intersections.clear();
-}
-
-BOOST_AUTO_TEST_CASE(line_clipping_test2) {
- rect_type rect(0, -1, 4, 3);
- std::vector<point_type> intersections;
- point_type origin(2, 1);
-
- for (int i = -50; i <= 50; i++)
- for (int j = -50; j <= 50; j++) {
- if (!i && !j) continue;
- intersections.clear();
- double x = 1.0 * i / 26;
- double y = 1.0 * j / 26;
- point_type direction(x, y);
- VU::intersect(origin, direction, VU::LINE, rect, intersections);
- BOOST_CHECK_EQUAL(SZ(intersections), 2);
- }
-}
Modified: sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp (original)
+++ sandbox/gtl/libs/polygon/test/voronoi_test_helper.hpp 2012-03-18 07:22:03 EDT (Sun, 18 Mar 2012)
@@ -41,7 +41,7 @@
typename Output::const_edge_iterator edge_it;
for (edge_it = output.edges().begin();
edge_it != output.edges().end(); edge_it++) {
- if (edge_it->is_bounded()) {
+ if (edge_it->is_finite()) {
const point_type &site_point = edge_it->cell()->point0();
const point_type &start_point = edge_it->vertex0()->vertex();
const point_type &end_point = edge_it->vertex1()->vertex();
@@ -126,7 +126,7 @@
typename Output::const_edge_iterator edge_it;
for (edge_it = output.edges().begin();
edge_it != output.edges().end(); edge_it++) {
- if (edge_it->is_bounded()) {
+ if (edge_it->is_finite()) {
const point_type &vertex0 = edge_it->vertex0()->vertex();
const point_type &vertex1 = edge_it->vertex1()->vertex();
if (comparator(vertex0, vertex1))
Modified: sandbox/gtl/libs/polygon/voronoi_example/voronoi_visualizer.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/voronoi_example/voronoi_visualizer.cpp (original)
+++ sandbox/gtl/libs/polygon/voronoi_example/voronoi_visualizer.cpp 2012-03-18 07:22:03 EDT (Sun, 18 Mar 2012)
@@ -71,7 +71,7 @@
for (const_edge_iterator it = vd_.edges().begin();
it != vd_.edges().end(); ++it) {
- if (!it->is_bounded()) {
+ if (!it->is_finite()) {
remove_exterior(&(*it));
}
}
@@ -155,7 +155,12 @@
continue;
}
std::vector<point_type> vec;
- voronoi_utils<coordinate_type>::discretize(*it, brect_, 1E-3, vec);
+ if (!it->is_finite())
+ voronoi_utils<coordinate_type>::clip(*it, brect_, vec);
+ else {
+ coordinate_type max_error = 1E-3 * (brect_.x_max() - brect_.x_min());
+ voronoi_utils<coordinate_type>::discretize(*it, max_error, vec);
+ }
for (int i = 0; i < static_cast<int>(vec.size()) - 1; ++i) {
glVertex2f(vec[i].x() - shift_.x(), vec[i].y() - shift_.y());
glVertex2f(vec[i+1].x() - shift_.x(), vec[i+1].y() - shift_.y());