[Boost-commit] svn:boost r80494 - in trunk: boost/polygon libs/polygon/doc libs/polygon/test

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
+&lt;typename segment_container_type&gt;<b><br />
+            </b>void <b>intersect_segments</b>(segment_container_type&amp; 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
+&lt;typename line_segment_type, <br />
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typename line_segment_iterator_type&gt;<b><br />
+            </b>void <b>intersect_segments</b>(<br />
+&nbsp;&nbsp;vector&ltpair&ltsize_t,
+            line_segment_type&gt &gt &amp; result, <br />
+&nbsp;&nbsp;line_segment_iterator_type begin_segs, <br />
+&nbsp;&nbsp;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
+&lt;typename point_container_type, <br />
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typename line_segment_iterator_type&gt;<b><br />
+            </b>size_t <b>segment_intersections</b>(point_container_type&amp; result, <br />
+&nbsp;&nbsp;line_segment_iterator_type begin_segs, <br />
+&nbsp;&nbsp;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
+&lt;typename rectangle_type, <br />
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typename
+                line_segment_iterator_type&gt;<b><br />
+            </b>void <b>segments_extents</b>(rectangle_type&amp; envelope,<br />
+&nbsp;&nbsp;line_segment_iterator_type begin_segs, <br />
+&nbsp;&nbsp;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;
 }