Subject: [Boost-commit] svn:boost r77242 - in sandbox/gtl: boost/polygon boost/polygon/detail libs/polygon/test libs/polygon/voronoi_example
From: sydorchuk.andriy_at_[hidden]
Date: 2012-03-05 17:42:08
Author: asydorchuk
Date: 2012-03-05 17:42:07 EST (Mon, 05 Mar 2012)
New Revision: 77242
URL: http://svn.boost.org/trac/boost/changeset/77242
Log:
Updating utilities terminology.
Cosmetic changes.
Text files modified:
sandbox/gtl/boost/polygon/detail/voronoi_ctypes.hpp | 4
sandbox/gtl/boost/polygon/detail/voronoi_predicates.hpp | 32
sandbox/gtl/boost/polygon/voronoi.hpp | 4
sandbox/gtl/boost/polygon/voronoi_diagram.hpp | 3
sandbox/gtl/boost/polygon/voronoi_utils.hpp | 758 +++++++++++++++++++--------------------
sandbox/gtl/libs/polygon/test/voronoi_clipping_test.cpp | 44 +-
sandbox/gtl/libs/polygon/voronoi_example/voronoi_visualizer.cpp | 13
7 files changed, 416 insertions(+), 442 deletions(-)
Modified: sandbox/gtl/boost/polygon/detail/voronoi_ctypes.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_ctypes.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_ctypes.hpp 2012-03-05 17:42:07 EST (Mon, 05 Mar 2012)
@@ -32,13 +32,13 @@
template <>
struct ulp_comparison<fpt64> {
- enum kResult {
+ enum Result {
LESS = -1,
EQUAL = 0,
MORE = 1
};
- kResult operator()(fpt64 a, fpt64 b, unsigned int maxUlps) const {
+ Result operator()(fpt64 a, fpt64 b, unsigned int maxUlps) const {
uint64 ll_a, ll_b;
// Reinterpret double bits as 64-bit signed integer.
Modified: sandbox/gtl/boost/polygon/detail/voronoi_predicates.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_predicates.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_predicates.hpp 2012-03-05 17:42:07 EST (Mon, 05 Mar 2012)
@@ -76,7 +76,7 @@
typedef struct orientation_test {
public:
// Represents orientation test result.
- enum kResult {
+ enum Orientation {
RIGHT = -1,
COLLINEAR = 0,
LEFT = 1
@@ -85,21 +85,21 @@
// Value is a determinant of two vectors (e.g. x1 * y2 - x2 * y1).
// Return orientation based on the sign of the determinant.
template <typename T>
- static kResult eval(T value) {
+ static Orientation eval(T value) {
if (is_zero(value)) return COLLINEAR;
return (is_neg(value)) ? RIGHT : LEFT;
}
template <typename T>
- static kResult eval(T dif_x1_, T dif_y1_, T dif_x2_, T dif_y2_) {
+ static Orientation eval(T dif_x1_, T dif_y1_, T dif_x2_, T dif_y2_) {
return eval(robust_cross_product(dif_x1_, dif_y1_,
dif_x2_, dif_y2_));
}
template <typename Point>
- static kResult eval(const Point &point1,
- const Point &point2,
- const Point &point3) {
+ static Orientation eval(const Point &point1,
+ const Point &point2,
+ const Point &point3) {
int_x2_type dx1 = static_cast<int_x2_type>(point1.x()) -
static_cast<int_x2_type>(point2.x());
int_x2_type dx2 = static_cast<int_x2_type>(point2.x()) -
@@ -161,34 +161,34 @@
}
bool operator()(const site_type &lhs, const circle_type &rhs) const {
- typename ulp_cmp_type::kResult xCmp =
+ typename ulp_cmp_type::Result xCmp =
ulp_cmp(to_fpt(lhs.x()), to_fpt(rhs.lower_x()), ULPS);
if (xCmp != ulp_cmp_type::EQUAL) {
return xCmp == ulp_cmp_type::LESS;
}
- typename ulp_cmp_type::kResult yCmp =
+ typename ulp_cmp_type::Result yCmp =
ulp_cmp(to_fpt(lhs.y()), to_fpt(rhs.lower_y()), ULPS);
return yCmp == ulp_cmp_type::LESS;
}
bool operator()(const circle_type &lhs, const site_type &rhs) const {
- typename ulp_cmp_type::kResult xCmp =
+ typename ulp_cmp_type::Result xCmp =
ulp_cmp(to_fpt(lhs.lower_x()), to_fpt(rhs.x()), ULPS);
if (xCmp != ulp_cmp_type::EQUAL) {
return xCmp == ulp_cmp_type::LESS;
}
- typename ulp_cmp_type::kResult yCmp =
+ typename ulp_cmp_type::Result yCmp =
ulp_cmp(to_fpt(lhs.lower_y()), to_fpt(rhs.y()), ULPS);
return yCmp == ulp_cmp_type::LESS;
}
bool operator()(const circle_type &lhs, const circle_type &rhs) const {
- typename ulp_cmp_type::kResult xCmp =
+ typename ulp_cmp_type::Result xCmp =
ulp_cmp(to_fpt(lhs.lower_x()), to_fpt(rhs.lower_x()), ULPSx2);
if (xCmp != ulp_cmp_type::EQUAL) {
return xCmp == ulp_cmp_type::LESS;
}
- typename ulp_cmp_type::kResult yCmp =
+ typename ulp_cmp_type::Result yCmp =
ulp_cmp(to_fpt(lhs.lower_y()), to_fpt(rhs.lower_y()), ULPSx2);
return yCmp == ulp_cmp_type::LESS;
}
@@ -350,7 +350,7 @@
return LESS;
return UNDEFINED;
} else {
- typename ot::kResult orientation = ot::eval(a, b, dif_x, dif_y);
+ typename ot::Orientation orientation = ot::eval(a, b, dif_x, dif_y);
if (orientation == ot::LEFT) {
if (!right_site.is_inverse())
return reverse_order ? LESS : UNDEFINED;
@@ -360,7 +360,7 @@
fpt_type fast_left_expr = a * (dif_y + dif_x) * (dif_y - dif_x);
fpt_type fast_right_expr = (to_fpt(2.0) * b) * dif_x * dif_y;
- typename ulp_cmp_type::kResult expr_cmp = ulp_cmp(fast_left_expr, fast_right_expr, 4);
+ typename ulp_cmp_type::Result expr_cmp = ulp_cmp(fast_left_expr, fast_right_expr, 4);
if (expr_cmp != ulp_cmp_type::EQUAL) {
if ((expr_cmp == ulp_cmp_type::MORE) ^ reverse_order)
return reverse_order ? LESS : MORE;
@@ -465,9 +465,9 @@
const site_type &site3,
int segment_index) const {
if (segment_index != 2) {
- typename ot::kResult orient1 = ot::eval(site1.point0(),
+ typename ot::Orientation orient1 = ot::eval(site1.point0(),
site2.point0(), site3.point0(true));
- typename ot::kResult orient2 = ot::eval(site1.point0(),
+ typename ot::Orientation orient2 = ot::eval(site1.point0(),
site2.point0(), site3.point1(true));
if (segment_index == 1 && site1.x0() >= site2.x0()) {
if (orient1 != ot::RIGHT)
Modified: sandbox/gtl/boost/polygon/voronoi.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi.hpp 2012-03-05 17:42:07 EST (Mon, 05 Mar 2012)
@@ -49,8 +49,8 @@
static inline void construct_voronoi(
const PC &points, const SC &segments, VD *output) {
default_voronoi_builder builder;
- builder.insert_sites(
- points.begin(), points.end(), segments.begin(), segments.end());
+ builder.insert_sites(points.begin(), points.end(),
+ segments.begin(), segments.end());
builder.construct(output);
builder.clear();
}
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-05 17:42:07 EST (Mon, 05 Mar 2012)
@@ -21,9 +21,6 @@
// Forward declarations.
template <typename T>
- class voronoi_cell;
-
- template <typename T>
class voronoi_edge;
// Bounding rectangle data structure. Contains coordinates
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-05 17:42:07 EST (Mon, 05 Mar 2012)
@@ -24,405 +24,383 @@
template<>
struct voronoi_utils_traits<double> {
- typedef double fpt_type;
- typedef detail::point_2d<fpt_type> point_type;
- typedef std::vector<point_type> point_set_type;
- typedef bounding_rectangle<fpt_type> brect_type;
- typedef struct {
- template <typename CT>
- fpt_type operator()(const CT& value) {
- return static_cast<fpt_type>(value);
- }
- } ctype_converter_type;
+ typedef double coordinate_type;
+ typedef detail::point_2d<coordinate_type> point_type;
+ typedef std::vector<point_type> point_set_type;
+ typedef bounding_rectangle<coordinate_type> brect_type;
+ typedef struct {
+ template <typename CT>
+ coordinate_type operator()(const CT& value) {
+ return static_cast<coordinate_type>(value);
+ }
+ } ctype_converter_type;
};
// Voronoi output post-processing tools.
template <typename T, typename TRAITS = voronoi_utils_traits<T> >
class voronoi_utils {
public:
- typedef typename TRAITS::fpt_type fpt_type;
- typedef typename TRAITS::point_type point_type;
- typedef typename TRAITS::point_set_type point_set_type;
- typedef typename TRAITS::brect_type brect_type;
- typedef typename TRAITS::ctype_converter_type ctype_converter_type;
-
- // There are three different types of edges:
- // 1) Segment edge - has both endpoints;
- // 2) Ray edge - has one endpoint, infinite
- // in the positive direction;
- // 3) Line edge - is infinite in both directions.
- enum kEdgeType {
- SEGMENT = 0,
- RAY = 1,
- LINE = 2
- };
-
- // Get a view rectangle based on the voronoi bounding rectangle.
- template <typename CT>
- static brect_type get_view_rectangle(const bounding_rectangle<CT> &brect,
- fpt_type scale = 1.0) {
- fpt_type x_len = to_fpt(brect.x_max()) - to_fpt(brect.x_min());
- fpt_type y_len = to_fpt(brect.y_max()) - to_fpt(brect.y_min());
- fpt_type x_mid = to_fpt(brect.x_max()) + to_fpt(brect.x_min());
- fpt_type y_mid = to_fpt(brect.y_max()) + to_fpt(brect.y_min());
- x_mid *= to_fpt(0.5);
- y_mid *= to_fpt(0.5);
- fpt_type offset = (std::max)(x_len, y_len) * scale * to_fpt(0.5);
- brect_type new_brect(x_mid - offset, y_mid - offset,
- x_mid + offset, y_mid + offset);
- return new_brect;
- }
-
- // Compute intermediate points for the voronoi edge within the given
- // bounding rectangle. The assumption is made that voronoi rectangle
- // contains all the finite endpoints of the edge.
- // Max_error is the maximum distance (relative to the minor of two
- // rectangle sides) allowed between the parabola and line segments
- // that interpolate it.
- template <typename CT>
- static point_set_type get_point_interpolation(
- const voronoi_edge<CT> *edge,
- const bounding_rectangle<CT> &brect,
- fpt_type max_error) {
- // Retrieve the cell to the left of the current edge.
- const typename voronoi_edge<CT>::voronoi_cell_type *cell1 =
- edge->cell();
-
- // Retrieve the cell to the right of the current edge.
- const typename voronoi_edge<CT>::voronoi_cell_type *cell2 =
- edge->twin()->cell();
-
- // edge_points - contains intermediate points.
- point_set_type edge_points;
- 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.
- edge_points.push_back(
- get_point(edge->vertex0()->vertex()));
- edge_points.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.
- find_intersections(origin, direction, LINE,
- brect, edge_points);
-
- // Update endpoints in case edge is a ray.
- if (edge->vertex1() != NULL)
- edge_points[1] = get_point(edge->vertex1()->vertex());
- if (edge->vertex0() != NULL)
- edge_points[0] = get_point(edge->vertex0()->vertex());
- }
- } else {
- // point1 - site point;
- const 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()) ?
- get_point(cell1->point0()) : get_point(cell2->point0());
-
- // point3 - endpoint of the segment site;
- const 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.
- edge_points.push_back(
- get_point(edge->vertex0()->vertex()));
- edge_points.push_back(
- get_point(edge->vertex1()->vertex()));
- fpt_type max_dist = max_error * brect.min_len();
- fill_intermediate_points(point1, point2, point3,
- edge_points, max_dist);
- } else {
- // Edge is a ray or line.
- // Clip it with the bounding rectangle.
- fpt_type dir_x =
- (cell1->contains_segment() ^ (point1 == point3)) ?
- point3.y() - point2.y() : point2.y() - point3.y();
- fpt_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.
- find_intersections(point1, direction, LINE,
- brect, edge_points);
-
- // Update endpoints in case edge is a ray.
- if (edge->vertex1() != NULL)
- edge_points[1] = get_point(edge->vertex1()->vertex());
- if (edge->vertex0() != NULL)
- edge_points[0] = get_point(edge->vertex0()->vertex());
- }
- }
- return edge_points;
- }
-
- // Find edge-rectangle intersection points.
- // Edge is represented by its origin, direction and type.
- static void find_intersections(
- const point_type &origin, const point_type &direction,
- kEdgeType edge_type, const brect_type &brect,
- point_set_type &intersections) {
- // Find the center of the rectangle.
- fpt_type center_x = (brect.x_min() + brect.x_max()) * to_fpt(0.5);
- fpt_type center_y = (brect.y_min() + brect.y_max()) * to_fpt(0.5);
-
- // Find the half-diagonal vector of the rectangle.
- fpt_type len_x = brect.x_max() - center_x;
- fpt_type len_y = brect.y_max() - center_y;
-
- // Find the vector between the origin and the center of the
- // rectangle.
- fpt_type diff_x = origin.x() - center_x;
- fpt_type diff_y = origin.y() - center_y;
-
- // Find the vector perpendicular to the direction vector.
- fpt_type perp_x = direction.y();
- fpt_type perp_y = -direction.x();
-
- // Projection of the vector between the origin and the center of
- // the rectangle on the line perpendicular to the direction vector.
- fpt_type lexpr = magnitude(perp_x * diff_x + perp_y * diff_y);
-
- // Maximum projection among any of the half-diagonals of the
- // rectangle on the line perpendicular to the direction vector.
- fpt_type rexpr = magnitude(perp_x * len_x) + magnitude(perp_y * len_y);
-
- // Intersection check. Compare projections.
- if (lexpr > rexpr)
- return;
-
- // Intersection parameters. If fT[i]_used is true than:
- // origin + fT[i] * direction = intersection point, i = 0 .. 1.
- // For different edge types next fT values are acceptable:
- // Segment: [0; 1];
- // Ray: [0; infinity];
- // Line: [-infinity; infinity].
- bool fT0_used = false;
- bool fT1_used = false;
- fpt_type fT0 = 0;
- fpt_type fT1 = 0;
-
- // Check for the intersections with the lines
- // going through the sides of the bounding rectangle.
- clip_line(+direction.x(), -diff_x - len_x,
- fT0_used, fT1_used, fT0, fT1);
- clip_line(-direction.x(), +diff_x - len_x,
- fT0_used, fT1_used, fT0, fT1);
- clip_line(+direction.y(), -diff_y - len_y,
- fT0_used, fT1_used, fT0, fT1);
- clip_line(-direction.y(), +diff_y - len_y,
- fT0_used, fT1_used, fT0, fT1);
-
- // 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()));
- 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()));
- }
+ typedef typename TRAITS::coordinate_type coordinate_type;
+ typedef typename TRAITS::point_type point_type;
+ typedef typename TRAITS::point_set_type point_set_type;
+ 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) {
+ 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());
+ coordinate_type y_mid = to_fpt(brect.y_max()) + to_fpt(brect.y_min());
+ x_mid *= to_fpt(0.5);
+ y_mid *= to_fpt(0.5);
+ coordinate_type offset = (std::max)(x_len, y_len) * factor * to_fpt(0.5);
+ brect_type new_brect(x_mid - offset, y_mid - offset,
+ x_mid + offset, y_mid + offset);
+ 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.
+ template <typename CT>
+ static void discretize(const voronoi_edge<CT> &edge,
+ const bounding_rectangle<CT> &brect,
+ coordinate_type max_error,
+ point_set_type &discretization) {
+ // Retrieve the cell to the left of the current edge.
+ const typename voronoi_edge<CT>::voronoi_cell_type *cell1 = edge.cell();
+
+ // Retrieve the cell to the right of the current edge.
+ 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, 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 {
+ // point1 - site point;
+ const 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()) ?
+ get_point(cell1->point0()) : get_point(cell2->point0());
+
+ // point3 - endpoint of the segment site;
+ const 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 max_dist = max_error * brect.min_len();
+ fill_intermediate_points(point1, point2, point3,
+ discretization, max_dist);
+ } 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());
+ }
+ }
+ }
+
+ // 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) {
+ // 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);
+
+ // Find the half-diagonal vector of the rectangle.
+ coordinate_type len_x = brect.x_max() - center_x;
+ coordinate_type len_y = brect.y_max() - center_y;
+
+ // Find the vector between the origin and the center of the
+ // rectangle.
+ coordinate_type diff_x = origin.x() - center_x;
+ coordinate_type diff_y = origin.y() - center_y;
+
+ // Find the vector perpendicular to the direction vector.
+ coordinate_type perp_x = direction.y();
+ coordinate_type perp_y = -direction.x();
+
+ // Projection of the vector between the origin and the center of
+ // the rectangle on the line perpendicular to the direction vector.
+ coordinate_type lexpr = magnitude(perp_x * diff_x + perp_y * diff_y);
+
+ // 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);
+
+ // Intersection check. Compare projections.
+ if (lexpr > rexpr)
+ return;
+
+ // Intersection parameters. If fT[i]_used is true than:
+ // origin + fT[i] * direction = intersection point, i = 0 .. 1.
+ // For different edge types next fT values are acceptable:
+ // Segment: [0; 1];
+ // Ray: [0; infinity];
+ // Line: [-infinity; infinity].
+ bool fT0_used = false;
+ bool fT1_used = false;
+ coordinate_type fT0 = 0;
+ coordinate_type fT1 = 0;
+
+ // Check for the intersections with the lines
+ // going through the sides of the bounding rectangle.
+ clip_line(+direction.x(), -diff_x - len_x, fT0_used, fT1_used, fT0, fT1);
+ clip_line(-direction.x(), +diff_x - len_x, fT0_used, fT1_used, fT0, fT1);
+ clip_line(+direction.y(), -diff_y - len_y, fT0_used, fT1_used, fT0, fT1);
+ clip_line(-direction.y(), +diff_y - len_y, fT0_used, fT1_used, fT0, fT1);
+
+ // 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()));
+ 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();
+ voronoi_utils();
- template <typename P>
- static point_type get_point(const P &point) {
- fpt_type x = to_fpt(point.x());
- fpt_type y = to_fpt(point.y());
- return point_type(x, y);
- }
-
- // Find intermediate points of the parabola. Number of points
- // is defined by the value of max_dist parameter - maximum distance
- // between parabola and line segments that interpolate it.
- // Parabola is a locus of points equidistant from the point and segment
- // sites. intermediate_points should contain two initial endpoints
- // of the edge (voronoi vertices). Intermediate points are inserted
- // between the given two endpoints.
- // Max_dist is the maximum distance allowed between parabola and line
- // segments that interpolate 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,
- fpt_type max_dist) {
- // Check if bisector is a segment.
- if (point_site == segment_site_start ||
- point_site == segment_site_end)
- return;
-
- // 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.
- fpt_type segm_vec_x = segment_site_end.x() -
- segment_site_start.x();
- fpt_type segm_vec_y = segment_site_end.y() -
- segment_site_start.y();
- fpt_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.
- fpt_type projection_start = sqr_segment_length *
- get_point_projection(intermediate_points[0],
- segment_site_start,
- segment_site_end);
- fpt_type projection_end = sqr_segment_length *
- 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).
- fpt_type point_vec_x = point_site.x() - segment_site_start.x();
- fpt_type point_vec_y = point_site.y() - segment_site_start.y();
- fpt_type rot_x = segm_vec_x * point_vec_x +
- segm_vec_y * point_vec_y;
- fpt_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];
- intermediate_points.pop_back();
-
- // Use stack to avoid recursion.
- std::stack<fpt_type> point_stack;
- point_stack.push(projection_end);
- fpt_type cur_x = projection_start;
- fpt_type cur_y = parabola_y(cur_x, rot_x, rot_y);
-
- // Adjust max_dist parameter in the transformed space.
- max_dist *= max_dist * sqr_segment_length;
-
- while (!point_stack.empty()) {
- fpt_type new_x = point_stack.top();
- fpt_type new_y = parabola_y(new_x, rot_x, rot_y);
-
- // Compute coordinates of the point of the parabola that is
- // furthest from the current line segment.
- fpt_type mid_x = (new_y - cur_y) / (new_x - cur_x) * rot_y +
- rot_x;
- fpt_type mid_y = parabola_y(mid_x, rot_x, rot_y);
-
- // Compute maximum distance between the given parabolic arc
- // and line segment that interpolates it.
- fpt_type dist = (new_y - cur_y) * (mid_x - cur_x) -
- (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));
- if (dist <= max_dist) {
- // Distance between parabola and line segment is
- // not greater than max_dist.
- point_stack.pop();
- fpt_type inter_x =
- (segm_vec_x * new_x - segm_vec_y * new_y) /
- sqr_segment_length + segment_site_start.x();
- fpt_type inter_y =
- (segm_vec_x * new_y + segm_vec_y * new_x) /
- 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;
- } else {
- point_stack.push(mid_x);
- }
- }
-
- // Update last point.
- intermediate_points.back() = last_point;
- }
-
- // Compute y(x) = ((x - a) * (x - a) + b * b) / (2 * b).
- static fpt_type parabola_y(fpt_type x, fpt_type a, fpt_type b) {
- return ((x - a) * (x - a) + b * b) / (to_fpt(2.0) * b);
- }
-
- // Check whether extent is compatible with the edge type.
- static bool check_extent(fpt_type extent, kEdgeType etype) {
- switch (etype) {
- case SEGMENT:
- return extent >= to_fpt(0.0) &&
- extent <= to_fpt(1.0);
- case RAY: return extent >= to_fpt(0.0);
- case LINE: return true;
- }
- return true;
- }
-
- // Compute the absolute value.
- static inline fpt_type magnitude(fpt_type value) {
- if (value >= to_fpt(0.0))
- return value;
- return -value;
- }
-
- // Find fT min and max values: fT = numer / denom.
- static void clip_line(fpt_type denom, fpt_type numer,
- bool &fT0_used, bool &fT1_used,
- fpt_type &fT0, fpt_type &fT1) {
- if (denom > to_fpt(0.0)) {
- if (fT1_used && numer > denom * fT1)
- return;
- if (!fT0_used || numer > denom * fT0) {
- fT0_used = true;
- fT0 = numer / denom;
- }
- } else if (denom < to_fpt(0.0)) {
- if (fT0_used && numer > denom * fT0)
- return;
- if (!fT1_used || numer > denom * fT1) {
- fT1_used = true;
- fT1 = numer / denom;
- }
- }
- }
-
- // Get normalized length of the distance between:
- // 1) point projection onto the segment;
- // 2) start point of the segment.
- // Return this length divided by the segment length.
- // This is made to avoid sqrt computation during transformation from
- // the initial space to the transformed one and vice versa.
- // Assumption is made that projection of the point lies
- // between the start-point and endpoint of the segment.
- static fpt_type get_point_projection(
- const point_type &point,
- const point_type &segment_start,
- const point_type &segment_end) {
- fpt_type segment_vec_x = segment_end.x() - segment_start.x();
- fpt_type segment_vec_y = segment_end.y() - segment_start.y();
- fpt_type point_vec_x = point.x() - segment_start.x();
- fpt_type point_vec_y = point.y() - segment_start.y();
- fpt_type sqr_segment_length = segment_vec_x * segment_vec_x +
- segment_vec_y * segment_vec_y;
- fpt_type vec_dot = segment_vec_x * point_vec_x +
- segment_vec_y * point_vec_y;
- return vec_dot / sqr_segment_length;
- }
-
- template <typename CT>
- static fpt_type to_fpt(const CT& value) {
- static ctype_converter_type converter;
- return converter(value);
- }
+ 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);
+ }
+
+ // Find intermediate points of the parabola.
+ // Parabola is a locus of points equidistant from the point and segment
+ // sites. intermediate_points should contain two initial endpoints
+ // of the edge (voronoi vertices). Intermediate points are inserted
+ // 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;
+
+ // 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;
+
+ // 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);
+ coordinate_type projection_end = sqr_segment_length *
+ 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;
+
+ // Save the last point.
+ point_type last_point = intermediate_points[1];
+ intermediate_points.pop_back();
+
+ // Use stack to avoid recursion.
+ std::stack<coordinate_type> point_stack;
+ point_stack.push(projection_end);
+ coordinate_type cur_x = projection_start;
+ coordinate_type cur_y = parabola_y(cur_x, rot_x, rot_y);
+
+ // Adjust max_dist parameter in the transformed space.
+ max_dist *= max_dist * sqr_segment_length;
+
+ while (!point_stack.empty()) {
+ coordinate_type new_x = point_stack.top();
+ coordinate_type new_y = parabola_y(new_x, rot_x, rot_y);
+
+ // 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_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);
+ dist = dist * dist / ((new_y - cur_y) * (new_y - cur_y) +
+ (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();
+ coordinate_type inter_y = (segm_vec_x * new_y + segm_vec_y * new_x) /
+ 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;
+ } else {
+ point_stack.push(mid_x);
+ }
+ }
+
+ // Update last point.
+ intermediate_points.back() = last_point;
+ }
+
+ // 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) {
+ return ((x - a) * (x - a) + b * b) / (to_fpt(2.0) * b);
+ }
+
+ // Check whether extent is compatible with the edge type.
+ static bool check_extent(coordinate_type extent, EdgeType etype) {
+ switch (etype) {
+ case SEGMENT: return extent >= to_fpt(0.0) && extent <= to_fpt(1.0);
+ case RAY: return extent >= to_fpt(0.0);
+ case LINE: return true;
+ }
+ return true;
+ }
+
+ // Compute the absolute value.
+ static inline coordinate_type magnitude(coordinate_type value) {
+ return (value >= to_fpt(0.0)) ? value : -value;
+ }
+
+ // 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) {
+ if (denom > to_fpt(0.0)) {
+ if (fT1_used && numer > denom * fT1)
+ return;
+ if (!fT0_used || numer > denom * fT0) {
+ fT0_used = true;
+ fT0 = numer / denom;
+ }
+ } else if (denom < to_fpt(0.0)) {
+ if (fT0_used && numer > denom * fT0)
+ return;
+ if (!fT1_used || numer > denom * fT1) {
+ fT1_used = true;
+ fT1 = numer / denom;
+ }
+ }
+ }
+
+ // Get normalized length of the distance between:
+ // 1) point projection onto the segment;
+ // 2) start point of the segment.
+ // Return this length divided by the segment length.
+ // This is made to avoid sqrt computation during transformation from
+ // the initial space to the transformed one and vice versa.
+ // Assumption is made that projection of the point lies
+ // between the start-point and endpoint of the segment.
+ static coordinate_type get_point_projection(
+ const point_type &point,
+ const point_type &segment_start,
+ const point_type &segment_end) {
+ coordinate_type segment_vec_x = segment_end.x() - segment_start.x();
+ 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;
+ return vec_dot / sqr_segment_length;
+ }
+
+ template <typename CT>
+ static coordinate_type to_fpt(const CT& value) {
+ static ctype_converter_type converter;
+ return converter(value);
+ }
};
} // polygon
} // boost
Modified: sandbox/gtl/libs/polygon/test/voronoi_clipping_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_clipping_test.cpp (original)
+++ sandbox/gtl/libs/polygon/test/voronoi_clipping_test.cpp 2012-03-05 17:42:07 EST (Mon, 05 Mar 2012)
@@ -1,6 +1,6 @@
// Boost.Polygon library voronoi_clipping_test.cpp file
-// Copyright Andrii Sydorchuk 2010-2011.
+// 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)
@@ -32,38 +32,38 @@
point_type direction5(5, -1);
std::vector<point_type> intersections;
- VU::find_intersections(origin, direction1_1, VU::SEGMENT, rect, 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::find_intersections(origin, direction1_2, VU::SEGMENT, rect, intersections);
+ 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::find_intersections(origin, direction1_3, VU::SEGMENT, rect, intersections);
+ VU::intersect(origin, direction1_3, VU::SEGMENT, rect, intersections);
BOOST_CHECK_EQUAL(intersections.empty(), true);
intersections.clear();
- VU::find_intersections(origin, direction2, VU::SEGMENT, rect, intersections);
+ 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::find_intersections(origin, direction3, VU::SEGMENT, rect, intersections);
+ 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::find_intersections(origin, direction4, VU::SEGMENT, rect, intersections);
+ 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::find_intersections(origin, direction5, VU::SEGMENT, rect, intersections);
+ 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();
@@ -78,7 +78,7 @@
for (int j = -50; j <= 50; j++) {
intersections.clear();
point_type direction(i, j);
- VU::find_intersections(origin, direction, VU::SEGMENT, rect, intersections);
+ VU::intersect(origin, direction, VU::SEGMENT, rect, intersections);
if (abs(i) >= 2 || abs(j) >= 2)
BOOST_CHECK_EQUAL(SZ(intersections), 1);
else
@@ -97,7 +97,7 @@
double x = 1.0 * i / 26;
double y = 1.0 * j / 26;
point_type direction(x, y);
- VU::find_intersections(origin, direction, VU::SEGMENT, rect, intersections);
+ VU::intersect(origin, direction, VU::SEGMENT, rect, intersections);
BOOST_CHECK_EQUAL(SZ(intersections), 0);
}
}
@@ -113,30 +113,30 @@
point_type direction5(5, -1);
std::vector<point_type> intersections;
- VU::find_intersections(origin, direction1, VU::RAY, rect, 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::find_intersections(origin, direction2, VU::RAY, rect, intersections);
+ 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::find_intersections(origin, direction3, VU::RAY, rect, intersections);
+ 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::find_intersections(origin, direction4, VU::RAY, rect, intersections);
+ 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::find_intersections(origin, direction5, VU::RAY, rect, intersections);
+ 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();
@@ -154,7 +154,7 @@
double x = 1.0 * i / 26;
double y = 1.0 * j / 26;
point_type direction(x, y);
- VU::find_intersections(origin, direction, VU::RAY, rect, intersections);
+ VU::intersect(origin, direction, VU::RAY, rect, intersections);
BOOST_CHECK_EQUAL(SZ(intersections), 1);
}
}
@@ -170,30 +170,30 @@
point_type direction5(-5, 1);
std::vector<point_type> intersections;
- VU::find_intersections(origin, direction1, VU::LINE, rect, 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::find_intersections(origin, direction2, VU::LINE, rect, intersections);
+ 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::find_intersections(origin, direction3, VU::LINE, rect, intersections);
+ 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::find_intersections(origin, direction4, VU::LINE, rect, intersections);
+ 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::find_intersections(origin, direction5, VU::LINE, rect, intersections);
+ 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();
@@ -211,7 +211,7 @@
double x = 1.0 * i / 26;
double y = 1.0 * j / 26;
point_type direction(x, y);
- VU::find_intersections(origin, direction, VU::LINE, rect, intersections);
+ VU::intersect(origin, direction, VU::LINE, rect, intersections);
BOOST_CHECK_EQUAL(SZ(intersections), 2);
}
}
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-05 17:42:07 EST (Mon, 05 Mar 2012)
@@ -62,7 +62,7 @@
// Build voronoi diagram.
vb_.construct(&vd_);
- brect_ = voronoi_utils<coordinate_type>::get_view_rectangle(
+ brect_ = voronoi_utils<coordinate_type>::scale(
vd_.bounding_rectangle(), 1.4);
shift_ = point_type((brect_.x_min() + brect_.x_max()) * 0.5,
(brect_.y_min() + brect_.y_max()) * 0.5);
@@ -153,12 +153,11 @@
if (internal_edges_only_ && exterior_edges_set_.count(&(*it))) {
continue;
}
- std::vector<point_type> temp_v =
- voronoi_utils<coordinate_type>::get_point_interpolation(
- &(*it), brect_, 1E-3);
- for (int i = 0; i < static_cast<int>(temp_v.size()) - 1; ++i) {
- glVertex2f(temp_v[i].x() - shift_.x(), temp_v[i].y() - shift_.y());
- glVertex2f(temp_v[i+1].x() - shift_.x(), temp_v[i+1].y() - shift_.y());
+ std::vector<point_type> vec;
+ voronoi_utils<coordinate_type>::discretize(*it, brect_, 1E-3, 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());
}
}
glEnd();