187 lines
6.7 KiB
C++
187 lines
6.7 KiB
C++
// 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
|