libs/polygon/example/voronoi_visual_utils.hpp
// Boost.Polygon library voronoi_graphic_utils.hpp header 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. #ifndef BOOST_POLYGON_VORONOI_VISUAL_UTILS #define BOOST_POLYGON_VORONOI_VISUAL_UTILS #include <stack> #include <vector> #include <boost/polygon/isotropy.hpp> #include <boost/polygon/point_concept.hpp> #include <boost/polygon/segment_concept.hpp> #include <boost/polygon/rectangle_concept.hpp> namespace boost { namespace polygon { // Utilities class, that contains set of routines handful for visualization. template <typename CT> class voronoi_visual_utils { public: // Discretize parabolic Voronoi edge. // Parabolic Voronoi edges are always formed by one point and one segment // from the initial input set. // // Args: // point: input point. // segment: input segment. // max_dist: maximum discretization distance. // discretization: point discretization of the given Voronoi edge. // // Template arguments: // InCT: coordinate type of the input geometries (usually integer). // Point: point type, should model point concept. // Segment: segment type, should model segment concept. // // Important: // discretization should contain both edge endpoints initially. template <class InCT1, class InCT2, template<class> class Point, template<class> class Segment> static typename enable_if< typename gtl_and< typename gtl_if< typename is_point_concept< typename geometry_concept< Point<InCT1> >::type >::type >::type, typename gtl_if< typename is_segment_concept< typename geometry_concept< Segment<InCT2> >::type >::type >::type >::type, void >::type discretize( const Point<InCT1>& point, const Segment<InCT2>& segment, const CT max_dist, std::vector< Point<CT> >* discretization) { // 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. CT segm_vec_x = cast(x(high(segment))) - cast(x(low(segment))); CT segm_vec_y = cast(y(high(segment))) - cast(y(low(segment))); CT 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. CT projection_start = sqr_segment_length * get_point_projection((*discretization)[0], segment); CT projection_end = sqr_segment_length * get_point_projection((*discretization)[1], segment); // Compute parabola parameters in the transformed space. // Parabola has next representation: // f(x) = ((x-rot_x)^2 + rot_y^2) / (2.0*rot_y). CT point_vec_x = cast(x(point)) - cast(x(low(segment))); CT point_vec_y = cast(y(point)) - cast(y(low(segment))); CT rot_x = segm_vec_x * point_vec_x + segm_vec_y * point_vec_y; CT rot_y = segm_vec_x * point_vec_y - segm_vec_y * point_vec_x; // Save the last point. Point<CT> last_point = (*discretization)[1]; discretization->pop_back(); // Use stack to avoid recursion. std::stack<CT> point_stack; point_stack.push(projection_end); CT cur_x = projection_start; CT cur_y = parabola_y(cur_x, rot_x, rot_y); // Adjust max_dist parameter in the transformed space. const CT max_dist_transformed = max_dist * max_dist * sqr_segment_length; while (!point_stack.empty()) { CT new_x = point_stack.top(); CT 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. CT mid_x = (new_y - cur_y) / (new_x - cur_x) * rot_y + rot_x; CT mid_y = parabola_y(mid_x, rot_x, rot_y); // Compute maximum distance between the given parabolic arc // and line segment that discretize it. CT 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_transformed) { // Distance between parabola and line segment is less than max_dist. point_stack.pop(); CT inter_x = (segm_vec_x * new_x - segm_vec_y * new_y) / sqr_segment_length + cast(x(low(segment))); CT inter_y = (segm_vec_x * new_y + segm_vec_y * new_x) / sqr_segment_length + cast(y(low(segment))); discretization->push_back(Point<CT>(inter_x, inter_y)); cur_x = new_x; cur_y = new_y; } else { point_stack.push(mid_x); } } // Update last point. discretization->back() = last_point; } private: // Compute y(x) = ((x - a) * (x - a) + b * b) / (2 * b). static CT parabola_y(CT x, CT a, CT b) { return ((x - a) * (x - a) + b * b) / (b + b); } // 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. The assumption is made that projection of // the point lies between the start-point and endpoint of the segment. template <class InCT, template<class> class Point, template<class> class Segment> static typename enable_if< typename gtl_and< typename gtl_if< typename is_point_concept< typename geometry_concept< Point<int> >::type >::type >::type, typename gtl_if< typename is_segment_concept< typename geometry_concept< Segment<long> >::type >::type >::type >::type, CT >::type get_point_projection( const Point<CT>& point, const Segment<InCT>& segment) { CT segment_vec_x = cast(x(high(segment))) - cast(x(low(segment))); CT segment_vec_y = cast(y(high(segment))) - cast(y(low(segment))); CT point_vec_x = x(point) - cast(x(low(segment))); CT point_vec_y = y(point) - cast(y(low(segment))); CT sqr_segment_length = segment_vec_x * segment_vec_x + segment_vec_y * segment_vec_y; CT vec_dot = segment_vec_x * point_vec_x + segment_vec_y * point_vec_y; return vec_dot / sqr_segment_length; } template <typename InCT> static CT cast(const InCT& value) { return static_cast<CT>(value); } }; } } #endif // BOOST_POLYGON_VORONOI_VISUAL_UTILS