boost/polygon/voronoi.hpp

   1 // Boost.Polygon library voronoi.hpp header file
   2
   3 //          Copyright Andrii Sydorchuk 2010-2012.
   4 // Distributed under the Boost Software License, Version 1.0.
   5 //    (See accompanying file LICENSE_1_0.txt or copy at
   6 //          http://www.boost.org/LICENSE_1_0.txt)
   7
   8 // See http://www.boost.org for updates, documentation, and revision history.
   9
  10 #ifndef BOOST_POLYGON_VORONOI
  11 #define BOOST_POLYGON_VORONOI
  12
  13 #include "isotropy.hpp"
  14 #include "point_concept.hpp"
  15 #include "segment_concept.hpp"
  16
  17 #include "voronoi_builder.hpp"
  18 #include "voronoi_diagram.hpp"
  19
  20 // Public methods to compute Voronoi diagram of a set of points and segments.
  21 // Coordinates of the points and of the endpoints of the segments should belong
  22 // to the 32-bit signed integer range [-2^31, 2^31-1]. To use wider input
  23 // coordinate range voronoi_builder configuration via coordinate type traits
  24 // is required.
  25 // Complexity - O(N*logN), memory usage - O(N), N - number of input objects.
  26 namespace boost {
  27 namespace polygon {
  28
  29 template <typename Point, typename VB>
  30 typename enable_if<
  31   typename gtl_if<
  32     typename is_point_concept<
  33       typename geometry_concept<Point>::type
  34     >::type
  35   >::type,
  36   std::size_t
  37 >::type insert(const Point& point, VB* vb) {
  38   return vb->insert_point(x(point), y(point));
  39 }
  40
  41 template <typename PointIterator, typename VB>
  42 typename enable_if<
  43   typename gtl_if<
  44     typename is_point_concept<
  45       typename geometry_concept<
  46         typename std::iterator_traits<PointIterator>::value_type
  47       >::type
  48     >::type
  49   >::type,
  50   void
  51 >::type insert(const PointIterator first, const PointIterator last, VB* vb) {
  52   for (PointIterator it = first; it != last; ++it) {
  53     insert(*it, vb);
  54   }
  55 }
  56
  57 template <typename Segment, typename VB>
  58 typename enable_if<
  59   typename gtl_if<
  60     typename is_segment_concept<
  61       typename geometry_concept<Segment>::type
  62     >::type
  63   >::type,
  64   std::size_t
  65 >::type insert(const Segment& segment, VB* vb) {
  66   return vb->insert_segment(
  67       x(low(segment)), y(low(segment)),
  68       x(high(segment)), y(high(segment)));
  69 }
  70
  71 template <typename SegmentIterator, typename VB>
  72 typename enable_if<
  73   typename gtl_if<
  74     typename is_segment_concept<
  75       typename geometry_concept<
  76         typename std::iterator_traits<SegmentIterator>::value_type
  77       >::type
  78     >::type
  79   >::type,
  80   void
  81 >::type insert(const SegmentIterator first,
  82                const SegmentIterator last,
  83                VB* vb) {
  84   for (SegmentIterator it = first; it != last; ++it) {
  85     insert(*it, vb);
  86   }
  87 }
  88
  89 template <typename PointIterator, typename VD>
  90 typename enable_if<
  91   typename gtl_if<
  92     typename is_point_concept<
  93       typename geometry_concept<
  94         typename std::iterator_traits<PointIterator>::value_type
  95       >::type
  96     >::type
  97   >::type,
  98   void
  99 >::type construct_voronoi(const PointIterator first,
 100                           const PointIterator last,
 101                           VD* vd) {
 102   default_voronoi_builder builder;
 103   insert(first, last, &builder);
 104   builder.construct(vd);
 105 }
 106
 107 template <typename SegmentIterator, typename VD>
 108 typename enable_if<
 109   typename gtl_if<
 110     typename is_segment_concept<
 111       typename geometry_concept<
 112         typename std::iterator_traits<SegmentIterator>::value_type
 113       >::type
 114     >::type
 115   >::type,
 116   void
 117 >::type construct_voronoi(const SegmentIterator first,
 118                           const SegmentIterator last,
 119                           VD* vd) {
 120   default_voronoi_builder builder;
 121   insert(first, last, &builder);
 122   builder.construct(vd);
 123 }
 124
 125 template <typename PointIterator, typename SegmentIterator, typename VD>
 126 typename enable_if<
 127   typename gtl_and<
 128     typename gtl_if<
 129       typename is_point_concept<
 130         typename geometry_concept<
 131           typename std::iterator_traits<PointIterator>::value_type
 132         >::type
 133       >::type
 134     >::type,
 135     typename gtl_if<
 136       typename is_segment_concept<
 137         typename geometry_concept<
 138           typename std::iterator_traits<SegmentIterator>::value_type
 139         >::type
 140       >::type
 141     >::type
 142   >::type,
 143   void
 144 >::type construct_voronoi(const PointIterator p_first,
 145                           const PointIterator p_last,
 146                           const SegmentIterator s_first,
 147                           const SegmentIterator s_last,
 148                           VD* vd) {
 149   default_voronoi_builder builder;
 150   insert(p_first, p_last, &builder);
 151   insert(s_first, s_last, &builder);
 152   builder.construct(vd);
 153 }
 154 }  // polygon
 155 }  // boost
 156
 157 #endif  // BOOST_POLYGON_VORONOI