Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r80534 - in trunk: boost/polygon libs/polygon/doc libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2012-09-15 15:38:04

Next message: daniel.j.walker_at_[hidden]: "[Boost-commit] svn:boost r80535 - trunk/libs/utility"
Previous message: vicente.botet_at_[hidden]: "[Boost-commit] svn:boost r80533 - trunk/libs/thread/src/win32"

Author: asydorchuk
Date: 2012-09-15 15:38:03 EDT (Sat, 15 Sep 2012)
New Revision: 80534
URL: http://svn.boost.org/trac/boost/changeset/80534

Log:
Polygon: Updating segment utils.

Text files modified:
   trunk/boost/polygon/segment_utils.hpp | 204 ++++++++++++++++++++++-----------------
   trunk/libs/polygon/doc/gtl_segment_concept.htm | 75 ++++++--------
   trunk/libs/polygon/test/gtl_boost_unit_test.cpp | 34 ++---
   3 files changed, 162 insertions(+), 151 deletions(-)

Modified: trunk/boost/polygon/segment_utils.hpp
==============================================================================
--- trunk/boost/polygon/segment_utils.hpp (original)
+++ trunk/boost/polygon/segment_utils.hpp 2012-09-15 15:38:03 EDT (Sat, 15 Sep 2012)
@@ -5,129 +5,155 @@
 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;
+#include <set>
+#include <vector>
+#include <utility>
+
+namespace boost {
+namespace polygon {
+
+template <typename SegmentIterator, typename Segment>
+typename enable_if<
+ typename gtl_and<
+ typename gtl_if<
+ typename is_segment_concept<
+ typename geometry_concept<
+ typename std::iterator_traits<SegmentIterator>::value_type
+ >::type
+ >::type
+ >::type,
+ typename gtl_if<
+ typename is_segment_concept<
+ typename geometry_concept<Segment>::type
+ >::type
+ >::type
+ >::type,
+ void
+>::type
+intersect_segments(
+ SegmentIterator first, SegmentIterator last,
+ std::vector<std::pair<std::size_t, Segment> >* result) {
+ typedef typename segment_traits<Segment>::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) {
+ half_edges.reserve(std::distance(first, last));
+ for (; first != last; ++first) {
 Point l, h;
- assign(l, low(*begin_segs));
- assign(h, high(*begin_segs));
+ assign(l, low(*first));
+ assign(h, high(*first));
 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) {
+ // 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)));
+ result->push_back(std::make_pair(id, construct<Segment>(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;
+template <typename SegmentIterator, typename SegmentContainer>
+typename enable_if<
+ typename gtl_and<
+ typename gtl_if<
+ typename is_segment_concept<
+ typename geometry_concept<
+ typename std::iterator_traits<SegmentIterator>::value_type
+ >::type
+ >::type
+ >::type,
+ typename gtl_if<
+ typename is_segment_concept<
+ typename geometry_concept<
+ typename SegmentContainer::value_type
+ >::type
+ >::type
+ >::type
+ >::type,
+ void
+>::type
+intersect_segments(
+ SegmentIterator first,
+ SegmentIterator last,
+ SegmentContainer* result) {
+ typedef typename SegmentContainer::value_type segment_type;
+ typedef typename segment_traits<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) {
+ half_edges.reserve(std::distance(first, last));
+ for (; first != last; ++first) {
 Point l, h;
- assign(l, low(*itr));
- assign(h, high(*itr));
+ assign(l, low(*first));
+ assign(h, high(*first));
 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));
+ // 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());
 }
-}

-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++));
+ result->reserve(result->size() + half_edges_out.size());
+ for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
+ Point l = half_edges_out[i].first.first;
+ Point h = half_edges_out[i].first.second;
+ result->push_back(construct<segment_type>(l, h));
 }
- 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;
+template <typename SegmentIterator, typename Rectangle>
+typename enable_if<
+ typename gtl_and<
+ typename gtl_if<
+ typename is_rectangle_concept<
+ typename geometry_concept<Rectangle>::type
+ >::type
+ >::type,
+ typename gtl_if<
+ typename is_segment_concept<
+ typename geometry_concept<
+ typename std::iterator_traits<SegmentIterator>::value_type
+ >::type
+ >::type
+ >::type
+ >::type,
+ bool
+>::type
+envelope_segments(
+ SegmentIterator first,
+ SegmentIterator last,
+ Rectangle* rect) {
+ for (SegmentIterator it = first; it != last; ++it) {
+ if (it == first) {
+ set_points(*rect, low(*it), high(*it));
+ } else {
+ encompass(*rect, low(*it));
+ encompass(*rect, high(*it));
+ }
 }
- return !first_iteration;
+ return first != last;
}
+} // polygon
+} // boost

