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