FM / polygon

/usr/include/boost/polygon

Name	Size	Mode	Actions
detail/	-	0755	rm
gmp_override.hpp	3245	0644	edit dl rm
gtl.hpp	696	0644	edit dl rm
interval_concept.hpp	25993	0644	edit dl rm
interval_data.hpp	2701	0644	edit dl rm
interval_traits.hpp	1364	0644	edit dl rm
isotropy.hpp	17571	0644	edit dl rm
point_concept.hpp	12743	0644	edit dl rm
point_data.hpp	3252	0644	edit dl rm
point_traits.hpp	1328	0644	edit dl rm
polygon.hpp	2418	0644	edit dl rm
polygon_45_data.hpp	2330	0644	edit dl rm
polygon_45_set_concept.hpp	19393	0644	edit dl rm
polygon_45_set_data.hpp	78330	0644	edit dl rm
polygon_45_set_traits.hpp	6216	0644	edit dl rm
polygon_45_with_holes_data.hpp	3510	0644	edit dl rm
polygon_90_data.hpp	2888	0644	edit dl rm
polygon_90_set_concept.hpp	26923	0644	edit dl rm
polygon_90_set_data.hpp	44501	0644	edit dl rm
polygon_90_set_traits.hpp	16451	0644	edit dl rm
polygon_90_with_holes_data.hpp	3994	0644	edit dl rm
polygon_data.hpp	2218	0644	edit dl rm
polygon_set_concept.hpp	26570	0644	edit dl rm
polygon_set_data.hpp	40251	0644	edit dl rm
polygon_set_traits.hpp	5385	0644	edit dl rm
polygon_traits.hpp	74180	0644	edit dl rm
polygon_with_holes_data.hpp	3458	0644	edit dl rm
rectangle_concept.hpp	50898	0644	edit dl rm
rectangle_data.hpp	2120	0644	edit dl rm
rectangle_traits.hpp	1349	0644	edit dl rm
segment_concept.hpp	20086	0644	edit dl rm
segment_data.hpp	2772	0644	edit dl rm
segment_traits.hpp	1463	0644	edit dl rm
segment_utils.hpp	4963	0644	edit dl rm
transform.hpp	15004	0644	edit dl rm
voronoi.hpp	4511	0644	edit dl rm
voronoi_builder.hpp	19672	0644	edit dl rm
voronoi_diagram.hpp	19489	0644	edit dl rm
voronoi_geometry_type.hpp	1407	0644	edit dl rm

Edit: /usr/include/boost/polygon/voronoi_builder.hpp (19672B)

// Boost.Polygon library voronoi_builder.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_BUILDER
#define BOOST_POLYGON_VORONOI_BUILDER

#include <algorithm>
#include <map>
#include <queue>
#include <utility>
#include <vector>

#include "detail/voronoi_ctypes.hpp"
#include "detail/voronoi_predicates.hpp"
#include "detail/voronoi_structures.hpp"

#include "voronoi_geometry_type.hpp"

namespace boost {
namespace polygon {
// GENERAL INFO:
// The sweepline algorithm implementation to compute Voronoi diagram of
// points and non-intersecting segments (excluding endpoints).
// Complexity - O(N*logN), memory usage - O(N), where N is the total number
// of input geometries.
//
// CONTRACT:
// 1) Input geometries should have integral (e.g. int32, int64) coordinate type.
// 2) Input geometries should not intersect except their endpoints.
//
// IMPLEMENTATION DETAILS:
// Each input point creates one input site. Each input segment creates three
// input sites: two for its endpoints and one for the segment itself (this is
// made to simplify output construction). All the site objects are constructed
// and sorted at the algorithm initialization step. Priority queue is used to
// dynamically hold circle events. At each step of the algorithm execution the
// leftmost event is retrieved by comparing the current site event and the
// topmost element from the circle event queue. STL map (red-black tree)
// container was chosen to hold state of the beach line. The keys of the map
// correspond to the neighboring sites that form a bisector and values map to
// the corresponding Voronoi edges in the output data structure.
template <typename T,
          typename CTT = detail::voronoi_ctype_traits<T>,
          typename VP = detail::voronoi_predicates<CTT> >
class voronoi_builder {
 public:
  typedef typename CTT::int_type int_type;
  typedef typename CTT::fpt_type fpt_type;

voronoi_builder() : index_(0) {}

// Each point creates a single site event.
  std::size_t insert_point(const int_type& x, const int_type& y) {
    site_events_.push_back(site_event_type(x, y));
    site_events_.back().initial_index(index_);
    site_events_.back().source_category(SOURCE_CATEGORY_SINGLE_POINT);
    return index_++;
  }

// Each segment creates three site events that correspond to:
  //   1) the start point of the segment;
  //   2) the end point of the segment;
  //   3) the segment itself defined by its start point.
  std::size_t insert_segment(
      const int_type& x1, const int_type& y1,
      const int_type& x2, const int_type& y2) {
    // Set up start point site.
    point_type p1(x1, y1);
    site_events_.push_back(site_event_type(p1));
    site_events_.back().initial_index(index_);
    site_events_.back().source_category(SOURCE_CATEGORY_SEGMENT_START_POINT);

// Set up end point site.
    point_type p2(x2, y2);
    site_events_.push_back(site_event_type(p2));
    site_events_.back().initial_index(index_);
    site_events_.back().source_category(SOURCE_CATEGORY_SEGMENT_END_POINT);

// Set up segment site.
    if (point_comparison_(p1, p2)) {
      site_events_.push_back(site_event_type(p1, p2));
      site_events_.back().source_category(SOURCE_CATEGORY_INITIAL_SEGMENT);
    } else {
      site_events_.push_back(site_event_type(p2, p1));
      site_events_.back().source_category(SOURCE_CATEGORY_REVERSE_SEGMENT);
    }
    site_events_.back().initial_index(index_);
    return index_++;
  }

// Run sweepline algorithm and fill output data structure.
  template <typename OUTPUT>
  void construct(OUTPUT* output) {
    // Init structures.
    output->_reserve(site_events_.size());
    init_sites_queue();
    init_beach_line(output);

// The algorithm stops when there are no events to process.
    event_comparison_predicate event_comparison;
    while (!circle_events_.empty() ||
           !(site_event_iterator_ == site_events_.end())) {
      if (circle_events_.empty()) {
        process_site_event(output);
      } else if (site_event_iterator_ == site_events_.end()) {
        process_circle_event(output);
      } else {
        if (event_comparison(*site_event_iterator_,
                             circle_events_.top().first)) {
          process_site_event(output);
        } else {
          process_circle_event(output);
        }
      }
      while (!circle_events_.empty() &&
             !circle_events_.top().first.is_active()) {
        circle_events_.pop();
      }
    }
    beach_line_.clear();

// Finish construction.
    output->_build();
  }

void clear() {
    index_ = 0;
    site_events_.clear();
  }

private:
  typedef detail::point_2d<int_type> point_type;
  typedef detail::site_event<int_type> site_event_type;
  typedef typename std::vector<site_event_type>::const_iterator
    site_event_iterator_type;
  typedef detail::circle_event<fpt_type> circle_event_type;
  typedef typename VP::template point_comparison_predicate<point_type>
    point_comparison_predicate;
  typedef typename VP::
    template event_comparison_predicate<site_event_type, circle_event_type>
    event_comparison_predicate;
  typedef typename VP::
    template circle_formation_predicate<site_event_type, circle_event_type>
    circle_formation_predicate_type;
  typedef void edge_type;
  typedef detail::beach_line_node_key<site_event_type> key_type;
  typedef detail::beach_line_node_data<edge_type, circle_event_type>
    value_type;
  typedef typename VP::template node_comparison_predicate<key_type>
    node_comparer_type;
  typedef std::map< key_type, value_type, node_comparer_type > beach_line_type;
  typedef typename beach_line_type::iterator beach_line_iterator;
  typedef std::pair<circle_event_type, beach_line_iterator> event_type;
  typedef struct {
    bool operator()(const event_type& lhs, const event_type& rhs) const {
      return predicate(rhs.first, lhs.first);
    }
    event_comparison_predicate predicate;
  } event_comparison_type;
  typedef detail::ordered_queue<event_type, event_comparison_type>
    circle_event_queue_type;
  typedef std::pair<point_type, beach_line_iterator> end_point_type;

void init_sites_queue() {
    // Sort site events.
    std::sort(site_events_.begin(), site_events_.end(),
        event_comparison_predicate());

// Remove duplicates.
    site_events_.erase(std::unique(
        site_events_.begin(), site_events_.end()), site_events_.end());

// Index sites.
    for (std::size_t cur = 0; cur < site_events_.size(); ++cur) {
      site_events_[cur].sorted_index(cur);
    }

// Init site iterator.
    site_event_iterator_ = site_events_.begin();
  }

template <typename OUTPUT>
  void init_beach_line(OUTPUT* output) {
    if (site_events_.empty())
      return;
    if (site_events_.size() == 1) {
      // Handle single site event case.
      output->_process_single_site(site_events_[0]);
      ++site_event_iterator_;
    } else {
      int skip = 0;

while (site_event_iterator_ != site_events_.end() &&
             VP::is_vertical(site_event_iterator_->point0(),
                             site_events_.begin()->point0()) &&
             VP::is_vertical(*site_event_iterator_)) {
        ++site_event_iterator_;
        ++skip;
      }

if (skip == 1) {
        // Init beach line with the first two sites.
        init_beach_line_default(output);
      } else {
        // Init beach line with collinear vertical sites.
        init_beach_line_collinear_sites(output);
      }
    }
  }

// Init beach line with the two first sites.
  // The first site is always a point.
  template <typename OUTPUT>
  void init_beach_line_default(OUTPUT* output) {
    // Get the first and the second site event.
    site_event_iterator_type it_first = site_events_.begin();
    site_event_iterator_type it_second = site_events_.begin();
    ++it_second;
    insert_new_arc(
        *it_first, *it_first, *it_second, beach_line_.end(), output);
    // The second site was already processed. Move the iterator.
    ++site_event_iterator_;
  }

// Init beach line with collinear sites.
  template <typename OUTPUT>
  void init_beach_line_collinear_sites(OUTPUT* output) {
    site_event_iterator_type it_first = site_events_.begin();
    site_event_iterator_type it_second = site_events_.begin();
    ++it_second;
    while (it_second != site_event_iterator_) {
      // Create a new beach line node.
      key_type new_node(*it_first, *it_second);

// Update the output.
      edge_type* edge = output->_insert_new_edge(*it_first, *it_second).first;

// Insert a new bisector into the beach line.
      beach_line_.insert(beach_line_.end(),
          std::pair<key_type, value_type>(new_node, value_type(edge)));

// Update iterators.
      ++it_first;
      ++it_second;
    }
  }

void deactivate_circle_event(value_type* value) {
    if (value->circle_event()) {
      value->circle_event()->deactivate();
      value->circle_event(NULL);
    }
  }

template <typename OUTPUT>
  void process_site_event(OUTPUT* output) {
    // Get next site event to process.
    site_event_type site_event = *site_event_iterator_;

// Move site iterator.
    site_event_iterator_type last = site_event_iterator_ + 1;

// If a new site is an end point of some segment,
    // remove temporary nodes from the beach line data structure.
    if (!site_event.is_segment()) {
      while (!end_points_.empty() &&
             end_points_.top().first == site_event.point0()) {
        beach_line_iterator b_it = end_points_.top().second;
        end_points_.pop();
        beach_line_.erase(b_it);
      }
    } else {
      while (last != site_events_.end() &&
             last->is_segment() && last->point0() == site_event.point0())
        ++last;
    }

// Find the node in the binary search tree with left arc
    // lying above the new site point.
    key_type new_key(*site_event_iterator_);
    beach_line_iterator right_it = beach_line_.lower_bound(new_key);

for (; site_event_iterator_ != last; ++site_event_iterator_) {
      site_event = *site_event_iterator_;
      beach_line_iterator left_it = right_it;

// Do further processing depending on the above node position.
      // For any two neighboring nodes the second site of the first node
      // is the same as the first site of the second node.
      if (right_it == beach_line_.end()) {
        // The above arc corresponds to the second arc of the last node.
        // Move the iterator to the last node.
        --left_it;

// Get the second site of the last node
        const site_event_type& site_arc = left_it->first.right_site();

// Insert new nodes into the beach line. Update the output.
        right_it = insert_new_arc(
            site_arc, site_arc, site_event, right_it, output);

// Add a candidate circle to the circle event queue.
        // There could be only one new circle event formed by
        // a new bisector and the one on the left.
        activate_circle_event(left_it->first.left_site(),
                              left_it->first.right_site(),
                              site_event, right_it);
      } else if (right_it == beach_line_.begin()) {
        // The above arc corresponds to the first site of the first node.
        const site_event_type& site_arc = right_it->first.left_site();

// Insert new nodes into the beach line. Update the output.
        left_it = insert_new_arc(
            site_arc, site_arc, site_event, right_it, output);

// If the site event is a segment, update its direction.
        if (site_event.is_segment()) {
          site_event.inverse();
        }

// Add a candidate circle to the circle event queue.
        // There could be only one new circle event formed by
        // a new bisector and the one on the right.
        activate_circle_event(site_event, right_it->first.left_site(),
            right_it->first.right_site(), right_it);
        right_it = left_it;
      } else {
        // The above arc corresponds neither to the first,
        // nor to the last site in the beach line.
        const site_event_type& site_arc2 = right_it->first.left_site();
        const site_event_type& site3 = right_it->first.right_site();

// Remove the candidate circle from the event queue.
        deactivate_circle_event(&right_it->second);
        --left_it;
        const site_event_type& site_arc1 = left_it->first.right_site();
        const site_event_type& site1 = left_it->first.left_site();

// Insert new nodes into the beach line. Update the output.
        beach_line_iterator new_node_it =
            insert_new_arc(site_arc1, site_arc2, site_event, right_it, output);

// Add candidate circles to the circle event queue.
        // There could be up to two circle events formed by
        // a new bisector and the one on the left or right.
        activate_circle_event(site1, site_arc1, site_event, new_node_it);

// If the site event is a segment, update its direction.
        if (site_event.is_segment()) {
          site_event.inverse();
        }
        activate_circle_event(site_event, site_arc2, site3, right_it);
        right_it = new_node_it;
      }
    }
  }

// In general case circle event is made of the three consecutive sites
  // that form two bisectors in the beach line data structure.
  // Let circle event sites be A, B, C, two bisectors that define
  // circle event are (A, B), (B, C). During circle event processing
  // we remove (A, B), (B, C) and insert (A, C). As beach line comparison
  // works correctly only if one of the nodes is a new one we remove
  // (B, C) bisector and change (A, B) bisector to the (A, C). That's
  // why we use const_cast there and take all the responsibility that
  // map data structure keeps correct ordering.
  template <typename OUTPUT>
  void process_circle_event(OUTPUT* output) {
    // Get the topmost circle event.
    const event_type& e = circle_events_.top();
    const circle_event_type& circle_event = e.first;
    beach_line_iterator it_first = e.second;
    beach_line_iterator it_last = it_first;

// Get the C site.
    site_event_type site3 = it_first->first.right_site();

// Get the half-edge corresponding to the second bisector - (B, C).
    edge_type* bisector2 = it_first->second.edge();

// Get the half-edge corresponding to the first bisector - (A, B).
    --it_first;
    edge_type* bisector1 = it_first->second.edge();

// Get the A site.
    site_event_type site1 = it_first->first.left_site();

if (!site1.is_segment() && site3.is_segment() &&
        site3.point1() == site1.point0()) {
      site3.inverse();
    }

// Change the (A, B) bisector node to the (A, C) bisector node.
    const_cast<key_type&>(it_first->first).right_site(site3);

// Insert the new bisector into the beach line.
    it_first->second.edge(output->_insert_new_edge(
        site1, site3, circle_event, bisector1, bisector2).first);

// Remove the (B, C) bisector node from the beach line.
    beach_line_.erase(it_last);
    it_last = it_first;

// Pop the topmost circle event from the event queue.
    circle_events_.pop();

// Check new triplets formed by the neighboring arcs
    // to the left for potential circle events.
    if (it_first != beach_line_.begin()) {
      deactivate_circle_event(&it_first->second);
      --it_first;
      const site_event_type& site_l1 = it_first->first.left_site();
      activate_circle_event(site_l1, site1, site3, it_last);
    }

// Check the new triplet formed by the neighboring arcs
    // to the right for potential circle events.
    ++it_last;
    if (it_last != beach_line_.end()) {
      deactivate_circle_event(&it_last->second);
      const site_event_type& site_r1 = it_last->first.right_site();
      activate_circle_event(site1, site3, site_r1, it_last);
    }
  }

// Insert new nodes into the beach line. Update the output.
  template <typename OUTPUT>
  beach_line_iterator insert_new_arc(
      const site_event_type& site_arc1, const site_event_type &site_arc2,
      const site_event_type& site_event, beach_line_iterator position,
      OUTPUT* output) {
    // Create two new bisectors with opposite directions.
    key_type new_left_node(site_arc1, site_event);
    key_type new_right_node(site_event, site_arc2);

// Set correct orientation for the first site of the second node.
    if (site_event.is_segment()) {
      new_right_node.left_site().inverse();
    }

// Update the output.
    std::pair<edge_type*, edge_type*> edges =
        output->_insert_new_edge(site_arc2, site_event);
    position = beach_line_.insert(position,
        typename beach_line_type::value_type(
            new_right_node, value_type(edges.second)));

if (site_event.is_segment()) {
      // Update the beach line with temporary bisector, that will
      // disappear after processing site event corresponding to the
      // second endpoint of the segment site.
      key_type new_node(site_event, site_event);
      new_node.right_site().inverse();
      position = beach_line_.insert(position,
          typename beach_line_type::value_type(new_node, value_type(NULL)));

// Update the data structure that holds temporary bisectors.
      end_points_.push(std::make_pair(site_event.point1(), position));
    }

position = beach_line_.insert(position,
        typename beach_line_type::value_type(
            new_left_node, value_type(edges.first)));

return position;
  }

// Add a new circle event to the event queue.
  // bisector_node corresponds to the (site2, site3) bisector.
  void activate_circle_event(const site_event_type& site1,
                             const site_event_type& site2,
                             const site_event_type& site3,
                             beach_line_iterator bisector_node) {
    circle_event_type c_event;
    // Check if the three input sites create a circle event.
    if (circle_formation_predicate_(site1, site2, site3, c_event)) {
      // Add the new circle event to the circle events queue.
      // Update bisector's circle event iterator to point to the
      // new circle event in the circle event queue.
      event_type& e = circle_events_.push(
          std::pair<circle_event_type, beach_line_iterator>(
              c_event, bisector_node));
      bisector_node->second.circle_event(&e.first);
    }
  }

private:
  point_comparison_predicate point_comparison_;
  struct end_point_comparison {
    bool operator() (const end_point_type& end1,
                     const end_point_type& end2) const {
      return point_comparison(end2.first, end1.first);
    }
    point_comparison_predicate point_comparison;
  };

std::vector<site_event_type> site_events_;
  site_event_iterator_type site_event_iterator_;
  std::priority_queue< end_point_type, std::vector<end_point_type>,
                       end_point_comparison > end_points_;
  circle_event_queue_type circle_events_;
  beach_line_type beach_line_;
  circle_formation_predicate_type circle_formation_predicate_;
  std::size_t index_;

// Disallow copy constructor and operator=
  voronoi_builder(const voronoi_builder&);
  void operator=(const voronoi_builder&);
};

typedef voronoi_builder<detail::int32> default_voronoi_builder;
}  // polygon
}  // boost

