Subject: [Boost-commit] svn:boost r80494 - in trunk: boost/polygon libs/polygon/doc libs/polygon/test
From: lucanus.j.simonson_at_[hidden]
Date: 2012-09-11 17:30:05
Author: ljsimons
Date: 2012-09-11 17:30:03 EDT (Tue, 11 Sep 2012)
New Revision: 80494
URL: http://svn.boost.org/trac/boost/changeset/80494
Log:
added segment utils to support preprocessing of line segment data to satisfy voronoi diagram precondition
Added:
trunk/boost/polygon/segment_utils.hpp (contents, props changed)
Text files modified:
trunk/boost/polygon/polygon.hpp | 2
trunk/libs/polygon/doc/gtl_segment_concept.htm | 82 ++++++++++++++++++++++++++++++++++++++++
trunk/libs/polygon/test/gtl_boost_unit_test.cpp | 57 +++++++++++++++++++++++++++
3 files changed, 141 insertions(+), 0 deletions(-)
Modified: trunk/boost/polygon/polygon.hpp
==============================================================================
--- trunk/boost/polygon/polygon.hpp (original)
+++ trunk/boost/polygon/polygon.hpp 2012-09-11 17:30:03 EDT (Tue, 11 Sep 2012)
@@ -93,4 +93,6 @@
#include "polygon_set_concept.hpp"
+#include "segment_utils.hpp"
+
#endif
Added: trunk/boost/polygon/segment_utils.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/polygon/segment_utils.hpp 2012-09-11 17:30:03 EDT (Tue, 11 Sep 2012)
@@ -0,0 +1,133 @@
+/*
+ Copyright 2012 Lucanus Simonson
+
+ 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_SEGMENT_UTILS_HPP
+#define BOOST_POLYGON_SEGMENT_UTILS_HPP
+
+namespace boost { namespace polygon{
+
+template <typename line_segment_type, typename line_segment_iterator_type>
+void intersect_segments(std::vector<std::pair<std::size_t, line_segment_type> >& result,
+ line_segment_iterator_type begin_segs, line_segment_iterator_type end_segs){
+ typedef typename segment_traits<line_segment_type>::coordinate_type 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_in = 0;
+ half_edges.reserve(std::distance(begin_segs, end_segs));
+ for(; begin_segs != end_segs; ++begin_segs) {
+ Point l, h;
+ assign(l, low(*begin_segs));
+ assign(h, high(*begin_segs));
+ half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
+ }
+ half_edges_out.reserve(half_edges.size());
+ //apparently no need to pre-sort data when calling validate_scan
+ if(half_edges.size() != 0)
+ line_intersection<Unit>::validate_scan(half_edges_out, half_edges.begin(), half_edges.end());
+ result.reserve(result.size() + half_edges_out.size());
+ for(std::size_t i = 0; i < half_edges_out.size(); ++i) {
+ std::size_t id = (std::size_t)(half_edges_out[i].second);
+ Point l = half_edges_out[i].first.first;
+ Point h = half_edges_out[i].first.second;
+ result.push_back(std::make_pair(id, construct<line_segment_type>(l, h)));
+ }
+}
+
+template <typename segment_container_type>
+void intersect_segments(segment_container_type& segments) {
+ typedef typename segment_container_type::value_type line_segment_type;
+ typedef typename segment_traits<line_segment_type>::coordinate_type 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_in = 0;
+ half_edges.reserve(std::distance(segments.begin(), segments.end()));
+ for(typename segment_container_type::iterator itr = segments.begin();
+ itr != segments.end(); ++itr) {
+ Point l, h;
+ assign(l, low(*itr));
+ assign(h, high(*itr));
+ half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
+ }
+ half_edges_out.reserve(half_edges.size());
+ //apparently no need to pre-sort data when calling validate_scan
+ if(half_edges.size() != 0)
+ line_intersection<Unit>::validate_scan(half_edges_out, half_edges.begin(), half_edges.end());
+ segments.clear();
+ for(std::size_t i = 0; i < half_edges_out.size(); ++i) {
+ std::size_t id = (std::size_t)(half_edges_out[i].second);
+ Point l = half_edges_out[i].first.first;
+ Point h = half_edges_out[i].first.second;
+ segments.push_back(construct<line_segment_type>(l, h));
+ }
+}
+
+template <typename cT, typename line_segment_iterator_type>
+std::size_t segment_intersections(cT& output_points,
+ line_segment_iterator_type begin_segs,
+ line_segment_iterator_type end_segs) {
+ typedef typename segment_traits<
+ typename std::iterator_traits<line_segment_iterator_type>::value_type
+ >::coordinate_type 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;
+ std::size_t range_size = std::distance(begin_segs, end_segs);
+ half_edges.reserve(range_size);
+ std::vector<typename std::iterator_traits<line_segment_iterator_type>::value_type> data_;
+ data_.insert(data_.end(), begin_segs, end_segs);
+ for(typename std::vector<typename std::iterator_traits<
+ line_segment_iterator_type>::value_type>::iterator itr = data_.begin();
+ itr != data_.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);
+}
+
+template <typename rectangle_type, typename line_segment_iterator_type>
+bool segments_extents(rectangle_type& rect,
+ line_segment_iterator_type begin_segs,
+ line_segment_iterator_type end_segs) {
+ bool first_iteration = true;
+ for( ;begin_segs != end_segs; ++begin_segs) {
+ rectangle_type edge_box;
+ set_points(edge_box, (*begin_segs).low(), (*begin_segs).high());
+ if(first_iteration)
+ rect = edge_box;
+ else
+ encompass(rect, edge_box);
+ first_iteration = false;
+ }
+ return !first_iteration;
+}
+
+}}
+
+#endif
Modified: trunk/libs/polygon/doc/gtl_segment_concept.htm
==============================================================================
--- trunk/libs/polygon/doc/gtl_segment_concept.htm (original)
+++ trunk/libs/polygon/doc/gtl_segment_concept.htm 2012-09-11 17:30:03 EDT (Tue, 11 Sep 2012)
@@ -468,6 +468,88 @@
</tr>
</tbody>
</table>
+
+ <h1>Segment Utils</h1>
+ <p> </p>
+ <p>The library provides several algorithms for the manipulation of
+ sets of segment data. In particular, the generalize line segment
+ intersection algorithm used for polygon set operations is exposed
+ through several interfaces to allow it to be used with any
+ collection or sequence of objects that model the <font face="Courier New">segment_concept</font>.
+ </p><h2>Functions</h2>
+ <table style="width: 100%;" id="table2" border="1">
+ <tbody>
+
+
+ <tr>
+ <td width="586"><font face="Courier New">template
+<typename segment_container_type><b><br />
+ </b>void <b>intersect_segments</b>(segment_container_type& segments)
+ </font></td>
+ <td>Modifies the contents of the container of segments such
+ that segments are split at their intersection points.
+ Postconditions: no segments intersect except at their end
+ points. Useful to satisfy the precondition of voronoi diagram
+ construction.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices + intersections.
+ </td>
+ </tr>
+ <tr>
+ <td width="586"><font face="Courier New">template
+<typename line_segment_type, <br />
+ typename line_segment_iterator_type><b><br />
+ </b>void <b>intersect_segments</b>(<br />
+ vector<pair<size_t,
+ line_segment_type> > & result, <br />
+ line_segment_iterator_type begin_segs, <br />
+ line_segment_iterator_type end_segs)
+ </font></td>
+ <td>Accumulates the result of splitting the segments in the
+ iterator range at their intersection points into the result container.
+ Postconditions: no segments intersect except at their end
+ points. The index of the input segment is paired with each
+ resultant segment
+ that was split to produce it to associate the result segments with
+ the inputs segments.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices + intersections.
+ </td>
+ </tr>
+ <tr>
+ <td width="586"><font face="Courier New">template
+<typename point_container_type, <br />
+ typename line_segment_iterator_type><b><br />
+ </b>size_t <b>segment_intersections</b>(point_container_type& result, <br />
+ line_segment_iterator_type begin_segs, <br />
+ line_segment_iterator_type end_segs)
+ </font></td>
+ <td>
+ Accumlates the intersection points of the iterator range of line segments
+ into the result container of points. Trivial intersections consisting
+ of abutting line segments that are an end point are not reported.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices + intersections.
+ </td>
+ </tr>
+ <tr>
+ <td width="586"><font face="Courier New">template
+<typename rectangle_type, <br />
+ typename
+ line_segment_iterator_type><b><br />
+ </b>void <b>segments_extents</b>(rectangle_type& envelope,<br />
+ line_segment_iterator_type begin_segs, <br />
+ line_segment_iterator_type end_segs)
+ </font></td>
+ <td>Computes the bounding rectangle of the the iterator range of
+ line segments.
+ Linear runtime.
+ </td>
+ </tr>
+
+
+
+
+ </tbody>
+ </table>
+
</td>
</tr>
<tr>
Modified: trunk/libs/polygon/test/gtl_boost_unit_test.cpp
==============================================================================
--- trunk/libs/polygon/test/gtl_boost_unit_test.cpp (original)
+++ trunk/libs/polygon/test/gtl_boost_unit_test.cpp 2012-09-11 17:30:03 EDT (Tue, 11 Sep 2012)
@@ -3665,6 +3665,63 @@
}
}
+ if(1){
+ using namespace boost::polygon;
+ typedef point_data<int> Point;
+ typedef segment_data<int> Dls;
+ Point pt1(0, 0);
+ Point pt2(10, 10);
+ Point pt3(20, 20);
+ Point pt4(20, 0);
+ Dls dls1(pt1, pt2);
+ Dls dls2(pt1, pt3);
+ Dls dls3(pt1, pt4);
+ Dls dls4(pt2, pt1);
+ typedef std::vector<segment_data<int> > Dlss;
+ Dlss dlss;
+ dlss.push_back(dls1);
+ dlss.push_back(dls2);
+ dlss.push_back(dls3);
+ dlss.push_back(dls4);
+ rectangle_data<int> rect;
+ segments_extents(rect, dlss.begin(), dlss.end());
+ assert_s(area(rect) == 400.0, "extents");
+ intersect_segments(dlss);
+ for(Dlss::iterator itr = dlss.begin(); itr != dlss.end(); ++itr) {
+ std::cout << *itr << std::endl;
+ }
+ assert_s(dlss.size() == 5, "intersection");
+ std::vector<Point> ips;
+ std::size_t nips = segment_intersections(ips, dlss.begin(), dlss.end());
+ assert_s(nips == 0, "points0");
+ Dls dls5(Point(0,5), Point(5,0));
+ dlss.push_back(dls5);
+ nips = segment_intersections(ips, dlss.begin(), dlss.end());
+ assert_s(nips == 2, "points1");
+ //for(std::size_t i = 0; i < ips.size(); ++i) {
+ // std::cout << ips[i] << std::endl;
+ //}
+ assert_s(ips[0] == Point(2,2), "points2");
+ assert_s(ips[1] == Point(5,0), "points3");
+ std::cout << std::endl;
+ intersect_segments(dlss);
+ for(Dlss::iterator itr = dlss.begin(); itr != dlss.end(); ++itr) {
+ std::cout << *itr << std::endl;
+ }
+ assert_s(dlss.size() == 11, "intersection2");
+ }
+
+ if(1){
+ using namespace boost::polygon;
+ std::vector<std::pair<std::size_t, segment_data<int> > > segs;
+ segment_data<int> sarray[2];
+ sarray[0] = segment_data<int>(point_data<int>(0,0), point_data<int>(10,10));
+ sarray[1] = segment_data<int>(point_data<int>(10,0), point_data<int>(0,10));
+ intersect_segments(segs, sarray, sarray+2);
+ std::cout << segs.size() << std::endl;
+ assert_s(segs.size() == 4, "intersection3");
+ }
+
std::cout << "ALL TESTS COMPLETE\n";
return 0;
}