-}}
-
-#endif
+#endif // BOOST_POLYGON_SEGMENT_UTILS_HPP

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-15 15:38:03 EDT (Sat, 15 Sep 2012)
@@ -1,6 +1,5 @@
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
-<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:(null)1="http://www.w3.org/TR/REC-html40" lang="en"><head>
-<title>Boost Polygon Library: Segment Concept</title>
@@ -16,6 +15,8 @@

+
+



@@ -483,30 +484,33 @@

 <tr>
 <td width="586">template
-<typename segment_container_type> 
- void intersect_segments(segment_container_type& segments)
+<typename SegmentIterator, 
+          typename SegmentContainer> 
+ void intersect_segments( 
+    SegmentIterator first, 
+    SegmentIterator last, 
+    SegmentContainer* result)
 </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
+ <td>Accumulates
+the result of splitting the segments in the iterator range at their
+intersection points into the result container. Preconditions: segment
+type used by all the input structures should model segment concept.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>
+ </td>
 </tr>
 <tr>
 <td width="586">template
-<typename line_segment_type, 
-          typename line_segment_iterator_type> 
+<typename SegmentIterator, 
+          typename Segment> 
 void intersect_segments( 
-  vector&ltpair&ltsize_t,
- line_segment_type&gt &gt & result, 
-  line_segment_iterator_type begin_segs, 
-  line_segment_iterator_type end_segs)
- </td>
+    SegmentIterator first, 
+    SegmentIterator last, 
+    vector<pair<size_t, Segment>* result)</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
+ Preconditions: segment type used by all the input structures should model segment concept. 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
@@ -514,34 +518,20 @@
 Expected n log n runtime, worst case quadratic runtime wrt. vertices + intersections.
 </td>
 </tr>
+
 <tr>
 <td width="586">template
-<typename point_container_type, 
-          typename line_segment_iterator_type> 
- size_t segment_intersections(point_container_type& result, 
-  line_segment_iterator_type begin_segs, 
-  line_segment_iterator_type end_segs)
- </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">template
-<typename rectangle_type, 
-          typename
- line_segment_iterator_type> 
- void segments_extents(rectangle_type& envelope, 
-  line_segment_iterator_type begin_segs, 
-  line_segment_iterator_type end_segs)
+<typename SegmentIterator, 
+          typename Rectangle> 
+ void envelope_segments( 
+    SegmentIterator first,     SegmentIterator last, 
+    Rectangle* rect)
 </td>
- <td>Computes the bounding rectangle of the the iterator range of
- line segments.
- Linear runtime.
- </td>
+ <td>Computes
+the bounding rectangle of the iterator range of line segments.
+Preconditions: segment type and rectangle type used by the input
+structures should model segment concept and rectangle concept
+respectively. Linear runtime. </td>
 </tr>

@@ -574,4 +564,5 @@
 </tbody>
</table>

-</body></html>
+
+</body></html>
\ No newline at end of file

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-15 15:38:03 EDT (Sat, 15 Sep 2012)
@@ -3665,7 +3665,7 @@
 }
 }

- if(1){
+ if (1) {
 using namespace boost::polygon;
 typedef point_data<int> Point;
 typedef segment_data<int> Dls;
@@ -3678,46 +3678,40 @@
 Dls dls3(pt1, pt4);
 Dls dls4(pt2, pt1);
 typedef std::vector<segment_data<int> > Dlss;
- Dlss dlss;
+ Dlss dlss, result;
 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) {
+ envelope_segments(dlss.begin(), dlss.end(), &rect);
+ assert_s(area(rect) == 400.0, "envelope");
+ intersect_segments(dlss.begin(), dlss.end(), &result);
+ dlss.swap(result);
+ 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) {
+ result.clear();
+ intersect_segments(dlss.begin(), dlss.end(), &result);
+ dlss.swap(result);
+ for (Dlss::iterator itr = dlss.begin(); itr != dlss.end(); ++itr) {
 std::cout << *itr << std::endl;
 }
 assert_s(dlss.size() == 11, "intersection2");
 }

- if(1){
+ 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::iterator_traits<segment_data<int>*>::value_type s = sarray[0];
+ intersect_segments(sarray, sarray+2, &segs);
 std::cout << segs.size() << std::endl;
 assert_s(segs.size() == 4, "intersection3");
 }

Next message: daniel.j.walker_at_[hidden]: "[Boost-commit] svn:boost r80535 - trunk/libs/utility"
Previous message: vicente.botet_at_[hidden]: "[Boost-commit] svn:boost r80533 - trunk/libs/thread/src/win32"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk