123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186 |
- // 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
|