Subject: [Boost-commit] svn:boost r74612 - in sandbox/gtl: boost/polygon boost/polygon/detail libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2011-09-29 15:08:10
Author: asydorchuk
Date: 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
New Revision: 74612
URL: http://svn.boost.org/trac/boost/changeset/74612
Log:
Updated sandbox version to the trunk one (release).
No additional changes made.
Added:
sandbox/gtl/boost/polygon/detail/minkowski.hpp (contents, props changed)
sandbox/gtl/boost/polygon/detail/polygon_simplify.hpp (contents, props changed)
sandbox/gtl/boost/polygon/detail/polygon_sort_adaptor.hpp (contents, props changed)
sandbox/gtl/boost/polygon/directed_line_segment_concept.hpp (contents, props changed)
sandbox/gtl/boost/polygon/directed_line_segment_data.hpp (contents, props changed)
sandbox/gtl/boost/polygon/directed_line_segment_set_data.hpp (contents, props changed)
sandbox/gtl/boost/polygon/directed_line_segment_traits.hpp (contents, props changed)
sandbox/gtl/boost/polygon/gtl.hpp (contents, props changed)
Text files modified:
sandbox/gtl/boost/polygon/detail/boolean_op_45.hpp | 2
sandbox/gtl/boost/polygon/detail/iterator_geometry_to_set.hpp | 28 +
sandbox/gtl/boost/polygon/detail/max_cover.hpp | 2
sandbox/gtl/boost/polygon/detail/polygon_45_formation.hpp | 52 +-
sandbox/gtl/boost/polygon/detail/polygon_45_set_view.hpp | 6
sandbox/gtl/boost/polygon/detail/polygon_45_touch.hpp | 2
sandbox/gtl/boost/polygon/detail/polygon_90_set_view.hpp | 180 +++++++----
sandbox/gtl/boost/polygon/detail/polygon_90_touch.hpp | 2
sandbox/gtl/boost/polygon/detail/polygon_arbitrary_formation.hpp | 113 ++++--
sandbox/gtl/boost/polygon/detail/polygon_formation.hpp | 2
sandbox/gtl/boost/polygon/detail/polygon_set_view.hpp | 12
sandbox/gtl/boost/polygon/detail/property_merge.hpp | 6
sandbox/gtl/boost/polygon/detail/property_merge_45.hpp | 2
sandbox/gtl/boost/polygon/detail/scan_arbitrary.hpp | 623 ++++++++++++++++++++-------------------
sandbox/gtl/boost/polygon/gmp_override.hpp | 1
sandbox/gtl/boost/polygon/interval_concept.hpp | 2
sandbox/gtl/boost/polygon/isotropy.hpp | 25 +
sandbox/gtl/boost/polygon/point_data.hpp | 18
sandbox/gtl/boost/polygon/polygon.hpp | 5
sandbox/gtl/boost/polygon/polygon_45_data.hpp | 2
sandbox/gtl/boost/polygon/polygon_45_set_data.hpp | 21
sandbox/gtl/boost/polygon/polygon_45_set_traits.hpp | 6
sandbox/gtl/boost/polygon/polygon_45_with_holes_data.hpp | 4
sandbox/gtl/boost/polygon/polygon_90_set_data.hpp | 315 ++++++++++++++++++++
sandbox/gtl/boost/polygon/polygon_90_set_traits.hpp | 5
sandbox/gtl/boost/polygon/polygon_data.hpp | 2
sandbox/gtl/boost/polygon/polygon_set_concept.hpp | 30 +
sandbox/gtl/boost/polygon/polygon_set_data.hpp | 275 +++++++++++++----
sandbox/gtl/boost/polygon/polygon_set_traits.hpp | 6
sandbox/gtl/boost/polygon/polygon_traits.hpp | 23 +
sandbox/gtl/boost/polygon/polygon_with_holes_data.hpp | 2
sandbox/gtl/libs/polygon/test/gtl_boost_unit_test.cpp | 132 ++++++++
32 files changed, 1347 insertions(+), 559 deletions(-)
Modified: sandbox/gtl/boost/polygon/detail/boolean_op_45.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/boolean_op_45.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/boolean_op_45.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -445,7 +445,7 @@
};
template <typename S45V>
static inline void sortScan45Vector(S45V& vec) {
- std::sort(vec.begin(), vec.end(), lessScan45Vertex());
+ polygon_sort(vec.begin(), vec.end(), lessScan45Vertex());
}
template <typename CountType, typename output_functor>
Modified: sandbox/gtl/boost/polygon/detail/iterator_geometry_to_set.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/iterator_geometry_to_set.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/iterator_geometry_to_set.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -29,7 +29,7 @@
public:
iterator_geometry_to_set() : rectangle_(), vertex_(), corner_(4), orient_(), is_hole_() {}
iterator_geometry_to_set(const rectangle_type& rectangle, direction_1d dir,
- orientation_2d orient = HORIZONTAL, bool is_hole = false) :
+ orientation_2d orient = HORIZONTAL, bool is_hole = false, bool = false, direction_1d = CLOCKWISE) :
rectangle_(), vertex_(), corner_(0), orient_(orient), is_hole_(is_hole) {
assign(rectangle_, rectangle);
if(dir == HIGH) corner_ = 4;
@@ -93,7 +93,7 @@
int polygon_index;
public:
iterator_geometry_to_set() : vertex_(), itrb(), itre(), last_vertex_(), is_hole_(), multiplier_(), first_pt(), second_pt(), pts(), use_wrap(), orient_(), polygon_index(-1) {}
- iterator_geometry_to_set(const polygon_type& polygon, direction_1d dir, orientation_2d orient = HORIZONTAL, bool is_hole = false) :
+ iterator_geometry_to_set(const polygon_type& polygon, direction_1d dir, orientation_2d orient = HORIZONTAL, bool is_hole = false, bool winding_override = false, direction_1d w = CLOCKWISE) :
vertex_(), itrb(), itre(), last_vertex_(),
is_hole_(is_hole), multiplier_(), first_pt(), second_pt(), pts(), use_wrap(),
orient_(orient), polygon_index(0) {
@@ -103,7 +103,9 @@
if(itrb == itre || dir == HIGH || size(polygon) < 4) {
polygon_index = -1;
} else {
- direction_1d wdir = winding(polygon);
+ direction_1d wdir = w;
+ if(!winding_override)
+ wdir = winding(polygon);
multiplier_ = wdir == LOW ? -1 : 1;
if(is_hole_) multiplier_ *= -1;
first_pt = pts[0] = *itrb;
@@ -182,9 +184,7 @@
vertex_.second.first =pts[1].get(orient_);
if(pts[1] == pts[2]) {
vertex_.second.second = 0;
- return;
- }
- if(pts[0].get(HORIZONTAL) != pts[1].get(HORIZONTAL)) {
+ } else if(pts[0].get(HORIZONTAL) != pts[1].get(HORIZONTAL)) {
vertex_.second.second = -1;
} else if(pts[0].get(VERTICAL) != pts[1].get(VERTICAL)) {
vertex_.second.second = 1;
@@ -214,7 +214,7 @@
public:
iterator_geometry_to_set() : itrb(), itre(), itrhib(), itrhie(), itrhb(), itrhe(), orient_(), is_hole_(), started_holes() {}
iterator_geometry_to_set(const polygon_with_holes_type& polygon, direction_1d dir,
- orientation_2d orient = HORIZONTAL, bool is_hole = false) :
+ orientation_2d orient = HORIZONTAL, bool is_hole = false, bool = false, direction_1d = CLOCKWISE) :
itrb(), itre(), itrhib(), itrhie(), itrhb(), itrhe(), orient_(orient), is_hole_(is_hole), started_holes() {
itre = iterator_geometry_to_set<polygon_90_concept, polygon_with_holes_type>(polygon, HIGH, orient, is_hole_);
itrhe = end_holes(polygon);
@@ -253,8 +253,13 @@
typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, HIGH, orient_, !is_hole_);
++itrhb;
} else {
- itrhib = itrhie = iterator_geometry_to_set<polygon_90_concept,
- typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>();
+ //in this case we have no holes so we just need the iterhib == itrhie, which
+ //is always true if they were default initialized in the initial case or
+ //both point to end of the previous hole processed
+ //no need to explicitly reset them, and it causes an stl debug assertion to use
+ //the default constructed iterator this way
+ //itrhib = itrhie = iterator_geometry_to_set<polygon_90_concept,
+ // typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>();
}
} else {
++itrhib;
@@ -266,8 +271,9 @@
typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, HIGH, orient_, !is_hole_);
++itrhb;
} else {
- itrhib = itrhie = iterator_geometry_to_set<polygon_90_concept,
- typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>();
+ //this is the same case as above
+ //itrhib = itrhie = iterator_geometry_to_set<polygon_90_concept,
+ // typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>();
}
}
}
Modified: sandbox/gtl/boost/polygon/detail/max_cover.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/max_cover.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/max_cover.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -213,7 +213,7 @@
Interval rectIvl = nodep->rect.get(orient);
leadingEdges.push_back(EdgeAssociation(std::pair<Unit, Interval>(leading, rectIvl), nodep));
}
- std::sort(leadingEdges.begin(), leadingEdges.end(), lessEdgeAssociation());
+ polygon_sort(leadingEdges.begin(), leadingEdges.end(), lessEdgeAssociation());
typename std::vector<EdgeAssociation>::iterator leadingBegin = leadingEdges.begin();
iT trailingBegin = beginNode;
while(leadingBegin != leadingEdges.end()) {
Added: sandbox/gtl/boost/polygon/detail/minkowski.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/detail/minkowski.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -0,0 +1,125 @@
+
+namespace boost { namespace polygon { namespace detail {
+
+template <typename coordinate_type>
+struct minkowski_offset {
+ typedef point_data<coordinate_type> point;
+ typedef polygon_set_data<coordinate_type> polygon_set;
+ typedef polygon_with_holes_data<coordinate_type> polygon;
+ typedef std::pair<point, point> edge;
+
+ static void convolve_two_segments(std::vector<point>& figure, const edge& a, const edge& b) {
+ figure.clear();
+ figure.push_back(point(a.first));
+ figure.push_back(point(a.first));
+ figure.push_back(point(a.second));
+ figure.push_back(point(a.second));
+ convolve(figure[0], b.second);
+ convolve(figure[1], b.first);
+ convolve(figure[2], b.first);
+ convolve(figure[3], b.second);
+ }
+
+ template <typename itrT1, typename itrT2>
+ static void convolve_two_point_sequences(polygon_set& result, itrT1 ab, itrT1 ae, itrT2 bb, itrT2 be) {
+ if(ab == ae || bb == be)
+ return;
+ point first_a = *ab;
+ point prev_a = *ab;
+ std::vector<point> vec;
+ polygon poly;
+ ++ab;
+ for( ; ab != ae; ++ab) {
+ point first_b = *bb;
+ point prev_b = *bb;
+ itrT2 tmpb = bb;
+ ++tmpb;
+ for( ; tmpb != be; ++tmpb) {
+ convolve_two_segments(vec, std::make_pair(prev_b, *tmpb), std::make_pair(prev_a, *ab));
+ set_points(poly, vec.begin(), vec.end());
+ result.insert(poly);
+ prev_b = *tmpb;
+ }
+ prev_a = *ab;
+ }
+ }
+
+ template <typename itrT>
+ static void convolve_point_sequence_with_polygons(polygon_set& result, itrT b, itrT e, const std::vector<polygon>& polygons) {
+ for(std::size_t i = 0; i < polygons.size(); ++i) {
+ convolve_two_point_sequences(result, b, e, begin_points(polygons[i]), end_points(polygons[i]));
+ for(typename polygon_with_holes_traits<polygon>::iterator_holes_type itrh = begin_holes(polygons[i]);
+ itrh != end_holes(polygons[i]); ++itrh) {
+ convolve_two_point_sequences(result, b, e, begin_points(*itrh), end_points(*itrh));
+ }
+ }
+ }
+
+ static void convolve_two_polygon_sets(polygon_set& result, const polygon_set& a, const polygon_set& b) {
+ result.clear();
+ std::vector<polygon> a_polygons;
+ std::vector<polygon> b_polygons;
+ a.get(a_polygons);
+ b.get(b_polygons);
+ for(std::size_t ai = 0; ai < a_polygons.size(); ++ai) {
+ convolve_point_sequence_with_polygons(result, begin_points(a_polygons[ai]),
+ end_points(a_polygons[ai]), b_polygons);
+ for(typename polygon_with_holes_traits<polygon>::iterator_holes_type itrh = begin_holes(a_polygons[ai]);
+ itrh != end_holes(a_polygons[ai]); ++itrh) {
+ convolve_point_sequence_with_polygons(result, begin_points(*itrh),
+ end_points(*itrh), b_polygons);
+ }
+ for(std::size_t bi = 0; bi < b_polygons.size(); ++bi) {
+ polygon tmp_poly = a_polygons[ai];
+ result.insert(convolve(tmp_poly, *(begin_points(b_polygons[bi]))));
+ tmp_poly = b_polygons[bi];
+ result.insert(convolve(tmp_poly, *(begin_points(a_polygons[ai]))));
+ }
+ }
+ }
+};
+
+}
+ template<typename T>
+ inline polygon_set_data<T>&
+ polygon_set_data<T>::resize(coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments) {
+ using namespace ::boost::polygon::operators;
+ if(!corner_fill_arc) {
+ if(resizing < 0)
+ return shrink(-resizing);
+ if(resizing > 0)
+ return bloat(resizing);
+ return *this;
+ }
+ if(resizing == 0) return *this;
+ if(empty()) return *this;
+ if(num_circle_segments < 3) num_circle_segments = 4;
+ rectangle_data<coordinate_type> rect;
+ extents(rect);
+ if(resizing < 0) {
+ ::boost::polygon::bloat(rect, 10);
+ (*this) = rect - (*this); //invert
+ }
+ //make_arc(std::vector<point_data< T> >& return_points,
+ //point_data< double> start, point_data< double> end,
+ //point_data< double> center, double r, unsigned int num_circle_segments)
+ std::vector<point_data<coordinate_type> > circle;
+ point_data<double> center(0.0, 0.0), start(0.0, (double)resizing);
+ make_arc(circle, start, start, center, std::abs((double)resizing),
+ num_circle_segments);
+ polygon_data<coordinate_type> poly;
+ set_points(poly, circle.begin(), circle.end());
+ polygon_set_data<coordinate_type> offset_set;
+ offset_set += poly;
+ polygon_set_data<coordinate_type> result;
+ detail::minkowski_offset<coordinate_type>::convolve_two_polygon_sets
+ (result, *this, offset_set);
+ if(resizing < 0) {
+ result = result & rect;//eliminate overhang
+ result = result ^ rect;//invert
+ }
+ *this = result;
+ return *this;
+ }
+
+}}
Modified: sandbox/gtl/boost/polygon/detail/polygon_45_formation.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/polygon_45_formation.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/polygon_45_formation.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -251,12 +251,14 @@
return;
}
Unit firstY = (*iter).y();
+ Unit firstX = (*iter).x();
++iter;
if(iter == tailp_->points.end()) {
tailp_->points.push_front(point);
return;
}
- if(iter->y() == point.y() && firstY == point.y()) {
+ if((iter->y() == point.y() && firstY == point.y()) ||
+ (iter->x() == point.x() && firstX == point.x())){
--iter;
*iter = point;
} else {
@@ -274,12 +276,14 @@
return;
}
Unit firstY = (*iter).y();
+ Unit firstX = (*iter).x();
++iter;
if(iter == tailp_->points.rend()) {
tailp_->points.push_back(point);
return;
}
- if(iter->y() == point.y() && firstY == point.y()) {
+ if((iter->y() == point.y() && firstY == point.y()) ||
+ (iter->x() == point.x() && firstX == point.x())){
--iter;
*iter = point;
} else {
@@ -492,7 +496,8 @@
inline Vertex45CompactT(const Point& point, int riseIn, int countIn) : pt(point), count() {
count[riseIn+1] = countIn;
}
- inline Vertex45CompactT(const Vertex45T& vertex) : pt(vertex.pt), count() {
+ template <typename ct2>
+ inline Vertex45CompactT(const typename boolean_op_45<Unit>::template Vertex45T<ct2>& vertex) : pt(vertex.pt), count() {
count[vertex.rise+1] = vertex.count;
}
inline Vertex45CompactT(const Vertex45CompactT& vertex) : pt(vertex.pt), count(vertex.count) {}
@@ -899,7 +904,7 @@
data.push_back(Vertex45(Point(10, 0), 2, -1));
data.push_back(Vertex45(Point(10, 10), 2, 1));
data.push_back(Vertex45(Point(10, 10), 0, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -923,7 +928,7 @@
data.push_back(Vertex45(Point(10, 10), 2, -1));
data.push_back(Vertex45(Point(10, 20), 2, 1));
data.push_back(Vertex45(Point(10, 20), 1, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -948,7 +953,7 @@
data.push_back(Vertex45(Point(10, 10), 0, -1));
data.push_back(Vertex45(Point(20, 10), 1, -1));
data.push_back(Vertex45(Point(20, 10), 0, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1013,7 +1018,7 @@
data.push_back(Vertex45(Point(12, 8), 1, -1));
// result == 12 8 -1 1
data.push_back(Vertex45(Point(12, 8), -1, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1046,7 +1051,7 @@
stdcout << "scanning\n";
scan45.scan(result, vertices.begin(), vertices.end());
- std::sort(result.begin(), result.end());
+ polygon_sort(result.begin(), result.end());
pf.scan(polys, result.begin(), result.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1118,7 +1123,7 @@
data.push_back(Vertex45(Point(8, 6), -1, -1));
data.push_back(Vertex45(Point(8, 6), 1, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1190,7 +1195,7 @@
data.push_back(Vertex45(Point(10, 8), -1, -1));
data.push_back(Vertex45(Point(10, 8), 1, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1234,7 +1239,7 @@
data.push_back(Vertex45(Point(10, 22), 2, -1));
data.push_back(Vertex45(Point(10, 22), 0, -1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1663,7 +1668,7 @@
data.push_back(Vertex45(Point(10, 0), 2, -1));
data.push_back(Vertex45(Point(10, 10), 2, 1));
data.push_back(Vertex45(Point(10, 10), 0, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1687,7 +1692,7 @@
data.push_back(Vertex45(Point(10, 10), 2, -1));
data.push_back(Vertex45(Point(10, 20), 2, 1));
data.push_back(Vertex45(Point(10, 20), 1, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1711,7 +1716,7 @@
data.push_back(Vertex45(Point(10, 10), 0, -1));
data.push_back(Vertex45(Point(20, 10), 1, -1));
data.push_back(Vertex45(Point(20, 10), 0, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1737,7 +1742,7 @@
data.push_back(Vertex45(Point(10, 10), 0, 1));
data.push_back(Vertex45(Point(20, 20), 1, 1));
data.push_back(Vertex45(Point(20, 20), 2, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1763,7 +1768,7 @@
data.push_back(Vertex45(Point(20, 10), 0, 1));
data.push_back(Vertex45(Point(20, -10), -1, -1));
data.push_back(Vertex45(Point(20, -10), 2, -1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1796,7 +1801,7 @@
data.push_back(Vertex45(Point(2, 2), 0, 1));
data.push_back(Vertex45(Point(3, 2), 1, 1));
data.push_back(Vertex45(Point(3, 2), 0, -1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1830,7 +1835,7 @@
data.push_back(Vertex45(Point(2, 2), 2, -1));
data.push_back(Vertex45(Point(2, 2), 0, -1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1894,7 +1899,7 @@
data.push_back(Vertex45(Point(12, 8), 1, -1));
// result == 12 8 -1 1
data.push_back(Vertex45(Point(12, 8), -1, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1928,7 +1933,7 @@
stdcout << "scanning\n";
scan45.scan(result, vertices.begin(), vertices.end());
- std::sort(result.begin(), result.end());
+ polygon_sort(result.begin(), result.end());
pf.scan(polys, result.begin(), result.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -2000,7 +2005,7 @@
data.push_back(Vertex45(Point(8, 6), -1, -1));
data.push_back(Vertex45(Point(8, 6), 1, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -2072,7 +2077,7 @@
data.push_back(Vertex45(Point(10, 8), -1, -1));
data.push_back(Vertex45(Point(10, 8), 1, 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -2116,7 +2121,7 @@
data.push_back(Vertex45(Point(10, 22), 2, -1));
data.push_back(Vertex45(Point(10, 22), 0, -1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -2244,6 +2249,7 @@
struct geometry_concept<PolyLine45PolygonData<T> > { typedef polygon_45_with_holes_concept type; };
template <typename T>
struct geometry_concept<PolyLine45HoleData<T> > { typedef polygon_45_concept type; };
+
}
}
#endif
Modified: sandbox/gtl/boost/polygon/detail/polygon_45_set_view.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/polygon_45_set_view.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/polygon_45_set_view.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -119,18 +119,18 @@
// orient_ = orient;
// output_.clear();
// output_.insert(output_.end(), input_begin, input_end);
- // std::sort(output_.begin(), output_.end());
+ // polygon_sort(output_.begin(), output_.end());
// }
};
template <typename ltype, typename rtype, int op_type>
- typename polygon_45_set_view<ltype, rtype, op_type>::iterator_type
+ typename polygon_45_set_traits<polygon_45_set_view<ltype, rtype, op_type> >::iterator_type
polygon_45_set_traits<polygon_45_set_view<ltype, rtype, op_type> >::
begin(const polygon_45_set_view<ltype, rtype, op_type>& polygon_45_set) {
return polygon_45_set.begin();
}
template <typename ltype, typename rtype, int op_type>
- typename polygon_45_set_view<ltype, rtype, op_type>::iterator_type
+ typename polygon_45_set_traits<polygon_45_set_view<ltype, rtype, op_type> >::iterator_type
polygon_45_set_traits<polygon_45_set_view<ltype, rtype, op_type> >::
end(const polygon_45_set_view<ltype, rtype, op_type>& polygon_45_set) {
return polygon_45_set.end();
Modified: sandbox/gtl/boost/polygon/detail/polygon_45_touch.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/polygon_45_touch.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/polygon_45_touch.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -186,7 +186,7 @@
template <typename graph_type>
static void performTouch(graph_type& graph, TouchSetData& tsd) {
- std::sort(tsd.begin(), tsd.end(), lessVertex45Compact());
+ polygon_sort(tsd.begin(), tsd.end(), lessVertex45Compact());
typedef std::vector<std::pair<Point, typename boolean_op_45<Unit>::template Scan45CountT<CountTouch> > > TSD;
TSD tsd_;
tsd_.reserve(tsd.size());
Modified: sandbox/gtl/boost/polygon/detail/polygon_90_set_view.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/polygon_90_set_view.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/polygon_90_set_view.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -33,56 +33,91 @@
static inline bool sorted(const polygon_90_set_view<ltype, rtype, op_type>& polygon_set);
};
- template <typename value_type, typename ltype, typename rtype, typename op_type>
- struct compute_90_set_value {
- static
- void value(value_type& output_, const ltype& lvalue_, const rtype& rvalue_, orientation_2d orient_) {
- value_type linput_(orient_);
- value_type rinput_(orient_);
- insert_into_view_arg(linput_, lvalue_, orient_);
- insert_into_view_arg(rinput_, rvalue_, orient_);
- output_.applyBooleanBinaryOp(linput_.begin(), linput_.end(),
- rinput_.begin(), rinput_.end(), boolean_op::BinaryCount<op_type>());
- }
- };
+ template <typename value_type, typename ltype, typename rtype, typename op_type>
+ struct compute_90_set_value {
+ static
+ void value(value_type& output_, const ltype& lvalue_, const rtype& rvalue_, orientation_2d orient_) {
+ value_type linput_(orient_);
+ value_type rinput_(orient_);
+ orientation_2d orient_l = polygon_90_set_traits<ltype>::orient(lvalue_);
+ orientation_2d orient_r = polygon_90_set_traits<rtype>::orient(rvalue_);
+ //std::cout << "compute_90_set_value-0 orientations (left, right, out):\t" << orient_l.to_int()
+ // << "," << orient_r.to_int() << "," << orient_.to_int() << std::endl;
+ insert_into_view_arg(linput_, lvalue_, orient_l);
+ insert_into_view_arg(rinput_, rvalue_, orient_r);
+ output_.applyBooleanBinaryOp(linput_.begin(), linput_.end(),
+ rinput_.begin(), rinput_.end(), boolean_op::BinaryCount<op_type>());
+ }
+ };
- template <typename value_type, typename lcoord, typename rcoord, typename op_type>
- struct compute_90_set_value<value_type, polygon_90_set_data<lcoord>, polygon_90_set_data<rcoord>, op_type> {
- static
- void value(value_type& output_, const polygon_90_set_data<lcoord>& lvalue_,
- const polygon_90_set_data<rcoord>& rvalue_, orientation_2d) {
- lvalue_.sort();
- rvalue_.sort();
- output_.applyBooleanBinaryOp(lvalue_.begin(), lvalue_.end(),
- rvalue_.begin(), rvalue_.end(), boolean_op::BinaryCount<op_type>());
- }
- };
+ template <typename value_type, typename lcoord, typename rcoord, typename op_type>
+ struct compute_90_set_value<value_type, polygon_90_set_data<lcoord>, polygon_90_set_data<rcoord>, op_type> {
+ static
+ void value(value_type& output_, const polygon_90_set_data<lcoord>& lvalue_,
+ const polygon_90_set_data<rcoord>& rvalue_, orientation_2d orient_) {
+ orientation_2d orient_l = lvalue_.orient();
+ orientation_2d orient_r = rvalue_.orient();
+ value_type linput_(orient_);
+ value_type rinput_(orient_);
+ //std::cout << "compute_90_set_value-1 orientations (left, right, out):\t" << orient_l.to_int()
+ // << "," << orient_r.to_int() << "," << orient_.to_int() << std::endl;
+ if((orient_ == orient_l) && (orient_== orient_r)){ // assume that most of the time this condition is met
+ lvalue_.sort();
+ rvalue_.sort();
+ output_.applyBooleanBinaryOp(lvalue_.begin(), lvalue_.end(),
+ rvalue_.begin(), rvalue_.end(), boolean_op::BinaryCount<op_type>());
+ }else if((orient_ != orient_l) && (orient_!= orient_r)){ // both the orientations are not equal to input
+ // easier way is to ignore the input orientation and use the input data's orientation, but not done so
+ insert_into_view_arg(linput_, lvalue_, orient_l);
+ insert_into_view_arg(rinput_, rvalue_, orient_r);
+ output_.applyBooleanBinaryOp(linput_.begin(), linput_.end(),
+ rinput_.begin(), rinput_.end(), boolean_op::BinaryCount<op_type>());
+ }else if(orient_ != orient_l){ // left hand side orientation is different
+ insert_into_view_arg(linput_, lvalue_, orient_l);
+ rvalue_.sort();
+ output_.applyBooleanBinaryOp(linput_.begin(), linput_.end(),
+ rvalue_.begin(), rvalue_.end(), boolean_op::BinaryCount<op_type>());
+ } else if(orient_ != orient_r){ // right hand side orientation is different
+ insert_into_view_arg(rinput_, rvalue_, orient_r);
+ lvalue_.sort();
+ output_.applyBooleanBinaryOp(lvalue_.begin(), lvalue_.end(),
+ rinput_.begin(), rinput_.end(), boolean_op::BinaryCount<op_type>());
+ }
+ }
+ };
- template <typename value_type, typename lcoord, typename rtype, typename op_type>
- struct compute_90_set_value<value_type, polygon_90_set_data<lcoord>, rtype, op_type> {
- static
- void value(value_type& output_, const polygon_90_set_data<lcoord>& lvalue_,
- const rtype& rvalue_, orientation_2d orient_) {
- value_type rinput_(orient_);
- lvalue_.sort();
- insert_into_view_arg(rinput_, rvalue_, orient_);
- output_.applyBooleanBinaryOp(lvalue_.begin(), lvalue_.end(),
- rinput_.begin(), rinput_.end(), boolean_op::BinaryCount<op_type>());
- }
- };
+ template <typename value_type, typename lcoord, typename rtype, typename op_type>
+ struct compute_90_set_value<value_type, polygon_90_set_data<lcoord>, rtype, op_type> {
+ static
+ void value(value_type& output_, const polygon_90_set_data<lcoord>& lvalue_,
+ const rtype& rvalue_, orientation_2d orient_) {
+ value_type rinput_(orient_);
+ lvalue_.sort();
+ orientation_2d orient_r = polygon_90_set_traits<rtype>::orient(rvalue_);
+ //std::cout << "compute_90_set_value-2 orientations (right, out):\t" << orient_r.to_int()
+ // << "," << orient_.to_int() << std::endl;
+ insert_into_view_arg(rinput_, rvalue_, orient_r);
+ output_.applyBooleanBinaryOp(lvalue_.begin(), lvalue_.end(),
+ rinput_.begin(), rinput_.end(), boolean_op::BinaryCount<op_type>());
+ }
+ };
- template <typename value_type, typename ltype, typename rcoord, typename op_type>
- struct compute_90_set_value<value_type, ltype, polygon_90_set_data<rcoord>, op_type> {
- static
- void value(value_type& output_, const ltype& lvalue_,
- const polygon_90_set_data<rcoord>& rvalue_, orientation_2d orient_) {
- value_type linput_(orient_);
- insert_into_view_arg(linput_, lvalue_, orient_);
- rvalue_.sort();
- output_.applyBooleanBinaryOp(linput_.begin(), linput_.end(),
- rvalue_.begin(), rvalue_.end(), boolean_op::BinaryCount<op_type>());
- }
- };
+ template <typename value_type, typename ltype, typename rcoord, typename op_type>
+ struct compute_90_set_value<value_type, ltype, polygon_90_set_data<rcoord>, op_type> {
+ static
+ void value(value_type& output_, const ltype& lvalue_,
+ const polygon_90_set_data<rcoord>& rvalue_, orientation_2d orient_) {
+ value_type linput_(orient_);
+ orientation_2d orient_l = polygon_90_set_traits<ltype>::orient(lvalue_);
+ insert_into_view_arg(linput_, lvalue_, orient_l);
+ rvalue_.sort();
+ //std::cout << "compute_90_set_value-3 orientations (left, out):\t" << orient_l.to_int()
+ // << "," << orient_.to_int() << std::endl;
+
+ output_.applyBooleanBinaryOp(linput_.begin(), linput_.end(),
+ rvalue_.begin(), rvalue_.end(), boolean_op::BinaryCount<op_type>());
+ }
+ };
template <typename ltype, typename rtype, typename op_type>
class polygon_90_set_view {
@@ -129,7 +164,7 @@
// orient_ = orient;
// output_.clear();
// output_.insert(output_.end(), input_begin, input_end);
-// std::sort(output_.begin(), output_.end());
+// polygon_sort(output_.begin(), output_.end());
// }
void sort() const {} //is always sorted
};
@@ -140,13 +175,13 @@
};
template <typename ltype, typename rtype, typename op_type>
- typename polygon_90_set_view<ltype, rtype, op_type>::iterator_type
+ typename polygon_90_set_traits<polygon_90_set_view<ltype, rtype, op_type> >::iterator_type
polygon_90_set_traits<polygon_90_set_view<ltype, rtype, op_type> >::
begin(const polygon_90_set_view<ltype, rtype, op_type>& polygon_set) {
return polygon_set.begin();
}
template <typename ltype, typename rtype, typename op_type>
- typename polygon_90_set_view<ltype, rtype, op_type>::iterator_type
+ typename polygon_90_set_traits<polygon_90_set_view<ltype, rtype, op_type> >::iterator_type
polygon_90_set_traits<polygon_90_set_view<ltype, rtype, op_type> >::
end(const polygon_90_set_view<ltype, rtype, op_type>& polygon_set) {
return polygon_set.end();
@@ -206,23 +241,34 @@
typedef type_1 type;
};
- template <typename geometry_type_1, typename geometry_type_2, typename op_type>
- geometry_type_1& self_assignment_boolean_op(geometry_type_1& lvalue_, const geometry_type_2& rvalue_) {
- typedef geometry_type_1 ltype;
- typedef geometry_type_2 rtype;
- typedef typename polygon_90_set_traits<ltype>::coordinate_type coordinate_type;
- typedef polygon_90_set_data<coordinate_type> value_type;
- orientation_2d orient_ = polygon_90_set_traits<ltype>::orient(lvalue_);
- value_type linput_(orient_);
- value_type rinput_(orient_);
- value_type output_(orient_);
- insert_into_view_arg(linput_, lvalue_, orient_);
- insert_into_view_arg(rinput_, rvalue_, orient_);
- output_.applyBooleanBinaryOp(linput_.begin(), linput_.end(),
- rinput_.begin(), rinput_.end(), boolean_op::BinaryCount<op_type>());
- polygon_90_set_mutable_traits<geometry_type_1>::set(lvalue_, output_.begin(), output_.end(), orient_);
- return lvalue_;
- }
+ template <typename geometry_type_1, typename geometry_type_2, typename op_type>
+ geometry_type_1& self_assignment_boolean_op(geometry_type_1& lvalue_, const geometry_type_2& rvalue_) {
+ typedef geometry_type_1 ltype;
+ typedef geometry_type_2 rtype;
+ typedef typename polygon_90_set_traits<ltype>::coordinate_type coordinate_type;
+ typedef polygon_90_set_data<coordinate_type> value_type;
+ orientation_2d orient_ = polygon_90_set_traits<ltype>::orient(lvalue_);
+ //BM: rvalue_ data set may have its own orientation for scanline
+ orientation_2d orient_r = polygon_90_set_traits<rtype>::orient(rvalue_);
+ //std::cout << "self-assignment boolean-op (left, right, out):\t" << orient_.to_int()
+ // << "," << orient_r.to_int() << "," << orient_.to_int() << std::endl;
+ value_type linput_(orient_);
+ // BM: the rinput_ set's (that stores the rvalue_ dataset polygons) scanline orientation is *forced*
+ // to be same as linput
+ value_type rinput_(orient_);
+ //BM: The output dataset's scanline orient is set as equal to first input dataset's (lvalue_) orientation
+ value_type output_(orient_);
+ insert_into_view_arg(linput_, lvalue_, orient_);
+ // BM: The last argument orient_r is the user initialized scanline orientation for rvalue_ data set.
+ // But since rinput (see above) is initialized to scanline orientation consistent with the lvalue_
+ // data set, this insertion operation will change the incoming rvalue_ dataset's scanline orientation
+ insert_into_view_arg(rinput_, rvalue_, orient_r);
+ // BM: boolean operation and output uses lvalue_ dataset's scanline orientation.
+ output_.applyBooleanBinaryOp(linput_.begin(), linput_.end(),
+ rinput_.begin(), rinput_.end(), boolean_op::BinaryCount<op_type>());
+ polygon_90_set_mutable_traits<geometry_type_1>::set(lvalue_, output_.begin(), output_.end(), orient_);
+ return lvalue_;
+ }
namespace operators {
struct y_ps90_b : gtl_yes {};
Modified: sandbox/gtl/boost/polygon/detail/polygon_90_touch.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/polygon_90_touch.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/polygon_90_touch.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -42,7 +42,7 @@
ivlIds_.second = that.ivlIds_.second;
incremented_ = that.incremented_;
return *this;
- };
+ }
inline bool operator==(const iterator& that) { return itr_ == that.itr_; }
inline bool operator!=(const iterator& that) { return itr_ != that.itr_; }
inline iterator& operator++() {
Modified: sandbox/gtl/boost/polygon/detail/polygon_arbitrary_formation.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/polygon_arbitrary_formation.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/polygon_arbitrary_formation.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -388,7 +388,8 @@
struct compute_intersection_pack {
typedef typename high_precision_type<Unit>::type high_precision;
high_precision y_high, dx1, dy1, dx2, dy2, x11, x21, y11, y21, x_num, y_num, x_den, y_den, x, y;
- static inline bool compute_lazy_intersection(Point& intersection, const half_edge& he1, const half_edge& he2, bool projected = false) {
+ static inline bool compute_lazy_intersection(Point& intersection, const half_edge& he1, const half_edge& he2,
+ bool projected = false, bool round_closest = false) {
long double y_high, dx1, dy1, dx2, dy2, x11, x21, y11, y21, x_num, y_num, x_den, y_den, x, y;
typedef rectangle_data<Unit> Rectangle;
Rectangle rect1, rect2;
@@ -445,11 +446,19 @@
//std::cout << "cross2 " << dy2 << " " << dx1 << " " << dy2 * dx1 << std::endl;
//Unit exp_x = compute_x_intercept<at>(x11, x21, y11, y21, dy1, dy2, dx1, dx2);
//Unit exp_y = compute_x_intercept<at>(y11, y21, x11, x21, dx1, dx2, dy1, dy2);
+ if(round_closest) {
+ x = x + 0.5;
+ y = y + 0.5;
+ }
Unit x_unit = (Unit)(x);
Unit y_unit = (Unit)(y);
//truncate downward if it went up due to negative number
if(x < x_unit) --x_unit;
if(y < y_unit) --y_unit;
+ if(is_horizontal(he1))
+ y_unit = he1.first.y();
+ if(is_horizontal(he2))
+ y_unit = he2.first.y();
//if(x != exp_x || y != exp_y)
// std::cout << exp_x << " " << exp_y << " " << x << " " << y << std::endl;
//Unit y1 = evalAtXforY(exp_x, he1.first, he1.second);
@@ -459,16 +468,22 @@
if(!projected && !contains(rect1, result, true)) return false;
if(!projected && !contains(rect2, result, true)) return false;
if(projected) {
- rectangle_data<long double> inf_rect((long double)(std::numeric_limits<Unit>::min)(),
- (long double) (std::numeric_limits<Unit>::min)(),
+ rectangle_data<long double> inf_rect(-(long double)(std::numeric_limits<Unit>::max)(),
+ -(long double) (std::numeric_limits<Unit>::max)(),
(long double)(std::numeric_limits<Unit>::max)(),
(long double) (std::numeric_limits<Unit>::max)() );
- return contains(inf_rect, intersection, true);
+ if(contains(inf_rect, point_data<long double>(x, y), true)) {
+ intersection = result;
+ return true;
+ } else
+ return false;
}
intersection = result;
return true;
}
- inline bool compute_intersection(Point& intersection, const half_edge& he1, const half_edge& he2, bool projected = false) {
+
+ inline bool compute_intersection(Point& intersection, const half_edge& he1, const half_edge& he2,
+ bool projected = false, bool round_closest = false) {
if(!projected && !intersects(he1, he2))
return false;
bool lazy_success = compute_lazy_intersection(intersection, he1, he2, projected);
@@ -481,6 +496,13 @@
} else {
return lazy_success;
}
+ return compute_exact_intersection(intersection, he1, he2, projected, round_closest);
+ }
+
+ inline bool compute_exact_intersection(Point& intersection, const half_edge& he1, const half_edge& he2,
+ bool projected = false, bool round_closest = false) {
+ if(!projected && !intersects(he1, he2))
+ return false;
typedef rectangle_data<Unit> Rectangle;
Rectangle rect1, rect2;
set_points(rect1, he1.first, he1.second);
@@ -532,15 +554,24 @@
y_den = (dx1 * dy2 - dx2 * dy1);
x = x_num / x_den;
y = y_num / y_den;
+ //std::cout << x << " " << y << std::endl;
//std::cout << "cross1 " << dy1 << " " << dx2 << " " << dy1 * dx2 << std::endl;
//std::cout << "cross2 " << dy2 << " " << dx1 << " " << dy2 * dx1 << std::endl;
//Unit exp_x = compute_x_intercept<at>(x11, x21, y11, y21, dy1, dy2, dx1, dx2);
//Unit exp_y = compute_x_intercept<at>(y11, y21, x11, x21, dx1, dx2, dy1, dy2);
+ if(round_closest) {
+ x = x + (high_precision)0.5;
+ y = y + (high_precision)0.5;
+ }
Unit x_unit = convert_high_precision_type<Unit>(x);
Unit y_unit = convert_high_precision_type<Unit>(y);
//truncate downward if it went up due to negative number
if(x < (high_precision)x_unit) --x_unit;
if(y < (high_precision)y_unit) --y_unit;
+ if(is_horizontal(he1))
+ y_unit = he1.first.y();
+ if(is_horizontal(he2))
+ y_unit = he2.first.y();
//if(x != exp_x || y != exp_y)
// std::cout << exp_x << " " << exp_y << " " << x << " " << y << std::endl;
//Unit y1 = evalAtXforY(exp_x, he1.first, he1.second);
@@ -549,6 +580,12 @@
Point result(x_unit, y_unit);
if(!contains(rect1, result, true)) return false;
if(!contains(rect2, result, true)) return false;
+ if(projected) {
+ high_precision b1 = (high_precision) (std::numeric_limits<Unit>::min)();
+ high_precision b2 = (high_precision) (std::numeric_limits<Unit>::max)();
+ if(x > b2 || y > b2 || x < b1 || y < b1)
+ return false;
+ }
intersection = result;
return true;
}
@@ -616,6 +653,10 @@
//truncate downward if it went up due to negative number
if(x < (high_precision)x_unit) --x_unit;
if(y < (high_precision)y_unit) --y_unit;
+ if(is_horizontal(he1))
+ y_unit = he1.first.y();
+ if(is_horizontal(he2))
+ y_unit = he2.first.y();
//if(x != exp_x || y != exp_y)
// std::cout << exp_x << " " << exp_y << " " << x << " " << y << std::endl;
//Unit y1 = evalAtXforY(exp_x, he1.first, he1.second);
@@ -872,7 +913,7 @@
inline active_tail_arbitrary(const vertex_half_edge& vertex, active_tail_arbitrary* otherTailp = 0) : tailp_(), otherTailp_(), holesList_(), head_() {
tailp_ = new poly_line_arbitrary;
tailp_->points.push_back(vertex.pt);
- bool headArray[4] = {false, true, true, true};
+ //bool headArray[4] = {false, true, true, true};
bool inverted = vertex.count == -1;
head_ = (!vertex.is_vertical) ^ inverted;
otherTailp_ = otherTailp;
@@ -1172,13 +1213,13 @@
inline less_half_edge_count() : pt_() {}
inline less_half_edge_count(Point point) : pt_(point) {}
inline bool operator () (const std::pair<Point, int>& elm1, const std::pair<Point, int>& elm2) const {
- return less_slope(pt_.get(HORIZONTAL), pt_.get(VERTICAL), elm1.first, elm2.first);
+ return scanline_base<Unit>::less_slope(pt_.get(HORIZONTAL), pt_.get(VERTICAL), elm1.first, elm2.first);
}
};
static inline void sort_vertex_arbitrary_count(vertex_arbitrary_count& count, const Point& pt) {
less_half_edge_count lfec(pt);
- std::sort(count.begin(), count.end(), lfec);
+ polygon_sort(count.begin(), count.end(), lfec);
}
typedef std::vector<std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*> > incoming_count;
@@ -1196,13 +1237,13 @@
Unit dx2 = elm2.first.first.first.get(HORIZONTAL) - elm2.first.first.second.get(HORIZONTAL);
Unit dy1 = elm1.first.first.first.get(VERTICAL) - elm1.first.first.second.get(VERTICAL);
Unit dy2 = elm2.first.first.first.get(VERTICAL) - elm2.first.first.second.get(VERTICAL);
- return less_slope(dx1, dy1, dx2, dy2);
+ return scanline_base<Unit>::less_slope(dx1, dy1, dx2, dy2);
}
};
static inline void sort_incoming_count(incoming_count& count, const Point& pt) {
less_incoming_count lfec(pt);
- std::sort(count.begin(), count.end(), lfec);
+ polygon_sort(count.begin(), count.end(), lfec);
}
static inline void compact_vertex_arbitrary_count(const Point& pt, vertex_arbitrary_count &count) {
@@ -1356,7 +1397,7 @@
bool have_vertical_tail_from_below = false;
if(c_size &&
- is_vertical(counts_from_scanline.back().first.first)) {
+ scanline_base<Unit>::is_vertical(counts_from_scanline.back().first.first)) {
have_vertical_tail_from_below = true;
}
//assert size = size_less_1 + 1
@@ -1704,7 +1745,7 @@
//std::cout << "checking whether ot handle hole\n";
if(currentIter == inputEnd ||
currentIter->pt.get(HORIZONTAL) != x_ ||
- on_above_or_below(currentIter->pt, half_edge(iter->first.pt, iter->first.other_pt)) != -1) {
+ scanline_base<Unit>::on_above_or_below(currentIter->pt, half_edge(iter->first.pt, iter->first.other_pt)) != -1) {
//(high_precision)(currentIter->pt.get(VERTICAL)) >= iter->first.evalAtX(x_)) {
//std::cout << "handle hole here\n";
@@ -1773,7 +1814,7 @@
data.push_back(vertex_half_edge(Point(10, 0), Point(10, 10), -1));
data.push_back(vertex_half_edge(Point(10, 10), Point(10, 0), 1));
data.push_back(vertex_half_edge(Point(10, 10), Point(0, 10), 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1797,7 +1838,7 @@
data.push_back(vertex_half_edge(Point(10, 10), Point(10, 20), -1));
data.push_back(vertex_half_edge(Point(10, 20), Point(10, 10), 1));
data.push_back(vertex_half_edge(Point(10, 20), Point(0, 10), 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1821,7 +1862,7 @@
data.push_back(vertex_half_edge(Point(2, -4), Point(2, 4), -1));
data.push_back(vertex_half_edge(Point(2, 4), Point(-2, 2), 1));
data.push_back(vertex_half_edge(Point(2, 4), Point(2, -4), 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1867,7 +1908,7 @@
data.push_back(vertex_half_edge(Point(10, 22), Point(10, 12), -1));
data.push_back(vertex_half_edge(Point(10, 22), Point(2, 22), -1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1914,7 +1955,7 @@
data.push_back(vertex_half_edge(Point(7, 2), Point(5, 5), -1));
data.push_back(vertex_half_edge(Point(7, 2), Point(5, 2), 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1954,7 +1995,7 @@
data.push_back(vertex_half_edge(Point(7, 2), Point(5, 5), -1));
data.push_back(vertex_half_edge(Point(7, 2), Point(4, 1), 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -1994,7 +2035,7 @@
data.push_back(vertex_half_edge(Point(7, 2), Point(5, 5), -1));
data.push_back(vertex_half_edge(Point(7, 2), Point(4, 1), 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -2022,7 +2063,7 @@
data.push_back(vertex_half_edge(Point(-1, 4), Point(0, 2), -1));
data.push_back(vertex_half_edge(Point(0, 2), Point(-1, 4), 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -2041,26 +2082,26 @@
he2.first = Point(0, 0);
he2.second = Point(10, 20);
Point result;
- bool b = compute_intersection(result, he1, he2);
+ bool b = scanline_base<Unit>::compute_intersection(result, he1, he2);
if(!b || result != Point(0, 0)) return false;
he1.first = Point(0, 10);
- b = compute_intersection(result, he1, he2);
+ b = scanline_base<Unit>::compute_intersection(result, he1, he2);
if(!b || result != Point(5, 10)) return false;
he1.first = Point(0, 11);
- b = compute_intersection(result, he1, he2);
+ b = scanline_base<Unit>::compute_intersection(result, he1, he2);
if(!b || result != Point(5, 10)) return false;
he1.first = Point(0, 0);
he1.second = Point(1, 9);
he2.first = Point(0, 9);
he2.second = Point(1, 0);
- b = compute_intersection(result, he1, he2);
+ b = scanline_base<Unit>::compute_intersection(result, he1, he2);
if(!b || result != Point(0, 4)) return false;
he1.first = Point(0, -10);
he1.second = Point(1, -1);
he2.first = Point(0, -1);
he2.second = Point(1, -10);
- b = compute_intersection(result, he1, he2);
+ b = scanline_base<Unit>::compute_intersection(result, he1, he2);
if(!b || result != Point(0, -5)) return false;
he1.first = Point((std::numeric_limits<int>::max)(), (std::numeric_limits<int>::max)()-1);
he1.second = Point((std::numeric_limits<int>::min)(), (std::numeric_limits<int>::max)());
@@ -2068,13 +2109,13 @@
he2.first = Point((std::numeric_limits<int>::max)()-1, (std::numeric_limits<int>::max)());
he2.second = Point((std::numeric_limits<int>::max)(), (std::numeric_limits<int>::min)());
//he2.second = Point((std::numeric_limits<int>::max)(), 0);
- b = compute_intersection(result, he1, he2);
+ b = scanline_base<Unit>::compute_intersection(result, he1, he2);
//b is false because of overflow error
he1.first = Point(1000, 2000);
he1.second = Point(1010, 2010);
he2.first = Point(1000, 2000);
he2.second = Point(1010, 2020);
- b = compute_intersection(result, he1, he2);
+ b = scanline_base<Unit>::compute_intersection(result, he1, he2);
if(!b || result != Point(1000, 2000)) return false;
return b;
@@ -2301,7 +2342,7 @@
bool have_vertical_tail_from_below = false;
if(c_size &&
- is_vertical(counts_from_scanline.back().first.first)) {
+ scanline_base<Unit>::is_vertical(counts_from_scanline.back().first.first)) {
have_vertical_tail_from_below = true;
}
//assert size = size_less_1 + 1
@@ -2607,7 +2648,7 @@
//std::cout << "current Y " << currentY << std::endl;
//std::cout << "scanline size " << scanData_.size() << std::endl;
//print(scanData_);
- iterator iter = lookUp_(currentY);
+ iterator iter = this->lookUp_(currentY);
//std::cout << "found element in scanline " << (iter != scanData_.end()) << std::endl;
//int counts[4] = {0, 0, 0, 0};
incoming_count counts_from_scanline;
@@ -2634,7 +2675,7 @@
}
Point currentPoint(polygon_arbitrary_formation<Unit>::x_, currentY);
//std::cout << "counts_from_scanline size " << counts_from_scanline.size() << std::endl;
- sort_incoming_count(counts_from_scanline, currentPoint);
+ this->sort_incoming_count(counts_from_scanline, currentPoint);
vertex_arbitrary_count incoming;
//std::cout << "aggregating\n";
@@ -2646,7 +2687,7 @@
} while(currentIter != inputEnd && currentIter->pt.get(VERTICAL) == currentY &&
currentIter->pt.get(HORIZONTAL) == polygon_arbitrary_formation<Unit>::x_);
//print(incoming);
- sort_vertex_arbitrary_count(incoming, currentPoint);
+ this->sort_vertex_arbitrary_count(incoming, currentPoint);
//std::cout << currentPoint.get(HORIZONTAL) << "," << currentPoint.get(VERTICAL) << std::endl;
//print(incoming);
//std::cout << "incoming counts from input size " << incoming.size() << std::endl;
@@ -2728,7 +2769,7 @@
data.push_back(vertex_half_edge(Point(10, 0), Point(10, 10), -1));
data.push_back(vertex_half_edge(Point(10, 10), Point(10, 0), 1));
data.push_back(vertex_half_edge(Point(10, 10), Point(0, 10), 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -2751,7 +2792,7 @@
data.push_back(vertex_half_edge(Point(10, 10), Point(10, 20), -1));
data.push_back(vertex_half_edge(Point(10, 20), Point(10, 10), 1));
data.push_back(vertex_half_edge(Point(10, 20), Point(0, 10), 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -2774,7 +2815,7 @@
data.push_back(vertex_half_edge(Point(2, -4), Point(2, 4), -1));
data.push_back(vertex_half_edge(Point(2, 4), Point(-2, 2), 1));
data.push_back(vertex_half_edge(Point(2, 4), Point(2, -4), 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -2819,7 +2860,7 @@
data.push_back(vertex_half_edge(Point(10, 22), Point(10, 12), -1));
data.push_back(vertex_half_edge(Point(10, 22), Point(2, 22), -1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
@@ -2866,7 +2907,7 @@
data.push_back(vertex_half_edge(Point(7, 2), Point(5, 5), -1));
data.push_back(vertex_half_edge(Point(7, 2), Point(5, 2), 1));
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(polys, data.begin(), data.end());
stdcout << "result size: " << polys.size() << std::endl;
for(std::size_t i = 0; i < polys.size(); ++i) {
Modified: sandbox/gtl/boost/polygon/detail/polygon_formation.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/polygon_formation.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/polygon_formation.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -1721,7 +1721,7 @@
unsigned int get_polygons(output_container& container, iterator_type begin, iterator_type end,
orientation_2d orient, bool fracture_holes, concept_type ) {
typedef typename output_container::value_type polygon_type;
- typedef typename iterator_type::value_type::first_type coordinate_type;
+ typedef typename std::iterator_traits<iterator_type>::value_type::first_type coordinate_type;
polygon_type poly;
unsigned int countPolygons = 0;
typedef typename geometry_concept<polygon_type>::type polygon_concept_type;
Modified: sandbox/gtl/boost/polygon/detail/polygon_set_view.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/polygon_set_view.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/polygon_set_view.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -14,7 +14,13 @@
inline void polygon_set_data<coordinate_type>::clean() const {
if(dirty_) {
polygon_45_set_data<coordinate_type> tmp;
- if(downcast(tmp) ) {
+ //very important:
+ //the 45 degree algorithm does not satisfy
+ //the precondition of arbitrary polygon formation
+ //that vertices be "linearly consistent"
+ //therefore it doesn't work to fall back on 45-degree
+ //booleans for arbitrary angle polygons
+ if(0) { //downcast(tmp) ) {
tmp.clean();
data_.clear();
is_45_ = true;
@@ -153,13 +159,13 @@
};
template <typename ltype, typename rtype, int op_type>
- typename polygon_set_view<ltype, rtype, op_type>::iterator_type
+ typename polygon_set_traits<polygon_set_view<ltype, rtype, op_type> >::iterator_type
polygon_set_traits<polygon_set_view<ltype, rtype, op_type> >::
begin(const polygon_set_view<ltype, rtype, op_type>& polygon_set) {
return polygon_set.begin();
}
template <typename ltype, typename rtype, int op_type>
- typename polygon_set_view<ltype, rtype, op_type>::iterator_type
+ typename polygon_set_traits<polygon_set_view<ltype, rtype, op_type> >::iterator_type
polygon_set_traits<polygon_set_view<ltype, rtype, op_type> >::
end(const polygon_set_view<ltype, rtype, op_type>& polygon_set) {
return polygon_set.end();
Added: sandbox/gtl/boost/polygon/detail/polygon_simplify.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/detail/polygon_simplify.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -0,0 +1,116 @@
+// Copyright 2011, Andrew Ross
+//
+// 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_DETAIL_SIMPLIFY_HPP
+#define BOOST_POLYGON_DETAIL_SIMPLIFY_HPP
+#include <vector>
+
+namespace boost { namespace polygon { namespace detail { namespace simplify_detail {
+
+ // Does a simplification/optimization pass on the polygon. If a given
+ // vertex lies within "len" of the line segment joining its neighbor
+ // vertices, it is removed.
+ template <typename T> //T is a model of point concept
+ std::size_t simplify(std::vector<T>& dst, const std::vector<T>& src,
+ typename coordinate_traits<
+ typename point_traits<T>::coordinate_type
+ >::coordinate_distance len)
+ {
+ using namespace boost::polygon;
+ typedef typename point_traits<T>::coordinate_type coordinate_type;
+ typedef typename coordinate_traits<coordinate_type>::area_type ftype;
+ typedef typename std::vector<T>::const_iterator iter;
+
+ std::vector<T> out;
+ out.reserve(src.size());
+ dst = src;
+ std::size_t final_result = 0;
+ std::size_t orig_size = src.size();
+
+ //I can't use == if T doesn't provide it, so use generic point concept compare
+ bool closed = equivalence(src.front(), src.back());
+
+ //we need to keep smoothing until we don't find points to remove
+ //because removing points in the first iteration through the
+ //polygon may leave it in a state where more removal is possible
+ bool not_done = true;
+ while(not_done) {
+ if(dst.size() < 3) {
+ dst.clear();
+ return orig_size;
+ }
+
+ // Start with the second, test for the last point
+ // explicitly, and exit after looping back around to the first.
+ ftype len2 = ftype(len) * ftype(len);
+ for(iter prev=dst.begin(), i=prev+1, next; /**/; i = next) {
+ next = i+1;
+ if(next == dst.end())
+ next = dst.begin();
+
+ // points A, B, C
+ ftype ax = x(*prev), ay = y(*prev);
+ ftype bx = x(*i), by = y(*i);
+ ftype cx = x(*next), cy = y(*next);
+
+ // vectors AB, BC and AC:
+ ftype abx = bx-ax, aby = by-ay;
+ ftype bcx = cx-bx, bcy = cy-by;
+ ftype acx = cx-ax, acy = cy-ay;
+
+ // dot products
+ ftype ab_ab = abx*abx + aby*aby;
+ ftype bc_bc = bcx*bcx + bcy*bcy;
+ ftype ac_ac = acx*acx + acy*acy;
+ ftype ab_ac = abx*acx + aby*acy;
+
+ // projection of AB along AC
+ ftype projf = ab_ac / ac_ac;
+ ftype projx = acx * projf, projy = acy * projf;
+
+ // perpendicular vector from the line AC to point B (i.e. AB - proj)
+ ftype perpx = abx - projx, perpy = aby - projy;
+
+ // Squared fractional distance of projection. FIXME: can
+ // remove this division, the decisions below can be made with
+ // just the sign of the quotient and a check to see if
+ // abs(numerator) is greater than abs(divisor).
+ ftype f2 = (projx*acx + projy*acx) / ac_ac;
+
+ // Square of the relevant distance from point B:
+ ftype dist2;
+ if (f2 < 0) dist2 = ab_ab;
+ else if(f2 > 1) dist2 = bc_bc;
+ else dist2 = perpx*perpx + perpy*perpy;
+
+ if(dist2 > len2) {
+ prev = i; // bump prev, we didn't remove the segment
+ out.push_back(*i);
+ }
+
+ if(i == dst.begin())
+ break;
+ }
+ std::size_t result = dst.size() - out.size();
+ if(result == 0) {
+ not_done = false;
+ } else {
+ final_result += result;
+ dst = out;
+ out.clear();
+ }
+ } //end of while loop
+ if(closed) {
+ //if the input was closed we want the output to be closed
+ --final_result;
+ dst.push_back(dst.front());
+ }
+ return final_result;
+ }
+
+
+}}}}
+
+#endif
Added: sandbox/gtl/boost/polygon/detail/polygon_sort_adaptor.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/detail/polygon_sort_adaptor.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -0,0 +1,67 @@
+/*
+ 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_SORT_ADAPTOR_HPP
+#define BOOST_POLYGON_SORT_ADAPTOR_HPP
+#ifdef __ICC
+#pragma warning(disable:2022)
+#pragma warning(disable:2023)
+#endif
+
+#include <algorithm>
+
+//! @brief polygon_sort_adaptor default implementation that calls std::sort
+namespace boost {
+ namespace polygon {
+
+ template<typename iterator_type>
+ struct dummy_to_delay_instantiation{
+ typedef int unit_type; // default GTL unit
+ };
+
+ //! @brief polygon_sort_adaptor default implementation that calls std::sort
+ template<typename T>
+ struct polygon_sort_adaptor {
+ //! @brief wrapper that mimics std::sort() function and takes
+ // the same arguments
+ template<typename RandomAccessIterator_Type>
+ static void sort(RandomAccessIterator_Type _First,
+ RandomAccessIterator_Type _Last)
+ {
+ std::sort(_First, _Last);
+ }
+ //! @brief wrapper that mimics std::sort() function overload and takes
+ // the same arguments
+ template<typename RandomAccessIterator_Type, typename Pred_Type>
+ static void sort(RandomAccessIterator_Type _First,
+ RandomAccessIterator_Type _Last,
+ const Pred_Type& _Comp)
+ {
+ std::sort(_First, _Last, _Comp);
+ }
+ };
+
+ //! @brief user level wrapper for sorting quantities
+ template <typename iter_type>
+ void polygon_sort(iter_type _b_, iter_type _e_)
+ {
+ polygon_sort_adaptor<typename dummy_to_delay_instantiation<iter_type>::unit_type>::sort(_b_, _e_);
+ }
+
+ //! @brief user level wrapper for sorting quantities that takes predicate
+ // as additional argument
+ template <typename iter_type, typename pred_type>
+ void polygon_sort(iter_type _b_, iter_type _e_, const pred_type& _pred_)
+ {
+ polygon_sort_adaptor<typename dummy_to_delay_instantiation<iter_type>::unit_type>::sort(_b_, _e_, _pred_);
+ }
+
+
+
+ } // namespace polygon
+} // namespace boost
+#endif
Modified: sandbox/gtl/boost/polygon/detail/property_merge.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/property_merge.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/property_merge.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -112,7 +112,7 @@
inline void perform_merge(result_type& result, property_merge_data& data) {
if(data.empty()) return;
//sort
- std::sort(data.begin(), data.end(), less_vertex_data<vertex_property>());
+ polygon_sort(data.begin(), data.end(), less_vertex_data<vertex_property>());
//scanline
bool firstIteration = true;
scanlinePosition = scanline.end();
@@ -156,7 +156,7 @@
class less_vertex_data {
public:
less_vertex_data() {}
- bool operator()(const T& lvalue, const T& rvalue) {
+ bool operator()(const T& lvalue, const T& rvalue) const {
if(lvalue.first.x() < rvalue.first.x()) return true;
if(lvalue.first.x() > rvalue.first.x()) return false;
if(lvalue.first.y() < rvalue.first.y()) return true;
@@ -442,7 +442,7 @@
inline void performExtract(T& result, property_merge_data& data) {
if(data.empty()) return;
//sort
- std::sort(data.begin(), data.end(), less_vertex_data<vertex_property>());
+ polygon_sort(data.begin(), data.end(), less_vertex_data<vertex_property>());
//scanline
bool firstIteration = true;
Modified: sandbox/gtl/boost/polygon/detail/property_merge_45.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/property_merge_45.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/property_merge_45.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -111,7 +111,7 @@
template <typename output_type>
static void performMerge(output_type& result, MergeSetData& tsd) {
- std::sort(tsd.begin(), tsd.end(), lessVertex45Compact());
+ polygon_sort(tsd.begin(), tsd.end(), lessVertex45Compact());
typedef std::vector<std::pair<Point, typename boolean_op_45<Unit>::template Scan45CountT<CountMerge> > > TSD;
TSD tsd_;
tsd_.reserve(tsd.size());
Modified: sandbox/gtl/boost/polygon/detail/scan_arbitrary.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/scan_arbitrary.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/scan_arbitrary.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -10,6 +10,7 @@
#ifdef BOOST_POLYGON_DEBUG_FILE
#include <fstream>
#endif
+#include "polygon_sort_adaptor.hpp"
namespace boost { namespace polygon{
template <typename Unit>
@@ -33,38 +34,38 @@
typedef std::map<half_edge, std::set<segment_id>, less_half_edge> edge_scanline;
typedef typename edge_scanline::iterator iterator;
- std::map<Unit, std::set<segment_id> > vertical_data_;
- edge_scanline edge_scanline_;
- Unit x_;
- int just_before_;
- segment_id segment_id_;
- std::vector<std::pair<half_edge, int> > event_edges_;
- std::set<Point> intersection_queue_;
+// std::map<Unit, std::set<segment_id> > vertical_data_;
+// edge_scanline edge_scanline_;
+// Unit x_;
+// int just_before_;
+// segment_id segment_id_;
+// std::vector<std::pair<half_edge, int> > event_edges_;
+// std::set<Point> intersection_queue_;
public:
- inline line_intersection() : vertical_data_(), edge_scanline_(), x_((std::numeric_limits<Unit>::max)()), just_before_(0), segment_id_(0), event_edges_(), intersection_queue_() {
- less_half_edge lessElm(&x_, &just_before_);
- edge_scanline_ = edge_scanline(lessElm);
- }
- inline line_intersection(const line_intersection& that) : vertical_data_(), edge_scanline_(), x_(), just_before_(), segment_id_(), event_edges_(), intersection_queue_() { (*this) = that; }
- inline line_intersection& operator=(const line_intersection& that) {
- x_ = that.x_;
- just_before_ = that.just_before_;
- segment_id_ = that.segment_id_;
+// inline line_intersection() : vertical_data_(), edge_scanline_(), x_((std::numeric_limits<Unit>::max)()), just_before_(0), segment_id_(0), event_edges_(), intersection_queue_() {
+// less_half_edge lessElm(&x_, &just_before_);
+// edge_scanline_ = edge_scanline(lessElm);
+// }
+// inline line_intersection(const line_intersection& that) : vertical_data_(), edge_scanline_(), x_(), just_before_(), segment_id_(), event_edges_(), intersection_queue_() { (*this) = that; }
+// inline line_intersection& operator=(const line_intersection& that) {
+// x_ = that.x_;
+// just_before_ = that.just_before_;
+// segment_id_ = that.segment_id_;
- //I cannot simply copy that.edge_scanline_ to this edge_scanline_ becuase the functor store pointers to other members!
- less_half_edge lessElm(&x_, &just_before_);
- edge_scanline_ = edge_scanline(lessElm);
-
- edge_scanline_.insert(that.edge_scanline_.begin(), that.edge_scanline_.end());
- return *this;
- }
-
- static inline void between(Point pt, Point pt1, Point pt2) {
- less_point lp;
- if(lp(pt1, pt2))
- return lp(pt, pt2) && lp(pt1, pt);
- return lp(pt, pt1) && lp(pt2, pt);
- }
+// //I cannot simply copy that.edge_scanline_ to this edge_scanline_ becuase the functor store pointers to other members!
+// less_half_edge lessElm(&x_, &just_before_);
+// edge_scanline_ = edge_scanline(lessElm);
+
+// edge_scanline_.insert(that.edge_scanline_.begin(), that.edge_scanline_.end());
+// return *this;
+// }
+
+// static inline void between(Point pt, Point pt1, Point pt2) {
+// less_point lp;
+// if(lp(pt1, pt2))
+// return lp(pt, pt2) && lp(pt1, pt);
+// return lp(pt, pt1) && lp(pt2, pt);
+// }
template <typename iT>
static inline void compute_histogram_in_y(iT begin, iT end, std::size_t size, std::vector<std::pair<Unit, std::pair<std::size_t, std::size_t> > >& histogram) {
@@ -75,7 +76,7 @@
ends.push_back(std::make_pair((*itr).first.first.y(), count));
ends.push_back(std::make_pair((*itr).first.second.y(), -count));
}
- std::sort(ends.begin(), ends.end());
+ polygon_sort(ends.begin(), ends.end());
histogram.reserve(ends.size());
histogram.push_back(std::make_pair(ends.front().first, std::make_pair(0, 0)));
for(typename std::vector<std::pair<Unit, int> >::iterator itr = ends.begin(); itr != ends.end(); ++itr) {
@@ -160,7 +161,7 @@
}
}
typename scanline_base<Unit>::compute_intersection_pack pack_;
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
//find all intersection points
for(typename std::vector<std::pair<half_edge, segment_id> >::iterator outer = data.begin();
outer != data.end(); ++outer) {
@@ -191,11 +192,13 @@
if(pack_.compute_intersection(intersection, he1, he2)) {
//their intersection point
pts.push_back(intersection);
+ intersection_points[(*inner).second].insert(intersection);
+ intersection_points[(*outer).second].insert(intersection);
}
}
}
}
- std::sort(pts.begin(), pts.end());
+ polygon_sort(pts.begin(), pts.end());
typename std::vector<Point>::iterator newend = std::unique(pts.begin(), pts.end());
typename std::vector<Point>::iterator lfinger = pts.begin();
//find all segments that interact with intersection points
@@ -216,7 +219,7 @@
//itr2 = pts.end();
while(lfinger != newend && (*lfinger).x() < startpt.x()) ++lfinger;
for(typename std::vector<Point>::iterator itr = lfinger ; itr != newend && (*itr).x() <= stoppt.x(); ++itr) {
- if(intersects_grid(*itr, he1))
+ if(scanline_base<Unit>::intersects_grid(*itr, he1))
intersection_points[id1].insert(*itr);
}
}
@@ -243,8 +246,8 @@
//edge changed orientation, invert count on edge
output_segments.back().second.second *= -1;
}
- if(!is_vertical(input_segments[intermediate_segments[i].second].first) &&
- is_vertical(output_segments.back().first)) {
+ if(!scanline_base<Unit>::is_vertical(input_segments[intermediate_segments[i].second].first) &&
+ scanline_base<Unit>::is_vertical(output_segments.back().first)) {
output_segments.back().second.second *= -1;
}
if(lp(output_segments.back().first.second, output_segments.back().first.first)) {
@@ -286,7 +289,7 @@
std::swap(data[i].first.first, data[i].first.second);
}
}
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
for(typename std::vector<std::pair<half_edge, segment_id> >::iterator outer = data.begin();
outer != data.end(); ++outer) {
const half_edge& he1 = (*outer).first;
@@ -349,14 +352,14 @@
segment_id id = (*iter).second;
const std::set<Point>& pts = intersection_points[id];
Point hpt(he.first.get(HORIZONTAL)+1, he.first.get(VERTICAL));
- if(!is_vertical(he) && less_slope(he.first.get(HORIZONTAL), he.first.get(VERTICAL),
+ if(!scanline_base<Unit>::is_vertical(he) && scanline_base<Unit>::less_slope(he.first.get(HORIZONTAL), he.first.get(VERTICAL),
he.second, hpt)) {
//slope is below horizontal
std::vector<Point> tmpPts;
tmpPts.reserve(pts.size());
tmpPts.insert(tmpPts.end(), pts.begin(), pts.end());
less_point_down_slope lpds;
- std::sort(tmpPts.begin(), tmpPts.end(), lpds);
+ polygon_sort(tmpPts.begin(), tmpPts.end(), lpds);
segment_edge(output_segments, he, id, tmpPts.begin(), tmpPts.end());
} else {
segment_edge(output_segments, he, id, pts.begin(), pts.end());
@@ -365,263 +368,263 @@
}
}
- //iT iterator over unsorted pair<Point> representing line segments of input
- //output_segments is populated with fully intersected output line segment half
- //edges and the index of the input segment that they are assoicated with
- //duplicate output half edges with different ids will be generated in the case
- //that parallel input segments intersection
- //outputs are in sorted order and include both begin and end events for
- //each segment
- template <typename iT>
- inline void scan(std::vector<std::pair<half_edge, int> >& output_segments,
- iT begin, iT end) {
- std::map<segment_id, std::set<Point> > intersection_points;
- scan(intersection_points, begin, end);
- segment_intersections(output_segments, intersection_points, begin, end);
- }
-
- //iT iterator over sorted sequence of half edge, segment id pairs representing segment begin and end points
- //intersection points provides a mapping from input segment id (vector index) to the set
- //of intersection points assocated with that input segment
- template <typename iT>
- inline void scan(std::map<segment_id, std::set<Point> >& intersection_points,
- iT begin, iT end) {
- for(iT iter = begin; iter != end; ++iter) {
- const std::pair<half_edge, int>& elem = *iter;
- const half_edge& he = elem.first;
- Unit current_x = he.first.get(HORIZONTAL);
- if(current_x != x_) {
- process_scan_event(intersection_points);
- while(!intersection_queue_.empty() &&
- (*(intersection_queue_.begin()).get(HORIZONTAL) < current_x)) {
- x_ = *(intersection_queue_.begin()).get(HORIZONTAL);
- process_intersections_at_scan_event(intersection_points);
- }
- x_ = current_x;
- }
- event_edges_.push_back(elem);
- }
- process_scan_event(intersection_points);
- }
+// //iT iterator over unsorted pair<Point> representing line segments of input
+// //output_segments is populated with fully intersected output line segment half
+// //edges and the index of the input segment that they are assoicated with
+// //duplicate output half edges with different ids will be generated in the case
+// //that parallel input segments intersection
+// //outputs are in sorted order and include both begin and end events for
+// //each segment
+// template <typename iT>
+// inline void scan(std::vector<std::pair<half_edge, int> >& output_segments,
+// iT begin, iT end) {
+// std::map<segment_id, std::set<Point> > intersection_points;
+// scan(intersection_points, begin, end);
+// segment_intersections(output_segments, intersection_points, begin, end);
+// }
+
+// //iT iterator over sorted sequence of half edge, segment id pairs representing segment begin and end points
+// //intersection points provides a mapping from input segment id (vector index) to the set
+// //of intersection points assocated with that input segment
+// template <typename iT>
+// inline void scan(std::map<segment_id, std::set<Point> >& intersection_points,
+// iT begin, iT end) {
+// for(iT iter = begin; iter != end; ++iter) {
+// const std::pair<half_edge, int>& elem = *iter;
+// const half_edge& he = elem.first;
+// Unit current_x = he.first.get(HORIZONTAL);
+// if(current_x != x_) {
+// process_scan_event(intersection_points);
+// while(!intersection_queue_.empty() &&
+// (*(intersection_queue_.begin()).get(HORIZONTAL) < current_x)) {
+// x_ = *(intersection_queue_.begin()).get(HORIZONTAL);
+// process_intersections_at_scan_event(intersection_points);
+// }
+// x_ = current_x;
+// }
+// event_edges_.push_back(elem);
+// }
+// process_scan_event(intersection_points);
+// }
- inline iterator lookup(const half_edge& he) {
- return edge_scanline_.find(he);
- }
+// inline iterator lookup(const half_edge& he) {
+// return edge_scanline_.find(he);
+// }
+
+// inline void insert_into_scanline(const half_edge& he, int id) {
+// edge_scanline_[he].insert(id);
+// }
+
+// inline void lookup_and_remove(const half_edge& he, int id) {
+// iterator remove_iter = lookup(he);
+// if(remove_iter == edge_scanline_.end()) {
+// //std::cout << "failed to find removal segment in scanline\n";
+// return;
+// }
+// std::set<segment_id>& ids = (*remove_iter).second;
+// std::set<segment_id>::iterator id_iter = ids.find(id);
+// if(id_iter == ids.end()) {
+// //std::cout << "failed to find removal segment id in scanline set\n";
+// return;
+// }
+// ids.erase(id_iter);
+// if(ids.empty())
+// edge_scanline_.erase(remove_iter);
+// }
+
+// static inline void update_segments(std::map<segment_id, std::set<Point> >& intersection_points,
+// const std::set<segment_id>& segments, Point pt) {
+// for(std::set<segment_id>::const_iterator itr = segments.begin(); itr != segments.end(); ++itr) {
+// intersection_points[*itr].insert(pt);
+// }
+// }
- inline void insert_into_scanline(const half_edge& he, int id) {
- edge_scanline_[he].insert(id);
- }
+// inline void process_intersections_at_scan_event(std::map<segment_id, std::set<Point> >& intersection_points) {
+// //there may be additional intersection points at this x location that haven't been
+// //found yet if vertical or near vertical line segments intersect more than
+// //once before the next x location
+// just_before_ = true;
+// std::set<iterator> intersecting_elements;
+// std::set<Unit> intersection_locations;
+// typedef typename std::set<Point>::iterator intersection_iterator;
+// intersection_iterator iter;
+// //first find all secondary intersection locations and all scanline iterators
+// //that are intersecting
+// for(iter = intersection_queue_.begin();
+// iter != intersection_queue_.end() && (*iter).get(HORIZONTAL) == x_; ++iter) {
+// Point pt = *iter;
+// Unit y = pt.get(VERTICAL);
+// intersection_locations.insert(y);
+// //if x_ is max there can be only end events and no sloping edges
+// if(x_ != (std::numeric_limits<Unit>::max)()) {
+// //deal with edges that project to the right of scanline
+// //first find the edges in the scanline adjacent to primary intersectin points
+// //lookup segment in scanline at pt
+// iterator itr = edge_scanline_.lower_bound(half_edge(pt, Point(x_+1, y)));
+// //look above pt in scanline until reaching end or segment that doesn't intersect
+// //1x1 grid upper right of pt
+// //look below pt in scanline until reaching begin or segment that doesn't interset
+// //1x1 grid upper right of pt
- inline void lookup_and_remove(const half_edge& he, int id) {
- iterator remove_iter = lookup(he);
- if(remove_iter == edge_scanline_.end()) {
- //std::cout << "failed to find removal segment in scanline\n";
- return;
- }
- std::set<segment_id>& ids = (*remove_iter).second;
- std::set<segment_id>::iterator id_iter = ids.find(id);
- if(id_iter == ids.end()) {
- //std::cout << "failed to find removal segment id in scanline set\n";
- return;
- }
- ids.erase(id_iter);
- if(ids.empty())
- edge_scanline_.erase(remove_iter);
- }
+// //second find edges in scanline on the y interval of each edge found in the previous
+// //step for x_ to x_ + 1
- static inline void update_segments(std::map<segment_id, std::set<Point> >& intersection_points,
- const std::set<segment_id>& segments, Point pt) {
- for(std::set<segment_id>::const_iterator itr = segments.begin(); itr != segments.end(); ++itr) {
- intersection_points[*itr].insert(pt);
- }
- }
+// //third find overlaps in the y intervals of all found edges to find all
+// //secondary intersection points
- inline void process_intersections_at_scan_event(std::map<segment_id, std::set<Point> >& intersection_points) {
- //there may be additional intersection points at this x location that haven't been
- //found yet if vertical or near vertical line segments intersect more than
- //once before the next x location
- just_before_ = true;
- std::set<iterator> intersecting_elements;
- std::set<Unit> intersection_locations;
- typedef typename std::set<Point>::iterator intersection_iterator;
- intersection_iterator iter;
- //first find all secondary intersection locations and all scanline iterators
- //that are intersecting
- for(iter = intersection_queue_.begin();
- iter != intersection_queue_.end() && (*iter).get(HORIZONTAL) == x_; ++iter) {
- Point pt = *iter;
- Unit y = pt.get(VERTICAL);
- intersection_locations.insert(y);
- //if x_ is max there can be only end events and no sloping edges
- if(x_ != (std::numeric_limits<Unit>::max)()) {
- //deal with edges that project to the right of scanline
- //first find the edges in the scanline adjacent to primary intersectin points
- //lookup segment in scanline at pt
- iterator itr = edge_scanline_.lower_bound(half_edge(pt, Point(x_+1, y)));
- //look above pt in scanline until reaching end or segment that doesn't intersect
- //1x1 grid upper right of pt
- //look below pt in scanline until reaching begin or segment that doesn't interset
- //1x1 grid upper right of pt
-
- //second find edges in scanline on the y interval of each edge found in the previous
- //step for x_ to x_ + 1
-
- //third find overlaps in the y intervals of all found edges to find all
- //secondary intersection points
-
- }
- }
- //erase the intersection points from the queue
- intersection_queue_.erase(intersection_queue_.begin(), iter);
- std::vector<scanline_element> insertion_edges;
- insertion_edges.reserve(intersecting_elements.size());
- std::vector<std::pair<Unit, iterator> > sloping_ends;
- //do all the work of updating the output of all intersecting
- for(typename std::set<iterator>::iterator inter_iter = intersecting_elements.begin();
- inter_iter != intersecting_elements.end(); ++inter_iter) {
- //if it is horizontal update it now and continue
- if(is_horizontal((*inter_iter).first)) {
- update_segments(intersection_points, (*inter_iter).second, Point(x_, (*inter_iter).first.get(VERTICAL)));
- } else {
- //if x_ is max there can be only end events and no sloping edges
- if(x_ != (std::numeric_limits<Unit>::max)()) {
- //insert its end points into the vector of sloping ends
- const half_edge& he = (*inter_iter).first;
- Unit y = evalAtXforY(x_, he.first, he.second);
- Unit y2 = evalAtXforY(x_+1, he.first, he.second);
- if(y2 >= y) y2 +=1; //we round up, in exact case we don't worry about overbite of one
- else y += 1; //downward sloping round up
- sloping_ends.push_back(std::make_pair(y, inter_iter));
- sloping_ends.push_back(std::make_pair(y2, inter_iter));
- }
- }
- }
+// }
+// }
+// //erase the intersection points from the queue
+// intersection_queue_.erase(intersection_queue_.begin(), iter);
+// std::vector<scanline_element> insertion_edges;
+// insertion_edges.reserve(intersecting_elements.size());
+// std::vector<std::pair<Unit, iterator> > sloping_ends;
+// //do all the work of updating the output of all intersecting
+// for(typename std::set<iterator>::iterator inter_iter = intersecting_elements.begin();
+// inter_iter != intersecting_elements.end(); ++inter_iter) {
+// //if it is horizontal update it now and continue
+// if(is_horizontal((*inter_iter).first)) {
+// update_segments(intersection_points, (*inter_iter).second, Point(x_, (*inter_iter).first.get(VERTICAL)));
+// } else {
+// //if x_ is max there can be only end events and no sloping edges
+// if(x_ != (std::numeric_limits<Unit>::max)()) {
+// //insert its end points into the vector of sloping ends
+// const half_edge& he = (*inter_iter).first;
+// Unit y = evalAtXforY(x_, he.first, he.second);
+// Unit y2 = evalAtXforY(x_+1, he.first, he.second);
+// if(y2 >= y) y2 +=1; //we round up, in exact case we don't worry about overbite of one
+// else y += 1; //downward sloping round up
+// sloping_ends.push_back(std::make_pair(y, inter_iter));
+// sloping_ends.push_back(std::make_pair(y2, inter_iter));
+// }
+// }
+// }
- //merge sloping element data
- std::sort(sloping_ends.begin(), sloping_ends.end());
- std::map<Unit, std::set<iterator> > sloping_elements;
- std::set<iterator> merge_elements;
- for(typename std::vector<std::pair<Unit, iterator> >::iterator slop_iter = sloping_ends.begin();
- slop_iter = sloping_ends.end(); ++slop_iter) {
- //merge into sloping elements
- typename std::set<iterator>::iterator merge_iterator = merge_elements.find((*slop_iter).second);
- if(merge_iterator = merge_elements.end()) {
- merge_elements.insert((*slop_iter).second);
- } else {
- merge_elements.erase(merge_iterator);
- }
- sloping_elements[(*slop_iter).first] = merge_elements;
- }
+// //merge sloping element data
+// polygon_sort(sloping_ends.begin(), sloping_ends.end());
+// std::map<Unit, std::set<iterator> > sloping_elements;
+// std::set<iterator> merge_elements;
+// for(typename std::vector<std::pair<Unit, iterator> >::iterator slop_iter = sloping_ends.begin();
+// slop_iter == sloping_ends.end(); ++slop_iter) {
+// //merge into sloping elements
+// typename std::set<iterator>::iterator merge_iterator = merge_elements.find((*slop_iter).second);
+// if(merge_iterator == merge_elements.end()) {
+// merge_elements.insert((*slop_iter).second);
+// } else {
+// merge_elements.erase(merge_iterator);
+// }
+// sloping_elements[(*slop_iter).first] = merge_elements;
+// }
- //scan intersection points
- typename std::map<Unit, std::set<segment_id> >::iterator vertical_iter = vertical_data_.begin();
- typename std::map<Unit, std::set<iterator> >::iterator sloping_iter = sloping_elements.begin();
- for(typename std::set<Unit>::iterator position_iter = intersection_locations.begin();
- position_iter = intersection_locations.end(); ++position_iter) {
- //look for vertical segments that intersect this point and update them
- Unit y = *position_iter;
- Point pt(x_, y);
- //handle vertical segments
- if(vertical_iter != vertical_data_.end()) {
- typename std::map<Unit, std::set<segment_id> >::iterator next_vertical = vertical_iter;
- for(++next_vertical; next_vertical != vertical_data_.end() &&
- (*next_vertical).first < y; ++next_vertical) {
- vertical_iter = next_vertical;
- }
- if((*vertical_iter).first < y && !(*vertical_iter).second.empty()) {
- update_segments(intersection_points, (*vertical_iter).second, pt);
- ++vertical_iter;
- if(vertical_iter != vertical_data_.end() && (*vertical_iter).first == y)
- update_segments(intersection_points, (*vertical_iter).second, pt);
- }
- }
- //handle sloping segments
- if(sloping_iter != sloping_elements.end()) {
- typename std::map<Unit, std::set<iterator> >::iterator next_sloping = sloping_iter;
- for(++next_sloping; next_sloping != sloping_elements.end() &&
- (*next_sloping).first < y; ++next_sloping) {
- sloping_iter = next_sloping;
- }
- if((*sloping_iter).first < y && !(*sloping_iter).second.empty()) {
- for(typename std::set<iterator>::iterator element_iter = (*sloping_iter).second.begin();
- element_iter != (*sloping_iter).second.end(); ++element_iter) {
- const half_edge& he = (*element_iter).first;
- if(intersects_grid(pt, he)) {
- update_segments(intersection_points, (*element_iter).second, pt);
- }
- }
- ++sloping_iter;
- if(sloping_iter != sloping_elements.end() && (*sloping_iter).first == y &&
- !(*sloping_iter).second.empty()) {
- for(typename std::set<iterator>::iterator element_iter = (*sloping_iter).second.begin();
- element_iter != (*sloping_iter).second.end(); ++element_iter) {
- const half_edge& he = (*element_iter).first;
- if(intersects_grid(pt, he)) {
- update_segments(intersection_points, (*element_iter).second, pt);
- }
- }
- }
- }
- }
- }
+// //scan intersection points
+// typename std::map<Unit, std::set<segment_id> >::iterator vertical_iter = vertical_data_.begin();
+// typename std::map<Unit, std::set<iterator> >::iterator sloping_iter = sloping_elements.begin();
+// for(typename std::set<Unit>::iterator position_iter = intersection_locations.begin();
+// position_iter == intersection_locations.end(); ++position_iter) {
+// //look for vertical segments that intersect this point and update them
+// Unit y = *position_iter;
+// Point pt(x_, y);
+// //handle vertical segments
+// if(vertical_iter != vertical_data_.end()) {
+// typename std::map<Unit, std::set<segment_id> >::iterator next_vertical = vertical_iter;
+// for(++next_vertical; next_vertical != vertical_data_.end() &&
+// (*next_vertical).first < y; ++next_vertical) {
+// vertical_iter = next_vertical;
+// }
+// if((*vertical_iter).first < y && !(*vertical_iter).second.empty()) {
+// update_segments(intersection_points, (*vertical_iter).second, pt);
+// ++vertical_iter;
+// if(vertical_iter != vertical_data_.end() && (*vertical_iter).first == y)
+// update_segments(intersection_points, (*vertical_iter).second, pt);
+// }
+// }
+// //handle sloping segments
+// if(sloping_iter != sloping_elements.end()) {
+// typename std::map<Unit, std::set<iterator> >::iterator next_sloping = sloping_iter;
+// for(++next_sloping; next_sloping != sloping_elements.end() &&
+// (*next_sloping).first < y; ++next_sloping) {
+// sloping_iter = next_sloping;
+// }
+// if((*sloping_iter).first < y && !(*sloping_iter).second.empty()) {
+// for(typename std::set<iterator>::iterator element_iter = (*sloping_iter).second.begin();
+// element_iter != (*sloping_iter).second.end(); ++element_iter) {
+// const half_edge& he = (*element_iter).first;
+// if(intersects_grid(pt, he)) {
+// update_segments(intersection_points, (*element_iter).second, pt);
+// }
+// }
+// ++sloping_iter;
+// if(sloping_iter != sloping_elements.end() && (*sloping_iter).first == y &&
+// !(*sloping_iter).second.empty()) {
+// for(typename std::set<iterator>::iterator element_iter = (*sloping_iter).second.begin();
+// element_iter != (*sloping_iter).second.end(); ++element_iter) {
+// const half_edge& he = (*element_iter).first;
+// if(intersects_grid(pt, he)) {
+// update_segments(intersection_points, (*element_iter).second, pt);
+// }
+// }
+// }
+// }
+// }
+// }
- //erase and reinsert edges into scanline with check for future intersection
- }
+// //erase and reinsert edges into scanline with check for future intersection
+// }
- inline void process_scan_event(std::map<segment_id, std::set<Point> >& intersection_points) {
- just_before_ = true;
+// inline void process_scan_event(std::map<segment_id, std::set<Point> >& intersection_points) {
+// just_before_ = true;
- //process end events by removing those segments from the scanline
- //and insert vertices of all events into intersection queue
- Point prev_point((std::numeric_limits<Unit>::min)(), (std::numeric_limits<Unit>::min)());
- less_point lp;
- std::set<segment_id> vertical_ids;
- vertical_data_.clear();
- for(std::size_t i = 0; i < event_edges_.size(); ++i) {
- segment_id id = event_edges_[i].second;
- const half_edge& he = event_edges_[i].first;
- //vertical half edges are handled during intersection processing because
- //they cannot be inserted into the scanline
- if(!is_vertical(he)) {
- if(lp(he.second, he.first)) {
- //half edge is end event
- lookup_and_remove(he, id);
- } else {
- //half edge is begin event
- insert_into_scanline(he, id);
- //note that they will be immediately removed and reinserted after
- //handling their intersection (vertex)
- //an optimization would allow them to be processed specially to avoid the redundant
- //removal and reinsertion
- }
- } else {
- //common case if you are lucky
- //update the map of y to set of segment id
- if(lp(he.second, he.first)) {
- //half edge is end event
- std::set<segment_id>::iterator itr = vertical_ids.find(id);
- if(itr == vertical_ids.end()) {
- //std::cout << "Failed to find end event id in vertical ids\n";
- } else {
- vertical_ids.erase(itr);
- vertical_data_[he.first.get(HORIZONTAL)] = vertical_ids;
- }
- } else {
- //half edge is a begin event
- vertical_ids.insert(id);
- vertical_data_[he.first.get(HORIZONTAL)] = vertical_ids;
- }
- }
- //prevent repeated insertion of same vertex into intersection queue
- if(prev_point != he.first)
- intersection_queue_.insert(he.first);
- else
- prev_point = he.first;
- // process intersections at scan event
- process_intersections_at_scan_event(intersection_points);
- }
- event_edges_.clear();
- }
+// //process end events by removing those segments from the scanline
+// //and insert vertices of all events into intersection queue
+// Point prev_point((std::numeric_limits<Unit>::min)(), (std::numeric_limits<Unit>::min)());
+// less_point lp;
+// std::set<segment_id> vertical_ids;
+// vertical_data_.clear();
+// for(std::size_t i = 0; i < event_edges_.size(); ++i) {
+// segment_id id = event_edges_[i].second;
+// const half_edge& he = event_edges_[i].first;
+// //vertical half edges are handled during intersection processing because
+// //they cannot be inserted into the scanline
+// if(!is_vertical(he)) {
+// if(lp(he.second, he.first)) {
+// //half edge is end event
+// lookup_and_remove(he, id);
+// } else {
+// //half edge is begin event
+// insert_into_scanline(he, id);
+// //note that they will be immediately removed and reinserted after
+// //handling their intersection (vertex)
+// //an optimization would allow them to be processed specially to avoid the redundant
+// //removal and reinsertion
+// }
+// } else {
+// //common case if you are lucky
+// //update the map of y to set of segment id
+// if(lp(he.second, he.first)) {
+// //half edge is end event
+// std::set<segment_id>::iterator itr = vertical_ids.find(id);
+// if(itr == vertical_ids.end()) {
+// //std::cout << "Failed to find end event id in vertical ids\n";
+// } else {
+// vertical_ids.erase(itr);
+// vertical_data_[he.first.get(HORIZONTAL)] = vertical_ids;
+// }
+// } else {
+// //half edge is a begin event
+// vertical_ids.insert(id);
+// vertical_data_[he.first.get(HORIZONTAL)] = vertical_ids;
+// }
+// }
+// //prevent repeated insertion of same vertex into intersection queue
+// if(prev_point != he.first)
+// intersection_queue_.insert(he.first);
+// else
+// prev_point = he.first;
+// // process intersections at scan event
+// process_intersections_at_scan_event(intersection_points);
+// }
+// event_edges_.clear();
+// }
public:
template <typename stream_type>
@@ -892,23 +895,23 @@
return false;
}
edges.pop_back();
- edges.push_back(std::make_pair(half_edge(Point(1, 0), Point(11, 11)), edges.size()));
+ edges.push_back(std::make_pair(half_edge(Point(1, 0), Point(11, 11)), (segment_id)edges.size()));
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "fail3\n";
return false;
}
- edges.push_back(std::make_pair(half_edge(Point(1, 0), Point(10, 11)), edges.size()));
+ edges.push_back(std::make_pair(half_edge(Point(1, 0), Point(10, 11)), (segment_id)edges.size()));
if(verify_scan(result, edges.begin(), edges.end())) {
stdcout << "fail4\n";
return false;
}
edges.pop_back();
- edges.push_back(std::make_pair(half_edge(Point(1, 2), Point(11, 11)), edges.size()));
+ edges.push_back(std::make_pair(half_edge(Point(1, 2), Point(11, 11)), (segment_id)edges.size()));
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "fail5 " << result.first << " " << result.second << "\n";
return false;
}
- edges.push_back(std::make_pair(half_edge(Point(0, 5), Point(0, 11)), edges.size()));
+ edges.push_back(std::make_pair(half_edge(Point(0, 5), Point(0, 11)), (segment_id)edges.size()));
if(verify_scan(result, edges.begin(), edges.end())) {
stdcout << "fail6 " << result.first << " " << result.second << "\n";
return false;
@@ -1048,7 +1051,7 @@
if(current_iter != scan_data_.end()) {
//make sure we are looking at element in scanline just below y
//if(evalAtXforY(x_, (*current_iter).first.first, (*current_iter).first.second) != y) {
- if(on_above_or_below(Point(x_, y), (*current_iter).first) != 0) {
+ if(scanline_base<Unit>::on_above_or_below(Point(x_, y), (*current_iter).first) != 0) {
Point e2(pt);
if(e2.get(VERTICAL) != (std::numeric_limits<Unit>::max)())
e2.set(VERTICAL, e2.get(VERTICAL) + 1);
@@ -1060,12 +1063,12 @@
if(current_iter != scan_data_.end()) {
//get the bottom iterator for elements at this point
//while(evalAtXforY(x_, (*current_iter).first.first, (*current_iter).first.second) >= (high_precision)y &&
- while(on_above_or_below(Point(x_, y), (*current_iter).first) != 1 &&
+ while(scanline_base<Unit>::on_above_or_below(Point(x_, y), (*current_iter).first) != 1 &&
current_iter != scan_data_.begin()) {
--current_iter;
}
//if(evalAtXforY(x_, (*current_iter).first.first, (*current_iter).first.second) >= (high_precision)y) {
- if(on_above_or_below(Point(x_, y), (*current_iter).first) != 1) {
+ if(scanline_base<Unit>::on_above_or_below(Point(x_, y), (*current_iter).first) != 1) {
properties_below.clear();
} else {
properties_below = (*current_iter).second;
@@ -1078,7 +1081,7 @@
while(current_iter != scan_data_.end() &&
//can only be true if y is integer
//evalAtXforY(x_, (*current_iter).first.first, (*current_iter).first.second) == y) {
- on_above_or_below(Point(x_, y), (*current_iter).first) == 0) {
+ scanline_base<Unit>::on_above_or_below(Point(x_, y), (*current_iter).first) == 0) {
//removal_set_.push_back(current_iter);
++current_iter;
}
@@ -1129,7 +1132,7 @@
y = vertical_edge_below.second.get(VERTICAL);
continue;
}
- if(is_vertical(he)) {
+ if(scanline_base<Unit>::is_vertical(he)) {
update_property_map(vertical_properties_above, vp.second);
vertical_edge_above = he;
} else {
@@ -1310,7 +1313,7 @@
output.push_back(vertex_half_edge(he.first, he.second, count));
output.push_back(vertex_half_edge(he.second, he.first, -count));
}
- std::sort(output.begin(), output.end());
+ polygon_sort(output.begin(), output.end());
}
class test_functor {
@@ -1514,7 +1517,7 @@
public:
less_vertex_data() : pack_() {}
less_vertex_data(typename scanline_base<Unit>::evalAtXforYPack* pack) : pack_(pack) {}
- bool operator()(const vertex_data_type& lvalue, const vertex_data_type& rvalue) {
+ bool operator() (const vertex_data_type& lvalue, const vertex_data_type& rvalue) const {
less_point lp;
if(lp(lvalue.first.first, rvalue.first.first)) return true;
if(lp(rvalue.first.first, lvalue.first.first)) return false;
@@ -1528,7 +1531,7 @@
inline void sort_property_merge_data() {
less_vertex_data<vertex_property> lvd(&evalAtXforYPack_);
- std::sort(pmd.begin(), pmd.end(), lvd);
+ polygon_sort(pmd.begin(), pmd.end(), lvd);
}
public:
inline property_merge_data& get_property_merge_data() { return pmd; }
@@ -1556,7 +1559,7 @@
sl.scan(result, mof, pmd.begin(), pmd.end());
}
- inline bool verify() {
+ inline bool verify1() {
std::pair<int, int> offenders;
std::vector<std::pair<half_edge, int> > lines;
int count = 0;
@@ -1573,7 +1576,7 @@
pts.push_back(lines[i].first.first);
pts.push_back(lines[i].first.second);
}
- std::sort(pts.begin(), pts.end());
+ polygon_sort(pts.begin(), pts.end());
for(std::size_t i = 0; i < pts.size(); i+=2) {
if(pts[i] != pts[i+1]) {
//stdcout << "Non-closed figures after line intersection!\n";
@@ -1683,7 +1686,7 @@
static inline void sort_vertex_half_edges(vertex_data& vertex) {
less_half_edge_pair lessF(vertex.first);
- std::sort(vertex.second.begin(), vertex.second.end(), lessF);
+ polygon_sort(vertex.second.begin(), vertex.second.end(), lessF);
}
class less_half_edge_pair {
@@ -1704,8 +1707,8 @@
//if half edge 1 is not vertical its slope is less than that of half edge 2
return get(pt1, HORIZONTAL) != get(pt2, HORIZONTAL);
}
- return less_slope(get(pt_, HORIZONTAL),
- get(pt_, VERTICAL), pt1, pt2);
+ return scanline_base<Unit>::less_slope(get(pt_, HORIZONTAL),
+ get(pt_, VERTICAL), pt1, pt2);
}
};
@@ -2154,7 +2157,7 @@
si.insert(poly, 444);
result.clear();
si.merge(result);
- si.verify();
+ si.verify1();
print(stdcout, si.pmd) << std::endl;
if(!result.empty()) {
psd = (*(result.begin())).second;
@@ -2165,7 +2168,7 @@
outpts.push_back((*itr).first.first);
outpts.push_back((*itr).first.second);
}
- std::sort(outpts.begin(), outpts.end());
+ polygon_sort(outpts.begin(), outpts.end());
for(std::size_t i = 0; i < outpts.size(); i+=2) {
if(outpts[i] != outpts[i+1]) {
stdcout << "Polygon set not a closed figure\n";
@@ -2514,7 +2517,7 @@
public:
less_vertex_data() : pack_() {}
less_vertex_data(typename scanline_base<Unit>::evalAtXforYPack* pack) : pack_(pack) {}
- bool operator()(const vertex_data_type& lvalue, const vertex_data_type& rvalue) {
+ bool operator()(const vertex_data_type& lvalue, const vertex_data_type& rvalue) const {
less_point lp;
if(lp(lvalue.first.first, rvalue.first.first)) return true;
if(lp(rvalue.first.first, lvalue.first.first)) return false;
@@ -2534,7 +2537,7 @@
elem.first = edge;
elem.second = 1;
if(edge.second < edge.first) elem.second *= -1;
- if(is_vertical(edge)) elem.second *= -1;
+ if(scanline_base<Unit>::is_vertical(edge)) elem.second *= -1;
#ifdef BOOST_POLYGON_MSVC
#pragma warning (disable: 4127)
#endif
@@ -2580,7 +2583,7 @@
inline void sort_property_merge_data() {
less_vertex_data<vertex_property> lvd(&evalAtXforYPack_);
- std::sort(pmd.begin(), pmd.end(), lvd);
+ polygon_sort(pmd.begin(), pmd.end(), lvd);
}
public:
inline arbitrary_boolean_op() : pmd(), evalAtXforYPack_() {}
@@ -2732,7 +2735,7 @@
public:
less_vertex_data() : pack_() {}
less_vertex_data(typename scanline_base<Unit>::evalAtXforYPack* pack) : pack_(pack) {}
- bool operator()(const vertex_data_type& lvalue, const vertex_data_type& rvalue) {
+ bool operator()(const vertex_data_type& lvalue, const vertex_data_type& rvalue) const {
less_point lp;
if(lp(lvalue.first.first, rvalue.first.first)) return true;
if(lp(rvalue.first.first, lvalue.first.first)) return false;
@@ -2804,7 +2807,7 @@
inline void sort_property_merge_data() {
less_vertex_data<vertex_property> lvd(&evalAtXforYPack_);
- std::sort(pmd.begin(), pmd.end(), lvd);
+ polygon_sort(pmd.begin(), pmd.end(), lvd);
}
public:
inline arbitrary_connectivity_extraction() : pmd(), evalAtXforYPack_() {}
Added: sandbox/gtl/boost/polygon/directed_line_segment_concept.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/directed_line_segment_concept.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -0,0 +1,453 @@
+/*
+ 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_CONCEPT_HPP
+#define BOOST_POLYGON_DIRECTED_LINE_SEGMENT_CONCEPT_HPP
+#include "isotropy.hpp"
+#include "directed_line_segment_data.hpp"
+#include "directed_line_segment_traits.hpp"
+#include "rectangle_concept.hpp"
+#include "detail/polygon_arbitrary_formation.hpp"
+
+namespace boost { namespace polygon{
+ struct directed_line_segment_concept {};
+
+ template <typename T>
+ struct is_directed_line_segment_concept { typedef gtl_no type; };
+ template <>
+ struct is_directed_line_segment_concept<directed_line_segment_concept> { typedef gtl_yes type; };
+
+ template <typename T>
+ struct is_mutable_directed_line_segment_concept { typedef gtl_no type; };
+ template <>
+ struct is_mutable_directed_line_segment_concept<directed_line_segment_concept> { typedef gtl_yes type; };
+
+ template <typename T, typename CT>
+ struct directed_line_segment_distance_type_by_concept { typedef void type; };
+ template <typename T>
+ struct directed_line_segment_distance_type_by_concept<T, gtl_yes> {
+ typedef typename coordinate_traits<typename directed_line_segment_traits<T>::coordinate_type>::coordinate_distance type; };
+
+ template <typename T>
+ struct directed_line_segment_distance_type {
+ typedef typename directed_line_segment_distance_type_by_concept<
+ T, typename is_directed_line_segment_concept<typename geometry_concept<T>::type>::type>::type type;
+ };
+
+ template <typename T, typename CT>
+ struct directed_line_segment_point_type_by_concept { typedef void type; };
+ template <typename T>
+ struct directed_line_segment_point_type_by_concept<T, gtl_yes> {
+ typedef typename directed_line_segment_traits<T>::point_type type; };
+
+ template <typename T>
+ struct directed_line_segment_point_type {
+ typedef typename directed_line_segment_point_type_by_concept<
+ T, typename is_directed_line_segment_concept<typename geometry_concept<T>::type>::type>::type type;
+ };
+
+ template <typename T, typename CT>
+ struct directed_line_segment_coordinate_type_by_concept { typedef void type; };
+ template <typename T>
+ struct directed_line_segment_coordinate_type_by_concept<T, gtl_yes> {
+ typedef typename directed_line_segment_traits<T>::coordinate_type type; };
+
+ template <typename T>
+ struct directed_line_segment_coordinate_type {
+ typedef typename directed_line_segment_coordinate_type_by_concept<
+ T, typename is_directed_line_segment_concept<typename geometry_concept<T>::type>::type>::type type;
+ };
+
+ template <typename T>
+ typename directed_line_segment_point_type<T>::type
+ get(const T& segment, direction_1d dir,
+ typename enable_if<typename gtl_if<typename is_directed_line_segment_concept<typename geometry_concept<T>::type>::type>::type>::type * = 0
+ ) {
+ return directed_line_segment_traits<T>::get(segment, dir);
+ }
+
+ template <typename T, typename point_type>
+ void
+ set(T& segment, direction_1d dir, point_type value,
+ typename enable_if<typename is_mutable_directed_line_segment_concept<typename geometry_concept<T>::type>::type>::type * = 0
+ ) {
+ directed_line_segment_mutable_traits<T>::set(segment, dir, value);
+ }
+
+ template <typename T, typename T2, typename T3>
+ T
+ construct(T2 low_value, T3 high_value,
+ typename enable_if<typename is_mutable_directed_line_segment_concept<typename geometry_concept<T>::type>::type>::type * = 0
+ ) {
+ return directed_line_segment_mutable_traits<T>::construct(low_value, high_value);
+ }
+
+ template <typename T, typename T2>
+ T
+ copy_construct(const T2& segment,
+ typename enable_if< typename gtl_and<typename is_mutable_directed_line_segment_concept<typename geometry_concept<T>::type>::type,
+ typename is_directed_line_segment_concept<typename geometry_concept<T2>::type>::type>::type>::type * = 0
+ ) {
+ return construct<T>
+ (get(segment, LOW ),
+ get(segment, HIGH));
+ }
+
+ template <typename T1, typename T2>
+ T1 &
+ assign(T1& lvalue, const T2& rvalue,
+ typename enable_if< typename gtl_and< typename is_mutable_directed_line_segment_concept<typename geometry_concept<T1>::type>::type,
+ typename is_directed_line_segment_concept<typename geometry_concept<T2>::type>::type>::type>::type * = 0) {
+ lvalue = copy_construct<T1>(rvalue);
+ return lvalue;
+ }
+
+ template <typename T, typename T2>
+ bool
+ equivalence(const T& segment1, const T2& segment2,
+ typename enable_if< typename gtl_and< typename is_directed_line_segment_concept<typename geometry_concept<T>::type>::type,
+ typename is_directed_line_segment_concept<typename geometry_concept<T2>::type>::type>::type>::type * = 0
+ ) {
+ return get(segment1, LOW) ==
+ get(segment2, LOW) &&
+ get(segment1, HIGH) ==
+ get(segment2, HIGH);
+ }
+
+ struct y_dls_on_above_or_below : gtl_yes {};
+
+ //-1 for below, 0 for on and 1 for above
+ template <typename segment_type>
+ typename enable_if< typename gtl_and< y_dls_on_above_or_below, typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type >::type, bool>::type
+ on_above_or_below(const segment_type& segment,
+ typename directed_line_segment_traits<segment_type>::point_type value) {
+ typedef polygon_arbitrary_formation<typename directed_line_segment_traits<segment_type>::coordinate_type> paf;
+ typename paf::Point pt, l, h;
+ assign(pt, value);
+ assign(l, low(segment));
+ assign(h, high(segment));
+ return paf::on_above_or_below(pt, typename paf::half_edge(l, h));
+ }
+
+ struct y_dls_contains : gtl_yes {};
+
+ template <typename segment_type>
+ typename enable_if< typename gtl_and< y_dls_contains, typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type >::type, bool>::type
+ contains(const segment_type& segment,
+ typename directed_line_segment_traits<segment_type>::point_type value,
+ bool consider_touch = true ) {
+ if(on_above_or_below(segment, value) == 0) {
+ rectangle_data<typename directed_line_segment_traits<segment_type>::coordinate_type> rect;
+ set_points(rect, low(segment), high(segment));
+ if(area(rect) == 0.0) {
+ if(!consider_touch) {
+ return !equivalence(value, low(segment)) && !equivalence(value, high(segment));
+ }
+ }
+ return contains(rect, value, consider_touch);
+ }
+ return false;
+ }
+
+ template <typename segment_type, typename segment_type_2>
+ bool
+ contains(const segment_type& segment,
+ const segment_type_2& value, bool consider_touch = true,
+ typename enable_if< typename gtl_and< typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type,
+ typename is_directed_line_segment_concept<typename geometry_concept<segment_type_2>::type>::type>::type>::type * = 0
+ ) {
+ return contains(segment, get(value, LOW), consider_touch) &&
+ contains(segment, get(value, HIGH), consider_touch);
+ }
+
+ // get the low point
+ template <typename segment_type>
+ typename directed_line_segment_point_type<segment_type>::type
+ low(const segment_type& segment,
+ typename enable_if< typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type * = 0
+ ) { return get(segment, LOW); }
+
+ // get the high point
+ template <typename segment_type>
+ typename directed_line_segment_point_type<segment_type>::type
+ high(const segment_type& segment,
+ typename enable_if< typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type * = 0
+ ) { return get(segment, HIGH); }
+
+ // get the center point
+ template <typename segment_type>
+ typename directed_line_segment_point_type<segment_type>::type
+ center(const segment_type& segment,
+ typename enable_if< typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type * = 0
+ ) {
+ return construct<typename directed_line_segment_traits<segment_type>::point_type>((x(high(segment)) + x(low(segment)))/2,
+ (y(high(segment)) + y(low(segment)))/2);
+
+ }
+
+ struct y_dls_low : gtl_yes {};
+
+ // set the low point to v
+ template <typename segment_type>
+ typename enable_if<typename gtl_and<y_dls_low, typename is_mutable_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type, void>::type
+ low(segment_type& segment,
+ typename directed_line_segment_traits<segment_type>::point_type v) { set(segment, LOW, v); }
+
+ struct y_dls_high : gtl_yes {};
+
+ // set the high coordinate to v
+ template <typename segment_type>
+ typename enable_if<typename gtl_and<y_dls_high, typename is_mutable_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type, void>::type
+ high(segment_type& segment,
+ typename directed_line_segment_traits<segment_type>::point_type v) { set(segment, HIGH, v); }
+
+ template <typename segment_type>
+ typename directed_line_segment_distance_type<segment_type>::type
+ length(const segment_type& segment,
+ typename enable_if< typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type * = 0
+ ) { return euclidean_distance(low(segment), high(segment)); }
+
+ struct y_dls_flip : gtl_yes {};
+
+ struct y_dls_scale_up : gtl_yes {};
+
+ // scale segment by factor
+ template <typename segment_type>
+ typename enable_if<typename gtl_and<y_dls_scale_up, typename is_mutable_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type, segment_type>::type &
+ scale_up(segment_type& segment,
+ typename coordinate_traits<typename directed_line_segment_traits<segment_type>::coordinate_type>::unsigned_area_type factor) {
+ typename directed_line_segment_point_type<segment_type>::type l = low(segment), h = high(segment);
+ low(segment, scale_up(l, factor));
+ high(segment, scale_up(h, factor));
+ return segment;
+ }
+
+ struct y_dls_scale_down : gtl_yes {};
+
+ template <typename segment_type>
+ typename enable_if<typename gtl_and<y_dls_scale_down, typename is_mutable_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type, segment_type>::type &
+ scale_down(segment_type& segment,
+ typename coordinate_traits<typename directed_line_segment_traits<segment_type>::coordinate_type>::unsigned_area_type factor) {
+ typename directed_line_segment_point_type<segment_type>::type l = low(segment), h = high(segment);
+ low(segment, scale_down(l, factor));
+ high(segment, scale_down(h, factor));
+ return segment;
+ }
+
+ struct y_dls_scale : gtl_yes {};
+
+ template <typename segment_type, typename scaling_type>
+ typename enable_if<typename gtl_and<y_dls_scale, typename is_mutable_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type, segment_type>::type &
+ scale(segment_type& segment, scaling_type factor) {
+ typename directed_line_segment_point_type<segment_type>::type l = low(segment), h = high(segment);
+ low(segment, scale(l, factor));
+ high(segment, scale(h, factor));
+ return segment;
+ }
+
+
+ struct y_dls_transform : gtl_yes {};
+
+ template <typename segment_type, typename transform_type>
+ typename enable_if<typename gtl_and<y_dls_transform, typename is_mutable_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type, segment_type>::type &
+ transform(segment_type& segment, const transform_type& val) {
+ typename directed_line_segment_point_type<segment_type>::type l = low(segment), h = high(segment);
+ low(segment, transform(l, val));
+ high(segment, transform(h, val));
+ return segment;
+ }
+ // move segment by delta
+ template <typename segment_type>
+ segment_type&
+ move(segment_type& segment, orientation_2d orient,
+ typename directed_line_segment_coordinate_type<segment_type>::type displacement,
+ typename enable_if<typename is_mutable_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type * = 0
+ ) {
+ typename directed_line_segment_point_type<segment_type>::type l = low(segment), h = high(segment);
+ low(segment, move(l, orient, displacement));
+ high(segment, move(h, orient, displacement));
+ return segment;
+ }
+
+ struct y_dls_convolve : gtl_yes {};
+
+ // convolve this with b
+ template <typename segment_type>
+ typename enable_if<typename gtl_and<y_dls_convolve, typename is_mutable_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type, segment_type>::type &
+ convolve(segment_type& segment,
+ const typename directed_line_segment_traits<segment_type>::point_type& b) {
+ typename directed_line_segment_point_type<segment_type>::type l = low(segment), h = high(segment);
+ low(segment, convolve(l, b));
+ high(segment, convolve(h, b));
+ return segment;
+ }
+
+ struct y_dls_deconvolve : gtl_yes {};
+
+ // deconvolve this with b
+ template <typename segment_type>
+ typename enable_if<typename gtl_and<y_dls_deconvolve, typename is_mutable_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type, segment_type>::type &
+ deconvolve(segment_type& segment,
+ const typename directed_line_segment_traits<segment_type>::point_type& b) {
+ typename directed_line_segment_point_type<segment_type>::type l = low(segment), h = high(segment);
+ low(segment, deconvolve(l, b));
+ high(segment, deconvolve(h, b));
+ return segment;
+ }
+
+ struct y_dls_e_dist1 : gtl_yes {};
+
+ // distance from a point to a segment
+ template <typename segment_type>
+ typename enable_if< typename gtl_and<y_dls_e_dist1, typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type>::type,
+ typename directed_line_segment_distance_type<segment_type>::type>::type
+ euclidean_distance(const segment_type& segment,
+ typename directed_line_segment_traits<segment_type>::point_type position) {
+ typedef typename directed_line_segment_distance_type<segment_type>::type Unit;
+ Unit x1 = x(low(segment));
+ Unit y1 = y(low(segment));
+ Unit x2 = x(high(segment));
+ Unit y2 = y(high(segment));
+ Unit X = x(position);
+ Unit Y = y(position);
+ Unit A = X - x1;
+ Unit B = Y - y1;
+ Unit C = x2 - x1;
+ Unit D = y2 - y1;
+ Unit length_sq = C * C + D * D;
+ Unit param = (A * C + B * D)/length_sq;
+ if(param > 1.0) {
+ return euclidean_distance(high(segment), position);
+ } else if(param < 0.0) {
+ return euclidean_distance(low(segment), position);
+ }
+ Unit denom = sqrt(length_sq);
+ if(denom == 0.0)
+ return 0.0;
+ Unit result = (A * D - C * B) / denom;
+ if(result < 0.0)
+ result *= -1;
+ return result;
+ }
+
+ struct y_dls_e_dist2 : gtl_yes {};
+
+ // distance between two segments
+ template <typename segment_type, typename segment_type_2>
+ typename enable_if<
+ typename gtl_and_3<y_dls_e_dist2, typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type,
+ typename is_directed_line_segment_concept<typename geometry_concept<segment_type_2>::type>::type>::type,
+ typename directed_line_segment_distance_type<segment_type>::type>::type
+ euclidean_distance(const segment_type& segment,
+ const segment_type_2& b) {
+ typename directed_line_segment_distance_type<segment_type>::type result1 = euclidean_distance(segment, low(b)),
+ result2 = euclidean_distance(segment, high(b));
+ if(result2 < result1) result1 = result2;
+ return result1;
+ }
+
+ struct y_dls_e_intersects : gtl_yes {};
+
+ // check if Interval b intersects `this` Interval
+ template <typename segment_type, typename segment_type_2>
+ typename enable_if< typename gtl_and_3<y_dls_e_intersects,
+ typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type,
+ typename is_directed_line_segment_concept<typename geometry_concept<segment_type_2>::type>::type
+ >::type, bool> ::type
+ intersects(const segment_type& segment, const segment_type_2& b, bool consider_touch = true) {
+ if(consider_touch) {
+ if(low(segment) == low(b) || low(segment) == high(b) || high(segment) == low(b) || high(segment) == high(b))
+ return true;
+ }
+ typedef polygon_arbitrary_formation<typename directed_line_segment_traits<segment_type>::coordinate_type> paf;
+ typename paf::Point l, h, l2, h2;
+ assign(l, low(segment));
+ assign(h, high(segment));
+ assign(l2, low(b));
+ assign(h2, high(b));
+ return paf::intersects(typename paf::half_edge(l, h), typename paf::half_edge(l2, h2));
+ }
+
+ struct y_dls_e_bintersect : gtl_yes {};
+
+ // check if Interval b partially overlaps `this` Interval
+ template <typename segment_type, typename segment_type_2>
+ typename enable_if<
+ typename gtl_and_3<y_dls_e_bintersect, typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type,
+ typename is_directed_line_segment_concept<typename geometry_concept<segment_type_2>::type>::type>::type,
+ bool>::type
+ boundaries_intersect(const segment_type& segment, const segment_type_2& b,
+ bool consider_touch = true) {
+ return (contains(segment, low(b), consider_touch) ||
+ contains(segment, high(b), consider_touch)) &&
+ (contains(b, low(segment), consider_touch) ||
+ contains(b, high(segment), consider_touch));
+ }
+
+ struct y_dls_abuts1 : gtl_yes {};
+
+ // check if they are end to end
+ template <typename segment_type, typename segment_type_2>
+ typename enable_if< typename gtl_and_3<y_dls_abuts1, typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type,
+ typename is_directed_line_segment_concept<typename geometry_concept<segment_type_2>::type>::type>::type,
+ bool>::type
+ abuts(const segment_type& segment, const segment_type_2& b, direction_1d dir) {
+ return dir.to_int() ? equivalence(low(b) , high(segment)) : equivalence(low(segment) , high(b));
+ }
+
+ struct y_dls_abuts2 : gtl_yes {};
+
+ // check if they are end to end
+ template <typename segment_type, typename segment_type_2>
+ typename enable_if<
+ typename gtl_and_3<y_dls_abuts2, typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type,
+ typename is_directed_line_segment_concept<typename geometry_concept<segment_type_2>::type>::type>::type,
+ bool>::type
+ abuts(const segment_type& segment, const segment_type_2& b) {
+ return abuts(segment, b, HIGH) || abuts(segment, b, LOW);
+ }
+
+ struct y_dls_intersect : gtl_yes {};
+
+ // set point to the intersection of segment and b
+ template <typename point_type, typename segment_type, typename segment_type_2>
+ typename enable_if< typename gtl_and_4<y_dls_intersect, typename is_mutable_point_concept<typename geometry_concept<point_type>::type>::type,
+ typename is_directed_line_segment_concept<typename geometry_concept<segment_type>::type>::type,
+ typename is_directed_line_segment_concept<typename geometry_concept<segment_type_2>::type>::type>::type,
+ bool>::type
+ intersection(point_type& intersection, const segment_type& segment, const segment_type_2& b,
+ bool projected = false, bool round_closest = false) {
+ typedef polygon_arbitrary_formation<typename directed_line_segment_traits<segment_type>::coordinate_type> paf;
+ typename paf::Point pt;
+ typename paf::Point l, h, l2, h2;
+ assign(l, low(segment));
+ assign(h, high(segment));
+ assign(l2, low(b));
+ assign(h2, high(b));
+ typename paf::half_edge he1(l, h), he2(l2, h2);
+ typename paf::compute_intersection_pack pack;
+ if(pack.compute_intersection(pt, he1, he2, projected, round_closest)) {
+ assign(intersection, pt);
+ return true;
+ }
+ return false;
+ }
+
+ template <class T>
+ template <class T2>
+ directed_line_segment_data<T>& directed_line_segment_data<T>::operator=(const T2& rvalue) {
+ assign(*this, rvalue);
+ return *this;
+ }
+
+ template <typename T>
+ struct geometry_concept<directed_line_segment_data<T> > {
+ typedef directed_line_segment_concept type;
+ };
+}
+}
+#endif
Added: sandbox/gtl/boost/polygon/directed_line_segment_data.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/directed_line_segment_data.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -0,0 +1,69 @@
+/*
+ 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_DATA_HPP
+#define BOOST_POLYGON_DIRECTED_LINE_SEGMENT_DATA_HPP
+#include "isotropy.hpp"
+#include "point_data.hpp"
+namespace boost { namespace polygon{
+ template <typename T>
+ class directed_line_segment_data {
+ public:
+ typedef T coordinate_type;
+ typedef point_data<T> point_type;
+ inline directed_line_segment_data()
+#ifndef BOOST_POLYGON_MSVC
+ :points_()
+#endif
+ {}
+ inline directed_line_segment_data(point_type low, point_type high)
+#ifndef BOOST_POLYGON_MSVC
+ :points_()
+#endif
+ {
+ points_[LOW] = low; points_[HIGH] = high;
+ }
+ inline directed_line_segment_data(const directed_line_segment_data& that)
+#ifndef BOOST_POLYGON_MSVC
+ :points_()
+#endif
+ {
+ (*this) = that;
+ }
+ inline directed_line_segment_data& operator=(const directed_line_segment_data& that) {
+ points_[0] = that.points_[0]; points_[1] = that.points_[1]; return *this;
+ }
+ template <typename T2>
+ inline directed_line_segment_data& operator=(const T2& rvalue);
+ inline point_type get(direction_1d dir) const {
+ return points_[dir.to_int()];
+ }
+ inline point_type low() const { return points_[0]; }
+ inline point_type high() const { return points_[1]; }
+ inline bool operator==(const directed_line_segment_data& that) const {
+ return low() == that.low() && high() == that.high(); }
+ inline bool operator!=(const directed_line_segment_data& that) const {
+ return low() != that.low() || high() != that.high(); }
+ inline bool operator<(const directed_line_segment_data& that) const {
+ if(points_[0] < that.points_[0]) return true;
+ if(points_[0] > that.points_[0]) return false;
+ if(points_[1] < that.points_[1]) return true;
+ return false;
+ }
+ inline bool operator<=(const directed_line_segment_data& that) const { return !(that < *this); }
+ inline bool operator>(const directed_line_segment_data& that) const { return that < *this; }
+ inline bool operator>=(const directed_line_segment_data& that) const { return !((*this) < that); }
+ inline void set(direction_1d dir, point_type value) {
+ points_[dir.to_int()] = value;
+ }
+private:
+ point_type points_[2];
+};
+
+}
+}
+#endif
Added: sandbox/gtl/boost/polygon/directed_line_segment_set_data.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/directed_line_segment_set_data.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 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
Added: sandbox/gtl/boost/polygon/directed_line_segment_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/directed_line_segment_traits.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -0,0 +1,42 @@
+/*
+ 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_TRAITS_HPP
+#define BOOST_POLYGON_DIRECTED_LINE_SEGMENT_TRAITS_HPP
+namespace boost { namespace polygon{
+ template <typename T>
+ struct directed_line_segment_traits {
+ typedef typename T::coordinate_type coordinate_type;
+ typedef typename T::point_type point_type;
+
+ static inline point_type get(const T& segment, direction_1d dir) {
+ return segment.get(dir);
+ }
+ };
+
+ template <typename T>
+ struct directed_line_segment_mutable_traits {
+ template <typename Point1>
+ static inline void set(T& segment, direction_1d dir, const Point1& value) {
+ typename directed_line_segment_traits<T>::point_type p1;
+ assign(p1, value);
+ segment.set(dir, value);
+ }
+
+ template <typename Point1, typename Point2>
+ static inline T construct(const Point1& low_value,
+ const Point2& high_value) {
+ typename directed_line_segment_traits<T>::point_type p1, p2;
+ assign(p1, low_value);
+ assign(p2, high_value);
+ return T(p1, p2);
+ }
+ };
+}
+}
+#endif
+
Modified: sandbox/gtl/boost/polygon/gmp_override.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/gmp_override.hpp (original)
+++ sandbox/gtl/boost/polygon/gmp_override.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -125,5 +125,4 @@
}
}
-
#endif
Added: sandbox/gtl/boost/polygon/gtl.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/gtl.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -0,0 +1,27 @@
+/*
+ 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 GTL_GTL_HPP
+#define GTL_GTL_HPP
+
+#ifdef __ICC
+#pragma warning (disable:1125)
+#endif
+
+#ifdef WIN32
+#pragma warning( disable: 4996 )
+#pragma warning( disable: 4800 )
+#endif
+
+#define BOOST_POLYGON_NO_DEPS
+#include "polygon.hpp"
+namespace gtl = boost::polygon;
+using namespace boost::polygon::operators;
+#if __ICC
+#pragma warning (default:1125)
+#endif
+#endif
Modified: sandbox/gtl/boost/polygon/interval_concept.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/interval_concept.hpp (original)
+++ sandbox/gtl/boost/polygon/interval_concept.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -471,7 +471,7 @@
typedef typename interval_traits<interval_type>::coordinate_type Unit;
Unit coords[4] = {low(interval), high(interval), low(b), high(b)};
//consider implementing faster sorting of small fixed length range
- std::sort(coords, coords+4);
+ polygon_sort(coords, coords+4);
low(interval, coords[1]);
high(interval, coords[2]);
return interval;
Modified: sandbox/gtl/boost/polygon/isotropy.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/isotropy.hpp (original)
+++ sandbox/gtl/boost/polygon/isotropy.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -48,7 +48,7 @@
#include <boost/mpl/or.hpp>
#else
-#ifdef WIN32
+#ifdef _WIN32
#define BOOST_POLYGON_MSVC
#endif
#ifdef __ICC
@@ -140,6 +140,7 @@
template <typename T>
struct coordinate_traits {};
+ //used to override long double with an infinite precision datatype
template <typename T>
struct high_precision_type {
typedef long double type;
@@ -150,6 +151,14 @@
return T(v);
}
+ //used to override std::sort with an alternative (parallel) algorithm
+ template <typename iter_type>
+ void polygon_sort(iter_type _b_, iter_type _e_);
+
+ template <typename iter_type, typename pred_type>
+ void polygon_sort(iter_type _b_, iter_type _e_, const pred_type& _pred_);
+
+
template <>
struct coordinate_traits<int> {
typedef int coordinate_type;
@@ -198,6 +207,16 @@
typedef double coordinate_distance;
};
+ template <>
+ struct coordinate_traits<long double> {
+ typedef long double coordinate_type;
+ typedef long double area_type;
+ typedef long double manhattan_area_type;
+ typedef long double unsigned_area_type;
+ typedef long double coordinate_difference;
+ typedef long double coordinate_distance;
+ };
+
template <typename T>
struct scaling_policy {
template <typename T2>
@@ -222,6 +241,8 @@
struct geometry_concept<float> { typedef coordinate_concept type; };
template <>
struct geometry_concept<double> { typedef coordinate_concept type; };
+ template <>
+ struct geometry_concept<long double> { typedef coordinate_concept type; };
#ifndef BOOST_POLYGON_NO_DEPS
struct gtl_no : mpl::bool_<false> {};
@@ -278,7 +299,7 @@
template <typename T>
struct gtl_if {
-#ifdef WIN32
+#ifdef BOOST_POLYGON_MSVC
typedef gtl_no type;
#endif
};
Modified: sandbox/gtl/boost/polygon/point_data.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/point_data.hpp (original)
+++ sandbox/gtl/boost/polygon/point_data.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -34,17 +34,29 @@
#endif
{ (*this) = that; }
template <typename other>
- point_data(const other& that) : coords_() { (*this) = that; }
+ point_data(const other& that)
+#ifndef BOOST_POLYGON_MSVC
+ :coords_()
+#endif
+ { (*this) = that; }
inline point_data& operator=(const point_data& that) {
coords_[0] = that.coords_[0]; coords_[1] = that.coords_[1]; return *this;
}
template<typename T1, typename T2>
- inline point_data(const T1& x, const T2& y):coords_() {
+ inline point_data(const T1& x, const T2& y)
+#ifndef BOOST_POLYGON_MSVC
+ :coords_()
+#endif
+ {
coords_[HORIZONTAL] = (coordinate_type)x;
coords_[VERTICAL] = (coordinate_type)y;
}
template <typename T2>
- inline point_data(const point_data<T2>& rvalue):coords_() {
+ inline point_data(const point_data<T2>& rvalue)
+#ifndef BOOST_POLYGON_MSVC
+ :coords_()
+#endif
+ {
coords_[HORIZONTAL] = (coordinate_type)(rvalue.x());
coords_[VERTICAL] = (coordinate_type)(rvalue.y());
}
Modified: sandbox/gtl/boost/polygon/polygon.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -7,6 +7,7 @@
*/
#ifndef BOOST_POLYGON_POLYGON_HPP
#define BOOST_POLYGON_POLYGON_HPP
+#define BOOST_POLYGON_VERSION 014401
#include "isotropy.hpp"
@@ -87,4 +88,8 @@
#include "polygon_set_concept.hpp"
+#include "directed_line_segment_data.hpp"
+#include "directed_line_segment_traits.hpp"
+#include "directed_line_segment_concept.hpp"
+
#endif
Modified: sandbox/gtl/boost/polygon/polygon_45_data.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_45_data.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_45_data.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -62,7 +62,7 @@
inline std::size_t size() const { return coords_.size(); }
-private:
+public:
std::vector<point_data<coordinate_type> > coords_;
};
Modified: sandbox/gtl/boost/polygon/polygon_45_set_data.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_45_set_data.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_45_set_data.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -212,7 +212,7 @@
void sort() const{
if(unsorted_) {
- std::sort(data_.begin(), data_.end());
+ polygon_sort(data_.begin(), data_.end());
unsorted_ = false;
}
}
@@ -220,6 +220,7 @@
template <typename input_iterator_type>
void set(input_iterator_type input_begin, input_iterator_type input_end) {
data_.clear();
+ reserve(std::distance(input_begin, input_end));
insert(input_begin, input_end);
dirty_ = true;
unsorted_ = true;
@@ -1262,7 +1263,7 @@
//std::cout << "SCAN " << currentX << "\n";
//scan event
scan45.scan(eventOut, eventIn.begin(), eventIn.end());
- std::sort(eventOut.begin(), eventOut.end());
+ polygon_sort(eventOut.begin(), eventOut.end());
std::size_t ptCount = 0;
for(std::size_t i = 0; i < eventOut.size(); ++i) {
if(!result_data.empty() &&
@@ -1333,7 +1334,7 @@
}
}
scan45.scan(eventOut, eventIn.begin(), eventIn.end());
- std::sort(eventOut.begin(), eventOut.end());
+ polygon_sort(eventOut.begin(), eventOut.end());
std::size_t ptCount = 0;
for(std::size_t i = 0; i < eventOut.size(); ++i) {
@@ -1385,7 +1386,7 @@
//std::cout << "SCAN " << currentX << "\n";
//scan event
scan45.scan(eventOut, eventIn.begin(), eventIn.end());
- std::sort(eventOut.begin(), eventOut.end());
+ polygon_sort(eventOut.begin(), eventOut.end());
std::size_t ptCount = 0;
for(std::size_t i = 0; i < eventOut.size(); ++i) {
if(!result_data.empty() &&
@@ -1422,7 +1423,7 @@
++iter1;
}
scan45.scan(eventOut, eventIn.begin(), eventIn.end());
- std::sort(eventOut.begin(), eventOut.end());
+ polygon_sort(eventOut.begin(), eventOut.end());
std::size_t ptCount = 0;
for(std::size_t i = 0; i < eventOut.size(); ++i) {
@@ -1541,11 +1542,11 @@
polygon_90_set_data<Unit> l90sd(VERTICAL), r90sd(VERTICAL), output(VERTICAL);
for(typename value_type::const_iterator itr = data_.begin(); itr != data_.end(); ++itr) {
if((*itr).count[3] == 0) continue; //skip all non vertical edges
- l90sd.insert(std::make_pair((*itr).pt.x(), std::make_pair((*itr).pt.y(), (*itr).count[3])), false, VERTICAL);
+ l90sd.insert(std::make_pair((*itr).pt.x(), std::make_pair<Unit, int>((*itr).pt.y(), (*itr).count[3])), false, VERTICAL);
}
for(typename value_type::const_iterator itr = rvalue.data_.begin(); itr != rvalue.data_.end(); ++itr) {
if((*itr).count[3] == 0) continue; //skip all non vertical edges
- r90sd.insert(std::make_pair((*itr).pt.x(), std::make_pair((*itr).pt.y(), (*itr).count[3])), false, VERTICAL);
+ r90sd.insert(std::make_pair((*itr).pt.x(), std::make_pair<Unit, int>((*itr).pt.y(), (*itr).count[3])), false, VERTICAL);
}
l90sd.sort();
r90sd.sort();
@@ -1639,7 +1640,7 @@
result.error_data_.push_back(ci);
}
Data2 new_result_data;
- std::sort(result_data.begin(), result_data.end());
+ polygon_sort(result_data.begin(), result_data.end());
applyUnary45OpOnVectors<Unit2, 0>(new_result_data, result_data); //OR operation
result_data.swap(new_result_data);
}
@@ -1673,7 +1674,7 @@
polygon_90_set_data<Unit> l90sd(VERTICAL);
for(typename value_type::const_iterator itr = data_.begin(); itr != data_.end(); ++itr) {
if((*itr).count[3] == 0) continue; //skip all non vertical edges
- l90sd.insert(std::make_pair((*itr).pt.x(), std::make_pair((*itr).pt.y(), (*itr).count[3])), false, VERTICAL);
+ l90sd.insert(std::make_pair((*itr).pt.x(), std::make_pair<Unit, int>((*itr).pt.y(), (*itr).count[3])), false, VERTICAL);
}
l90sd.sort();
#ifdef BOOST_POLYGON_MSVC
@@ -1749,7 +1750,7 @@
result.error_data_.push_back(ci);
}
Data2 new_result_data;
- std::sort(result_data.begin(), result_data.end());
+ polygon_sort(result_data.begin(), result_data.end());
applyUnary45OpOnVectors<Unit2, 0>(new_result_data, result_data); //OR operation
result_data.swap(new_result_data);
}
Modified: sandbox/gtl/boost/polygon/polygon_45_set_traits.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_45_set_traits.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_45_set_traits.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -94,6 +94,7 @@
static inline void set(std::list<T>& polygon_set, input_iterator_type input_begin, input_iterator_type input_end) {
polygon_set.clear();
polygon_45_set_data<typename polygon_45_set_traits<std::list<T> >::coordinate_type> ps;
+ ps.reserve(std::distance(input_begin, input_end));
ps.insert(input_begin, input_end);
ps.sort();
ps.clean();
@@ -105,7 +106,10 @@
template <typename input_iterator_type>
static inline void set(std::vector<T>& polygon_set, input_iterator_type input_begin, input_iterator_type input_end) {
polygon_set.clear();
+ size_t num_ele = std::distance(input_begin, input_end);
+ polygon_set.reserve(num_ele);
polygon_45_set_data<typename polygon_45_set_traits<std::list<T> >::coordinate_type> ps;
+ ps.reserve(num_ele);
ps.insert(input_begin, input_end);
ps.sort();
ps.clean();
@@ -137,7 +141,7 @@
static inline bool clean(const polygon_45_set_data<T>& polygon_set) { polygon_set.clean(); return true; }
- static inline bool sorted(const polygon_45_set_data<T>& polygon_set) { int untested = 0;polygon_set.sort(); return true; }
+ static inline bool sorted(const polygon_45_set_data<T>& polygon_set) { polygon_set.sort(); return true; }
};
}
Modified: sandbox/gtl/boost/polygon/polygon_45_with_holes_data.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_45_with_holes_data.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_45_with_holes_data.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -96,10 +96,12 @@
return holes_.size();
}
-private:
+public:
polygon_45_data<coordinate_type> self_;
std::list<hole_type> holes_;
};
+
+
}
}
#endif
Modified: sandbox/gtl/boost/polygon/polygon_90_set_data.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_90_set_data.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_90_set_data.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -244,6 +244,48 @@
// get the scanline orientation of the polygon set
inline orientation_2d orient() const { return orient_; }
+ // Start BM
+ // The problem: If we have two polygon sets with two different scanline orientations:
+ // I tried changing the orientation of one to coincide with other (If not, resulting boolean operation
+ // produces spurious results).
+ // First I tried copying polygon data from one of the sets into another set with corrected orientation
+ // using one of the copy constructor that takes in orientation (see somewhere above in this file) --> copy constructor throws error
+ // Then I tried another approach:(see below). This approach also fails to produce the desired results when test case is run.
+ // Here is the part that beats me: If I comment out the whole section, I can do all the operations (^=, -=, &= )these commented out
+ // operations perform. So then why do we need them?. Hence, I commented out this whole section.
+ // End BM
+ // polygon_90_set_data<coordinate_type>& operator-=(const polygon_90_set_data& that) {
+ // sort();
+ // that.sort();
+ // value_type data;
+ // std::swap(data, data_);
+ // applyBooleanBinaryOp(data.begin(), data.end(),
+ // that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryNot>());
+ // return *this;
+ // }
+ // polygon_90_set_data<coordinate_type>& operator^=(const polygon_90_set_data& that) {
+ // sort();
+ // that.sort();
+ // value_type data;
+ // std::swap(data, data_);
+ // applyBooleanBinaryOp(data.begin(), data.end(),
+ // that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryXor>());
+ // return *this;
+ // }
+ // polygon_90_set_data<coordinate_type>& operator&=(const polygon_90_set_data& that) {
+ // sort();
+ // that.sort();
+ // value_type data;
+ // std::swap(data, data_);
+ // applyBooleanBinaryOp(data.begin(), data.end(),
+ // that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryAnd>());
+ // return *this;
+ // }
+ // polygon_90_set_data<coordinate_type>& operator|=(const polygon_90_set_data& that) {
+ // insert(that);
+ // return *this;
+ // }
+
void clean() const {
sort();
if(dirty_) {
@@ -254,7 +296,7 @@
void sort() const{
if(unsorted_) {
- std::sort(data_.begin(), data_.end());
+ polygon_sort(data_.begin(), data_.end());
unsorted_ = false;
}
}
@@ -262,6 +304,7 @@
template <typename input_iterator_type>
void set(input_iterator_type input_begin, input_iterator_type input_end, orientation_2d orient) {
data_.clear();
+ reserve(std::distance(input_begin, input_end));
data_.insert(data_.end(), input_begin, input_end);
orient_ = orient;
dirty_ = true;
@@ -297,7 +340,7 @@
}
polygon_90_set_data&
- bloat(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,
+ bloat2(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,
typename coordinate_traits<coordinate_type>::unsigned_area_type east_bloating,
typename coordinate_traits<coordinate_type>::unsigned_area_type south_bloating,
typename coordinate_traits<coordinate_type>::unsigned_area_type north_bloating) {
@@ -318,11 +361,257 @@
return *this;
}
+ static void modify_pt(point_data<coordinate_type>& pt, const point_data<coordinate_type>& prev_pt,
+ const point_data<coordinate_type>& current_pt, const point_data<coordinate_type>& next_pt,
+ coordinate_type west_bloating,
+ coordinate_type east_bloating,
+ coordinate_type south_bloating,
+ coordinate_type north_bloating) {
+ bool pxl = prev_pt.x() < current_pt.x();
+ bool pyl = prev_pt.y() < current_pt.y();
+ bool nxl = next_pt.x() < current_pt.x();
+ bool nyl = next_pt.y() < current_pt.y();
+ bool pxg = prev_pt.x() > current_pt.x();
+ bool pyg = prev_pt.y() > current_pt.y();
+ bool nxg = next_pt.x() > current_pt.x();
+ bool nyg = next_pt.y() > current_pt.y();
+ //two of the four if statements will execute
+ if(pxl)
+ pt.y(current_pt.y() - south_bloating);
+ if(pxg)
+ pt.y(current_pt.y() + north_bloating);
+ if(nxl)
+ pt.y(current_pt.y() + north_bloating);
+ if(nxg)
+ pt.y(current_pt.y() - south_bloating);
+ if(pyl)
+ pt.x(current_pt.x() + east_bloating);
+ if(pyg)
+ pt.x(current_pt.x() - west_bloating);
+ if(nyl)
+ pt.x(current_pt.x() - west_bloating);
+ if(nyg)
+ pt.x(current_pt.x() + east_bloating);
+ }
+ static void resize_poly_up(std::vector<point_data<coordinate_type> >& poly,
+ coordinate_type west_bloating,
+ coordinate_type east_bloating,
+ coordinate_type south_bloating,
+ coordinate_type north_bloating) {
+ point_data<coordinate_type> first_pt = poly[0];
+ point_data<coordinate_type> second_pt = poly[1];
+ point_data<coordinate_type> prev_pt = poly[0];
+ point_data<coordinate_type> current_pt = poly[1];
+ for(std::size_t i = 2; i < poly.size(); ++i) {
+ point_data<coordinate_type> next_pt = poly[i];
+ modify_pt(poly[i-1], prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
+ prev_pt = current_pt;
+ current_pt = next_pt;
+ }
+ point_data<coordinate_type> next_pt = first_pt;
+ modify_pt(poly.back(), prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
+ prev_pt = current_pt;
+ current_pt = next_pt;
+ next_pt = second_pt;
+ modify_pt(poly[0], prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
+ remove_colinear_pts(poly);
+ }
+ static bool resize_poly_down(std::vector<point_data<coordinate_type> >& poly,
+ coordinate_type west_shrinking,
+ coordinate_type east_shrinking,
+ coordinate_type south_shrinking,
+ coordinate_type north_shrinking) {
+ rectangle_data<coordinate_type> extents_rectangle;
+ set_points(extents_rectangle, poly[0], poly[0]);
+ point_data<coordinate_type> first_pt = poly[0];
+ point_data<coordinate_type> second_pt = poly[1];
+ point_data<coordinate_type> prev_pt = poly[0];
+ point_data<coordinate_type> current_pt = poly[1];
+ encompass(extents_rectangle, current_pt);
+ for(std::size_t i = 2; i < poly.size(); ++i) {
+ point_data<coordinate_type> next_pt = poly[i];
+ encompass(extents_rectangle, next_pt);
+ modify_pt(poly[i-1], prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking);
+ prev_pt = current_pt;
+ current_pt = next_pt;
+ }
+ if(delta(extents_rectangle, HORIZONTAL) < std::abs(west_shrinking + east_shrinking))
+ return false;
+ if(delta(extents_rectangle, VERTICAL) < std::abs(north_shrinking + south_shrinking))
+ return false;
+ point_data<coordinate_type> next_pt = first_pt;
+ modify_pt(poly.back(), prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking);
+ prev_pt = current_pt;
+ current_pt = next_pt;
+ next_pt = second_pt;
+ modify_pt(poly[0], prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking);
+ return remove_colinear_pts(poly);
+ }
+
+ static bool remove_colinear_pts(std::vector<point_data<coordinate_type> >& poly) {
+ bool found_colinear = true;
+ while(found_colinear && poly.size() >= 4) {
+ found_colinear = false;
+ typename std::vector<point_data<coordinate_type> >::iterator itr = poly.begin();
+ itr += poly.size() - 1; //get last element position
+ typename std::vector<point_data<coordinate_type> >::iterator itr2 = poly.begin();
+ typename std::vector<point_data<coordinate_type> >::iterator itr3 = itr2;
+ ++itr3;
+ std::size_t count = 0;
+ for( ; itr3 < poly.end(); ++itr3) {
+ if(((*itr).x() == (*itr2).x() && (*itr).x() == (*itr3).x()) ||
+ ((*itr).y() == (*itr2).y() && (*itr).y() == (*itr3).y()) ) {
+ ++count;
+ found_colinear = true;
+ } else {
+ itr = itr2;
+ ++itr2;
+ }
+ *itr2 = *itr3;
+ }
+ itr3 = poly.begin();
+ if(((*itr).x() == (*itr2).x() && (*itr).x() == (*itr3).x()) ||
+ ((*itr).y() == (*itr2).y() && (*itr).y() == (*itr3).y()) ) {
+ ++count;
+ found_colinear = true;
+ }
+ poly.erase(poly.end() - count, poly.end());
+ }
+ return poly.size() >= 4;
+ }
+
+ polygon_90_set_data&
+ bloat(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,
+ typename coordinate_traits<coordinate_type>::unsigned_area_type east_bloating,
+ typename coordinate_traits<coordinate_type>::unsigned_area_type south_bloating,
+ typename coordinate_traits<coordinate_type>::unsigned_area_type north_bloating) {
+ std::list<polygon_45_with_holes_data<coordinate_type> > polys;
+ get(polys);
+ clear();
+ for(typename std::list<polygon_45_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
+ itr != polys.end(); ++itr) {
+ //polygon_90_set_data<coordinate_type> psref;
+ //psref.insert(view_as<polygon_90_concept>((*itr).self_));
+ //rectangle_data<coordinate_type> prerect;
+ //psref.extents(prerect);
+ resize_poly_up((*itr).self_.coords_, west_bloating, east_bloating, south_bloating, north_bloating);
+ iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
+ begin_input(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE),
+ end_input(view_as<polygon_90_concept>((*itr).self_), HIGH, orient_, false, true, COUNTERCLOCKWISE);
+ insert(begin_input, end_input, orient_);
+ //polygon_90_set_data<coordinate_type> pstest;
+ //pstest.insert(view_as<polygon_90_concept>((*itr).self_));
+ //psref.bloat2(west_bloating, east_bloating, south_bloating, north_bloating);
+ //if(!equivalence(psref, pstest)) {
+ // std::cout << "test failed\n";
+ //}
+ for(typename std::list<polygon_45_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
+ itrh != (*itr).holes_.end(); ++itrh) {
+ //rectangle_data<coordinate_type> rect;
+ //psref.extents(rect);
+ //polygon_90_set_data<coordinate_type> psrefhole;
+ //psrefhole.insert(prerect);
+ //psrefhole.insert(view_as<polygon_90_concept>(*itrh), true);
+ //polygon_45_data<coordinate_type> testpoly(*itrh);
+ if(resize_poly_down((*itrh).coords_, west_bloating, east_bloating, south_bloating, north_bloating)) {
+ iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
+ begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
+ end_input2(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
+ insert(begin_input2, end_input2, orient_);
+ //polygon_90_set_data<coordinate_type> pstesthole;
+ //pstesthole.insert(rect);
+ //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
+ // begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true);
+ //pstesthole.insert(begin_input2, end_input, orient_);
+ //psrefhole.bloat2(west_bloating, east_bloating, south_bloating, north_bloating);
+ //if(!equivalence(psrefhole, pstesthole)) {
+ // std::cout << (winding(testpoly) == CLOCKWISE) << std::endl;
+ // std::cout << (winding(*itrh) == CLOCKWISE) << std::endl;
+ // polygon_90_set_data<coordinate_type> c(psrefhole);
+ // c.clean();
+ // polygon_90_set_data<coordinate_type> a(pstesthole);
+ // polygon_90_set_data<coordinate_type> b(pstesthole);
+ // a.sort();
+ // b.clean();
+ // std::cout << "test hole failed\n";
+ // //std::cout << testpoly << std::endl;
+ //}
+ }
+ }
+ }
+ return *this;
+ }
+
polygon_90_set_data&
shrink(typename coordinate_traits<coordinate_type>::unsigned_area_type west_shrinking,
typename coordinate_traits<coordinate_type>::unsigned_area_type east_shrinking,
typename coordinate_traits<coordinate_type>::unsigned_area_type south_shrinking,
typename coordinate_traits<coordinate_type>::unsigned_area_type north_shrinking) {
+ std::list<polygon_45_with_holes_data<coordinate_type> > polys;
+ get(polys);
+ clear();
+ for(typename std::list<polygon_45_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
+ itr != polys.end(); ++itr) {
+ //polygon_90_set_data<coordinate_type> psref;
+ //psref.insert(view_as<polygon_90_concept>((*itr).self_));
+ //rectangle_data<coordinate_type> prerect;
+ //psref.extents(prerect);
+ //polygon_45_data<coordinate_type> testpoly((*itr).self_);
+ if(resize_poly_down((*itr).self_.coords_, -west_shrinking, -east_shrinking, -south_shrinking, -north_shrinking)) {
+ iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
+ begin_input(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE),
+ end_input(view_as<polygon_90_concept>((*itr).self_), HIGH, orient_, false, true, COUNTERCLOCKWISE);
+ insert(begin_input, end_input, orient_);
+ //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
+ // begin_input2(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE);
+ //polygon_90_set_data<coordinate_type> pstest;
+ //pstest.insert(begin_input2, end_input, orient_);
+ //psref.shrink2(west_shrinking, east_shrinking, south_shrinking, north_shrinking);
+ //if(!equivalence(psref, pstest)) {
+ // std::cout << "test failed\n";
+ //}
+ for(typename std::list<polygon_45_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
+ itrh != (*itr).holes_.end(); ++itrh) {
+ //rectangle_data<coordinate_type> rect;
+ //psref.extents(rect);
+ //polygon_90_set_data<coordinate_type> psrefhole;
+ //psrefhole.insert(prerect);
+ //psrefhole.insert(view_as<polygon_90_concept>(*itrh), true);
+ //polygon_45_data<coordinate_type> testpoly(*itrh);
+ resize_poly_up((*itrh).coords_, -west_shrinking, -east_shrinking, -south_shrinking, -north_shrinking);
+ iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
+ begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
+ end_input2(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
+ insert(begin_input2, end_input2, orient_);
+ //polygon_90_set_data<coordinate_type> pstesthole;
+ //pstesthole.insert(rect);
+ //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
+ // begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true);
+ //pstesthole.insert(begin_input2, end_input, orient_);
+ //psrefhole.shrink2(west_shrinking, east_shrinking, south_shrinking, north_shrinking);
+ //if(!equivalence(psrefhole, pstesthole)) {
+ // std::cout << (winding(testpoly) == CLOCKWISE) << std::endl;
+ // std::cout << (winding(*itrh) == CLOCKWISE) << std::endl;
+ // polygon_90_set_data<coordinate_type> c(psrefhole);
+ // c.clean();
+ // polygon_90_set_data<coordinate_type> a(pstesthole);
+ // polygon_90_set_data<coordinate_type> b(pstesthole);
+ // a.sort();
+ // b.clean();
+ // std::cout << "test hole failed\n";
+ // //std::cout << testpoly << std::endl;
+ //}
+ }
+ }
+ }
+ return *this;
+ }
+
+ polygon_90_set_data&
+ shrink2(typename coordinate_traits<coordinate_type>::unsigned_area_type west_shrinking,
+ typename coordinate_traits<coordinate_type>::unsigned_area_type east_shrinking,
+ typename coordinate_traits<coordinate_type>::unsigned_area_type south_shrinking,
+ typename coordinate_traits<coordinate_type>::unsigned_area_type north_shrinking) {
rectangle_data<coordinate_type> externalBoundary;
if(!extents(externalBoundary)) return *this;
::boost::polygon::bloat(externalBoundary, 10); //bloat by diferential ammount
@@ -353,6 +642,28 @@
}
polygon_90_set_data&
+ shrink(direction_2d dir, typename coordinate_traits<coordinate_type>::unsigned_area_type shrinking) {
+ if(dir == WEST)
+ return shrink(shrinking, 0, 0, 0);
+ if(dir == EAST)
+ return shrink(0, shrinking, 0, 0);
+ if(dir == SOUTH)
+ return shrink(0, 0, shrinking, 0);
+ return shrink(0, 0, 0, shrinking);
+ }
+
+ polygon_90_set_data&
+ bloat(direction_2d dir, typename coordinate_traits<coordinate_type>::unsigned_area_type shrinking) {
+ if(dir == WEST)
+ return bloat(shrinking, 0, 0, 0);
+ if(dir == EAST)
+ return bloat(0, shrinking, 0, 0);
+ if(dir == SOUTH)
+ return bloat(0, 0, shrinking, 0);
+ return bloat(0, 0, 0, shrinking);
+ }
+
+ polygon_90_set_data&
resize(coordinate_type west, coordinate_type east, coordinate_type south, coordinate_type north);
polygon_90_set_data& move(coordinate_type x_delta, coordinate_type y_delta) {
Modified: sandbox/gtl/boost/polygon/polygon_90_set_traits.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_90_set_traits.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_90_set_traits.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -278,6 +278,7 @@
static inline void set(std::list<T>& polygon_set, input_iterator_type input_begin, input_iterator_type input_end, orientation_2d orient) {
polygon_set.clear();
polygon_90_set_data<typename polygon_90_set_traits<std::list<T> >::coordinate_type> ps(orient);
+ ps.reserve(std::distance(input_begin, input_end));
ps.insert(input_begin, input_end, orient);
ps.clean();
get_90_dispatch(polygon_set, ps, orient, concept_type());
@@ -289,7 +290,10 @@
template <typename input_iterator_type>
static inline void set(std::vector<T>& polygon_set, input_iterator_type input_begin, input_iterator_type input_end, orientation_2d orient) {
polygon_set.clear();
+ size_t num_ele = std::distance(input_begin, input_end);
+ polygon_set.reserve(num_ele);
polygon_90_set_data<typename polygon_90_set_traits<std::list<T> >::coordinate_type> ps(orient);
+ ps.reserve(num_ele);
ps.insert(input_begin, input_end, orient);
ps.clean();
get_90_dispatch(polygon_set, ps, orient, concept_type());
@@ -304,6 +308,7 @@
input_iterator_type input_begin, input_iterator_type input_end,
orientation_2d orient) {
polygon_set.clear();
+ polygon_set.reserve(std::distance(input_begin, input_end));
polygon_set.insert(input_begin, input_end, orient);
}
Modified: sandbox/gtl/boost/polygon/polygon_data.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_data.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_data.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -60,7 +60,7 @@
inline std::size_t size() const { return coords_.size(); }
-private:
+public:
std::vector<point_data<coordinate_type> > coords_;
};
Modified: sandbox/gtl/boost/polygon/polygon_set_concept.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_set_concept.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_set_concept.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -8,6 +8,7 @@
#ifndef BOOST_POLYGON_POLYGON_SET_CONCEPT_HPP
#define BOOST_POLYGON_POLYGON_SET_CONCEPT_HPP
#include "polygon_set_data.hpp"
+#include "detail/polygon_simplify.hpp"
namespace boost { namespace polygon{
template <typename T, typename T2>
@@ -148,16 +149,39 @@
return retval;
}
- // TODO: Dafna add ngon parameter passing
+ template <typename polygon_set_type>
+ typename enable_if< typename is_mutable_polygon_set_type<polygon_set_type>::type,
+ std::size_t>::type
+ simplify(polygon_set_type& polygon_set, typename coordinate_traits<
+ typename polygon_set_traits<polygon_set_type>::coordinate_type
+ >::coordinate_distance threshold) {
+ typedef typename polygon_set_traits<polygon_set_type>::coordinate_type Unit;
+ typedef polygon_with_holes_data<Unit> p_type;
+ std::vector<p_type> polys;
+ assign(polys, polygon_set);
+ std::size_t retval = 0;
+ for(std::size_t i = 0; i < polys.size(); ++i) {
+ retval += detail::simplify_detail::simplify(polys[i].self_.coords_,
+ polys[i].self_.coords_, threshold);
+ for(typename std::list<polygon_data<Unit> >::iterator itrh =
+ polys[i].holes_.begin(); itrh != (polys[i].holes_.end()); ++itrh) {
+ retval += detail::simplify_detail::simplify((*itrh).coords_,
+ (*itrh).coords_, threshold);
+ }
+ }
+ assign(polygon_set, polys);
+ return retval;
+ }
+
template <typename polygon_set_type, typename coord_type>
typename enable_if< typename is_mutable_polygon_set_type<polygon_set_type>::type,
polygon_set_type>::type &
- resize(polygon_set_type& polygon_set, coord_type resizing, bool corner_fill_arcs = false, int ngon=0) {
+ resize(polygon_set_type& polygon_set, coord_type resizing, bool corner_fill_arcs = false, int num_circle_segments = 0) {
typedef typename polygon_set_traits<polygon_set_type>::coordinate_type Unit;
clean(polygon_set);
polygon_set_data<Unit> ps;
assign(ps, polygon_set);
- ps.resize(resizing, corner_fill_arcs,ngon);
+ ps.resize(resizing, corner_fill_arcs,num_circle_segments);
assign(polygon_set, ps);
return polygon_set;
}
Modified: sandbox/gtl/boost/polygon/polygon_set_data.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_set_data.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_set_data.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -11,7 +11,6 @@
#include "polygon_45_set_concept.hpp"
#include "polygon_traits.hpp"
#include "detail/polygon_arbitrary_formation.hpp"
-#include <iostream>
namespace boost { namespace polygon {
@@ -120,38 +119,7 @@
template <typename polygon_type>
inline void insert(const polygon_type& polygon_object, bool is_hole, polygon_concept ) {
- bool first_iteration = true;
- point_type first_point;
- point_type previous_point;
- point_type current_point;
- direction_1d winding_dir = winding(polygon_object);
- int multiplier = winding_dir == COUNTERCLOCKWISE ? 1 : -1;
- if(is_hole) multiplier *= -1;
- for(typename polygon_traits<polygon_type>::iterator_type itr = begin_points(polygon_object);
- itr != end_points(polygon_object); ++itr) {
- assign(current_point, *itr);
- if(first_iteration) {
- first_iteration = false;
- first_point = previous_point = current_point;
- } else {
- if(previous_point != current_point) {
- element_type elem(edge_type(previous_point, current_point),
- ( previous_point.get(HORIZONTAL) == current_point.get(HORIZONTAL) ? -1 : 1) * multiplier);
- insert_clean(elem);
- }
- }
- previous_point = current_point;
- }
- current_point = first_point;
- if(!first_iteration) {
- if(previous_point != current_point) {
- element_type elem(edge_type(previous_point, current_point),
- ( previous_point.get(HORIZONTAL) == current_point.get(HORIZONTAL) ? -1 : 1) * multiplier);
- insert_clean(elem);
- }
- dirty_ = true;
- unsorted_ = true;
- }
+ insert_vertex_sequence(begin_points(polygon_object), end_points(polygon_object), winding(polygon_object), is_hole);
}
inline void insert(const polygon_set_data& ps, bool is_hole = false) {
@@ -229,9 +197,37 @@
template <class iT>
inline void insert_vertex_sequence(iT begin_vertex, iT end_vertex, direction_1d winding, bool is_hole) {
- polygon_data<coordinate_type> poly;
- poly.set(begin_vertex, end_vertex);
- insert(poly, is_hole);
+ bool first_iteration = true;
+ point_type first_point;
+ point_type previous_point;
+ point_type current_point;
+ direction_1d winding_dir = winding;
+ int multiplier = winding_dir == COUNTERCLOCKWISE ? 1 : -1;
+ if(is_hole) multiplier *= -1;
+ for( ; begin_vertex != end_vertex; ++begin_vertex) {
+ assign(current_point, *begin_vertex);
+ if(first_iteration) {
+ first_iteration = false;
+ first_point = previous_point = current_point;
+ } else {
+ if(previous_point != current_point) {
+ element_type elem(edge_type(previous_point, current_point),
+ ( previous_point.get(HORIZONTAL) == current_point.get(HORIZONTAL) ? -1 : 1) * multiplier);
+ insert_clean(elem);
+ }
+ }
+ previous_point = current_point;
+ }
+ current_point = first_point;
+ if(!first_iteration) {
+ if(previous_point != current_point) {
+ element_type elem(edge_type(previous_point, current_point),
+ ( previous_point.get(HORIZONTAL) == current_point.get(HORIZONTAL) ? -1 : 1) * multiplier);
+ insert_clean(elem);
+ }
+ dirty_ = true;
+ unsorted_ = true;
+ }
}
template <typename output_container>
@@ -251,7 +247,7 @@
data.push_back(vertex_half_edge((*itr).first.first, (*itr).first.second, (*itr).second));
data.push_back(vertex_half_edge((*itr).first.second, (*itr).first.first, -1 * (*itr).second));
}
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(container, data.begin(), data.end());
//std::cout << "DONE FORMING POLYGONS\n";
}
@@ -324,7 +320,7 @@
void sort() const{
if(unsorted_) {
- std::sort(data_.begin(), data_.end());
+ polygon_sort(data_.begin(), data_.end());
unsorted_ = false;
}
}
@@ -332,6 +328,7 @@
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;
@@ -362,17 +359,7 @@
}
inline polygon_set_data&
- resize(coordinate_type resizing, bool corner_fill_arc = false, unsigned int num_circle_segments=0) {
- if(resizing == 0) return *this;
- std::list<polygon_with_holes_data<coordinate_type> > pl;
- get(pl);
- clear();
- for(typename std::list<polygon_with_holes_data<coordinate_type> >::iterator itr = pl.begin(); itr != pl.end(); ++itr) {
- insert_with_resize(*itr, resizing, corner_fill_arc, num_circle_segments);
- }
- clean();
- return *this;
- }
+ resize(coordinate_type resizing, bool corner_fill_arc = false, unsigned int num_circle_segments=0);
template <typename transform_type>
inline polygon_set_data&
@@ -401,8 +388,13 @@
inline polygon_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) {
+ bool vb = (*itr).first.first.x() == (*itr).first.second.x();
::boost::polygon::scale_down((*itr).first.first, factor);
::boost::polygon::scale_down((*itr).first.second, factor);
+ bool va = (*itr).first.first.x() == (*itr).first.second.x();
+ if(!vb && va) {
+ (*itr).second *= -1;
+ }
}
unsorted_ = true;
dirty_ = true;
@@ -413,14 +405,168 @@
inline polygon_set_data& scale(polygon_set_data& polygon_set,
const scaling_type& scaling) {
for(typename value_type::iterator itr = begin(); itr != end(); ++itr) {
+ bool vb = (*itr).first.first.x() == (*itr).first.second.x();
::boost::polygon::scale((*itr).first.first, scaling);
::boost::polygon::scale((*itr).first.second, scaling);
+ bool va = (*itr).first.first.x() == (*itr).first.second.x();
+ if(!vb && va) {
+ (*itr).second *= -1;
+ }
}
unsorted_ = true;
dirty_ = true;
return *this;
}
+ static inline void compute_offset_edge(point_data<long double>& pt1, point_data<long double>& pt2,
+ const point_data<long double>& prev_pt,
+ const point_data<long double>& current_pt,
+ long double distance, int multiplier) {
+ long double dx = current_pt.x() - prev_pt.x();
+ long double dy = current_pt.y() - prev_pt.y();
+ long double edge_length = std::sqrt(dx*dx + dy*dy);
+ long double dnx = dy;
+ long double dny = -dx;
+ dnx = dnx * (long double)distance / edge_length;
+ dny = dny * (long double)distance / edge_length;
+ pt1.x(prev_pt.x() + (long double)dnx * (long double)multiplier);
+ pt2.x(current_pt.x() + (long double)dnx * (long double)multiplier);
+ pt1.y(prev_pt.y() + (long double)dny * (long double)multiplier);
+ pt2.y(current_pt.y() + (long double)dny * (long double)multiplier);
+ }
+
+ static inline void modify_pt(point_data<coordinate_type>& pt, const point_data<coordinate_type>& prev_pt,
+ const point_data<coordinate_type>& current_pt, const point_data<coordinate_type>& next_pt,
+ coordinate_type distance, coordinate_type multiplier) {
+ std::pair<point_data<long double>, point_data<long double> > he1, he2;
+ he1.first.x((long double)(prev_pt.x()));
+ he1.first.y((long double)(prev_pt.y()));
+ he1.second.x((long double)(current_pt.x()));
+ he1.second.y((long double)(current_pt.y()));
+ he2.first.x((long double)(current_pt.x()));
+ he2.first.y((long double)(current_pt.y()));
+ he2.second.x((long double)(next_pt.x()));
+ he2.second.y((long double)(next_pt.y()));
+ compute_offset_edge(he1.first, he1.second, prev_pt, current_pt, distance, multiplier);
+ compute_offset_edge(he2.first, he2.second, current_pt, next_pt, distance, multiplier);
+ typename scanline_base<long double>::compute_intersection_pack pack;
+ point_data<long double> rpt;
+ point_data<long double> bisectorpt((he1.second.x()+he2.first.x())/2,
+ (he1.second.y()+he2.first.y())/2);
+ point_data<long double> orig_pt((long double)pt.x(), (long double)pt.y());
+ if(euclidean_distance(bisectorpt, orig_pt) < distance/2) {
+ if(!pack.compute_lazy_intersection(rpt, he1, he2, true, false)) {
+ rpt = he1.second; //colinear offset edges use shared point
+ }
+ } else {
+ if(!pack.compute_lazy_intersection(rpt, he1, std::pair<point_data<long double>, point_data<long double> >(orig_pt, bisectorpt), true, false)) {
+ rpt = he1.second; //colinear offset edges use shared point
+ }
+ }
+ pt.x((coordinate_type)(std::floor(rpt.x()+0.5)));
+ pt.y((coordinate_type)(std::floor(rpt.y()+0.5)));
+ }
+
+ static void resize_poly_up(std::vector<point_data<coordinate_type> >& poly, coordinate_type distance, coordinate_type multiplier) {
+ point_data<coordinate_type> first_pt = poly[0];
+ point_data<coordinate_type> second_pt = poly[1];
+ point_data<coordinate_type> prev_pt = poly[0];
+ point_data<coordinate_type> current_pt = poly[1];
+ for(std::size_t i = 2; i < poly.size()-1; ++i) {
+ point_data<coordinate_type> next_pt = poly[i];
+ modify_pt(poly[i-1], prev_pt, current_pt, next_pt, distance, multiplier);
+ prev_pt = current_pt;
+ current_pt = next_pt;
+ }
+ point_data<coordinate_type> next_pt = first_pt;
+ modify_pt(poly[poly.size()-2], prev_pt, current_pt, next_pt, distance, multiplier);
+ prev_pt = current_pt;
+ current_pt = next_pt;
+ next_pt = second_pt;
+ modify_pt(poly[0], prev_pt, current_pt, next_pt, distance, multiplier);
+ poly.back() = poly.front();
+ }
+ static bool resize_poly_down(std::vector<point_data<coordinate_type> >& poly, coordinate_type distance, coordinate_type multiplier) {
+ std::vector<point_data<coordinate_type> > orig_poly(poly);
+ rectangle_data<coordinate_type> extents_rectangle;
+ set_points(extents_rectangle, poly[0], poly[0]);
+ point_data<coordinate_type> first_pt = poly[0];
+ point_data<coordinate_type> second_pt = poly[1];
+ point_data<coordinate_type> prev_pt = poly[0];
+ point_data<coordinate_type> current_pt = poly[1];
+ encompass(extents_rectangle, current_pt);
+ for(std::size_t i = 2; i < poly.size()-1; ++i) {
+ point_data<coordinate_type> next_pt = poly[i];
+ encompass(extents_rectangle, next_pt);
+ modify_pt(poly[i-1], prev_pt, current_pt, next_pt, distance, multiplier);
+ prev_pt = current_pt;
+ current_pt = next_pt;
+ }
+ if(delta(extents_rectangle, HORIZONTAL) <= std::abs(2*distance))
+ return false;
+ if(delta(extents_rectangle, VERTICAL) <= std::abs(2*distance))
+ return false;
+ point_data<coordinate_type> next_pt = first_pt;
+ modify_pt(poly[poly.size()-2], prev_pt, current_pt, next_pt, distance, multiplier);
+ prev_pt = current_pt;
+ current_pt = next_pt;
+ next_pt = second_pt;
+ modify_pt(poly[0], prev_pt, current_pt, next_pt, distance, multiplier);
+ poly.back() = poly.front();
+ //if the line segments formed between orignial and new points cross for an edge that edge inverts
+ //if all edges invert the polygon should be discarded
+ //if even one edge does not invert return true because the polygon is valid
+ bool non_inverting_edge = false;
+ for(std::size_t i = 1; i < poly.size(); ++i) {
+ std::pair<point_data<coordinate_type>, point_data<coordinate_type> >
+ he1(poly[i], orig_poly[i]),
+ he2(poly[i-1], orig_poly[i-1]);
+ if(!scanline_base<coordinate_type>::intersects(he1, he2)) {
+ non_inverting_edge = true;
+ break;
+ }
+ }
+ return non_inverting_edge;
+ }
+
+ polygon_set_data&
+ bloat(typename coordinate_traits<coordinate_type>::unsigned_area_type distance) {
+ std::list<polygon_with_holes_data<coordinate_type> > polys;
+ get(polys);
+ clear();
+ for(typename std::list<polygon_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
+ itr != polys.end(); ++itr) {
+ resize_poly_up((*itr).self_.coords_, (coordinate_type)distance, (coordinate_type)1);
+ insert_vertex_sequence((*itr).self_.begin(), (*itr).self_.end(), COUNTERCLOCKWISE, false); //inserts without holes
+ for(typename std::list<polygon_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
+ itrh != (*itr).holes_.end(); ++itrh) {
+ if(resize_poly_down((*itrh).coords_, (coordinate_type)distance, (coordinate_type)1)) {
+ insert_vertex_sequence((*itrh).coords_.begin(), (*itrh).coords_.end(), CLOCKWISE, true);
+ }
+ }
+ }
+ return *this;
+ }
+
+ polygon_set_data&
+ shrink(typename coordinate_traits<coordinate_type>::unsigned_area_type distance) {
+ std::list<polygon_with_holes_data<coordinate_type> > polys;
+ get(polys);
+ clear();
+ for(typename std::list<polygon_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
+ itr != polys.end(); ++itr) {
+ if(resize_poly_down((*itr).self_.coords_, (coordinate_type)distance, (coordinate_type)-1)) {
+ insert_vertex_sequence((*itr).self_.begin(), (*itr).self_.end(), COUNTERCLOCKWISE, false); //inserts without holes
+ for(typename std::list<polygon_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
+ itrh != (*itr).holes_.end(); ++itrh) {
+ resize_poly_up((*itrh).coords_, (coordinate_type)distance, (coordinate_type)-1);
+ insert_vertex_sequence((*itrh).coords_.begin(), (*itrh).coords_.end(), CLOCKWISE, true);
+ }
+ }
+ }
+ return *this;
+ }
+
// TODO:: should be private
template <typename geometry_type>
inline polygon_set_data&
@@ -478,10 +624,10 @@
// for all corners
polygon_set_data<T> sizingSet;
- bool sizing_sign = resizing>0;
+ bool sizing_sign = resizing<0;
bool prev_concave = true;
point_data<T> prev_point;
- int iCtr=0;
+ //int iCtr=0;
//insert minkofski shapes on edges and corners
@@ -495,7 +641,9 @@
double direction = normal1.x()*normal2.y()- normal2.x()*normal1.y();
bool convex = direction>0;
- bool treat_as_concave = convex ^ sizing_sign ;
+ bool treat_as_concave = !convex;
+ if(sizing_sign)
+ treat_as_concave = convex;
point_data<double> v;
assign(v, normal1);
double s2 = (v.x()*v.x()+v.y()*v.y());
@@ -574,7 +722,7 @@
//insert original shape
tmp.insert(poly, false, polygon_concept());
- if(resizing < 0 ^ hole) tmp -= sizingSet;
+ if((resizing < 0) ^ hole) tmp -= sizingSet;
else tmp += sizingSet;
//tmp.clean();
insert(tmp, hole);
@@ -652,7 +800,7 @@
data.push_back(vertex_half_edge((*itr).first.first, (*itr).first.second, (*itr).second));
data.push_back(vertex_half_edge((*itr).first.second, (*itr).first.first, -1 * (*itr).second));
}
- std::sort(data.begin(), data.end());
+ polygon_sort(data.begin(), data.end());
pf.scan(container, data.begin(), data.end());
}
};
@@ -663,13 +811,13 @@
typedef polygon_set_concept type;
};
- template <typename T>
- inline double compute_area(point_data<T>& a, point_data<T>& b, point_data<T>& c) {
+// template <typename T>
+// inline double compute_area(point_data<T>& a, point_data<T>& b, point_data<T>& c) {
- return (double)(b.x()-a.x())*(double)(c.y()-a.y())- (double)(c.x()-a.x())*(double)(b.y()-a.y());
+// return (double)(b.x()-a.x())*(double)(c.y()-a.y())- (double)(c.x()-a.x())*(double)(b.y()-a.y());
- }
+// }
template <typename T>
inline int make_resizing_vertex_list(std::vector<std::vector<point_data< T> > >& return_points,
@@ -710,7 +858,7 @@
std::pair<point_data<double>,point_data<double> > he1(start_offset,mid1_offset);
std::pair<point_data<double>,point_data<double> > he2(mid2_offset ,end_offset);
- typedef typename high_precision_type<double>::type high_precision;
+ //typedef typename high_precision_type<double>::type high_precision;
point_data<T> intersect;
typename scanline_base<T>::compute_intersection_pack pack;
@@ -724,8 +872,8 @@
return_points_back.push_back(start);
return_points_back.push_back(curr_prev);
- double d1= compute_area(intersect,middle,start);
- double d2= compute_area(start,curr_prev,intersect);
+ //double d1= compute_area(intersect,middle,start);
+ //double d2= compute_area(start,curr_prev,intersect);
curr_prev = intersect;
@@ -755,7 +903,7 @@
ps += 2.0 * our_pi;
if (pe <= 0.0)
pe += 2.0 * our_pi;
- if (ps >= 2.0 * M_PI)
+ if (ps >= 2.0 * our_pi)
ps -= 2.0 * our_pi;
while (pe <= ps)
pe += 2.0 * our_pi;
@@ -772,7 +920,7 @@
}
return_points.push_back(round_down<T>(center));
return_points.push_back(round_down<T>(start));
- int i=0;
+ unsigned int i=0;
double curr_angle = ps+delta_angle;
while( curr_angle < pe - 0.01 && i < 2 * num_circle_segments) {
i++;
@@ -857,5 +1005,6 @@
#include "detail/polygon_set_view.hpp"
#include "polygon_set_concept.hpp"
+#include "detail/minkowski.hpp"
#endif
Modified: sandbox/gtl/boost/polygon/polygon_set_traits.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_set_traits.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_set_traits.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -82,6 +82,7 @@
static inline void set(std::list<T>& polygon_set, input_iterator_type input_begin, input_iterator_type input_end) {
polygon_set.clear();
polygon_set_data<typename polygon_set_traits<std::list<T> >::coordinate_type> ps;
+ ps.reserve(std::distance(input_begin, input_end));
ps.insert(input_begin, input_end);
ps.get(polygon_set);
}
@@ -91,7 +92,10 @@
template <typename input_iterator_type>
static inline void set(std::vector<T>& polygon_set, input_iterator_type input_begin, input_iterator_type input_end) {
polygon_set.clear();
+ size_t num_ele = std::distance(input_begin, input_end);
+ polygon_set.reserve(num_ele);
polygon_set_data<typename polygon_set_traits<std::list<T> >::coordinate_type> ps;
+ ps.reserve(num_ele);
ps.insert(input_begin, input_end);
ps.get(polygon_set);
}
@@ -121,7 +125,7 @@
static inline bool clean(const polygon_set_data<T>& polygon_set) { polygon_set.clean(); return true; }
- static inline bool sorted(const polygon_set_data<T>& polygon_set) { int untested = 0;polygon_set.sort(); return true; }
+ static inline bool sorted(const polygon_set_data<T>& polygon_set) { polygon_set.sort(); return true; }
};
}
Modified: sandbox/gtl/boost/polygon/polygon_traits.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_traits.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_traits.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -758,7 +758,10 @@
if(pts.size() < 3) { pts.clear(); return; }
Point firstPt = pts.front();
Point prevPt = firstPt;
- std::unique(pts.begin(), pts.end());
+ typename std::vector<point_data<Unit> >::iterator endLocation = std::unique(pts.begin(), pts.end());
+ if(endLocation != pts.end()){
+ pts.resize(endLocation - pts.begin());
+ }
if(pts.back() == pts[0]) pts.pop_back();
//iterate over point triplets
int numPts = pts.size();
@@ -1170,7 +1173,7 @@
//odd count implies boundary condition
if(counts[0] % 2 || counts[1] % 2) return consider_touch;
//an odd number of edges to the left implies interior pt
- return counts[0] % 4 != 0;
+ return counts[winding(polygon) == COUNTERCLOCKWISE ? 0 : 1] % 4 != 0;
}
//TODO: refactor to expose as user APIs
@@ -1348,10 +1351,18 @@
if(oabedge == 0) return consider_touch;
if(oabedge == 1) ++above;
} else if(x(point) == xmax) {
- Point tmppt;
- assign(tmppt, point);
- if( edge_utils<Unit>::on_above_or_below(tmppt, he) == 0 ) {
- return consider_touch;
+ if(x(point) == xmin) {
+ Unit ymin = (std::min)(y(he.first), y(he.second));
+ Unit ymax = (std::max)(y(he.first), y(he.second));
+ Unit ypt = y(point);
+ if(ypt <= ymax && ypt >= ymin)
+ return consider_touch;
+ } else {
+ Point tmppt;
+ assign(tmppt, point);
+ if( edge_utils<Unit>::on_above_or_below(tmppt, he) == 0 ) {
+ return consider_touch;
+ }
}
}
}
Modified: sandbox/gtl/boost/polygon/polygon_with_holes_data.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_with_holes_data.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_with_holes_data.hpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -96,7 +96,7 @@
return holes_.size();
}
-private:
+public:
polygon_data<coordinate_type> self_;
std::list<hole_type> holes_;
};
Modified: sandbox/gtl/libs/polygon/test/gtl_boost_unit_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/gtl_boost_unit_test.cpp (original)
+++ sandbox/gtl/libs/polygon/test/gtl_boost_unit_test.cpp 2011-09-29 15:08:04 EDT (Thu, 29 Sep 2011)
@@ -3364,6 +3364,138 @@
return 1;
}
+ {
+ polygon_set_data<int> ps;
+ polygon_90_set_data<int> ps90;
+ rectangle_data<int> rect(0, 1, 10, 100);
+ std::vector<polygon_data<int> > rupolys, rupolys45;
+ ps.insert(rect);
+ ps90.insert(rect);
+ ps.bloat(10);
+ ps90.bloat(10, 10, 10, 10);
+ rupolys.clear();
+ rupolys45.clear();
+ ps.get(rupolys);
+ ps90.get(rupolys45);
+ std::cout << rupolys[0] << std::endl;
+ std::cout << rupolys45[0] << std::endl;
+ if(!equivalence(ps, ps90)) {
+ std::cout << "test manhattan vs general resize up failed\n";
+ return 1;
+ }
+ ps.shrink(10);
+ ps90.shrink(10, 10, 10, 10);
+ if(!equivalence(ps, rect)) {
+ std::cout << "test manhattan vs general resize down failed\n";
+ return 1;
+ }
+ rectangle_data<int> rect2(3, 4, 6, 80);
+ ps -= rect2;
+ ps90 -= rect2;
+ ps.bloat(1);
+ ps90.bloat(1, 1, 1, 1);
+ if(!equivalence(ps, ps90)) {
+ std::cout << "test manhattan vs general with hole resize up failed\n";
+ return 1;
+ }
+ ps.shrink(1);
+ ps90.shrink(1, 1, 1, 1);
+ if(!equivalence(ps, ps90)) {
+ std::cout << "test manhattan vs general with hole resize down failed\n";
+ return 1;
+ }
+ ps.clear();
+ polygon_45_data<int> poly;
+ std::vector<point_data<int> > pts;
+ pts.push_back(point_data<int>(0, 0));
+ pts.push_back(point_data<int>(10, 0));
+ pts.push_back(point_data<int>(0, 10));
+ polygon_45_set_data<int> ps45;
+ set_points(poly, pts.begin(), pts.end());
+ ps.insert(poly);
+ ps45.insert(poly);
+ ps.bloat(9);
+ ps45.resize(9);
+ rupolys.clear();
+ rupolys45.clear();
+ ps.get(rupolys);
+ ps45.get(rupolys45);
+ std::cout << rupolys[0] << std::endl;
+ std::cout << rupolys45[0] << std::endl;
+ pts.clear();
+ pts.push_back(point_data<int>(32, -9));
+ pts.push_back(point_data<int>(-9, 32));
+ pts.push_back(point_data<int>(-9, -9));
+ set_points(poly, pts.begin(), pts.end());
+ if(!equivalence(ps, poly)) {
+ std::cout << "test general resize up failed\n";
+ return 1;
+ }
+ // this test is waived due to rounding differences between 45 and general resizing
+ // general resizing is computing floating point coordinates for the intersection
+ // and rounding those to closest while 45 is computing the normal point and rounding
+ // that to closest, it turns out to result in different intersection point
+ // we want the general to be more accurate to avoid artifacts
+ //if(!equivalence(ps, ps45)) {
+ // std::cout << "test 45 vs general resize up failed\n";
+ // return 1;
+ //}
+ ps.shrink(9);
+ ps45.resize(-9);
+ if(!equivalence(ps, ps45)) {
+ std::cout << "test 45 vs general resize down failed\n";
+ return 1;
+ }
+ pts.clear();
+ pts.push_back(point_data<int>(1, 1));
+ pts.push_back(point_data<int>(7, 1));
+ pts.push_back(point_data<int>(1, 7));
+ set_points(poly, pts.begin(), pts.end());
+ ps.insert(poly, true);
+ ps45.insert(poly, true);
+ ps.bloat(1);
+ ps45.resize(1);
+ rupolys.clear();
+ rupolys45.clear();
+ ps.get(rupolys);
+ ps45.get(rupolys45);
+ std::cout << rupolys[0] << std::endl;
+ std::cout << rupolys45[0] << std::endl;
+ pts.clear();
+ pts.push_back(point_data<int>(12, -1));
+ pts.push_back(point_data<int>(5, 6));
+ pts.push_back(point_data<int>(5, 2));
+ pts.push_back(point_data<int>(2, 2));
+ pts.push_back(point_data<int>(2, 5));
+ pts.push_back(point_data<int>(5, 2));
+ pts.push_back(point_data<int>(5, 6));
+ pts.push_back(point_data<int>(-1, 12));
+ pts.push_back(point_data<int>(-1, -1));
+ pts.push_back(point_data<int>(12, -1));
+ set_points(poly, pts.begin(), pts.end());
+ if(!equivalence(ps, poly)) {
+ std::cout << "test general resize up with holes failed\n";
+ return 1;
+ }
+ //waived
+ //if(!equivalence(ps, ps45)) {
+ // std::cout << "test 45 vs general resize up with holes failed\n";
+ // return 1;
+ //}
+ ps.shrink(1);
+ ps45.resize(-1);
+ if(!equivalence(ps, ps45)) {
+ std::cout << "test 45 vs general resize down with holes failed\n";
+ return 1;
+ }
+ ps.shrink(10);
+ ps45.resize(-10);
+ if(!equivalence(ps, ps45)) {
+ std::cout << "test 45 vs general resize down 2 with holes failed\n";
+ return 1;
+ }
+ }
+
std::cout << "ALL TESTS COMPLETE\n";
return 0;
}