#endif  // BOOST_POLYGON_VORONOI_BUILDER

// Boost.Polygon library voronoi_builder.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_BUILDER #define BOOST_POLYGON_VORONOI_BUILDER #include #include #include #include #include #include "detail/voronoi_ctypes.hpp" #include "detail/voronoi_predicates.hpp" #include "detail/voronoi_structures.hpp" #include "voronoi_geometry_type.hpp" namespace boost { namespace polygon { // GENERAL INFO: // The sweepline algorithm implementation to compute Voronoi diagram of // points and non-intersecting segments (excluding endpoints). // Complexity - O(N*logN), memory usage - O(N), where N is the total number // of input geometries. // // CONTRACT: // 1) Input geometries should have integral (e.g. int32, int64) coordinate type. // 2) Input geometries should not intersect except their endpoints. // // IMPLEMENTATION DETAILS: // Each input point creates one input site. Each input segment creates three // input sites: two for its endpoints and one for the segment itself (this is // made to simplify output construction). All the site objects are constructed // and sorted at the algorithm initialization step. Priority queue is used to // dynamically hold circle events. At each step of the algorithm execution the // leftmost event is retrieved by comparing the current site event and the // topmost element from the circle event queue. STL map (red-black tree) // container was chosen to hold state of the beach line. The keys of the map // correspond to the neighboring sites that form a bisector and values map to // the corresponding Voronoi edges in the output data structure. template , typename VP = detail::voronoi_predicates > class voronoi_builder { public: typedef typename CTT::int_type int_type; typedef typename CTT::fpt_type fpt_type; voronoi_builder() : index_(0) {} // Each point creates a single site event. std::size_t insert_point(const int_type& x, const int_type& y) { site_events_.push_back(site_event_type(x, y)); site_events_.back().initial_index(index_); site_events_.back().source_category(SOURCE_CATEGORY_SINGLE_POINT); return index_++; } // Each segment creates three site events that correspond to: // 1) the start point of the segment; // 2) the end point of the segment; // 3) the segment itself defined by its start point. std::size_t insert_segment( const int_type& x1, const int_type& y1, const int_type& x2, const int_type& y2) { // Set up start point site. point_type p1(x1, y1); site_events_.push_back(site_event_type(p1)); site_events_.back().initial_index(index_); site_events_.back().source_category(SOURCE_CATEGORY_SEGMENT_START_POINT); // Set up end point site. point_type p2(x2, y2); site_events_.push_back(site_event_type(p2)); site_events_.back().initial_index(index_); site_events_.back().source_category(SOURCE_CATEGORY_SEGMENT_END_POINT); // Set up segment site. if (point_comparison_(p1, p2)) { site_events_.push_back(site_event_type(p1, p2)); site_events_.back().source_category(SOURCE_CATEGORY_INITIAL_SEGMENT); } else { site_events_.push_back(site_event_type(p2, p1)); site_events_.back().source_category(SOURCE_CATEGORY_REVERSE_SEGMENT); } site_events_.back().initial_index(index_); return index_++; } // Run sweepline algorithm and fill output data structure. template void construct(OUTPUT* output) { // Init structures. output->_reserve(site_events_.size()); init_sites_queue(); init_beach_line(output); // The algorithm stops when there are no events to process. event_comparison_predicate event_comparison; while (!circle_events_.empty() || !(site_event_iterator_ == site_events_.end())) { if (circle_events_.empty()) { process_site_event(output); } else if (site_event_iterator_ == site_events_.end()) { process_circle_event(output); } else { if (event_comparison(*site_event_iterator_, circle_events_.top().first)) { process_site_event(output); } else { process_circle_event(output); } } while (!circle_events_.empty() && !circle_events_.top().first.is_active()) { circle_events_.pop(); } } beach_line_.clear(); // Finish construction. output->_build(); } void clear() { index_ = 0; site_events_.clear(); } private: typedef detail::point_2d point_type; typedef detail::site_event site_event_type; typedef typename std::vector::const_iterator site_event_iterator_type; typedef detail::circle_event circle_event_type; typedef typename VP::template point_comparison_predicate point_comparison_predicate; typedef typename VP:: template event_comparison_predicate event_comparison_predicate; typedef typename VP:: template circle_formation_predicate circle_formation_predicate_type; typedef void edge_type; typedef detail::beach_line_node_key key_type; typedef detail::beach_line_node_data value_type; typedef typename VP::template node_comparison_predicate node_comparer_type; typedef std::map< key_type, value_type, node_comparer_type > beach_line_type; typedef typename beach_line_type::iterator beach_line_iterator; typedef std::pair event_type; typedef struct { bool operator()(const event_type& lhs, const event_type& rhs) const { return predicate(rhs.first, lhs.first); } event_comparison_predicate predicate; } event_comparison_type; typedef detail::ordered_queue circle_event_queue_type; typedef std::pair end_point_type; void init_sites_queue() { // Sort site events. std::sort(site_events_.begin(), site_events_.end(), event_comparison_predicate()); // Remove duplicates. site_events_.erase(std::unique( site_events_.begin(), site_events_.end()), site_events_.end()); // Index sites. for (std::size_t cur = 0; cur < site_events_.size(); ++cur) { site_events_[cur].sorted_index(cur); } // Init site iterator. site_event_iterator_ = site_events_.begin(); } template void init_beach_line(OUTPUT* output) { if (site_events_.empty()) return; if (site_events_.size() == 1) { // Handle single site event case. output->_process_single_site(site_events_[0]); ++site_event_iterator_; } else { int skip = 0; while (site_event_iterator_ != site_events_.end() && VP::is_vertical(site_event_iterator_->point0(), site_events_.begin()->point0()) && VP::is_vertical(*site_event_iterator_)) { ++site_event_iterator_; ++skip; } if (skip == 1) { // Init beach line with the first two sites. init_beach_line_default(output); } else { // Init beach line with collinear vertical sites. init_beach_line_collinear_sites(output); } } } // Init beach line with the two first sites. // The first site is always a point. template void init_beach_line_default(OUTPUT* output) { // Get the first and the second site event. site_event_iterator_type it_first = site_events_.begin(); site_event_iterator_type it_second = site_events_.begin(); ++it_second; insert_new_arc( *it_first, *it_first, *it_second, beach_line_.end(), output); // The second site was already processed. Move the iterator. ++site_event_iterator_; } // Init beach line with collinear sites. template void init_beach_line_collinear_sites(OUTPUT* output) { site_event_iterator_type it_first = site_events_.begin(); site_event_iterator_type it_second = site_events_.begin(); ++it_second; while (it_second != site_event_iterator_) { // Create a new beach line node. key_type new_node(*it_first, *it_second); // Update the output. edge_type* edge = output->_insert_new_edge(*it_first, *it_second).first; // Insert a new bisector into the beach line. beach_line_.insert(beach_line_.end(), std::pair(new_node, value_type(edge))); // Update iterators. ++it_first; ++it_second; } } void deactivate_circle_event(value_type* value) { if (value->circle_event()) { value->circle_event()->deactivate(); value->circle_event(NULL); } } template void process_site_event(OUTPUT* output) { // Get next site event to process. site_event_type site_event = *site_event_iterator_; // Move site iterator. site_event_iterator_type last = site_event_iterator_ + 1; // If a new site is an end point of some segment, // remove temporary nodes from the beach line data structure. if (!site_event.is_segment()) { while (!end_points_.empty() && end_points_.top().first == site_event.point0()) { beach_line_iterator b_it = end_points_.top().second; end_points_.pop(); beach_line_.erase(b_it); } } else { while (last != site_events_.end() && last->is_segment() && last->point0() == site_event.point0()) ++last; } // Find the node in the binary search tree with left arc // lying above the new site point. key_type new_key(*site_event_iterator_); beach_line_iterator right_it = beach_line_.lower_bound(new_key); for (; site_event_iterator_ != last; ++site_event_iterator_) { site_event = *site_event_iterator_; beach_line_iterator left_it = right_it; // Do further processing depending on the above node position. // For any two neighboring nodes the second site of the first node // is the same as the first site of the second node. if (right_it == beach_line_.end()) { // The above arc corresponds to the second arc of the last node. // Move the iterator to the last node. --left_it; // Get the second site of the last node const site_event_type& site_arc = left_it->first.right_site(); // Insert new nodes into the beach line. Update the output. right_it = insert_new_arc( site_arc, site_arc, site_event, right_it, output); // Add a candidate circle to the circle event queue. // There could be only one new circle event formed by // a new bisector and the one on the left. activate_circle_event(left_it->first.left_site(), left_it->first.right_site(), site_event, right_it); } else if (right_it == beach_line_.begin()) { // The above arc corresponds to the first site of the first node. const site_event_type& site_arc = right_it->first.left_site(); // Insert new nodes into the beach line. Update the output. left_it = insert_new_arc( site_arc, site_arc, site_event, right_it, output); // If the site event is a segment, update its direction. if (site_event.is_segment()) { site_event.inverse(); } // Add a candidate circle to the circle event queue. // There could be only one new circle event formed by // a new bisector and the one on the right. activate_circle_event(site_event, right_it->first.left_site(), right_it->first.right_site(), right_it); right_it = left_it; } else { // The above arc corresponds neither to the first, // nor to the last site in the beach line. const site_event_type& site_arc2 = right_it->first.left_site(); const site_event_type& site3 = right_it->first.right_site(); // Remove the candidate circle from the event queue. deactivate_circle_event(&right_it->second); --left_it; const site_event_type& site_arc1 = left_it->first.right_site(); const site_event_type& site1 = left_it->first.left_site(); // Insert new nodes into the beach line. Update the output. beach_line_iterator new_node_it = insert_new_arc(site_arc1, site_arc2, site_event, right_it, output); // Add candidate circles to the circle event queue. // There could be up to two circle events formed by // a new bisector and the one on the left or right. activate_circle_event(site1, site_arc1, site_event, new_node_it); // If the site event is a segment, update its direction. if (site_event.is_segment()) { site_event.inverse(); } activate_circle_event(site_event, site_arc2, site3, right_it); right_it = new_node_it; } } } // In general case circle event is made of the three consecutive sites // that form two bisectors in the beach line data structure. // Let circle event sites be A, B, C, two bisectors that define // circle event are (A, B), (B, C). During circle event processing // we remove (A, B), (B, C) and insert (A, C). As beach line comparison // works correctly only if one of the nodes is a new one we remove // (B, C) bisector and change (A, B) bisector to the (A, C). That's // why we use const_cast there and take all the responsibility that // map data structure keeps correct ordering. template void process_circle_event(OUTPUT* output) { // Get the topmost circle event. const event_type& e = circle_events_.top(); const circle_event_type& circle_event = e.first; beach_line_iterator it_first = e.second; beach_line_iterator it_last = it_first; // Get the C site. site_event_type site3 = it_first->first.right_site(); // Get the half-edge corresponding to the second bisector - (B, C). edge_type* bisector2 = it_first->second.edge(); // Get the half-edge corresponding to the first bisector - (A, B). --it_first; edge_type* bisector1 = it_first->second.edge(); // Get the A site. site_event_type site1 = it_first->first.left_site(); if (!site1.is_segment() && site3.is_segment() && site3.point1() == site1.point0()) { site3.inverse(); } // Change the (A, B) bisector node to the (A, C) bisector node. const_cast(it_first->first).right_site(site3); // Insert the new bisector into the beach line. it_first->second.edge(output->_insert_new_edge( site1, site3, circle_event, bisector1, bisector2).first); // Remove the (B, C) bisector node from the beach line. beach_line_.erase(it_last); it_last = it_first; // Pop the topmost circle event from the event queue. circle_events_.pop(); // Check new triplets formed by the neighboring arcs // to the left for potential circle events. if (it_first != beach_line_.begin()) { deactivate_circle_event(&it_first->second); --it_first; const site_event_type& site_l1 = it_first->first.left_site(); activate_circle_event(site_l1, site1, site3, it_last); } // Check the new triplet formed by the neighboring arcs // to the right for potential circle events. ++it_last; if (it_last != beach_line_.end()) { deactivate_circle_event(&it_last->second); const site_event_type& site_r1 = it_last->first.right_site(); activate_circle_event(site1, site3, site_r1, it_last); } } // Insert new nodes into the beach line. Update the output. template beach_line_iterator insert_new_arc( const site_event_type& site_arc1, const site_event_type &site_arc2, const site_event_type& site_event, beach_line_iterator position, OUTPUT* output) { // Create two new bisectors with opposite directions. key_type new_left_node(site_arc1, site_event); key_type new_right_node(site_event, site_arc2); // Set correct orientation for the first site of the second node. if (site_event.is_segment()) { new_right_node.left_site().inverse(); } // Update the output. std::pair edges = output->_insert_new_edge(site_arc2, site_event); position = beach_line_.insert(position, typename beach_line_type::value_type( new_right_node, value_type(edges.second))); if (site_event.is_segment()) { // Update the beach line with temporary bisector, that will // disappear after processing site event corresponding to the // second endpoint of the segment site. key_type new_node(site_event, site_event); new_node.right_site().inverse(); position = beach_line_.insert(position, typename beach_line_type::value_type(new_node, value_type(NULL))); // Update the data structure that holds temporary bisectors. end_points_.push(std::make_pair(site_event.point1(), position)); } position = beach_line_.insert(position, typename beach_line_type::value_type( new_left_node, value_type(edges.first))); return position; } // Add a new circle event to the event queue. // bisector_node corresponds to the (site2, site3) bisector. void activate_circle_event(const site_event_type& site1, const site_event_type& site2, const site_event_type& site3, beach_line_iterator bisector_node) { circle_event_type c_event; // Check if the three input sites create a circle event. if (circle_formation_predicate_(site1, site2, site3, c_event)) { // Add the new circle event to the circle events queue. // Update bisector's circle event iterator to point to the // new circle event in the circle event queue. event_type& e = circle_events_.push( std::pair( c_event, bisector_node)); bisector_node->second.circle_event(&e.first); } } private: point_comparison_predicate point_comparison_; struct end_point_comparison { bool operator() (const end_point_type& end1, const end_point_type& end2) const { return point_comparison(end2.first, end1.first); } point_comparison_predicate point_comparison; }; std::vector site_events_; site_event_iterator_type site_event_iterator_; std::priority_queue< end_point_type, std::vector, end_point_comparison > end_points_; circle_event_queue_type circle_events_; beach_line_type beach_line_; circle_formation_predicate_type circle_formation_predicate_; std::size_t index_; // Disallow copy constructor and operator= voronoi_builder(const voronoi_builder&); void operator=(const voronoi_builder&); }; typedef voronoi_builder default_voronoi_builder; } // polygon } // boost #endif // BOOST_POLYGON_VORONOI_BUILDER