Subject: [Boost-commit] svn:boost r73497 - trunk/boost/polygon
From: lucanus.j.simonson_at_[hidden]
Date: 2011-08-02 15:16:42
Author: ljsimons
Date: 2011-08-02 15:16:41 EDT (Tue, 02 Aug 2011)
New Revision: 73497
URL: http://svn.boost.org/trac/boost/changeset/73497
Log:
added directed_line_esgment_set_data for voronoi diagram integration
Added:
trunk/boost/polygon/directed_line_segment_set_data.hpp (contents, props changed)
Added: trunk/boost/polygon/directed_line_segment_set_data.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/polygon/directed_line_segment_set_data.hpp 2011-08-02 15:16:41 EDT (Tue, 02 Aug 2011)
@@ -0,0 +1,270 @@
+/*
+ Copyright 2008 Intel Corporation
+
+ Use, modification and distribution are subject to 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).
+*/
+#ifndef BOOST_POLYGON_DIRECTED_LINE_SEGMENT_SET_DATA_HPP
+#define BOOST_POLYGON_DIRECTED_LINE_SEGMENT_SET_DATA_HPP
+
+namespace boost { namespace polygon{
+ template <typename T>
+ class directed_line_segment_set_data {
+ public:
+ typedef T coordinate_type;
+ typedef point_data<T> point_type;
+ typedef directed_line_segment_data<T> directed_line_segment_type;
+ typedef std::vector<directed_line_segment_type> value_type;
+ typedef typename std::vector<directed_line_segment_type>::const_iterator iterator_type;
+
+ inline directed_line_segment_set_data() : data_(), dirty_(false), unsorted_(false) {}
+ inline directed_line_segment_set_data(const directed_line_segment_set_data& that):
+ data_(that.data_), dirty_(that.dirty_), unsorted_(that.unsorted_) {}
+ inline directed_line_segment_set_data& operator=(const directed_line_segment_set_data& that) {
+ if(this == &that) return *this;
+ data_ = that.data_;
+ dirty_ = that.dirty_;
+ unsorted_ = that.unsorted_;
+ return *this;
+ }
+ template <typename T2>
+ inline directed_line_segment_set_data& operator=(const T2& rvalue) {
+ data_.clear();
+ bool unsorted = !sorted(rvalue);
+ bool dirty = !dirty(rvalue);
+ insert(begin(rvalue), end(rvalue));
+ unsorted_ = unsorted;
+ dirty_ = dirty;
+ return *this;
+ }
+
+ inline bool operator==(const directed_line_segment_set_data& that) const {
+ clean();
+ that.clean();
+ sort();
+ that.sort();
+ return data_ == that.data_;
+ }
+ inline bool operator!=(const directed_line_segment_set_data& that) const {
+ return !(*this == that);
+ }
+
+ template <typename iT>
+ inline void insert(iT begin_segments, iT end_segments) {
+ data_.clear();
+ for(; begin_segments != end_segments; ++begin_segments) {
+ insert(*begin_segments);
+ }
+ }
+
+ template <typename ST>
+ inline void insert(ST segment) {
+ unsorted_ = true;
+ dirty_ = true;
+ directed_line_segment_type tmp_seg;
+ assign(tmp_seg, segment);
+ data_.push_back(tmp_seg);
+ }
+
+ inline void clear() { data_.clear(); unsorted_ = false; dirty_ = false; }
+
+ inline iterator_type begin() const {
+ return data_.begin();
+ }
+
+ inline iterator_type end() const {
+ return data_.end();
+ }
+
+ const value_type& value() const {
+ return data_;
+ }
+
+ template <typename output_container>
+ inline void get(output_container& output) const {
+ for(std::size_t i = 0; i < size(); ++i) {
+ output.push_back(typename output_container::value_type());
+ assign(output.back(), data_[i]);
+ }
+ }
+
+ inline bool empty() const { return data_.empty(); }
+
+ inline std::size_t size() const { clean(); return data_.size(); }
+
+ inline std::size_t capacity() const { return data_.capacity(); }
+
+ inline void reserve(std::size_t size) { return data_.reserve(size); }
+
+ inline bool sorted() const { return !unsorted_; }
+
+ inline bool dirty() const { return dirty_; }
+
+ void clean() const {
+ typedef T Unit;
+ typedef typename scanline_base<Unit>::Point Point;
+ typedef typename scanline_base<Unit>::half_edge half_edge;
+ typedef int segment_id;
+ std::vector<std::pair<half_edge, segment_id> > half_edges;
+ std::vector<std::pair<half_edge, segment_id> > half_edges_out;
+ segment_id id = 0;
+ half_edges.reserve(data_.size());
+ for(iterator_type itr = begin(); itr != end(); ++itr) {
+ Point l = (*itr).low();
+ Point h = (*itr).high();
+ half_edges.push_back(std::make_pair(half_edge(l, h), id++));
+ }
+ half_edges_out.reserve(half_edges.size());
+ //apparently no need to pre-sort data when calling validate_scan
+ line_intersection<Unit>::validate_scan(half_edges_out, half_edges.begin(), half_edges.end());
+ value_type result;
+ result.reserve(half_edges_out.size());
+ for(std::size_t i = 0; i < half_edges_out.size(); ++i) {
+ id = half_edges_out[i].second;
+ Point l = half_edges_out[i].first.first;
+ Point h = half_edges_out[i].first.second;
+ directed_line_segment_type orig_seg = data_[id];
+ if(orig_seg.high() < orig_seg.low())
+ std::swap(l, h);
+ result.push_back(directed_line_segment_type(l, h));
+ }
+ std::swap(result, data_);
+ dirty_ = false;
+ unsorted_ = true;
+ };
+
+ void sort() const{
+ if(unsorted_) {
+ polygon_sort(data_.begin(), data_.end());
+ unsorted_ = false;
+ }
+ }
+
+ template <typename input_iterator_type>
+ void set(input_iterator_type input_begin, input_iterator_type input_end) {
+ clear();
+ reserve(std::distance(input_begin,input_end));
+ insert(input_begin, input_end);
+ dirty_ = true;
+ unsorted_ = true;
+ }
+
+ void set(const value_type& value) {
+ data_ = value;
+ dirty_ = true;
+ unsorted_ = true;
+ }
+
+ template <typename rectangle_type>
+ bool extents(rectangle_type& rect) {
+ if(empty()) return false;
+ bool first_iteration = true;
+ for(iterator_type itr = begin();
+ itr != end(); ++itr) {
+ rectangle_type edge_box;
+ set_points(edge_box, (*itr).low(), (*itr).high());
+ if(first_iteration)
+ rect = edge_box;
+ else
+ encompass(rect, edge_box);
+ first_iteration = false;
+ }
+ return true;
+ }
+
+ template <typename transform_type>
+ inline directed_line_segment_set_data&
+ transform(const transform_type& tr) {
+ for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) {
+ point_type l = (*itr).low();
+ point_type h = (*itr).high();
+ ::boost::polygon::transform(l, tr);
+ ::boost::polygon::transform(h, tr);
+ (*itr).low(l);
+ (*itr).high(h);
+ }
+ unsorted_ = true;
+ return *this;
+ }
+
+ inline directed_line_segment_set_data&
+ scale_up(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
+ for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) {
+ point_type l = (*itr).low();
+ point_type h = (*itr).high();
+ ::boost::polygon::scale_up(l, factor);
+ ::boost::polygon::scale_up(h, factor);
+ (*itr).low(l);
+ (*itr).high(h);
+ }
+ return *this;
+ }
+
+ inline directed_line_segment_set_data&
+ scale_down(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
+ for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) {
+ point_type l = (*itr).low();
+ point_type h = (*itr).high();
+ ::boost::polygon::scale_down(l, factor);
+ ::boost::polygon::scale_down(h, factor);
+ (*itr).low(l);
+ (*itr).high(h);
+ }
+ return *this;
+ }
+
+ template <typename scaling_type>
+ inline directed_line_segment_set_data& scale(const scaling_type& scaling) {
+ for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) {
+ point_type l = (*itr).low();
+ point_type h = (*itr).high();
+ ::boost::polygon::scale(l, scaling);
+ ::boost::polygon::scale(h, scaling);
+ (*itr).low(l);
+ (*itr).high(h);
+ }
+ return *this;
+ }
+
+ template <typename cT>
+ std::size_t get_intersection_points(cT& output_points) const {
+ typedef T Unit;
+ typedef typename scanline_base<Unit>::Point Point;
+ typedef typename scanline_base<Unit>::half_edge half_edge;
+ typedef int segment_id;
+ std::vector<std::pair<half_edge, segment_id> > half_edges;
+ std::vector<std::pair<half_edge, segment_id> > half_edges_out;
+ segment_id id = 0;
+ half_edges.reserve(data_.size());
+ for(iterator_type itr = begin(); itr != end(); ++itr) {
+ Point l = (*itr).low();
+ Point h = (*itr).high();
+ half_edges.push_back(std::make_pair(half_edge(l, h), id++));
+ }
+ half_edges_out.reserve(half_edges.size());
+ std::vector<std::set<Point> > intersection_points(half_edges.size(), std::set<Point>());
+ line_intersection<Unit>::validate_scan_divide_and_conquer(intersection_points, half_edges.begin(), half_edges.end());
+ std::vector<Point> tmp_points;
+ for(std::size_t i = 0; i < intersection_points.size(); ++i) {
+ typename std::set<Point>::iterator itr2 = intersection_points[i].begin();
+ for(; itr2 != intersection_points[i].end(); ++itr2)
+ if(data_[i].low() != *itr2 && data_[i].high() != *itr2)
+ tmp_points.push_back(*itr2);
+ }
+ polygon_sort(tmp_points.begin(), tmp_points.end());
+ typename std::vector<Point>::iterator new_end = std::unique(tmp_points.begin(), tmp_points.end());
+ output_points.insert(output_points.end(), tmp_points.begin(), new_end);
+ return std::distance(tmp_points.begin(), new_end);
+ };
+
+
+private:
+ mutable value_type data_;
+ mutable bool dirty_;
+ mutable bool unsorted_;
+};
+
+}
+}
+#endif