[Boost-commit] svn:boost r77365 - in sandbox/gtl: boost/polygon libs/polygon/test libs/polygon/voronoi_example

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());