Subject: [Boost-commit] svn:boost r76813 - sandbox/gtl/boost/polygon
From: sydorchuk.andriy_at_[hidden]
Date: 2012-01-31 15:53:05
Author: asydorchuk
Date: 2012-01-31 15:53:05 EST (Tue, 31 Jan 2012)
New Revision: 76813
URL: http://svn.boost.org/trac/boost/changeset/76813
Log:
Minor optimizations to the voronoi of segments algorithm.
Text files modified:
sandbox/gtl/boost/polygon/voronoi_builder.hpp | 24 ++++++++++++++----------
1 files changed, 14 insertions(+), 10 deletions(-)
Modified: sandbox/gtl/boost/polygon/voronoi_builder.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_builder.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_builder.hpp 2012-01-31 15:53:05 EST (Tue, 31 Jan 2012)
@@ -263,7 +263,7 @@
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_.insert(beach_line_.end(),
std::pair<key_type, value_type>(new_node, value_type(edge)));
// Update iterators.
@@ -301,14 +301,14 @@
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_;
- // Create degenerate node.
- key_type new_key(site_event);
-
- // Find the node in the binary search tree with left arc
- // lying above the new site point.
- beach_line_iterator right_it = beach_line_.lower_bound(new_key);
beach_line_iterator left_it = right_it;
// Do further processing depending on the above node position.
@@ -336,7 +336,7 @@
const site_event_type &site_arc = right_it->first.left_site();
// Insert new nodes into the beach line. Update the output.
- insert_new_arc(site_arc, site_arc, site_event, right_it, 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()) {
@@ -348,6 +348,7 @@
// 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.
@@ -376,6 +377,7 @@
}
activate_circle_event(site_event, site_arc2, site3,
right_it);
+ right_it = new_node_it;
}
}
}
@@ -483,8 +485,10 @@
end_points_.push(std::make_pair(site_event.point1(), position));
}
- return beach_line_.insert(position,
- typename beach_line_type::value_type(new_left_node, value_type(edges.first)));
+ position = beach_line_.insert(position,
+ beach_line_type::value_type(new_left_node, value_type(edges.first)));
+
+ return position;
}
// Add a new circle event to the event queue.