view release on metacpan or  search on metacpan

src/boost/polygon/voronoi_builder.hpp  view on Meta::CPAN

// 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 (except endpoints).
// Complexity - O(N*logN), memory usage - O(N), where N is the total number
// of input geometries. Input geometries should have integer coordinate type.
//
// IMPLEMENTATION DETAILS:
// Each input point creates one site event. Each input segment creates three
// site events: two for its endpoints and one for the segment itself (this is
// made to simplify output construction). All the site events 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) {

src/boost/polygon/voronoi_builder.hpp  view on Meta::CPAN

    }

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