|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r58551 - in sandbox/gtl/boost/polygon: . detail
From: lucanus.j.simonson_at_[hidden]
Date: 2009-12-28 15:19:51
Author: ljsimons
Date: 2009-12-28 15:19:50 EST (Mon, 28 Dec 2009)
New Revision: 58551
URL: http://svn.boost.org/trac/boost/changeset/58551
Log:
performance improvements to aribtrary angle algorithms
Text files modified:
sandbox/gtl/boost/polygon/detail/polygon_arbitrary_formation.hpp | 171 ++++++++++++++++++++++++++++++++++-----
sandbox/gtl/boost/polygon/detail/scan_arbitrary.hpp | 134 +++++++++++++++++++++++++-----
sandbox/gtl/boost/polygon/gmp_override.hpp | 9 +
sandbox/gtl/boost/polygon/isotropy.hpp | 7 +
4 files changed, 273 insertions(+), 48 deletions(-)
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 2009-12-28 15:19:50 EST (Mon, 28 Dec 2009)
@@ -66,6 +66,11 @@
return cross_1 == cross_2 && (cross_1_sign == cross_2_sign || cross_1 == 0);
}
+ template <typename T>
+ static inline bool equal_slope_hp(const T& dx1, const T& dy1, const T& dx2, const T& dy2) {
+ return dx1 * dy2 == dx2 * dy1;
+ }
+
static inline bool equal_slope(const Unit& x, const Unit& y,
const Point& pt1, const Point& pt2) {
const Point* pts[2] = {&pt1, &pt2};
@@ -170,20 +175,52 @@
}
static inline typename high_precision_type<Unit>::type evalAtXforY(Unit xIn, Point pt, Point other_pt) {
+ typename high_precision_type<Unit>::type
+ evalAtXforYret, evalAtXforYxIn, evalAtXforYx1, evalAtXforYy1, evalAtXforYdx1, evalAtXforYdx,
+ evalAtXforYdy, evalAtXforYx2, evalAtXforYy2, evalAtXforY0;
//y = (x - x1)dy/dx + y1
//y = (xIn - pt.x)*(other_pt.y-pt.y)/(other_pt.x-pt.x) + pt.y
//assert pt.x != other_pt.x
- Unit x1 = pt.get(HORIZONTAL);
- Unit y1 = pt.get(VERTICAL);
typedef typename high_precision_type<Unit>::type high_precision;
- high_precision dx1 = (high_precision)xIn - (high_precision)pt.get(HORIZONTAL);
- if(dx1 == high_precision(0)) return (high_precision)(pt.get(VERTICAL));
- high_precision dx = (high_precision)(other_pt.get(HORIZONTAL)) - (high_precision)x1;
- high_precision dy = (high_precision)(other_pt.get(VERTICAL)) - (high_precision)y1;
- high_precision y = (((high_precision)dx1) * (high_precision)dy / (high_precision)dx + (high_precision)y1);
- return y;
+ evalAtXforYxIn = (high_precision)xIn;
+ evalAtXforYx1 = pt.get(HORIZONTAL);
+ evalAtXforYy1 = pt.get(VERTICAL);
+ evalAtXforYdx1 = evalAtXforYxIn - evalAtXforYx1;
+ evalAtXforY0 = high_precision(0);
+ if(evalAtXforYdx1 == evalAtXforY0) return evalAtXforYret = evalAtXforYy1;
+ evalAtXforYx2 = (high_precision)other_pt.get(HORIZONTAL);
+ evalAtXforYy2 = (high_precision)other_pt.get(VERTICAL);
+
+ evalAtXforYdx = evalAtXforYx2 - evalAtXforYx1;
+ evalAtXforYdy = evalAtXforYy2 - evalAtXforYy1;
+ evalAtXforYret = ((evalAtXforYdx1) * evalAtXforYdy / evalAtXforYdx + evalAtXforYy1);
+ return evalAtXforYret;
}
+ struct evalAtXforYPack {
+ typename high_precision_type<Unit>::type
+ evalAtXforYret, evalAtXforYxIn, evalAtXforYx1, evalAtXforYy1, evalAtXforYdx1, evalAtXforYdx,
+ evalAtXforYdy, evalAtXforYx2, evalAtXforYy2, evalAtXforY0;
+ inline const typename high_precision_type<Unit>::type& evalAtXforY(Unit xIn, Point pt, Point other_pt) {
+ //y = (x - x1)dy/dx + y1
+ //y = (xIn - pt.x)*(other_pt.y-pt.y)/(other_pt.x-pt.x) + pt.y
+ //assert pt.x != other_pt.x
+ typedef typename high_precision_type<Unit>::type high_precision;
+ evalAtXforYxIn = (high_precision)xIn;
+ evalAtXforYx1 = pt.get(HORIZONTAL);
+ evalAtXforYy1 = pt.get(VERTICAL);
+ evalAtXforYdx1 = evalAtXforYxIn - evalAtXforYx1;
+ evalAtXforY0 = high_precision(0);
+ if(evalAtXforYdx1 == evalAtXforY0) return evalAtXforYret = evalAtXforYy1;
+ evalAtXforYx2 = (high_precision)other_pt.get(HORIZONTAL);
+ evalAtXforYy2 = (high_precision)other_pt.get(VERTICAL);
+
+ evalAtXforYdx = evalAtXforYx2 - evalAtXforYx1;
+ evalAtXforYdy = evalAtXforYy2 - evalAtXforYy1;
+ evalAtXforYret = ((evalAtXforYdx1) * evalAtXforYdy / evalAtXforYdx + evalAtXforYy1);
+ return evalAtXforYret;
+ }
+ };
static inline bool is_vertical(const half_edge& he) {
return he.first.get(HORIZONTAL) == he.second.get(HORIZONTAL);
@@ -202,17 +239,25 @@
private:
Unit *x_; //x value at which to apply comparison
int *justBefore_;
+ evalAtXforYPack * pack_;
public:
- inline less_half_edge() : x_(0), justBefore_(0) {}
- inline less_half_edge(Unit *x, int *justBefore) : x_(x), justBefore_(justBefore) {}
- inline less_half_edge(const less_half_edge& that) : x_(that.x_), justBefore_(that.justBefore_) {}
- inline less_half_edge& operator=(const less_half_edge& that) { x_ = that.x_; justBefore_ = that.justBefore_; return *this; }
+ inline less_half_edge() : x_(0), justBefore_(0), pack_(0) {}
+ inline less_half_edge(Unit *x, int *justBefore, evalAtXforYPack * packIn) : x_(x), justBefore_(justBefore), pack_(packIn) {}
+ inline less_half_edge(const less_half_edge& that) : x_(that.x_), justBefore_(that.justBefore_),
+ pack_(that.pack_){}
+ inline less_half_edge& operator=(const less_half_edge& that) {
+ x_ = that.x_;
+ justBefore_ = that.justBefore_;
+ pack_ = that.pack_;
+ return *this; }
inline bool operator () (const half_edge& elm1, const half_edge& elm2) const {
- //Unit y1 = evalAtXforY(*x_ + !*justBefore_, elm1.first, elm1.second);
- //Unit y2 = evalAtXforY(*x_ + !*justBefore_, elm2.first, elm2.second);
+ if(std::max(elm1.first.y(), elm1.second.y()) < std::min(elm2.first.y(), elm2.second.y()))
+ return true;
+ if(std::min(elm1.first.y(), elm1.second.y()) > std::max(elm2.first.y(), elm2.second.y()))
+ return false;
typedef typename high_precision_type<Unit>::type high_precision;
- high_precision y1 = evalAtXforY(*x_, elm1.first, elm1.second);
- high_precision y2 = evalAtXforY(*x_, elm2.first, elm2.second);
+ high_precision y1 = pack_->evalAtXforY(*x_, elm1.first, elm1.second);
+ high_precision y2 = pack_->evalAtXforY(*x_, elm2.first, elm2.second);
if(y1 < y2) return true;
if(y1 == y2) {
//if justBefore is true we invert the result of the comparison of slopes
@@ -337,6 +382,83 @@
return q + r;
}
+ 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;
+ inline bool compute_intersection(Point& intersection, const half_edge& he1, const half_edge& he2) {
+ typedef rectangle_data<Unit> Rectangle;
+ Rectangle rect1, rect2;
+ set_points(rect1, he1.first, he1.second);
+ set_points(rect2, he2.first, he2.second);
+ if(!::boost::polygon::intersects(rect1, rect2, true)) return false;
+ if(is_vertical(he1)) {
+ if(is_vertical(he2)) return false;
+ y_high = evalAtXforY(he1.first.get(HORIZONTAL), he2.first, he2.second);
+ Unit y = convert_high_precision_type<Unit>(y_high);
+ if(y_high < (high_precision)y) --y;
+ if(contains(rect1.get(VERTICAL), y, true)) {
+ intersection = Point(he1.first.get(HORIZONTAL), y);
+ return true;
+ } else {
+ return false;
+ }
+ } else if(is_vertical(he2)) {
+ y_high = evalAtXforY(he2.first.get(HORIZONTAL), he1.first, he1.second);
+ Unit y = convert_high_precision_type<Unit>(y_high);
+ if(y_high < (high_precision)y) --y;
+ if(contains(rect2.get(VERTICAL), y, true)) {
+ intersection = Point(he2.first.get(HORIZONTAL), y);
+ return true;
+ } else {
+ return false;
+ }
+ }
+ //the bounding boxes of the two line segments intersect, so we check closer to find the intersection point
+ dy2 = (high_precision)(he2.second.get(VERTICAL)) -
+ (high_precision)(he2.first.get(VERTICAL));
+ dy1 = (high_precision)(he1.second.get(VERTICAL)) -
+ (high_precision)(he1.first.get(VERTICAL));
+ dx2 = (high_precision)(he2.second.get(HORIZONTAL)) -
+ (high_precision)(he2.first.get(HORIZONTAL));
+ dx1 = (high_precision)(he1.second.get(HORIZONTAL)) -
+ (high_precision)(he1.first.get(HORIZONTAL));
+ if(equal_slope_hp(dx1, dy1, dx2, dy2)) return false;
+ //the line segments have different slopes
+ //we can assume that the line segments are not vertical because such an intersection is handled elsewhere
+ x11 = (high_precision)(he1.first.get(HORIZONTAL));
+ x21 = (high_precision)(he2.first.get(HORIZONTAL));
+ y11 = (high_precision)(he1.first.get(VERTICAL));
+ y21 = (high_precision)(he2.first.get(VERTICAL));
+ //Unit exp_x = ((at)x11 * (at)dy1 * (at)dx2 - (at)x21 * (at)dy2 * (at)dx1 + (at)y21 * (at)dx1 * (at)dx2 - (at)y11 * (at)dx1 * (at)dx2) / ((at)dy1 * (at)dx2 - (at)dy2 * (at)dx1);
+ //Unit exp_y = ((at)y11 * (at)dx1 * (at)dy2 - (at)y21 * (at)dx2 * (at)dy1 + (at)x21 * (at)dy1 * (at)dy2 - (at)x11 * (at)dy1 * (at)dy2) / ((at)dx1 * (at)dy2 - (at)dx2 * (at)dy1);
+ x_num = (x11 * dy1 * dx2 - x21 * dy2 * dx1 + y21 * dx1 * dx2 - y11 * dx1 * dx2);
+ x_den = (dy1 * dx2 - dy2 * dx1);
+ y_num = (y11 * dx1 * dy2 - y21 * dx2 * dy1 + x21 * dy1 * dy2 - x11 * dy1 * dy2);
+ y_den = (dx1 * dy2 - dx2 * dy1);
+ x = x_num / x_den;
+ y = y_num / y_den;
+ //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);
+ 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(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);
+ //Unit y2 = evalAtXforY(exp_x, he2.first, he2.second);
+ //std::cout << exp_x << " " << exp_y << " " << y1 << " " << y2 << std::endl;
+ Point result(x_unit, y_unit);
+ if(!contains(rect1, result, true)) return false;
+ if(!contains(rect2, result, true)) return false;
+ intersection = result;
+ return true;
+ }
+ };
+
static inline bool compute_intersection(Point& intersection, const half_edge& he1, const half_edge& he2) {
typedef typename high_precision_type<Unit>::type high_precision;
typedef rectangle_data<Unit> Rectangle;
@@ -347,7 +469,7 @@
if(is_vertical(he1)) {
if(is_vertical(he2)) return false;
high_precision y_high = evalAtXforY(he1.first.get(HORIZONTAL), he2.first, he2.second);
- Unit y = (Unit)y_high;
+ Unit y = convert_high_precision_type<Unit>(y_high);
if(y_high < (high_precision)y) --y;
if(contains(rect1.get(VERTICAL), y, true)) {
intersection = Point(he1.first.get(HORIZONTAL), y);
@@ -357,7 +479,7 @@
}
} else if(is_vertical(he2)) {
high_precision y_high = evalAtXforY(he2.first.get(HORIZONTAL), he1.first, he1.second);
- Unit y = (Unit)y_high;
+ Unit y = convert_high_precision_type<Unit>(y_high);
if(y_high < (high_precision)y) --y;
if(contains(rect2.get(VERTICAL), y, true)) {
intersection = Point(he2.first.get(HORIZONTAL), y);
@@ -375,7 +497,7 @@
(high_precision)(he2.first.get(HORIZONTAL));
high_precision dx1 = (high_precision)(he1.second.get(HORIZONTAL)) -
(high_precision)(he1.first.get(HORIZONTAL));
- if(equal_slope(dx1, dy1, dx2, dy2)) return false;
+ if(equal_slope_hp(dx1, dy1, dx2, dy2)) return false;
//the line segments have different slopes
//we can assume that the line segments are not vertical because such an intersection is handled elsewhere
high_precision x11 = (high_precision)(he1.first.get(HORIZONTAL));
@@ -394,8 +516,8 @@
//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);
- Unit x_unit = (Unit)x;
- Unit y_unit = (Unit)y;
+ 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;
@@ -1452,7 +1574,7 @@
//we need to handle the hole now and not at the next input vertex
active_tail_arbitrary* at = iter->second;
high_precision precise_y = iter->first.evalAtX(x_);
- Unit fracture_y = (Unit)(precise_y);
+ Unit fracture_y = convert_high_precision_type<Unit>(precise_y);
if(precise_y < fracture_y) --fracture_y;
Point point(x_, fracture_y);
verticalTail->getOtherActiveTail()->pushPoint(point);
@@ -1993,7 +2115,7 @@
iterator previter) {
active_tail_arbitrary* iterTail = (*previter).second;
Point prevPoint(polygon_arbitrary_formation<Unit>::x_,
- (Unit)previter->first.evalAtX(polygon_arbitrary_formation<Unit>::x_));
+ convert_high_precision_type<Unit>(previter->first.evalAtX(polygon_arbitrary_formation<Unit>::x_)));
iterTail->pushPoint(prevPoint);
std::pair<active_tail_arbitrary*, active_tail_arbitrary*> tailPair =
active_tail_arbitrary::createActiveTailsAsPair(prevPoint, true, 0, false);
@@ -2421,7 +2543,8 @@
currentIter->pt.y() > (*iter).first.evalAtX(polygon_arbitrary_formation<Unit>::x_))) {
//splice vertical pair into edge above
active_tail_arbitrary* tailabove = (*iter).second;
- Point point(polygon_arbitrary_formation<Unit>::x_, (Unit)(*iter).first.evalAtX(polygon_arbitrary_formation<Unit>::x_));
+ Point point(polygon_arbitrary_formation<Unit>::x_,
+ convert_high_precision_type<Unit>((*iter).first.evalAtX(polygon_arbitrary_formation<Unit>::x_)));
verticalPair.second->pushPoint(point);
active_tail_arbitrary::joinChains(point, tailabove, verticalPair.first, true, output);
(*iter).second = verticalPair.second;
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 2009-12-28 15:19:50 EST (Mon, 28 Dec 2009)
@@ -7,7 +7,9 @@
*/
#ifndef BOOST_POLYGON_SCAN_ARBITRARY_HPP
#define BOOST_POLYGON_SCAN_ARBITRARY_HPP
+#ifdef BOOST_POLYGON_DEBUG_FILE
#include <fstream>
+#endif
namespace boost { namespace polygon{
template <typename Unit>
@@ -63,11 +65,85 @@
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, int size, std::vector<std::pair<Unit, std::size_t> >& histogram) {
+ std::vector<std::pair<Unit, int> > ends;
+ ends.reserve(size * 2);
+ for(iT itr = begin ; itr != end; ++itr) {
+ int count = (*itr).first.first.y() < (*itr).first.second.y() ? 1 : -1;
+ 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());
+ histogram.reserve(ends.size());
+ histogram.push_back(std::make_pair(ends.front().first, 0));
+ for(typename std::vector<std::pair<Unit, int> >::iterator itr = ends.begin(); itr != ends.end(); ++itr) {
+ if((*itr).first != histogram.back().first) {
+ histogram.push_back(std::make_pair((*itr).first, histogram.back().second));
+ }
+ histogram.back().second += (*itr).second;
+ }
+ }
+
+ template <typename iT>
+ static inline void compute_y_cuts(std::vector<Unit>& y_cuts, iT begin, iT end, std::size_t size) {
+ if(begin == end) return;
+ if(size < 10) return;
+ std::size_t min_cut = size;
+ iT cut = begin;
+ std::size_t position = 0;
+ std::size_t cut_size = 0;
+ for(iT itr = begin; itr != end; ++itr, ++position) {
+ if(position < size / 3)
+ continue;
+ if(size - position < size / 3) break;
+ if((*itr).second < min_cut) {
+ cut = itr;
+ min_cut = (*cut).second;
+ cut_size = position;
+ }
+ }
+ if(cut_size == 0 || (*cut).second > size / 3)
+ return;
+ compute_y_cuts(y_cuts, begin, cut, cut_size);
+ y_cuts.push_back((*cut).first);
+ compute_y_cuts(y_cuts, cut, end, size - cut_size);
+ }
+
+ template <typename iT>
+ static inline void validate_scan_divide_and_conquer(std::vector<std::set<Point> >& intersection_points,
+ iT begin, iT end) {
+ std::vector<std::pair<Unit, std::size_t> > histogram;
+ compute_histogram_in_y(begin, end, std::distance(begin, end), histogram);
+ std::vector<Unit> y_cuts;
+ compute_y_cuts(y_cuts, histogram.begin(), histogram.end(), histogram.size());
+ std::map<Unit, std::vector<std::pair<half_edge, segment_id> > > bins;
+ bins[histogram.front().first] = std::vector<std::pair<half_edge, segment_id> >();
+ for(typename std::vector<Unit>::iterator itr = y_cuts.begin(); itr != y_cuts.end(); ++itr) {
+ bins[*itr] = std::vector<std::pair<half_edge, segment_id> >();
+ }
+ for(iT itr = begin; itr != end; ++itr) {
+ typename std::map<Unit, std::vector<std::pair<half_edge, segment_id> > >::iterator lb =
+ bins.lower_bound(std::min((*itr).first.first.y(), (*itr).first.second.y()));
+ if(lb != bins.begin())
+ --lb;
+ typename std::map<Unit, std::vector<std::pair<half_edge, segment_id> > >::iterator ub =
+ bins.upper_bound(std::max((*itr).first.first.y(), (*itr).first.second.y()));
+ for( ; lb != ub; ++lb) {
+ (*lb).second.push_back(*itr);
+ }
+ }
+ validate_scan(intersection_points, bins[histogram.front().first].begin(), bins[histogram.front().first].end());
+ for(typename std::vector<Unit>::iterator itr = y_cuts.begin(); itr != y_cuts.end(); ++itr) {
+ validate_scan(intersection_points, bins[*itr].begin(), bins[*itr].end());
+ }
+ }
+
//quadratic algorithm to do same work as optimal scan for cross checking
//assume sorted input
template <typename iT>
- static inline void validate_scan(std::map<segment_id, std::set<Point> >& intersection_points,
+ static inline void validate_scan(std::vector<std::set<Point> >& intersection_points,
iT begin, iT end) {
std::set<Point> pts;
std::vector<std::pair<half_edge, segment_id> > data(begin, end);
@@ -76,6 +152,7 @@
std::swap(data[i].first.first, data[i].first.second);
}
}
+ typename scanline_base<Unit>::compute_intersection_pack pack_;
std::sort(data.begin(), data.end());
//find all intersection points
for(typename std::vector<std::pair<half_edge, segment_id> >::iterator outer = data.begin();
@@ -94,7 +171,7 @@
he1.first.get(HORIZONTAL)))
break;
Point intersection;
- if(compute_intersection(intersection, he1, he2)) {
+ if(pack_.compute_intersection(intersection, he1, he2)) {
//their intersection point
pts.insert(intersection);
}
@@ -155,8 +232,9 @@
template <typename iT>
static inline void validate_scan(std::vector<std::pair<half_edge, int> >& output_segments,
iT begin, iT end) {
- std::map<segment_id, std::set<Point> > intersection_points;
- validate_scan(intersection_points, begin, end);
+ std::vector<std::set<Point> > intersection_points(std::distance(begin, end));
+ validate_scan_divide_and_conquer(intersection_points, begin, end);
+ //validate_scan(intersection_points, begin, end);
segment_intersections(output_segments, intersection_points, begin, end);
}
@@ -223,7 +301,7 @@
template <typename iT>
static inline void segment_intersections(std::vector<std::pair<half_edge, int> >& output_segments,
- std::map<segment_id, std::set<Point> >& intersection_points,
+ std::vector<std::set<Point> >& intersection_points,
iT begin, iT end) {
for(iT iter = begin; iter != end; ++iter) {
//less_point lp;
@@ -527,14 +605,14 @@
return false;
}
input.pop_back();
- input.push_back(std::make_pair(half_edge(Point(1, 0), Point(11, 11)), 3));
+ input.push_back(std::make_pair(half_edge(Point(1, 0), Point(11, 11)), input.size()));
edges.clear();
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail3 " << result.first << " " << result.second << "\n";
return false;
}
- input.push_back(std::make_pair(half_edge(Point(1, 0), Point(10, 11)), 4));
+ input.push_back(std::make_pair(half_edge(Point(1, 0), Point(10, 11)), input.size()));
edges.clear();
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
@@ -542,14 +620,14 @@
return false;
}
input.pop_back();
- input.push_back(std::make_pair(half_edge(Point(1, 2), Point(11, 11)), 5));
+ input.push_back(std::make_pair(half_edge(Point(1, 2), Point(11, 11)), input.size()));
edges.clear();
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail5 " << result.first << " " << result.second << "\n";
return false;
}
- input.push_back(std::make_pair(half_edge(Point(0, 5), Point(0, 11)), 6));
+ input.push_back(std::make_pair(half_edge(Point(0, 5), Point(0, 11)), input.size()));
edges.clear();
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
@@ -776,23 +854,23 @@
return false;
}
edges.pop_back();
- edges.push_back(std::make_pair(half_edge(Point(1, 0), Point(11, 11)), 3));
+ edges.push_back(std::make_pair(half_edge(Point(1, 0), Point(11, 11)), 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)), 4));
+ edges.push_back(std::make_pair(half_edge(Point(1, 0), Point(10, 11)), 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)), 5));
+ edges.push_back(std::make_pair(half_edge(Point(1, 2), Point(11, 11)), 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)), 6));
+ edges.push_back(std::make_pair(half_edge(Point(0, 5), Point(0, 11)), edges.size()));
if(verify_scan(result, edges.begin(), edges.end())) {
stdcout << "fail6 " << result.first << " " << result.second << "\n";
return false;
@@ -866,10 +944,11 @@
Unit x_;
Unit y_;
int just_before_;
+ typename scanline_base<Unit>::evalAtXforYPack evalAtXforYPack_;
public:
inline scanline() : scan_data_(), removal_set_(), insertion_set_(), end_point_queue_(),
x_((std::numeric_limits<Unit>::max)()), y_((std::numeric_limits<Unit>::max)()), just_before_(false) {
- less_half_edge lessElm(&x_, &just_before_);
+ less_half_edge lessElm(&x_, &just_before_, &evalAtXforYPack_);
scan_data_ = scanline_type(lessElm);
}
inline scanline(const scanline& that) : scan_data_(), removal_set_(), insertion_set_(), end_point_queue_(),
@@ -921,11 +1000,11 @@
#pragma warning( disable: 4127 )
#endif
while(true) {
- if(begin == end || (!first_iteration && (high_precision)(((*begin).first.first.get(VERTICAL)) != y ||
+ if(begin == end || (!first_iteration && ((high_precision)((*begin).first.first.get(VERTICAL)) != y ||
(*begin).first.first.get(HORIZONTAL) != x_))) {
//lookup iterator range in scanline for elements coming in from the left
//that end at this y
- Point pt(x_, (Unit)y);
+ Point pt(x_, convert_high_precision_type<Unit>(y));
//grab the properties coming in from below
property_map properties_below;
if(current_iter != scan_data_.end()) {
@@ -1384,25 +1463,28 @@
typedef std::pair<half_edge, property_map> vertex_data;
property_merge_data pmd;
+ typename scanline_base<Unit>::evalAtXforYPack evalAtXforYPack_;
template<typename vertex_data_type>
class less_vertex_data {
+ typename scanline_base<Unit>::evalAtXforYPack* pack_;
public:
less_vertex_data() {}
+ less_vertex_data(typename scanline_base<Unit>::evalAtXforYPack* pack) : pack_(pack) {}
bool operator()(const vertex_data_type& lvalue, const vertex_data_type& rvalue) {
less_point lp;
if(lp(lvalue.first.first, rvalue.first.first)) return true;
if(lp(rvalue.first.first, lvalue.first.first)) return false;
Unit x = lvalue.first.first.get(HORIZONTAL);
int just_before_ = 0;
- less_half_edge lhe(&x, &just_before_);
+ less_half_edge lhe(&x, &just_before_, pack_);
return lhe(lvalue.first, rvalue.first);
}
};
inline void sort_property_merge_data() {
- less_vertex_data<vertex_property> lvd;
+ less_vertex_data<vertex_property> lvd(&evalAtXforYPack_);
std::sort(pmd.begin(), pmd.end(), lvd);
}
public:
@@ -2380,18 +2462,21 @@
typedef std::pair<half_edge, property_map> vertex_data;
property_merge_data pmd;
+ typename scanline_base<Unit>::evalAtXforYPack evalAtXforYPack_;
template<typename vertex_data_type>
class less_vertex_data {
+ typename scanline_base<Unit>::evalAtXforYPack* pack_;
public:
less_vertex_data() {}
+ less_vertex_data(typename scanline_base<Unit>::evalAtXforYPack* pack) : pack_(pack) {}
bool operator()(const vertex_data_type& lvalue, const vertex_data_type& rvalue) {
less_point lp;
if(lp(lvalue.first.first, rvalue.first.first)) return true;
if(lp(rvalue.first.first, lvalue.first.first)) return false;
Unit x = lvalue.first.first.get(HORIZONTAL);
int just_before_ = 0;
- less_half_edge lhe(&x, &just_before_);
+ less_half_edge lhe(&x, &just_before_, pack_);
return lhe(lvalue.first, rvalue.first);
}
};
@@ -2450,7 +2535,7 @@
};
inline void sort_property_merge_data() {
- less_vertex_data<vertex_property> lvd;
+ less_vertex_data<vertex_property> lvd(&evalAtXforYPack_);
std::sort(pmd.begin(), pmd.end(), lvd);
}
public:
@@ -2593,18 +2678,21 @@
typedef std::pair<half_edge, property_map> vertex_data;
property_merge_data pmd;
+ typename scanline_base<Unit>::evalAtXforYPack evalAtXforYPack_;
template<typename vertex_data_type>
class less_vertex_data {
+ typename scanline_base<Unit>::evalAtXforYPack* pack_;
public:
less_vertex_data() {}
+ less_vertex_data(typename scanline_base<Unit>::evalAtXforYPack* pack) : pack_(pack) {}
bool operator()(const vertex_data_type& lvalue, const vertex_data_type& rvalue) {
less_point lp;
if(lp(lvalue.first.first, rvalue.first.first)) return true;
if(lp(rvalue.first.first, lvalue.first.first)) return false;
Unit x = lvalue.first.first.get(HORIZONTAL);
int just_before_ = 0;
- less_half_edge lhe(&x, &just_before_);
+ less_half_edge lhe(&x, &just_before_, pack_);
return lhe(lvalue.first, rvalue.first);
}
};
@@ -2669,7 +2757,7 @@
};
inline void sort_property_merge_data() {
- less_vertex_data<vertex_property> lvd;
+ less_vertex_data<vertex_property> lvd(&evalAtXforYPack_);
std::sort(pmd.begin(), pmd.end(), lvd);
}
public:
Modified: sandbox/gtl/boost/polygon/gmp_override.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/gmp_override.hpp (original)
+++ sandbox/gtl/boost/polygon/gmp_override.hpp 2009-12-28 15:19:50 EST (Mon, 28 Dec 2009)
@@ -111,9 +111,16 @@
template <>
struct high_precision_type<int> {
- typedef gmp_int type;
+ typedef mpq_class type;
};
+ template <>
+ int convert_high_precision_type<int>(const mpq_class& v) {
+ mpz_class num = v.get_num();
+ mpz_class den = v.get_den();
+ num /= den;
+ return num.get_si();
+ };
}
}
Modified: sandbox/gtl/boost/polygon/isotropy.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/isotropy.hpp (original)
+++ sandbox/gtl/boost/polygon/isotropy.hpp 2009-12-28 15:19:50 EST (Mon, 28 Dec 2009)
@@ -40,6 +40,8 @@
typedef long long polygon_long_long_type;
typedef unsigned long long polygon_ulong_long_type;
#endif
+#include <boost/mpl/size_t.hpp>
+#include <boost/mpl/protect.hpp>
#include <boost/utility/enable_if.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/and.hpp>
@@ -143,6 +145,11 @@
typedef long double type;
};
+ template <typename T>
+ T convert_high_precision_type(const typename high_precision_type<T>::type& v) {
+ return T(v);
+ };
+
template <>
struct coordinate_traits<int> {
typedef int coordinate_type;
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk