Chris@16: // Boost.Polygon library voronoi.hpp header file
Chris@16: 
Chris@16: //          Copyright Andrii Sydorchuk 2010-2012.
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: //    (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //          http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: // See http://www.boost.org for updates, documentation, and revision history.
Chris@16: 
Chris@16: #ifndef BOOST_POLYGON_VORONOI
Chris@16: #define BOOST_POLYGON_VORONOI
Chris@16: 
Chris@16: #include "isotropy.hpp"
Chris@16: #include "point_concept.hpp"
Chris@16: #include "segment_concept.hpp"
Chris@16: 
Chris@16: #include "voronoi_builder.hpp"
Chris@16: #include "voronoi_diagram.hpp"
Chris@16: 
Chris@16: // Public methods to compute Voronoi diagram of a set of points and segments.
Chris@16: // Coordinates of the points and of the endpoints of the segments should belong
Chris@16: // to the 32-bit signed integer range [-2^31, 2^31-1]. To use wider input
Chris@16: // coordinate range voronoi_builder configuration via coordinate type traits
Chris@16: // is required.
Chris@16: // Complexity - O(N*logN), memory usage - O(N), N - number of input objects.
Chris@16: namespace boost {
Chris@16: namespace polygon {
Chris@16: 
Chris@16: template <typename Point, typename VB>
Chris@16: typename enable_if<
Chris@16:   typename gtl_if<
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<Point>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16:   std::size_t
Chris@16: >::type insert(const Point& point, VB* vb) {
Chris@16:   return vb->insert_point(x(point), y(point));
Chris@16: }
Chris@16: 
Chris@16: template <typename PointIterator, typename VB>
Chris@16: typename enable_if<
Chris@16:   typename gtl_if<
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<
Chris@16:         typename std::iterator_traits<PointIterator>::value_type
Chris@16:       >::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16:   void
Chris@16: >::type insert(const PointIterator first, const PointIterator last, VB* vb) {
Chris@16:   for (PointIterator it = first; it != last; ++it) {
Chris@16:     insert(*it, vb);
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: template <typename Segment, typename VB>
Chris@16: typename enable_if<
Chris@16:   typename gtl_if<
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<Segment>::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16:   std::size_t
Chris@16: >::type insert(const Segment& segment, VB* vb) {
Chris@16:   return vb->insert_segment(
Chris@16:       x(low(segment)), y(low(segment)),
Chris@16:       x(high(segment)), y(high(segment)));
Chris@16: }
Chris@16: 
Chris@16: template <typename SegmentIterator, typename VB>
Chris@16: typename enable_if<
Chris@16:   typename gtl_if<
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<
Chris@16:         typename std::iterator_traits<SegmentIterator>::value_type
Chris@16:       >::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16:   void
Chris@16: >::type insert(const SegmentIterator first,
Chris@16:                const SegmentIterator last,
Chris@16:                VB* vb) {
Chris@16:   for (SegmentIterator it = first; it != last; ++it) {
Chris@16:     insert(*it, vb);
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: template <typename PointIterator, typename VD>
Chris@16: typename enable_if<
Chris@16:   typename gtl_if<
Chris@16:     typename is_point_concept<
Chris@16:       typename geometry_concept<
Chris@16:         typename std::iterator_traits<PointIterator>::value_type
Chris@16:       >::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16:   void
Chris@16: >::type construct_voronoi(const PointIterator first,
Chris@16:                           const PointIterator last,
Chris@16:                           VD* vd) {
Chris@16:   default_voronoi_builder builder;
Chris@16:   insert(first, last, &builder);
Chris@16:   builder.construct(vd);
Chris@16: }
Chris@16: 
Chris@16: template <typename SegmentIterator, typename VD>
Chris@16: typename enable_if<
Chris@16:   typename gtl_if<
Chris@16:     typename is_segment_concept<
Chris@16:       typename geometry_concept<
Chris@16:         typename std::iterator_traits<SegmentIterator>::value_type
Chris@16:       >::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16:   void
Chris@16: >::type construct_voronoi(const SegmentIterator first,
Chris@16:                           const SegmentIterator last,
Chris@16:                           VD* vd) {
Chris@16:   default_voronoi_builder builder;
Chris@16:   insert(first, last, &builder);
Chris@16:   builder.construct(vd);
Chris@16: }
Chris@16: 
Chris@16: template <typename PointIterator, typename SegmentIterator, typename VD>
Chris@16: typename enable_if<
Chris@16:   typename gtl_and<
Chris@16:     typename gtl_if<
Chris@16:       typename is_point_concept<
Chris@16:         typename geometry_concept<
Chris@16:           typename std::iterator_traits<PointIterator>::value_type
Chris@16:         >::type
Chris@16:       >::type
Chris@16:     >::type,
Chris@16:     typename gtl_if<
Chris@16:       typename is_segment_concept<
Chris@16:         typename geometry_concept<
Chris@16:           typename std::iterator_traits<SegmentIterator>::value_type
Chris@16:         >::type
Chris@16:       >::type
Chris@16:     >::type
Chris@16:   >::type,
Chris@16:   void
Chris@16: >::type construct_voronoi(const PointIterator p_first,
Chris@16:                           const PointIterator p_last,
Chris@16:                           const SegmentIterator s_first,
Chris@16:                           const SegmentIterator s_last,
Chris@16:                           VD* vd) {
Chris@16:   default_voronoi_builder builder;
Chris@16:   insert(p_first, p_last, &builder);
Chris@16:   insert(s_first, s_last, &builder);
Chris@16:   builder.construct(vd);
Chris@16: }
Chris@16: }  // polygon
Chris@16: }  // boost
Chris@16: 
Chris@16: #endif  // BOOST_POLYGON_VORONOI