Google Git
Sign in
chromium / webm / webmlive / 30da35b5e63e20b1436b52538052db391a4f471a / . / third_party / boost / include / boost / polygon / detail / scan_arbitrary.hpp
blob: 7a4d0de6e33824437fb5039fc0938c0189913f58 [file] [log] [blame]
/*
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_SCAN_ARBITRARY_HPP
#define BOOST_POLYGON_SCAN_ARBITRARY_HPP
#ifdef BOOST_POLYGON_DEBUG_FILE
#include <fstream>
#endif
#include "polygon_sort_adaptor.hpp"
namespace boost { namespace polygon{
template <typename Unit>
class line_intersection : public scanline_base<Unit> {
private:
typedef typename scanline_base<Unit>::Point Point;
//the first point is the vertex and and second point establishes the slope of an edge eminating from the vertex
//typedef std::pair<Point, Point> half_edge;
typedef typename scanline_base<Unit>::half_edge half_edge;
//scanline comparator functor
typedef typename scanline_base<Unit>::less_half_edge less_half_edge;
typedef typename scanline_base<Unit>::less_point less_point;
//when parallel half edges are encounterd the set of segments is expanded
//when a edge leaves the scanline it is removed from the set
//when the set is empty the element is removed from the map
typedef int segment_id;
typedef std::pair<half_edge, std::set<segment_id> > scanline_element;
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_;
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_;
// //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) {
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));
}
gtlsort(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) {
if((*itr).first != histogram.back().first) {
histogram.push_back(std::make_pair((*itr).first, histogram.back().second));
}
if((*itr).second < 0)
histogram.back().second.second -= (*itr).second;
histogram.back().second.first += (*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 < 30) return; //30 is empirically chosen, but the algorithm is not sensitive to this constant
std::size_t min_cut = size;
iT cut = begin;
std::size_t position = 0;
std::size_t cut_size = 0;
std::size_t histogram_size = std::distance(begin, end);
for(iT itr = begin; itr != end; ++itr, ++position) {
if(position < histogram_size / 3)
continue;
if(histogram_size - position < histogram_size / 3) break;
if((*itr).second.first < min_cut) {
cut = itr;
min_cut = (*cut).second.first;
cut_size = position;
}
}
if(cut_size == 0 || (*cut).second.first > size / 9) //nine is empirically chosen
return;
compute_y_cuts(y_cuts, begin, cut, (*cut).second.first + (*cut).second.second);
y_cuts.push_back((*cut).first);
compute_y_cuts(y_cuts, cut, end, size - (*cut).second.second);
}
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::pair<std::size_t, 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(), std::distance(begin, end));
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(), *itr);
}
}
template <typename iT>
static inline void validate_scan(std::vector<std::set<Point> >& intersection_points,
iT begin, iT end) {
validate_scan(intersection_points, begin, end, (std::numeric_limits<Unit>::min)());
}
//quadratic algorithm to do same work as optimal scan for cross checking
template <typename iT>
static inline void validate_scan(std::vector<std::set<Point> >& intersection_points,
iT begin, iT end, Unit min_y) {
std::vector<Point> pts;
std::vector<std::pair<half_edge, segment_id> > data(begin, end);
for(std::size_t i = 0; i < data.size(); ++i) {
if(data[i].first.second < data[i].first.first) {
std::swap(data[i].first.first, data[i].first.second);
}
}
typename scanline_base<Unit>::compute_intersection_pack pack_;
gtlsort(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) {
const half_edge& he1 = (*outer).first;
//its own end points
pts.push_back(he1.first);
pts.push_back(he1.second);
std::set<Point>& segmentpts = intersection_points[(*outer).second];
for(typename std::set<Point>::iterator itr = segmentpts.begin(); itr != segmentpts.end(); ++itr) {
if((*itr).y() > min_y - 1)
pts.push_back(*itr);
}
bool have_first_y = he1.first.y() >= min_y && he1.second.y() >= min_y;
for(typename std::vector<std::pair<half_edge, segment_id> >::iterator inner = outer;
inner != data.end(); ++inner) {
const half_edge& he2 = (*inner).first;
if(have_first_y || (he2.first.y() >= min_y && he2.second.y() >= min_y)) {
//at least one segment has a low y value within the range
if(he1 == he2) continue;
if((std::min)(he2. first.get(HORIZONTAL),
he2.second.get(HORIZONTAL)) >=
(std::max)(he1.second.get(HORIZONTAL),
he1.first.get(HORIZONTAL)))
break;
if(he1.first == he2.first || he1.second == he2.second)
continue;
Point intersection;
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);
}
}
}
}
gtlsort(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
for(typename std::vector<std::pair<half_edge, segment_id> >::iterator outer = data.begin();
outer != data.end(); ++outer) {
const half_edge& he1 = (*outer).first;
segment_id id1 = (*outer).second;
typedef rectangle_data<Unit> Rectangle;
//Rectangle rect1;
//set_points(rect1, he1.first, he1.second);
//typename std::vector<Point>::iterator itr = lower_bound(pts.begin(), newend, (std::min)(he1.first, he1.second));
//typename std::vector<Point>::iterator itr2 = upper_bound(pts.begin(), newend, (std::max)(he1.first, he1.second));
Point startpt = (std::min)(he1.first, he1.second);
Point stoppt = (std::max)(he1.first, he1.second);
//while(itr != newend && itr != pts.begin() && (*itr).get(HORIZONTAL) >= (std::min)(he1.first.get(HORIZONTAL), he1.second.get(HORIZONTAL))) --itr;
//while(itr2 != newend && (*itr2).get(HORIZONTAL) <= (std::max)(he1.first.get(HORIZONTAL), he1.second.get(HORIZONTAL))) ++itr2;
//itr = pts.begin();
//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(scanline_base<Unit>::intersects_grid(*itr, he1))
intersection_points[id1].insert(*itr);
}
}
}
template <typename iT, typename property_type>
static inline void validate_scan(std::vector<std::pair<half_edge, std::pair<property_type, int> > >& output_segments,
iT begin, iT end) {
std::vector<std::pair<property_type, int> > input_properties;
std::vector<std::pair<half_edge, int> > input_segments, intermediate_segments;
int index = 0;
for( ; begin != end; ++begin) {
input_properties.push_back((*begin).second);
input_segments.push_back(std::make_pair((*begin).first, index++));
}
validate_scan(intermediate_segments, input_segments.begin(), input_segments.end());
for(std::size_t i = 0; i < intermediate_segments.size(); ++i) {
output_segments.push_back(std::make_pair(intermediate_segments[i].first,
input_properties[intermediate_segments[i].second]));
less_point lp;
if(lp(output_segments.back().first.first, output_segments.back().first.second) !=
lp(input_segments[intermediate_segments[i].second].first.first,
input_segments[intermediate_segments[i].second].first.second)) {
//edge changed orientation, invert count on edge
output_segments.back().second.second *= -1;
}
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)) {
std::swap(output_segments.back().first.first, output_segments.back().first.second);
}
}
}
template <typename iT>
static inline void validate_scan(std::vector<std::pair<half_edge, int> >& output_segments,
iT begin, iT 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);
// std::pair<segment_id, segment_id> offenders;
// if(!verify_scan(offenders, output_segments.begin(), output_segments.end())) {
// std::cout << "break here!\n";
// for(typename std::set<Point>::iterator itr = intersection_points[offenders.first].begin();
// itr != intersection_points[offenders.first].end(); ++itr) {
// std::cout << (*itr).x() << " " << (*itr).y() << " ";
// } std::cout << std::endl;
// for(typename std::set<Point>::iterator itr = intersection_points[offenders.second].begin();
// itr != intersection_points[offenders.second].end(); ++itr) {
// std::cout << (*itr).x() << " " << (*itr).y() << " ";
// } std::cout << std::endl;
// exit(1);
// }
}
//quadratic algorithm to find intersections
template <typename iT, typename segment_id>
static inline bool verify_scan(std::pair<segment_id, segment_id>& offenders,
iT begin, iT end) {
std::vector<std::pair<half_edge, segment_id> > data(begin, end);
for(std::size_t i = 0; i < data.size(); ++i) {
if(data[i].first.second < data[i].first.first) {
std::swap(data[i].first.first, data[i].first.second);
}
}
gtlsort(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;
segment_id id1 = (*outer).second;
for(typename std::vector<std::pair<half_edge, segment_id> >::iterator inner = outer;
inner != data.end(); ++inner) {
const half_edge& he2 = (*inner).first;
if(he1 == he2) continue;
if((std::min)(he2. first.get(HORIZONTAL),
he2.second.get(HORIZONTAL)) >
(std::max)(he1.second.get(HORIZONTAL),
he1.first.get(HORIZONTAL)))
break;
segment_id id2 = (*inner).second;
if(scanline_base<Unit>::intersects(he1, he2)) {
offenders.first = id1;
offenders.second = id2;
//std::cout << he1.first.x() << " " << he1.first.y() << " " << he1.second.x() << " " << he1.second.y() << " " << he2.first.x() << " " << he2.first.y() << " " << he2.second.x() << " " << he2.second.y() << std::endl;
return false;
}
}
}
return true;
}
class less_point_down_slope : public std::binary_function<Point, Point, bool> {
public:
inline less_point_down_slope() {}
inline bool operator () (const Point& pt1, const Point& pt2) const {
if(pt1.get(HORIZONTAL) < pt2.get(HORIZONTAL)) return true;
if(pt1.get(HORIZONTAL) == pt2.get(HORIZONTAL)) {
if(pt1.get(VERTICAL) > pt2.get(VERTICAL)) return true;
}
return false;
}
};
template <typename iT>
static inline void segment_edge(std::vector<std::pair<half_edge, int> >& output_segments,
const half_edge& , segment_id id, iT begin, iT end) {
iT current = begin;
iT next = begin;
++next;
while(next != end) {
output_segments.push_back(std::make_pair(half_edge(*current, *next), id));
current = next;
++next;
}
}
template <typename iT>
static inline void segment_intersections(std::vector<std::pair<half_edge, int> >& output_segments,
std::vector<std::set<Point> >& intersection_points,
iT begin, iT end) {
for(iT iter = begin; iter != end; ++iter) {
//less_point lp;
const half_edge& he = (*iter).first;
//if(lp(he.first, he.second)) {
// //it is the begin event
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(!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;
gtlsort(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());
}
//}
}
}
// //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 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 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));
// }
// }
// }
// //merge sloping element data
// gtlsort(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);
// }
// }
// }
// }
// }
// }
// //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;
// //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>
static inline bool test_validate_scan(stream_type& stdcout) {
std::vector<std::pair<half_edge, segment_id> > input, edges;
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), 0));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 10)), 1));
std::pair<segment_id, segment_id> result;
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail1 " << result.first << " " << result.second << "\n";
return false;
}
input.push_back(std::make_pair(half_edge(Point(0, 5), Point(5, 5)), 2));
edges.clear();
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail2 " << result.first << " " << result.second << "\n";
return false;
}
input.pop_back();
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)), input.size()));
edges.clear();
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail4 " << result.first << " " << result.second << "\n";
return false;
}
input.pop_back();
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)), input.size()));
edges.clear();
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail6 " << result.first << " " << result.second << "\n";
return false;
}
input.pop_back();
for(std::size_t i = 0; i < input.size(); ++i) {
std::swap(input[i].first.first, input[i].first.second);
}
edges.clear();
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail5 2 " << result.first << " " << result.second << "\n";
return false;
}
for(std::size_t i = 0; i < input.size(); ++i) {
input[i].first.first = Point(input[i].first.first.get(HORIZONTAL) * -1,
input[i].first.first.get(VERTICAL) * -1);
input[i].first.second = Point(input[i].first.second.get(HORIZONTAL) * -1,
input[i].first.second.get(VERTICAL) * -1);
}
edges.clear();
validate_scan(edges, input.begin(), input.end());
stdcout << edges.size() << std::endl;
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail5 3 " << result.first << " " << result.second << "\n";
return false;
}
input.clear();
edges.clear();
input.push_back(std::make_pair(half_edge(Point(5, 7), Point(7, 6)), 0));
input.push_back(std::make_pair(half_edge(Point(2, 4), Point(6, 7)), 1));
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail2 1 " << result.first << " " << result.second << "\n";
print(input);
print(edges);
return false;
}
input.clear();
edges.clear();
input.push_back(std::make_pair(half_edge(Point(3, 2), Point(1, 7)), 0));
input.push_back(std::make_pair(half_edge(Point(0, 6), Point(7, 4)), 1));
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail2 2 " << result.first << " " << result.second << "\n";
print(input);
print(edges);
return false;
}
input.clear();
edges.clear();
input.push_back(std::make_pair(half_edge(Point(6, 6), Point(1, 0)), 0));
input.push_back(std::make_pair(half_edge(Point(3, 6), Point(2, 3)), 1));
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail2 3 " << result.first << " " << result.second << "\n";
print(input);
print(edges);
return false;
}
input.clear();
edges.clear();
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(7, 0)), 0));
input.push_back(std::make_pair(half_edge(Point(6, 0), Point(2, 0)), 1));
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail2 4 " << result.first << " " << result.second << "\n";
print(input);
print(edges);
return false;
}
input.clear();
edges.clear();
input.push_back(std::make_pair(half_edge(Point(-17333131 - -17208131, -10316869 - -10191869), Point(0, 0)), 0));
input.push_back(std::make_pair(half_edge(Point(-17291260 - -17208131, -10200000 - -10191869), Point(-17075000 - -17208131, -10200000 - -10191869)), 1));
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail2 5 " << result.first << " " << result.second << "\n";
print(input);
print(edges);
return false;
}
input.clear();
edges.clear();
input.push_back(std::make_pair(half_edge(Point(-17333131, -10316869), Point(-17208131, -10191869)), 0));
input.push_back(std::make_pair(half_edge(Point(-17291260, -10200000), Point(-17075000, -10200000)), 1));
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail2 6 " << result.first << " " << result.second << "\n";
print(input);
print(edges);
return false;
}
input.clear();
edges.clear();
input.push_back(std::make_pair(half_edge(Point(-9850009+9853379, -286971+290340), Point(-12777869+9853379, -3214831+290340)), 0));
input.push_back(std::make_pair(half_edge(Point(-5223510+9853379, -290340+290340), Point(-9858140+9853379, -290340+290340)), 1));
validate_scan(edges, input.begin(), input.end());
print(edges);
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail2 7 " << result.first << " " << result.second << "\n";
print(input);
print(edges);
return false;
}
input.clear();
edges.clear();
input.push_back(std::make_pair(half_edge(Point(-9850009, -286971), Point(-12777869, -3214831)), 0));
input.push_back(std::make_pair(half_edge(Point(-5223510, -290340), Point(-9858140, -290340)), 1));
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail2 8 " << result.first << " " << result.second << "\n";
print(input);
print(edges);
return false;
}
//3 3 2 2: 0; 4 2 0 6: 1; 0 3 6 3: 2; 4 1 5 5: 3;
input.clear();
edges.clear();
input.push_back(std::make_pair(half_edge(Point(3, 3), Point(2, 2)), 0));
input.push_back(std::make_pair(half_edge(Point(4, 2), Point(0, 6)), 1));
input.push_back(std::make_pair(half_edge(Point(0, 3), Point(6, 3)), 2));
input.push_back(std::make_pair(half_edge(Point(4, 1), Point(5, 5)), 3));
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail4 1 " << result.first << " " << result.second << "\n";
print(input);
print(edges);
return false;
}
//5 7 1 3: 0; 4 5 2 1: 1; 2 5 2 1: 2; 4 1 5 3: 3;
input.clear();
edges.clear();
input.push_back(std::make_pair(half_edge(Point(5, 7), Point(1, 3)), 0));
input.push_back(std::make_pair(half_edge(Point(4, 5), Point(2, 1)), 1));
input.push_back(std::make_pair(half_edge(Point(2, 5), Point(2, 1)), 2));
input.push_back(std::make_pair(half_edge(Point(4, 1), Point(5, 3)), 3));
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail4 2 " << result.first << " " << result.second << "\n";
print(input);
print(edges);
return false;
}
//1 0 -4 -1: 0; 0 0 2 -1: 1;
input.clear();
edges.clear();
input.push_back(std::make_pair(half_edge(Point(1, 0), Point(-4, -1)), 0));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(2, -1)), 1));
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail2 5 " << result.first << " " << result.second << "\n";
print(input);
print(edges);
return false;
}
Unit min_c =0;
Unit max_c =0;
for(unsigned int outer = 0; outer < 1000; ++outer) {
input.clear();
for(unsigned int i = 0; i < 4; ++i) {
Unit x1 = rand();
Unit x2 = rand();
Unit y1 = rand();
Unit y2 = rand();
int neg1 = rand() % 2;
if(neg1) x1 *= -1;
int neg2 = rand() % 2;
if(neg2) x2 *= -1;
int neg3 = rand() % 2;
if(neg3) y1 *= -1;
int neg4 = rand() % 2;
if(neg4) y2 *= -1;
if(x1 < min_c) min_c = x1;
if(x2 < min_c) min_c = x2;
if(y1 < min_c) min_c = y1;
if(y2 < min_c) min_c = y2;
if(x1 > max_c) max_c = x1;
if(x2 > max_c) max_c = x2;
if(y1 > max_c) max_c = y1;
if(y2 > max_c) max_c = y2;
Point pt1(x1, y1);
Point pt2(x2, y2);
if(pt1 != pt2)
input.push_back(std::make_pair(half_edge(pt1, pt2), i));
}
edges.clear();
validate_scan(edges, input.begin(), input.end());
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "s fail9 " << outer << ": " << result.first << " " << result.second << "\n";
print(input);
print(edges);
return false;
}
}
return true;
}
//static void print(const std::pair<half_edge, segment_id>& segment) {
//std::cout << segment.first.first << " " << segment.first.second << ": " << segment.second << "; ";
//}
static void print(const std::vector<std::pair<half_edge, segment_id> >& vec) {
for(std::size_t i = 0; i < vec.size(); ++ i) {
// print(vec[i]);
}
//std::cout << std::endl;
}
template <typename stream_type>
static inline bool test_verify_scan(stream_type& stdcout) {
std::vector<std::pair<half_edge, segment_id> > edges;
edges.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), 0));
edges.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 10)), 1));
std::pair<segment_id, segment_id> result;
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "fail1\n";
return false;
}
edges.push_back(std::make_pair(half_edge(Point(0, 5), Point(5, 5)), 2));
if(verify_scan(result, edges.begin(), edges.end())) {
stdcout << "fail2\n";
return false;
}
edges.pop_back();
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)), (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)), (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)), (segment_id)edges.size()));
if(verify_scan(result, edges.begin(), edges.end())) {
stdcout << "fail6 " << result.first << " " << result.second << "\n";
return false;
}
edges.pop_back();
for(std::size_t i = 0; i < edges.size(); ++i) {
std::swap(edges[i].first.first, edges[i].first.second);
}
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "fail5 2 " << result.first << " " << result.second << "\n";
return false;
}
for(std::size_t i = 0; i < edges.size(); ++i) {
edges[i].first.first = Point(edges[i].first.first.get(HORIZONTAL) * -1,
edges[i].first.first.get(VERTICAL) * -1);
edges[i].first.second = Point(edges[i].first.second.get(HORIZONTAL) * -1,
edges[i].first.second.get(VERTICAL) * -1);
}
if(!verify_scan(result, edges.begin(), edges.end())) {
stdcout << "fail5 3 " << result.first << " " << result.second << "\n";
return false;
}
return true;
}
};
//scanline consumes the "flattened" fully intersected line segments produced by
//a pass of line_intersection along with property and count information and performs a
//useful operation like booleans or property merge or connectivity extraction
template <typename Unit, typename property_type, typename keytype = std::set<property_type> >
class scanline : public scanline_base<Unit> {
public:
//definitions
typedef typename scanline_base<Unit>::Point Point;
//the first point is the vertex and and second point establishes the slope of an edge eminating from the vertex
//typedef std::pair<Point, Point> half_edge;
typedef typename scanline_base<Unit>::half_edge half_edge;
//scanline comparator functor
typedef typename scanline_base<Unit>::less_half_edge less_half_edge;
typedef typename scanline_base<Unit>::less_point less_point;
typedef keytype property_set;
//this is the data type used internally to store the combination of property counts at a given location
typedef std::vector<std::pair<property_type, int> > property_map;
//this data structure assocates a property and count to a half edge
typedef std::pair<half_edge, std::pair<property_type, int> > vertex_property;
//this data type is used internally to store the combined property data for a given half edge
typedef std::pair<half_edge, property_map> vertex_data;
//this data type stores the combination of many half edges
typedef std::vector<vertex_property> property_merge_data;
//this data structure stores end points of edges in the scanline
typedef std::set<Point, less_point> end_point_queue;
//this is the output data type that is created by the scanline before it is post processed based on content of property sets
typedef std::pair<half_edge, std::pair<property_set, property_set> > half_edge_property;
//this is the scanline data structure
typedef std::map<half_edge, property_map, less_half_edge> scanline_type;
typedef std::pair<half_edge, property_map> scanline_element;
typedef typename scanline_type::iterator iterator;
typedef typename scanline_type::const_iterator const_iterator;
//data
scanline_type scan_data_;
std::vector<iterator> removal_set_; //edges to be removed at the current scanline stop
std::vector<scanline_element> insertion_set_; //edge to be inserted after current scanline stop
end_point_queue end_point_queue_;
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), evalAtXforYPack_() {
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_(),
x_((std::numeric_limits<Unit>::max)()), y_((std::numeric_limits<Unit>::max)()), just_before_(false), evalAtXforYPack_() {
(*this) = that; }
inline scanline& operator=(const scanline& that) {
x_ = that.x_;
y_ = that.y_;
just_before_ = that.just_before_;
end_point_queue_ = that.end_point_queue_;
//I cannot simply copy that.scanline_type to this scanline_type becuase the functor store pointers to other members!
less_half_edge lessElm(&x_, &just_before_);
scan_data_ = scanline_type(lessElm);
scan_data_.insert(that.scan_data_.begin(), that.scan_data_.end());
return *this;
}
template <typename result_type, typename result_functor>
void write_out(result_type& result, result_functor rf, const half_edge& he,
const property_map& pm_left, const property_map& pm_right) {
//std::cout << "write out ";
//std::cout << he.first << ", " << he.second << std::endl;
property_set ps_left, ps_right;
set_unique_property(ps_left, pm_left);
set_unique_property(ps_right, pm_right);
if(ps_left != ps_right) {
//std::cout << "!equivalent\n";
rf(result, he, ps_left, ps_right);
}
}
template <typename result_type, typename result_functor, typename iT>
iT handle_input_events(result_type& result, result_functor rf, iT begin, iT end) {
typedef typename high_precision_type<Unit>::type high_precision;
//for each event
property_map vertical_properties_above;
property_map vertical_properties_below;
half_edge vertical_edge_above;
half_edge vertical_edge_below;
std::vector<scanline_element> insertion_elements;
//current_iter should increase monotonically toward end as we process scanline stop
iterator current_iter = scan_data_.begin();
just_before_ = true;
Unit y = (std::numeric_limits<Unit>::min)();
bool first_iteration = true;
//we want to return from inside the loop when we hit end or new x
#ifdef BOOST_POLYGON_MSVC
#pragma warning( disable: 4127 )
#endif
while(true) {
if(begin == end || (!first_iteration && ((*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_, y);
//grab the properties coming in from below
property_map properties_below;
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(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);
else
e2.set(VERTICAL, e2.get(VERTICAL) - 1);
half_edge vhe(pt, e2);
current_iter = scan_data_.lower_bound(vhe);
}
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(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(scanline_base<Unit>::on_above_or_below(Point(x_, y), (*current_iter).first) != 1) {
properties_below.clear();
} else {
properties_below = (*current_iter).second;
//move back up to y or one past y
++current_iter;
}
}
}
std::vector<iterator> edges_from_left;
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) {
scanline_base<Unit>::on_above_or_below(Point(x_, y), (*current_iter).first) == 0) {
//removal_set_.push_back(current_iter);
++current_iter;
}
//merge vertical count with count from below
if(!vertical_properties_below.empty()) {
merge_property_maps(vertical_properties_below, properties_below);
//write out vertical edge
write_out(result, rf, vertical_edge_below, properties_below, vertical_properties_below);
} else {
merge_property_maps(vertical_properties_below, properties_below);
}
//iteratively add intertion element counts to count from below
//and write them to insertion set
for(std::size_t i = 0; i < insertion_elements.size(); ++i) {
if(i == 0) {
merge_property_maps(insertion_elements[i].second, vertical_properties_below);
write_out(result, rf, insertion_elements[i].first, insertion_elements[i].second, vertical_properties_below);
} else {
merge_property_maps(insertion_elements[i].second, insertion_elements[i-1].second);
write_out(result, rf, insertion_elements[i].first, insertion_elements[i].second, insertion_elements[i-1].second);
}
insertion_set_.push_back(insertion_elements[i]);
}
if((begin == end || (*begin).first.first.get(HORIZONTAL) != x_)) {
if(vertical_properties_above.empty()) {
return begin;
} else {
y = vertical_edge_above.second.get(VERTICAL);
vertical_properties_below.clear();
vertical_properties_above.swap(vertical_properties_below);
vertical_edge_below = vertical_edge_above;
insertion_elements.clear();
continue;
}
}
vertical_properties_below.clear();
vertical_properties_above.swap(vertical_properties_below);
vertical_edge_below = vertical_edge_above;
insertion_elements.clear();
}
if(begin != end) {
const vertex_property& vp = *begin;
const half_edge& he = vp.first;
y = he.first.get(VERTICAL);
first_iteration = false;
if(! vertical_properties_below.empty() &&
vertical_edge_below.second.get(VERTICAL) < y) {
y = vertical_edge_below.second.get(VERTICAL);
continue;
}
if(scanline_base<Unit>::is_vertical(he)) {
update_property_map(vertical_properties_above, vp.second);
vertical_edge_above = he;
} else {
if(insertion_elements.empty() ||
insertion_elements.back().first != he) {
insertion_elements.push_back(scanline_element(he, property_map()));
}
update_property_map(insertion_elements.back().second, vp.second);
}
++begin;
}
}
#ifdef BOOST_POLYGON_MSVC
#pragma warning( default: 4127 )
#endif
}
inline void erase_end_events(typename end_point_queue::iterator epqi) {
end_point_queue_.erase(end_point_queue_.begin(), epqi);
for(typename std::vector<iterator>::iterator retire_itr = removal_set_.begin();
retire_itr != removal_set_.end(); ++retire_itr) {
scan_data_.erase(*retire_itr);
}
removal_set_.clear();
}
inline void remove_retired_edges_from_scanline() {
just_before_ = true;
typename end_point_queue::iterator epqi = end_point_queue_.begin();
Unit current_x = x_;
Unit previous_x = x_;
while(epqi != end_point_queue_.end() &&
(*epqi).get(HORIZONTAL) <= current_x) {
x_ = (*epqi).get(HORIZONTAL);
if(x_ != previous_x) erase_end_events(epqi);
previous_x = x_;
//lookup elements
Point e2(*epqi);
if(e2.get(VERTICAL) != (std::numeric_limits<Unit>::max)())
e2.set(VERTICAL, e2.get(VERTICAL) + 1);
else
e2.set(VERTICAL, e2.get(VERTICAL) - 1);
half_edge vhe_e(*epqi, e2);
iterator current_iter = scan_data_.lower_bound(vhe_e);
while(current_iter != scan_data_.end() && (*current_iter).first.second == (*epqi)) {
//evalAtXforY(x_, (*current_iter).first.first, (*current_iter).first.second) == (*epqi).get(VERTICAL)) {
removal_set_.push_back(current_iter);
++current_iter;
}
++epqi;
}
x_ = current_x;
erase_end_events(epqi);
}
inline void insert_new_edges_into_scanline() {
just_before_ = false;
for(typename std::vector<scanline_element>::iterator insert_itr = insertion_set_.begin();
insert_itr != insertion_set_.end(); ++insert_itr) {
scan_data_.insert(*insert_itr);
end_point_queue_.insert((*insert_itr).first.second);
}
insertion_set_.clear();
}
//iterator over range of vertex property elements and call result functor
//passing edge to be output, the merged data on both sides and the result
template <typename result_type, typename result_functor, typename iT>
void scan(result_type& result, result_functor rf, iT begin, iT end) {
while(begin != end) {
x_ = (*begin).first.first.get(HORIZONTAL); //update scanline stop location
//print_scanline();
--x_;
remove_retired_edges_from_scanline();
++x_;
begin = handle_input_events(result, rf, begin, end);
remove_retired_edges_from_scanline();
//print_scanline();
insert_new_edges_into_scanline();
}
//print_scanline();
x_ = (std::numeric_limits<Unit>::max)();
remove_retired_edges_from_scanline();
}
//inline void print_scanline() {
// std::cout << "scanline at " << x_ << ": ";
// for(iterator itr = scan_data_.begin(); itr != scan_data_.end(); ++itr) {
// const scanline_element& se = *itr;
// const half_edge& he = se.first;
// const property_map& mp = se.second;
// std::cout << he.first << ", " << he.second << " ( ";
// for(std::size_t i = 0; i < mp.size(); ++i) {
// std::cout << mp[i].first << ":" << mp[i].second << " ";
// } std::cout << ") ";
// } std::cout << std::endl;
//}
static inline void merge_property_maps(property_map& mp, const property_map& mp2) {
property_map newmp;
newmp.reserve(mp.size() + mp2.size());
unsigned int i = 0;
unsigned int j = 0;
while(i != mp.size() && j != mp2.size()) {
if(mp[i].first < mp2[j].first) {
newmp.push_back(mp[i]);
++i;
} else if(mp[i].first > mp2[j].first) {
newmp.push_back(mp2[j]);
++j;
} else {
int count = mp[i].second;
count += mp2[j].second;
if(count) {
newmp.push_back(mp[i]);
newmp.back().second = count;
}
++i;
++j;
}
}
while(i != mp.size()) {
newmp.push_back(mp[i]);
++i;
}
while(j != mp2.size()) {
newmp.push_back(mp2[j]);
++j;
}
mp.swap(newmp);
}
static inline void update_property_map(property_map& mp, const std::pair<property_type, int>& prop_data) {
property_map newmp;
newmp.reserve(mp.size() +1);
bool consumed = false;
for(std::size_t i = 0; i < mp.size(); ++i) {
if(!consumed && prop_data.first == mp[i].first) {
consumed = true;
int count = prop_data.second + mp[i].second;
if(count)
newmp.push_back(std::make_pair(prop_data.first, count));
} else if(!consumed && prop_data.first < mp[i].first) {
consumed = true;
newmp.push_back(prop_data);
newmp.push_back(mp[i]);
} else {
newmp.push_back(mp[i]);
}
}
if(!consumed) newmp.push_back(prop_data);
mp.swap(newmp);
}
static inline void set_unique_property(property_set& unqiue_property, const property_map& property) {
unqiue_property.clear();
for(typename property_map::const_iterator itr = property.begin(); itr != property.end(); ++itr) {
if((*itr).second > 0)
unqiue_property.insert(unqiue_property.end(), (*itr).first);
}
}
static inline bool common_vertex(const half_edge& he1, const half_edge& he2) {
return he1.first == he2.first ||
he1.first == he2.second ||
he1.second == he2.first ||
he1.second == he2.second;
}
typedef typename scanline_base<Unit>::vertex_half_edge vertex_half_edge;
template <typename iT>
static inline void convert_segments_to_vertex_half_edges(std::vector<vertex_half_edge>& output, iT begin, iT end) {
for( ; begin != end; ++begin) {
const half_edge& he = (*begin).first;
int count = (*begin).second;
output.push_back(vertex_half_edge(he.first, he.second, count));
output.push_back(vertex_half_edge(he.second, he.first, -count));
}
gtlsort(output.begin(), output.end());
}
class test_functor {
public:
inline test_functor() {}
inline void operator()(std::vector<std::pair<half_edge, std::pair<property_set, property_set> > >& result,
const half_edge& he, const property_set& ps_left, const property_set& ps_right) {
result.push_back(std::make_pair(he, std::make_pair(ps_left, ps_right)));
}
};
template <typename stream_type>
static inline bool test_scanline(stream_type& stdcout) {
std::vector<std::pair<half_edge, std::pair<property_set, property_set> > > result;
std::vector<std::pair<half_edge, std::pair<property_type, int> > > input;
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 0)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 10), Point(10, 10)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(10, 0), Point(10, 10)), std::make_pair(0, -1)));
scanline sl;
test_functor tf;
sl.scan(result, tf, input.begin(), input.end());
stdcout << "scanned\n";
for(std::size_t i = 0; i < result.size(); ++i) {
stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
} stdcout << std::endl;
input.clear();
result.clear();
input.push_back(std::make_pair(half_edge(Point(-1, -1), Point(10, 0)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(-1, -1), Point(0, 10)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(0, 10), Point(11, 11)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(10, 0), Point(11, 11)), std::make_pair(0, 1)));
scanline sl2;
sl2.scan(result, tf, input.begin(), input.end());
stdcout << "scanned\n";
for(std::size_t i = 0; i < result.size(); ++i) {
stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
} stdcout << std::endl;
input.clear();
result.clear();
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 0)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 10), Point(10, 10)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(1, 1), Point(8, 2)), std::make_pair(1, 1)));
input.push_back(std::make_pair(half_edge(Point(1, 1), Point(2, 8)), std::make_pair(1, -1)));
input.push_back(std::make_pair(half_edge(Point(2, 8), Point(9, 9)), std::make_pair(1, -1)));
input.push_back(std::make_pair(half_edge(Point(8, 2), Point(9, 9)), std::make_pair(1, 1)));
input.push_back(std::make_pair(half_edge(Point(10, 0), Point(10, 10)), std::make_pair(0, -1)));
scanline sl3;
sl3.scan(result, tf, input.begin(), input.end());
stdcout << "scanned\n";
for(std::size_t i = 0; i < result.size(); ++i) {
stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
} stdcout << std::endl;
input.clear();
result.clear();
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 0)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 10), Point(10, 10)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(1, 1), Point(8, 2)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(1, 1), Point(2, 8)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(2, 8), Point(9, 9)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(8, 2), Point(9, 9)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(10, 0), Point(10, 10)), std::make_pair(0, -1)));
scanline sl4;
sl4.scan(result, tf, input.begin(), input.end());
stdcout << "scanned\n";
for(std::size_t i = 0; i < result.size(); ++i) {
stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
} stdcout << std::endl;
input.clear();
result.clear();
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 0)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(9, 1)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(1, 9)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 10), Point(10, 10)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(1, 9), Point(10, 10)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(9, 1), Point(10, 10)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(10, 0), Point(10, 10)), std::make_pair(0, -1)));
scanline sl5;
sl5.scan(result, tf, input.begin(), input.end());
stdcout << "scanned\n";
for(std::size_t i = 0; i < result.size(); ++i) {
stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
} stdcout << std::endl;
input.clear();
result.clear();
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 0)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(9, 1)), std::make_pair(1, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(1, 9)), std::make_pair(1, -1)));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 10), Point(10, 10)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(1, 9), Point(10, 10)), std::make_pair(1, -1)));
input.push_back(std::make_pair(half_edge(Point(9, 1), Point(10, 10)), std::make_pair(1, 1)));
input.push_back(std::make_pair(half_edge(Point(10, 0), Point(10, 10)), std::make_pair(0, -1)));
scanline sl6;
sl6.scan(result, tf, input.begin(), input.end());
stdcout << "scanned\n";
for(std::size_t i = 0; i < result.size(); ++i) {
stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
} stdcout << std::endl;
input.clear();
result.clear();
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(10, 0)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(9, 1)), std::make_pair(1, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(1, 9)), std::make_pair(1, -1)));
input.push_back(std::make_pair(half_edge(Point(0, 0), Point(0, 10)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 10), Point(10, 10)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(0, 20), Point(10, 20)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 20), Point(9, 21)), std::make_pair(1, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 20), Point(1, 29)), std::make_pair(1, -1)));
input.push_back(std::make_pair(half_edge(Point(0, 20), Point(0, 30)), std::make_pair(0, 1)));
input.push_back(std::make_pair(half_edge(Point(0, 30), Point(10, 30)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(1, 9), Point(10, 10)), std::make_pair(1, -1)));
input.push_back(std::make_pair(half_edge(Point(1, 29), Point(10, 30)), std::make_pair(1, -1)));
input.push_back(std::make_pair(half_edge(Point(9, 1), Point(10, 10)), std::make_pair(1, 1)));
input.push_back(std::make_pair(half_edge(Point(9, 21), Point(10, 30)), std::make_pair(1, 1)));
input.push_back(std::make_pair(half_edge(Point(10, 20), Point(10, 30)), std::make_pair(0, -1)));
input.push_back(std::make_pair(half_edge(Point(10, 20), Point(10, 30)), std::make_pair(0, -1)));
scanline sl7;
sl7.scan(result, tf, input.begin(), input.end());
stdcout << "scanned\n";
for(std::size_t i = 0; i < result.size(); ++i) {
stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
} stdcout << std::endl;
input.clear();
result.clear();
input.push_back(std::make_pair(half_edge(Point(-1, -1), Point(10, 0)), std::make_pair(0, 1))); //a
input.push_back(std::make_pair(half_edge(Point(-1, -1), Point(0, 10)), std::make_pair(0, -1))); //a
input.push_back(std::make_pair(half_edge(Point(0, 10), Point(11, 11)), std::make_pair(0, -1))); //a
input.push_back(std::make_pair(half_edge(Point(10, 0), Point(20, 0)), std::make_pair(0, 1))); //b
input.push_back(std::make_pair(half_edge(Point(10, 0), Point(11, 11)), std::make_pair(0, -1))); //b
input.push_back(std::make_pair(half_edge(Point(10, 0), Point(11, 11)), std::make_pair(0, 1))); //a
input.push_back(std::make_pair(half_edge(Point(11, 11), Point(20, 10)), std::make_pair(0, -1))); //b
input.push_back(std::make_pair(half_edge(Point(20, 0), Point(30, 0)), std::make_pair(0, 1))); //c
input.push_back(std::make_pair(half_edge(Point(20, 0), Point(20, 10)), std::make_pair(0, -1))); //b
input.push_back(std::make_pair(half_edge(Point(20, 0), Point(20, 10)), std::make_pair(0, 1))); //c
input.push_back(std::make_pair(half_edge(Point(20, 10), Point(30, 10)), std::make_pair(0, -1))); //c
input.push_back(std::make_pair(half_edge(Point(30, 0), Point(30, 10)), std::make_pair(0, -1))); //c
scanline sl8;
sl8.scan(result, tf, input.begin(), input.end());
stdcout << "scanned\n";
for(std::size_t i = 0; i < result.size(); ++i) {
stdcout << result[i].first.first << ", " << result[i].first.second << "; ";
} stdcout << std::endl;
return true;
}
};
template <typename Unit>
class merge_output_functor {
public:
typedef typename scanline_base<Unit>::half_edge half_edge;
merge_output_functor() {}
template <typename result_type, typename key_type>
void operator()(result_type& result, const half_edge& edge, const key_type& left, const key_type& right) {
typename std::pair<half_edge, int> elem;
elem.first = edge;
elem.second = 1;
if(edge.second < edge.first) elem.second *= -1;
if(scanline_base<Unit>::is_vertical(edge)) elem.second *= -1;
if(!left.empty())
result[left].insert_clean(elem);
elem.second *= -1;
if(!right.empty())
result[right].insert_clean(elem);
}
};
template <typename Unit, typename property_type, typename key_type = std::set<property_type>,
typename output_functor_type = merge_output_functor<Unit> >
class property_merge : public scanline_base<Unit> {
protected:
typedef typename scanline_base<Unit>::Point Point;
//the first point is the vertex and and second point establishes the slope of an edge eminating from the vertex
//typedef std::pair<Point, Point> half_edge;
typedef typename scanline_base<Unit>::half_edge half_edge;
//scanline comparator functor
typedef typename scanline_base<Unit>::less_half_edge less_half_edge;
typedef typename scanline_base<Unit>::less_point less_point;
//this data structure assocates a property and count to a half edge
typedef std::pair<half_edge, std::pair<property_type, int> > vertex_property;
//this data type stores the combination of many half edges
typedef std::vector<vertex_property> property_merge_data;
//this is the data type used internally to store the combination of property counts at a given location
typedef std::vector<std::pair<property_type, int> > property_map;
//this data type is used internally to store the combined property data for a given half edge
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() : pack_() {}
less_vertex_data(typename scanline_base<Unit>::evalAtXforYPack* pack) : pack_(pack) {}
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;
Unit x = lvalue.first.first.get(HORIZONTAL);
int just_before_ = 0;
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(&evalAtXforYPack_);
gtlsort(pmd.begin(), pmd.end(), lvd);
}
public:
inline property_merge_data& get_property_merge_data() { return pmd; }
inline property_merge() : pmd(), evalAtXforYPack_() {}
inline property_merge(const property_merge& pm) : pmd(pm.pmd), evalAtXforYPack_(pm.evalAtXforYPack_) {}
inline property_merge& operator=(const property_merge& pm) { pmd = pm.pmd; return *this; }
template <typename polygon_type>
void insert(const polygon_type& polygon_object, const property_type& property_value, bool is_hole = false) {
insert(polygon_object, property_value, is_hole, typename geometry_concept<polygon_type>::type());
}
//result type should be std::map<std::set<property_type>, polygon_set_type>
//or std::map<std::vector<property_type>, polygon_set_type>
template <typename result_type>
void merge(result_type& result) {
if(pmd.empty()) return;
//intersect data
property_merge_data tmp_pmd;
line_intersection<Unit>::validate_scan(tmp_pmd, pmd.begin(), pmd.end());
pmd.swap(tmp_pmd);
sort_property_merge_data();
scanline<Unit, property_type, key_type> sl;
output_functor_type mof;
sl.scan(result, mof, pmd.begin(), pmd.end());
}
inline bool verify1() {
std::pair<int, int> offenders;
std::vector<std::pair<half_edge, int> > lines;
int count = 0;
for(std::size_t i = 0; i < pmd.size(); ++i) {
lines.push_back(std::make_pair(pmd[i].first, count++));
}
if(!line_intersection<Unit>::verify_scan(offenders, lines.begin(), lines.end())) {
//stdcout << "Intersection failed!\n";
//stdcout << offenders.first << " " << offenders.second << std::endl;
return false;
}
std::vector<Point> pts;
for(std::size_t i = 0; i < lines.size(); ++i) {
pts.push_back(lines[i].first.first);
pts.push_back(lines[i].first.second);
}
gtlsort(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";
return false;
}
}
return true;
}
void clear() {*this = property_merge();}
protected:
template <typename polygon_type>
void insert(const polygon_type& polygon_object, const property_type& property_value, bool is_hole,
polygon_concept ) {
bool first_iteration = true;
bool second_iteration = true;
Point first_point;
Point second_point;
Point previous_previous_point;
Point previous_point;
Point current_point;
direction_1d winding_dir = winding(polygon_object);
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(second_iteration) {
if(previous_point != current_point) {
second_iteration = false;
previous_previous_point = previous_point;
second_point = previous_point = current_point;
}
} else {
if(previous_point != current_point) {
create_vertex(pmd, previous_point, current_point, winding_dir,
is_hole, property_value);
previous_previous_point = previous_point;
previous_point = current_point;
}
}
}
current_point = first_point;
if(!first_iteration && !second_iteration) {
if(previous_point != current_point) {
create_vertex(pmd, previous_point, current_point, winding_dir,
is_hole, property_value);
previous_previous_point = previous_point;
previous_point = current_point;
}
current_point = second_point;
create_vertex(pmd, previous_point, current_point, winding_dir,
is_hole, property_value);
previous_previous_point = previous_point;
previous_point = current_point;
}
}
template <typename polygon_with_holes_type>
void insert(const polygon_with_holes_type& polygon_with_holes_object, const property_type& property_value, bool is_hole,
polygon_with_holes_concept tag) {
insert(polygon_with_holes_object, property_value, is_hole, polygon_concept());
for(typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type itr =
begin_holes(polygon_with_holes_object);
itr != end_holes(polygon_with_holes_object); ++itr) {
insert(*itr, property_value, !is_hole, polygon_concept());
}
}
template <typename rectangle_type>
void insert(const rectangle_type& rectangle_object, const property_type& property_value, bool is_hole,
rectangle_concept ) {
polygon_90_data<Unit> poly;
assign(poly, rectangle_object);
insert(poly, property_value, is_hole, polygon_concept());
}
public: //change to private when done testing
static inline void create_vertex(property_merge_data& pmd,
const Point& current_point,
const Point& next_point,
direction_1d winding,
bool is_hole, const property_type& property) {
if(current_point == next_point) return;
vertex_property current_vertex;
current_vertex.first.first = current_point;
current_vertex.first.second = next_point;
current_vertex.second.first = property;
int multiplier = 1;
if(winding == CLOCKWISE)
multiplier = -1;
if(is_hole)
multiplier *= -1;
if(current_point < next_point) {
multiplier *= -1;
std::swap(current_vertex.first.first, current_vertex.first.second);
}
current_vertex.second.second = multiplier * (euclidean_distance(next_point, current_point, HORIZONTAL) == 0 ? -1: 1);
pmd.push_back(current_vertex);
//current_vertex.first.second = previous_point;
//current_vertex.second.second *= -1;
//pmd.push_back(current_vertex);
}
static inline void sort_vertex_half_edges(vertex_data& vertex) {
less_half_edge_pair lessF(vertex.first);
gtlsort(vertex.second.begin(), vertex.second.end(), lessF);
}
class less_half_edge_pair {
private:
Point pt_;
public:
less_half_edge_pair(const Point& pt) : pt_(pt) {}
bool operator()(const half_edge& e1, const half_edge& e2) {
const Point& pt1 = e1.first;
const Point& pt2 = e2.first;
if(get(pt1, HORIZONTAL) ==
get(pt_, HORIZONTAL)) {
//vertical edge is always largest
return false;
}
if(get(pt2, HORIZONTAL) ==
get(pt_, HORIZONTAL)) {
//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 scanline_base<Unit>::less_slope(get(pt_, HORIZONTAL),
get(pt_, VERTICAL), pt1, pt2);
}
};
public:
//test functions
template <typename stream_type>
static stream_type& print (stream_type& o, const property_map& c)
{
o << "count: {";
for(typename property_map::const_iterator itr = c.begin(); itr != c.end(); ++itr) {
o << ((*itr).first) << ":" << ((*itr).second) << " ";
}
return o << "} ";
}
template <typename stream_type>
static stream_type& print (stream_type& o, const half_edge& he)
{
o << "half edge: (";
o << (he.first);
return o << ", " << (he.second) << ") ";
}
template <typename stream_type>
static stream_type& print (stream_type& o, const vertex_property& c)
{
o << "vertex property: {";
print(o, c.first);
o << ", " << c.second.first << ":" << c.second.second << " ";
return o;
}
template <typename stream_type>
static stream_type& print (stream_type& o, const std::vector<vertex_property>& hev)
{
o << "vertex properties: {";
for(std::size_t i = 0; i < hev.size(); ++i) {
print(o, (hev[i])) << " ";
}
return o << "} ";
}
template <typename stream_type>
static stream_type& print (stream_type& o, const std::vector<half_edge>& hev)
{
o << "half edges: {";
for(std::size_t i = 0; i < hev.size(); ++i) {
print(o, (hev[i])) << " ";
}
return o << "} ";
}
template <typename stream_type>
static stream_type& print (stream_type& o, const vertex_data& v)
{
return print(o << "vertex: <" << (v.first) << ", ", (v.second)) << "> ";
}
template <typename stream_type>
static stream_type& print (stream_type& o, const std::vector<vertex_data>& vv)
{
o << "vertices: {";
for(std::size_t i = 0; i < vv.size(); ++i) {
print(o, (vv[i])) << " ";
}
return o << "} ";
}
template <typename stream_type>
static inline bool test_insertion(stream_type& stdcout) {
property_merge si;
rectangle_data<Unit> rect;
xl(rect, 0);
yl(rect, 1);
xh(rect, 10);
yh(rect, 11);
si.insert(rect, 333);
print(stdcout, si.pmd) << std::endl;
Point pts[4] = {Point(0, 0), Point(10,-3), Point(13, 8), Point(0, 0) };
polygon_data<Unit> poly;
property_merge si2;
poly.set(pts, pts+3);
si2.insert(poly, 444);
si2.sort_property_merge_data();
print(stdcout, si2.pmd) << std::endl;
property_merge si3;
poly.set(pts, pts+4);
si3.insert(poly, 444);
si3.sort_property_merge_data();
stdcout << (si2.pmd == si3.pmd) << std::endl;
std::reverse(pts, pts+4);
property_merge si4;
poly.set(pts, pts+4);
si4.insert(poly, 444);
si4.sort_property_merge_data();
print(stdcout, si4.pmd) << std::endl;
stdcout << (si2.pmd == si4.pmd) << std::endl;
std::reverse(pts, pts+3);
property_merge si5;
poly.set(pts, pts+4);
si5.insert(poly, 444);
si5.sort_property_merge_data();
stdcout << (si2.pmd == si5.pmd) << std::endl;
return true;
}
template <typename stream_type>
static inline bool test_merge(stream_type& stdcout) {
property_merge si;
rectangle_data<Unit> rect;
xl(rect, 0);
yl(rect, 1);
xh(rect, 10);
yh(rect, 11);
si.insert(rect, 333);
std::map<std::set<property_type>, polygon_set_data<Unit> > result;
si.merge(result);
print(stdcout, si.pmd) << std::endl;
polygon_set_data<Unit> psd = (*(result.begin())).second;
std::vector<polygon_data<Unit> > polys;
psd.get(polys);
if(polys.size() != 1) {
stdcout << "fail merge 1\n";
return false;
}
stdcout << (polys[0]) << std::endl;
si.clear();
std::vector<Point> pts;
pts.push_back(Point(0, 0));
pts.push_back(Point(10, -10));
pts.push_back(Point(10, 10));
polygon_data<Unit> poly;
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
pts.clear();
pts.push_back(Point(5, 0));
pts.push_back(Point(-5, -10));
pts.push_back(Point(-5, 10));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
result.clear();
si.merge(result);
print(stdcout, si.pmd) << std::endl;
psd = (*(result.begin())).second;
stdcout << psd << std::endl;
polys.clear();
psd.get(polys);
if(polys.size() != 1) {
stdcout << "fail merge 2\n";
return false;
}
//Polygon { -4 -1, 3 3, -2 3 }
//Polygon { 0 -4, -4 -2, -2 1 }
si.clear();
pts.clear();
pts.push_back(Point(-4, -1));
pts.push_back(Point(3, 3));
pts.push_back(Point(-2, 3));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
pts.clear();
pts.push_back(Point(0, -4));
pts.push_back(Point(-4, -2));
pts.push_back(Point(-2, 1));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
result.clear();
si.merge(result);
print(stdcout, si.pmd) << std::endl;
psd = (*(result.begin())).second;
stdcout << psd << std::endl;
polys.clear();
psd.get(polys);
if(polys.size() != 1) {
stdcout << "fail merge 3\n";
return false;
}
stdcout << "Polygon { -2 2, -2 2, 1 4 } \n";
stdcout << "Polygon { 2 4, 2 -4, -3 1 } \n";
si.clear();
pts.clear();
pts.push_back(Point(-2, 2));
pts.push_back(Point(-2, 2));
pts.push_back(Point(1, 4));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
pts.clear();
pts.push_back(Point(2, 4));
pts.push_back(Point(2, -4));
pts.push_back(Point(-3, 1));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
result.clear();
si.merge(result);
print(stdcout, si.pmd) << std::endl;
psd = (*(result.begin())).second;
stdcout << psd << std::endl;
polys.clear();
psd.get(polys);
if(polys.size() != 1) {
stdcout << "fail merge 4\n";
return false;
}
stdcout << (polys[0]) << std::endl;
stdcout << "Polygon { -4 0, -2 -3, 3 -4 } \n";
stdcout << "Polygon { -1 1, 1 -2, -4 -3 } \n";
si.clear();
pts.clear();
pts.push_back(Point(-4, 0));
pts.push_back(Point(-2, -3));
pts.push_back(Point(3, -4));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
pts.clear();
pts.push_back(Point(-1, 1));
pts.push_back(Point(1, -2));
pts.push_back(Point(-4, -3));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
result.clear();
si.merge(result);
print(stdcout, si.pmd) << std::endl;
psd = (*(result.begin())).second;
stdcout << psd << std::endl;
polys.clear();
psd.get(polys);
if(polys.size() != 1) {
stdcout << "fail merge 5\n";
return false;
}
stdcout << "Polygon { 2 2, -2 0, 0 1 } \n";
stdcout << "Polygon { 4 -2, 3 -1, 2 3 } \n";
si.clear();
pts.clear();
pts.push_back(Point(2, 2));
pts.push_back(Point(-2, 0));
pts.push_back(Point(0, 1));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
pts.clear();
pts.push_back(Point(4, -2));
pts.push_back(Point(3, -1));
pts.push_back(Point(2, 3));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
result.clear();
si.merge(result);
print(stdcout, si.pmd) << std::endl;
if(!result.empty()) {
psd = (*(result.begin())).second;
stdcout << psd << std::endl;
polys.clear();
psd.get(polys);
if(polys.size() != 1) {
stdcout << "fail merge 6\n";
return false;
}
stdcout << (polys[0]) << std::endl;
}
stdcout << "Polygon { 0 2, 3 -1, 4 1 } \n";
stdcout << "Polygon { -4 3, 3 3, 4 2 } \n";
si.clear();
pts.clear();
pts.push_back(Point(0, 2));
pts.push_back(Point(3, -1));
pts.push_back(Point(4, 1));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
pts.clear();
pts.push_back(Point(-4, 3));
pts.push_back(Point(3, 3));
pts.push_back(Point(4, 2));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
result.clear();
si.merge(result);
print(stdcout, si.pmd) << std::endl;
if(!result.empty()) {
psd = (*(result.begin())).second;
stdcout << psd << std::endl;
polys.clear();
psd.get(polys);
if(polys.size() == 0) {
stdcout << "fail merge 7\n";
return false;
}
stdcout << (polys[0]) << std::endl;
}
stdcout << "Polygon { 1 -2, -1 4, 3 -2 } \n";
stdcout << "Polygon { 0 -3, 3 1, -3 -4 } \n";
si.clear();
pts.clear();
pts.push_back(Point(1, -2));
pts.push_back(Point(-1, 4));
pts.push_back(Point(3, -2));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
pts.clear();
pts.push_back(Point(0, -3));
pts.push_back(Point(3, 1));
pts.push_back(Point(-3, -4));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
result.clear();
si.merge(result);
print(stdcout, si.pmd) << std::endl;
if(!result.empty()) {
psd = (*(result.begin())).second;
stdcout << psd << std::endl;
polys.clear();
psd.get(polys);
if(polys.size() == 0) {
stdcout << "fail merge 8\n";
return false;
}
stdcout << (polys[0]) << std::endl;
}
stdcout << "Polygon { 2 2, 3 0, -3 4 } \n";
stdcout << "Polygon { -2 -2, 0 0, -1 -1 } \n";
si.clear();
pts.clear();
pts.push_back(Point(2, 2));
pts.push_back(Point(3, 0));
pts.push_back(Point(-3, 4));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
pts.clear();
pts.push_back(Point(-2, -2));
pts.push_back(Point(0, 0));
pts.push_back(Point(-1, -1));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
result.clear();
si.merge(result);
print(stdcout, si.pmd) << std::endl;
if(!result.empty()) {
psd = (*(result.begin())).second;
stdcout << psd << std::endl;
polys.clear();
psd.get(polys);
if(polys.size() == 0) {
stdcout << "fail merge 9\n";
return false;
}
stdcout << (polys[0]) << std::endl;
}
si.clear();
pts.clear();
//5624841,17616200,75000,9125000
//pts.push_back(Point(5624841,75000));
//pts.push_back(Point(5624841,9125000));
//pts.push_back(Point(17616200,9125000));
//pts.push_back(Point(17616200,75000));
pts.push_back(Point(12262940, 6652520 )); pts.push_back(Point(12125750, 6652520 )); pts.push_back(Point(12121272, 6652961 )); pts.push_back(Point(12112981, 6656396 )); pts.push_back(Point(12106636, 6662741 )); pts.push_back(Point(12103201, 6671032 )); pts.push_back(Point(12103201, 6680007 )); pts.push_back(Point(12106636, 6688298 ));
pts.push_back(Point(12109500, 6691780 )); pts.push_back(Point(12748600, 7330890 )); pts.push_back(Point(15762600, 7330890 )); pts.push_back(Point(15904620, 7472900 )); pts.push_back(Point(15909200, 7473030 )); pts.push_back(Point(15935830, 7476006 )); pts.push_back(Point(15992796, 7499602 )); pts.push_back(Point(16036397, 7543203 ));
pts.push_back(Point(16059993, 7600169 )); pts.push_back(Point(16059993, 7661830 )); pts.push_back(Point(16036397, 7718796 )); pts.push_back(Point(15992796, 7762397 )); pts.push_back(Point(15935830, 7785993 )); pts.push_back(Point(15874169, 7785993 )); pts.push_back(Point(15817203, 7762397 )); pts.push_back(Point(15773602, 7718796 ));
pts.push_back(Point(15750006, 7661830 )); pts.push_back(Point(15747030, 7635200 )); pts.push_back(Point(15746900, 7630620 )); pts.push_back(Point(15670220, 7553930 )); pts.push_back(Point(14872950, 7553930 )); pts.push_back(Point(14872950, 7626170 ));
pts.push_back(Point(14869973, 7661280 )); pts.push_back(Point(14846377, 7718246 )); pts.push_back(Point(14802776, 7761847 )); pts.push_back(Point(14745810, 7785443 )); pts.push_back(Point(14684149, 7785443 )); pts.push_back(Point(14627183, 7761847 )); pts.push_back(Point(14583582, 7718246 ));
pts.push_back(Point(14559986, 7661280 )); pts.push_back(Point(14557070, 7636660 )); pts.push_back(Point(14556670, 7625570 )); pts.push_back(Point(13703330, 7625570 )); pts.push_back(Point(13702930, 7636660 )); pts.push_back(Point(13699993, 7661830 )); pts.push_back(Point(13676397, 7718796 ));
pts.push_back(Point(13632796, 7762397 )); pts.push_back(Point(13575830, 7785993 )); pts.push_back(Point(13514169, 7785993 )); pts.push_back(Point(13457203, 7762397 )); pts.push_back(Point(13436270, 7745670 )); pts.push_back(Point(13432940, 7742520 )); pts.push_back(Point(12963760, 7742520 ));
pts.push_back(Point(12959272, 7742961 )); pts.push_back(Point(12950981, 7746396 )); pts.push_back(Point(12944636, 7752741 )); pts.push_back(Point(12941201, 7761032 )); pts.push_back(Point(12941201, 7770007 )); pts.push_back(Point(12944636, 7778298 )); pts.push_back(Point(12947490, 7781780 ));
pts.push_back(Point(13425330, 8259620 )); pts.push_back(Point(15601330, 8259620 )); pts.push_back(Point(15904620, 8562900 )); pts.push_back(Point(15909200, 8563030 )); pts.push_back(Point(15935830, 8566006 )); pts.push_back(Point(15992796, 8589602 )); pts.push_back(Point(16036397, 8633203 ));
pts.push_back(Point(16059993, 8690169 )); pts.push_back(Point(16059993, 8751830 )); pts.push_back(Point(16036397, 8808796 )); pts.push_back(Point(15992796, 8852397 )); pts.push_back(Point(15935830, 8875993 )); pts.push_back(Point(15874169, 8875993 )); pts.push_back(Point(15817203, 8852397 )); pts.push_back(Point(15773602, 8808796 ));
pts.push_back(Point(15750006, 8751830 )); pts.push_back(Point(15747030, 8725200 )); pts.push_back(Point(15746900, 8720620 )); pts.push_back(Point(15508950, 8482660 )); pts.push_back(Point(14689890, 8482660 )); pts.push_back(Point(14685412, 8483101 )); pts.push_back(Point(14677121, 8486536 ));
pts.push_back(Point(14670776, 8492881 )); pts.push_back(Point(14667341, 8501172 )); pts.push_back(Point(14667341, 8510147 )); pts.push_back(Point(14670776, 8518438 )); pts.push_back(Point(14673630, 8521920 )); pts.push_back(Point(14714620, 8562900 )); pts.push_back(Point(14719200, 8563030 )); pts.push_back(Point(14745830, 8566006 ));
pts.push_back(Point(14802796, 8589602 )); pts.push_back(Point(14846397, 8633203 )); pts.push_back(Point(14869993, 8690169 )); pts.push_back(Point(14869993, 8751830 )); pts.push_back(Point(14846397, 8808796 )); pts.push_back(Point(14802796, 8852397 )); pts.push_back(Point(14745830, 8875993 )); pts.push_back(Point(14684169, 8875993 ));
pts.push_back(Point(14627203, 8852397 )); pts.push_back(Point(14583602, 8808796 )); pts.push_back(Point(14560006, 8751830 )); pts.push_back(Point(14557030, 8725200 )); pts.push_back(Point(14556900, 8720620 )); pts.push_back(Point(14408270, 8571980 )); pts.push_back(Point(13696320, 8571980 )); pts.push_back(Point(13696320, 8675520 ));
pts.push_back(Point(13699963, 8690161 )); pts.push_back(Point(13699963, 8751818 )); pts.push_back(Point(13676368, 8808781 )); pts.push_back(Point(13632771, 8852378 )); pts.push_back(Point(13575808, 8875973 )); pts.push_back(Point(13514151, 8875973 )); pts.push_back(Point(13457188, 8852378 )); pts.push_back(Point(13436270, 8835670 )); pts.push_back(Point(13432940, 8832520 ));
pts.push_back(Point(13281760, 8832520 )); pts.push_back(Point(13277272, 8832961 )); pts.push_back(Point(13268981, 8836396 )); pts.push_back(Point(13262636, 8842741 )); pts.push_back(Point(13259201, 8851032 )); pts.push_back(Point(13259201, 8860007 )); pts.push_back(Point(13262636, 8868298 )); pts.push_back(Point(13265500, 8871780 ));
pts.push_back(Point(13518710, 9125000 )); pts.push_back(Point(16270720, 9125000 )); pts.push_back(Point(16270720, 8939590 )); pts.push_back(Point(17120780, 8939590 )); pts.push_back(Point(17120780, 9125000 )); pts.push_back(Point(17616200, 9125000 )); pts.push_back(Point(17616200, 75000 )); pts.push_back(Point(16024790, 75000 ));
pts.push_back(Point(16021460, 80700 )); pts.push_back(Point(16016397, 88796 )); pts.push_back(Point(15972796, 132397 )); pts.push_back(Point(15915830, 155993 )); pts.push_back(Point(15908730, 157240 )); pts.push_back(Point(15905000, 157800 )); pts.push_back(Point(15516800, 546000 )); pts.push_back(Point(15905000, 934200 ));
pts.push_back(Point(15908730, 934760 )); pts.push_back(Point(15915830, 936006 )); pts.push_back(Point(15972796, 959602 )); pts.push_back(Point(16016397, 1003203 )); pts.push_back(Point(16039993, 1060169 )); pts.push_back(Point(16039993, 1121830 )); pts.push_back(Point(16016397, 1178796 )); pts.push_back(Point(15972796, 1222397 ));
pts.push_back(Point(15915830, 1245993 )); pts.push_back(Point(15854169, 1245993 )); pts.push_back(Point(15797203, 1222397 )); pts.push_back(Point(15753602, 1178796 )); pts.push_back(Point(15730006, 1121830 )); pts.push_back(Point(15728760, 1114730 )); pts.push_back(Point(15728200, 1111000 )); pts.push_back(Point(15363500, 746300 ));
pts.push_back(Point(14602620, 746300 )); pts.push_back(Point(14598142, 746741 )); pts.push_back(Point(14589851, 750176 )); pts.push_back(Point(14583506, 756521 )); pts.push_back(Point(14580071, 764812 )); pts.push_back(Point(14580071, 773787 )); pts.push_back(Point(14583506, 782078 )); pts.push_back(Point(14586360, 785560 ));
pts.push_back(Point(14586370, 785560 )); pts.push_back(Point(14735000, 934200 )); pts.push_back(Point(14738730, 934760 )); pts.push_back(Point(14745830, 936006 )); pts.push_back(Point(14802796, 959602 )); pts.push_back(Point(14846397, 1003203 )); pts.push_back(Point(14869993, 1060169 ));
pts.push_back(Point(14870450, 1062550 )); pts.push_back(Point(14872170, 1071980 )); pts.push_back(Point(14972780, 1071980 )); pts.push_back(Point(15925000, 2024200 )); pts.push_back(Point(15928730, 2024760 )); pts.push_back(Point(15935830, 2026006 )); pts.push_back(Point(15992796, 2049602 ));
pts.push_back(Point(16036397, 2093203 )); pts.push_back(Point(16059993, 2150169 )); pts.push_back(Point(16059993, 2211830 )); pts.push_back(Point(16036397, 2268796 )); pts.push_back(Point(15992796, 2312397 )); pts.push_back(Point(15935830, 2335993 )); pts.push_back(Point(15874169, 2335993 ));
pts.push_back(Point(15817203, 2312397 )); pts.push_back(Point(15773602, 2268796 )); pts.push_back(Point(15750006, 2211830 )); pts.push_back(Point(15748760, 2204730 )); pts.push_back(Point(15748200, 2201000 )); pts.push_back(Point(14869220, 1322020 )); pts.push_back(Point(14088350, 1322020 ));
pts.push_back(Point(14083862, 1322461 )); pts.push_back(Point(14075571, 1325896 )); pts.push_back(Point(14069226, 1332241 )); pts.push_back(Point(14065791, 1340532 )); pts.push_back(Point(14065791, 1349507 )); pts.push_back(Point(14069226, 1357798 )); pts.push_back(Point(14072080, 1361280 ));
pts.push_back(Point(14072090, 1361280 )); pts.push_back(Point(14735000, 2024200 )); pts.push_back(Point(14738730, 2024760 )); pts.push_back(Point(14745830, 2026006 )); pts.push_back(Point(14802796, 2049602 )); pts.push_back(Point(14846397, 2093203 )); pts.push_back(Point(14869993, 2150169 ));
pts.push_back(Point(14869993, 2211830 )); pts.push_back(Point(14846397, 2268796 )); pts.push_back(Point(14802796, 2312397 )); pts.push_back(Point(14745830, 2335993 )); pts.push_back(Point(14684169, 2335993 )); pts.push_back(Point(14627203, 2312397 )); pts.push_back(Point(14583602, 2268796 )); pts.push_back(Point(14560006, 2211830 ));
pts.push_back(Point(14558760, 2204730 )); pts.push_back(Point(14558200, 2201000 )); pts.push_back(Point(13752220, 1395020 )); pts.push_back(Point(12991340, 1395020 )); pts.push_back(Point(12986862, 1395461 )); pts.push_back(Point(12978571, 1398896 )); pts.push_back(Point(12972226, 1405241 ));
pts.push_back(Point(12968791, 1413532 )); pts.push_back(Point(12968791, 1422507 )); pts.push_back(Point(12972226, 1430798 )); pts.push_back(Point(12975080, 1434280 )); pts.push_back(Point(12975090, 1434280 )); pts.push_back(Point(13565000, 2024200 )); pts.push_back(Point(13568730, 2024760 )); pts.push_back(Point(13575830, 2026006 ));
pts.push_back(Point(13632796, 2049602 )); pts.push_back(Point(13676397, 2093203 )); pts.push_back(Point(13699993, 2150169 )); pts.push_back(Point(13699993, 2211830 )); pts.push_back(Point(13676397, 2268796 )); pts.push_back(Point(13632796, 2312397 )); pts.push_back(Point(13575830, 2335993 ));
pts.push_back(Point(13514169, 2335993 )); pts.push_back(Point(13457203, 2312397 )); pts.push_back(Point(13413602, 2268796 )); pts.push_back(Point(13390006, 2211830 )); pts.push_back(Point(13388760, 2204730 )); pts.push_back(Point(13388200, 2201000 )); pts.push_back(Point(12655220, 1468020 ));
pts.push_back(Point(11894340, 1468020 )); pts.push_back(Point(11889862, 1468461 )); pts.push_back(Point(11881571, 1471896 )); pts.push_back(Point(11875226, 1478241 )); pts.push_back(Point(11871791, 1486532 )); pts.push_back(Point(11871791, 1495507 ));
pts.push_back(Point(11875226, 1503798 )); pts.push_back(Point(11878090, 1507280 )); pts.push_back(Point(12395000, 2024200 )); pts.push_back(Point(12398730, 2024760 )); pts.push_back(Point(12405830, 2026006 )); pts.push_back(Point(12462796, 2049602 )); pts.push_back(Point(12506397, 2093203 ));
pts.push_back(Point(12529993, 2150169 )); pts.push_back(Point(12529993, 2211830 )); pts.push_back(Point(12506397, 2268796 )); pts.push_back(Point(12462796, 2312397 )); pts.push_back(Point(12405830, 2335993 )); pts.push_back(Point(12344169, 2335993 ));
pts.push_back(Point(12287203, 2312397 )); pts.push_back(Point(12243602, 2268796 )); pts.push_back(Point(12220006, 2211830 )); pts.push_back(Point(12218760, 2204730 )); pts.push_back(Point(12218200, 2201000 )); pts.push_back(Point(11558220, 1541020 ));
pts.push_back(Point(10797340, 1541020 )); pts.push_back(Point(10792862, 1541461 )); pts.push_back(Point(10784571, 1544896 )); pts.push_back(Point(10778226, 1551241 )); pts.push_back(Point(10774791, 1559532 )); pts.push_back(Point(10774791, 1568507 )); pts.push_back(Point(10778226, 1576798 )); pts.push_back(Point(10781080, 1580280 ));
pts.push_back(Point(10781090, 1580280 )); pts.push_back(Point(11225000, 2024200 )); pts.push_back(Point(11228730, 2024760 )); pts.push_back(Point(11235830, 2026006 )); pts.push_back(Point(11292796, 2049602 )); pts.push_back(Point(11336397, 2093203 )); pts.push_back(Point(11359993, 2150169 ));
pts.push_back(Point(11359993, 2211830 )); pts.push_back(Point(11336397, 2268796 )); pts.push_back(Point(11292796, 2312397 )); pts.push_back(Point(11235830, 2335993 )); pts.push_back(Point(11174169, 2335993 )); pts.push_back(Point(11117203, 2312397 )); pts.push_back(Point(11073602, 2268796 )); pts.push_back(Point(11050006, 2211830 ));
pts.push_back(Point(11048760, 2204730 )); pts.push_back(Point(11048200, 2201000 )); pts.push_back(Point(10461220, 1614020 )); pts.push_back(Point( 5647400, 1614020 )); pts.push_back(Point( 5642912, 1614461 ));
pts.push_back(Point( 5634621, 1617896 )); pts.push_back(Point( 5628276, 1624241 )); pts.push_back(Point( 5624841, 1632532 )); pts.push_back(Point( 5624841, 1641507 )); pts.push_back(Point( 5628276, 1649798 )); pts.push_back(Point( 5631130, 1653280 ));
pts.push_back(Point( 5688490, 1710640 )); pts.push_back(Point( 9722350, 1710640 )); pts.push_back(Point(10034620, 2022900 )); pts.push_back(Point(10039200, 2023030 )); pts.push_back(Point(10065830, 2026006 )); pts.push_back(Point(10122796, 2049602 ));
pts.push_back(Point(10166397, 2093203 )); pts.push_back(Point(10189993, 2150169 )); pts.push_back(Point(10189993, 2211830 )); pts.push_back(Point(10166397, 2268796 )); pts.push_back(Point(10158620, 2279450 )); pts.push_back(Point(10158620, 2404900 )); pts.push_back(Point(10548950, 2795240 ));
pts.push_back(Point(15586950, 2795240 )); pts.push_back(Point(15904620, 3112900 )); pts.push_back(Point(15909200, 3113030 )); pts.push_back(Point(15935830, 3116006 )); pts.push_back(Point(15992796, 3139602 )); pts.push_back(Point(16036397, 3183203 )); pts.push_back(Point(16059993, 3240169 )); pts.push_back(Point(16059993, 3301830 ));
pts.push_back(Point(16036397, 3358796 )); pts.push_back(Point(15992796, 3402397 )); pts.push_back(Point(15935830, 3425993 )); pts.push_back(Point(15874169, 3425993 )); pts.push_back(Point(15817203, 3402397 )); pts.push_back(Point(15773602, 3358796 )); pts.push_back(Point(15750006, 3301830 )); pts.push_back(Point(15747030, 3275200 ));
pts.push_back(Point(15746900, 3270620 )); pts.push_back(Point(15494570, 3018280 )); pts.push_back(Point(14675510, 3018280 )); pts.push_back(Point(14671032, 3018721 )); pts.push_back(Point(14662741, 3022156 )); pts.push_back(Point(14656396, 3028501 )); pts.push_back(Point(14652961, 3036792 ));
pts.push_back(Point(14652961, 3045767 )); pts.push_back(Point(14656396, 3054058 )); pts.push_back(Point(14659260, 3057540 )); pts.push_back(Point(14714620, 3112900 )); pts.push_back(Point(14719200, 3113030 )); pts.push_back(Point(14745830, 3116006 )); pts.push_back(Point(14802796, 3139602 ));
pts.push_back(Point(14846397, 3183203 )); pts.push_back(Point(14869993, 3240169 )); pts.push_back(Point(14869993, 3301830 )); pts.push_back(Point(14846397, 3358796 )); pts.push_back(Point(14802796, 3402397 )); pts.push_back(Point(14745830, 3425993 )); pts.push_back(Point(14684169, 3425993 )); pts.push_back(Point(14627203, 3402397 ));
pts.push_back(Point(14583602, 3358796 )); pts.push_back(Point(14560006, 3301830 )); pts.push_back(Point(14557030, 3275200 )); pts.push_back(Point(14556900, 3270620 )); pts.push_back(Point(14370700, 3084410 )); pts.push_back(Point(13702830, 3084410 )); pts.push_back(Point(13702830, 3263160 ));
pts.push_back(Point(13700003, 3302210 )); pts.push_back(Point(13676407, 3359176 )); pts.push_back(Point(13632806, 3402777 )); pts.push_back(Point(13575840, 3426373 )); pts.push_back(Point(13514179, 3426373 )); pts.push_back(Point(13457213, 3402777 )); pts.push_back(Point(13413612, 3359176 ));
pts.push_back(Point(13390016, 3302210 )); pts.push_back(Point(13387030, 3275200 )); pts.push_back(Point(13386900, 3270620 )); pts.push_back(Point(13266840, 3150550 )); pts.push_back(Point(12532920, 3150550 )); pts.push_back(Point(12532920, 3264990 )); pts.push_back(Point(12529993, 3301820 ));
pts.push_back(Point(12506397, 3358786 )); pts.push_back(Point(12462796, 3402387 )); pts.push_back(Point(12405830, 3425983 )); pts.push_back(Point(12344169, 3425983 )); pts.push_back(Point(12287203, 3402387 )); pts.push_back(Point(12243602, 3358786 )); pts.push_back(Point(12220006, 3301820 )); pts.push_back(Point(12217030, 3275200 ));
pts.push_back(Point(12216900, 3270620 )); pts.push_back(Point(12157460, 3211170 )); pts.push_back(Point(11362030, 3211170 )); pts.push_back(Point(11360250, 3220520 )); pts.push_back(Point(11359993, 3221830 )); pts.push_back(Point(11336397, 3278796 ));
pts.push_back(Point(11292796, 3322397 )); pts.push_back(Point(11235830, 3345993 )); pts.push_back(Point(11174169, 3345993 )); pts.push_back(Point(11117203, 3322397 )); pts.push_back(Point(11096270, 3305670 )); pts.push_back(Point(11092940, 3302520 )); pts.push_back(Point(10680760, 3302520 ));
pts.push_back(Point(10676272, 3302961 )); pts.push_back(Point(10667981, 3306396 )); pts.push_back(Point(10661636, 3312741 )); pts.push_back(Point(10658201, 3321032 )); pts.push_back(Point(10658201, 3330007 )); pts.push_back(Point(10661636, 3338298 )); pts.push_back(Point(10664500, 3341780 ));
pts.push_back(Point(11264260, 3941550 )); pts.push_back(Point(15643260, 3941550 )); pts.push_back(Point(15904620, 4202900 )); pts.push_back(Point(15909200, 4203030 )); pts.push_back(Point(15935830, 4206006 )); pts.push_back(Point(15992796, 4229602 ));
pts.push_back(Point(16036397, 4273203 )); pts.push_back(Point(16059993, 4330169 )); pts.push_back(Point(16059993, 4391830 )); pts.push_back(Point(16036397, 4448796 )); pts.push_back(Point(15992796, 4492397 ));
pts.push_back(Point(15935830, 4515993 )); pts.push_back(Point(15874169, 4515993 )); pts.push_back(Point(15817203, 4492397 )); pts.push_back(Point(15773602, 4448796 )); pts.push_back(Point(15750006, 4391830 )); pts.push_back(Point(15747030, 4365200 )); pts.push_back(Point(15746900, 4360620 ));
pts.push_back(Point(15550880, 4164590 )); pts.push_back(Point(14825070, 4164590 )); pts.push_back(Point(14825070, 4247610 )); pts.push_back(Point(14846397, 4273213 )); pts.push_back(Point(14869993, 4330179 )); pts.push_back(Point(14869993, 4391840 )); pts.push_back(Point(14846397, 4448806 ));
pts.push_back(Point(14802796, 4492407 )); pts.push_back(Point(14745830, 4516003 )); pts.push_back(Point(14684169, 4516003 )); pts.push_back(Point(14627203, 4492407 )); pts.push_back(Point(14583602, 4448806 )); pts.push_back(Point(14560006, 4391840 )); pts.push_back(Point(14557030, 4365200 ));
pts.push_back(Point(14556900, 4360620 )); pts.push_back(Point(14432520, 4236230 )); pts.push_back(Point(13702830, 4236230 )); pts.push_back(Point(13702830, 4352930 )); pts.push_back(Point(13699993, 4391750 )); pts.push_back(Point(13676397, 4448716 ));
pts.push_back(Point(13632796, 4492317 )); pts.push_back(Point(13575830, 4515913 )); pts.push_back(Point(13514169, 4515913 )); pts.push_back(Point(13457203, 4492317 )); pts.push_back(Point(13413602, 4448716 )); pts.push_back(Point(13390006, 4391750 )); pts.push_back(Point(13387030, 4365200 ));
pts.push_back(Point(13386900, 4360620 )); pts.push_back(Point(13334170, 4307880 )); pts.push_back(Point(12532990, 4307880 )); pts.push_back(Point(12532990, 4357550 )); pts.push_back(Point(12529993, 4391760 )); pts.push_back(Point(12506397, 4448726 )); pts.push_back(Point(12462796, 4492327 ));
pts.push_back(Point(12405830, 4515923 )); pts.push_back(Point(12344169, 4515923 )); pts.push_back(Point(12287203, 4492327 )); pts.push_back(Point(12243602, 4448726 )); pts.push_back(Point(12220006, 4391760 )); pts.push_back(Point(12217970, 4378710 )); pts.push_back(Point(12216810, 4368500 ));
pts.push_back(Point(11363190, 4368500 )); pts.push_back(Point(11362030, 4378710 )); pts.push_back(Point(11359983, 4391828 )); pts.push_back(Point(11336388, 4448791 )); pts.push_back(Point(11292791, 4492388 )); pts.push_back(Point(11235828, 4515983 )); pts.push_back(Point(11174171, 4515983 )); pts.push_back(Point(11117208, 4492388 ));
pts.push_back(Point(11096270, 4475670 )); pts.push_back(Point(11092940, 4472520 )); pts.push_back(Point(11057750, 4472520 )); pts.push_back(Point(11053272, 4472961 )); pts.push_back(Point(11044981, 4476396 )); pts.push_back(Point(11038636, 4482741 )); pts.push_back(Point(11035201, 4491032 ));
pts.push_back(Point(11035201, 4500007 )); pts.push_back(Point(11038636, 4508298 )); pts.push_back(Point(11041490, 4511780 )); pts.push_back(Point(11573490, 5043780 )); pts.push_back(Point(15655490, 5043780 )); pts.push_back(Point(15904620, 5292900 ));
pts.push_back(Point(15909200, 5293030 )); pts.push_back(Point(15935830, 5296006 )); pts.push_back(Point(15992796, 5319602 )); pts.push_back(Point(16036397, 5363203 )); pts.push_back(Point(16059993, 5420169 )); pts.push_back(Point(16059993, 5481830 )); pts.push_back(Point(16036397, 5538796 ));
pts.push_back(Point(15992796, 5582397 )); pts.push_back(Point(15935830, 5605993 )); pts.push_back(Point(15874169, 5605993 )); pts.push_back(Point(15817203, 5582397 )); pts.push_back(Point(15773602, 5538796 )); pts.push_back(Point(15750006, 5481830 )); pts.push_back(Point(15747030, 5455200 ));
pts.push_back(Point(15746900, 5450620 )); pts.push_back(Point(15563110, 5266820 )); pts.push_back(Point(14857380, 5266820 )); pts.push_back(Point(14857380, 5382430 )); pts.push_back(Point(14869993, 5420179 )); pts.push_back(Point(14869993, 5481840 )); pts.push_back(Point(14846397, 5538806 )); pts.push_back(Point(14802796, 5582407 ));
pts.push_back(Point(14745830, 5606003 )); pts.push_back(Point(14684169, 5606003 )); pts.push_back(Point(14627203, 5582407 )); pts.push_back(Point(14583602, 5538806 )); pts.push_back(Point(14560006, 5481840 )); pts.push_back(Point(14557030, 5455200 )); pts.push_back(Point(14556900, 5450620 )); pts.push_back(Point(14444750, 5338460 ));
pts.push_back(Point(13702890, 5338460 )); pts.push_back(Point(13702890, 5364400 )); pts.push_back(Point(13699993, 5401800 )); pts.push_back(Point(13676397, 5458766 )); pts.push_back(Point(13632796, 5502367 )); pts.push_back(Point(13575830, 5525963 )); pts.push_back(Point(13514169, 5525963 )); pts.push_back(Point(13457203, 5502367 ));
pts.push_back(Point(13413602, 5458766 )); pts.push_back(Point(13390006, 5401800 )); pts.push_back(Point(13389230, 5397620 )); pts.push_back(Point(13387590, 5388060 )); pts.push_back(Point(12532960, 5388060 )); pts.push_back(Point(12532960, 5446220 )); pts.push_back(Point(12529993, 5481820 ));
pts.push_back(Point(12506397, 5538786 )); pts.push_back(Point(12462796, 5582387 )); pts.push_back(Point(12405830, 5605983 )); pts.push_back(Point(12344169, 5605983 )); pts.push_back(Point(12287203, 5582387 )); pts.push_back(Point(12266270, 5565670 )); pts.push_back(Point(12262940, 5562520 )); pts.push_back(Point(11737750, 5562520 ));
pts.push_back(Point(11733272, 5562961 )); pts.push_back(Point(11724981, 5566396 )); pts.push_back(Point(11718636, 5572741 )); pts.push_back(Point(11715201, 5581032 )); pts.push_back(Point(11715201, 5590007 )); pts.push_back(Point(11718636, 5598298 )); pts.push_back(Point(11721500, 5601780 ));
pts.push_back(Point(12287760, 6168050 )); pts.push_back(Point(15689760, 6168050 )); pts.push_back(Point(15904620, 6382900 )); pts.push_back(Point(15909200, 6383030 )); pts.push_back(Point(15935830, 6386006 )); pts.push_back(Point(15992796, 6409602 ));
pts.push_back(Point(16036397, 6453203 )); pts.push_back(Point(16059993, 6510169 )); pts.push_back(Point(16059993, 6571830 )); pts.push_back(Point(16036397, 6628796 )); pts.push_back(Point(15992796, 6672397 )); pts.push_back(Point(15935830, 6695993 )); pts.push_back(Point(15874169, 6695993 ));
pts.push_back(Point(15817203, 6672397 )); pts.push_back(Point(15773602, 6628796 )); pts.push_back(Point(15750006, 6571830 )); pts.push_back(Point(15747030, 6545200 )); pts.push_back(Point(15746900, 6540620 )); pts.push_back(Point(15597380, 6391090 )); pts.push_back(Point(14858060, 6391090 ));
pts.push_back(Point(14858060, 6473860 )); pts.push_back(Point(14869993, 6510179 )); pts.push_back(Point(14869993, 6571840 )); pts.push_back(Point(14846397, 6628806 )); pts.push_back(Point(14802796, 6672407 )); pts.push_back(Point(14745830, 6696003 )); pts.push_back(Point(14684169, 6696003 ));
pts.push_back(Point(14627203, 6672407 )); pts.push_back(Point(14583602, 6628806 )); pts.push_back(Point(14560006, 6571840 )); pts.push_back(Point(14557030, 6545200 )); pts.push_back(Point(14556900, 6540620 )); pts.push_back(Point(14479020, 6462730 ));
pts.push_back(Point(13702990, 6462730 )); pts.push_back(Point(13702990, 6537170 )); pts.push_back(Point(13700003, 6571840 )); pts.push_back(Point(13676407, 6628806 )); pts.push_back(Point(13632806, 6672407 )); pts.push_back(Point(13575840, 6696003 ));
pts.push_back(Point(13514179, 6696003 )); pts.push_back(Point(13457213, 6672407 )); pts.push_back(Point(13413612, 6628806 )); pts.push_back(Point(13390016, 6571840 )); pts.push_back(Point(13387040, 6545550 )); pts.push_back(Point(13386710, 6534380 ));
pts.push_back(Point(12533290, 6534380 )); pts.push_back(Point(12532960, 6545550 )); pts.push_back(Point(12529983, 6571828 )); pts.push_back(Point(12506388, 6628791 )); pts.push_back(Point(12462791, 6672388 )); pts.push_back(Point(12405828, 6695983 ));
pts.push_back(Point(12344171, 6695983 )); pts.push_back(Point(12287208, 6672388 )); pts.push_back(Point(12266270, 6655670 ));
poly.set(pts.begin(), pts.end());
si.insert(poly, 444);
result.clear();
si.merge(result);
si.verify1();
print(stdcout, si.pmd) << std::endl;
if(!result.empty()) {
psd = (*(result.begin())).second;
stdcout << psd << std::endl;
std::vector<Point> outpts;
for(typename polygon_set_data<Unit>::iterator_type itr = psd.begin();
itr != psd.end(); ++itr) {
outpts.push_back((*itr).first.first);
outpts.push_back((*itr).first.second);
}
gtlsort(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";
stdcout << i << std::endl;
stdcout << outpts[i] << " " << outpts[i+1] << std::endl;
return 0;
}
}
polys.clear();
psd.get(polys);
if(polys.size() == 0) {
stdcout << "fail merge 10\n";
return false;
}
stdcout << (polys[0]) << std::endl;
}
for(unsigned int i = 0; i < 10; ++i) {
stdcout << "random case # " << i << std::endl;
si.clear();
pts.clear();
pts.push_back(Point(rand()%9-4, rand()%9-4));
pts.push_back(Point(rand()%9-4, rand()%9-4));
pts.push_back(Point(rand()%9-4, rand()%9-4));
polygon_data<Unit> poly1;
poly1.set(pts.begin(), pts.end());
stdcout << poly1 << std::endl;
si.insert(poly1, 444);
pts.clear();
pts.push_back(Point(rand()%9-4, rand()%9-4));
pts.push_back(Point(rand()%9-4, rand()%9-4));
pts.push_back(Point(rand()%9-4, rand()%9-4));
polygon_data<Unit> poly2;
poly2.set(pts.begin(), pts.end());
stdcout << poly2 << std::endl;
si.insert(poly2, 444);
result.clear();
si.merge(result);
print(stdcout, si.pmd) << std::endl;
if(!result.empty()) {
psd = (*(result.begin())).second;
stdcout << psd << std::endl;
polys.clear();
psd.get(polys);
if(polys.size() == 0) {
si.clear();
si.insert(poly1, 333);
result.clear();
si.merge(result);
psd = (*(result.begin())).second;
std::vector<polygon_data<Unit> > polys1;
psd.get(polys1);
si.clear();
si.insert(poly2, 333);
result.clear();
si.merge(result);
psd = (*(result.begin())).second;
std::vector<polygon_data<Unit> > polys2;
psd.get(polys2);
if(!polys1.empty() || !polys2.empty()) {
stdcout << "fail random merge " << i << std::endl;
return false;
}
}
}
if(!polys.empty())
stdcout << polys.size() << ": " << (polys[0]) << std::endl;
}
return true;
}
template <typename stream_type>
static inline bool check_rectangle_trio(rectangle_data<Unit> rect1, rectangle_data<Unit> rect2, rectangle_data<Unit> rect3, stream_type& stdcout) {
property_merge si;
std::map<std::set<property_type>, polygon_set_data<Unit> > result;
std::vector<polygon_data<Unit> > polys;
property_merge_90<property_type, Unit> si90;
std::map<std::set<property_type>, polygon_90_set_data<Unit> > result90;
std::vector<polygon_data<Unit> > polys90;
si.insert(rect1, 111);
si90.insert(rect1, 111);
stdcout << rect1 << std::endl;
si.insert(rect2, 222);
si90.insert(rect2, 222);
stdcout << rect2 << std::endl;
si.insert(rect3, 333);
si90.insert(rect3, 333);
stdcout << rect3 << std::endl;
si.merge(result);
si90.merge(result90);
if(result.size() != result90.size()) {
stdcout << "merge failed with size mismatch\n";
return 0;
}
typename std::map<std::set<property_type>, polygon_90_set_data<Unit> >::iterator itr90 = result90.begin();
for(typename std::map<std::set<property_type>, polygon_set_data<Unit> >::iterator itr = result.begin();
itr != result.end(); ++itr) {
for(typename std::set<property_type>::const_iterator set_itr = (*itr).first.begin();
set_itr != (*itr).first.end(); ++set_itr) {
stdcout << (*set_itr) << " ";
} stdcout << ") \n";
polygon_set_data<Unit> psd = (*itr).second;
polygon_90_set_data<Unit> psd90 = (*itr90).second;
polys.clear();
polys90.clear();
psd.get(polys);
psd90.get(polys90);
if(polys.size() != polys90.size()) {
stdcout << "merge failed with polygon count mismatch\n";
stdcout << psd << std::endl;
for(std::size_t j = 0; j < polys.size(); ++j) {
stdcout << polys[j] << std::endl;
}
stdcout << "reference\n";
for(std::size_t j = 0; j < polys90.size(); ++j) {
stdcout << polys90[j] << std::endl;
}
return 0;
}
bool failed = false;
for(std::size_t j = 0; j < polys.size(); ++j) {
stdcout << polys[j] << std::endl;
stdcout << polys90[j] << std::endl;
#ifdef BOOST_POLYGON_ICC
#pragma warning (disable:1572)
#endif
if(area(polys[j]) != area(polys90[j])) {
#ifdef BOOST_POLYGON_ICC
#pragma warning (default:1572)
#endif
stdcout << "merge failed with area mismatch\n";
failed = true;
}
}
if(failed) return 0;
++itr90;
}
return true;
}
template <typename stream_type>
static inline bool test_manhattan_intersection(stream_type& stdcout) {
rectangle_data<Unit> rect1, rect2, rect3;
set_points(rect1, (Point(-1, 2)), (Point(1, 4)));
set_points(rect2, (Point(-1, 2)), (Point(2, 3)));
set_points(rect3, (Point(-3, 0)), (Point(4, 2)));
if(!check_rectangle_trio(rect1, rect2, rect3, stdcout)) {
return false;
}
for(unsigned int i = 0; i < 100; ++i) {
property_merge si;
std::map<std::set<property_type>, polygon_set_data<Unit> > result;
std::vector<polygon_data<Unit> > polys;
property_merge_90<property_type, Unit> si90;
std::map<std::set<property_type>, polygon_90_set_data<Unit> > result90;
std::vector<polygon_data<Unit> > polys90;
stdcout << "random case # " << i << std::endl;
set_points(rect1, (Point(rand()%9-4, rand()%9-4)), (Point(rand()%9-4, rand()%9-4)));
set_points(rect2, (Point(rand()%9-4, rand()%9-4)), (Point(rand()%9-4, rand()%9-4)));
set_points(rect3, (Point(rand()%9-4, rand()%9-4)), (Point(rand()%9-4, rand()%9-4)));
if(!check_rectangle_trio(rect1, rect2, rect3, stdcout)) {
return false;
}
}
return true;
}
template <typename stream_type>
static inline bool test_intersection(stream_type& stdcout) {
property_merge si;
rectangle_data<Unit> rect;
xl(rect, 0);
yl(rect, 10);
xh(rect, 30);
yh(rect, 20);
si.insert(rect, 333);
xl(rect, 10);
yl(rect, 0);
xh(rect, 20);
yh(rect, 30);
si.insert(rect, 444);
xl(rect, 15);
yl(rect, 0);
xh(rect, 25);
yh(rect, 30);
si.insert(rect, 555);
std::map<std::set<property_type>, polygon_set_data<Unit> > result;
si.merge(result);
print(stdcout, si.pmd) << std::endl;
for(typename std::map<std::set<property_type>, polygon_set_data<Unit> >::iterator itr = result.begin();
itr != result.end(); ++itr) {
stdcout << "( ";
for(typename std::set<property_type>::const_iterator set_itr = (*itr).first.begin();
set_itr != (*itr).first.end(); ++set_itr) {
stdcout << (*set_itr) << " ";
} stdcout << ") \n";
polygon_set_data<Unit> psd = (*itr).second;
stdcout << psd << std::endl;
std::vector<polygon_data<Unit> > polys;
psd.get(polys);
for(std::size_t i = 0; i < polys.size(); ++i) {
stdcout << polys[i] << std::endl;
}
}
std::vector<Point> pts;
std::vector<polygon_data<Unit> > polys;
for(unsigned int i = 0; i < 10; ++i) {
property_merge si2;
stdcout << "random case # " << i << std::endl;
si.clear();
pts.clear();
pts.push_back(Point(rand()%9-4, rand()%9-4));
pts.push_back(Point(rand()%9-4, rand()%9-4));
pts.push_back(Point(rand()%9-4, rand()%9-4));
polygon_data<Unit> poly1;
poly1.set(pts.begin(), pts.end());
stdcout << poly1 << std::endl;
si.insert(poly1, 444);
si2.insert(poly1, 333);
pts.clear();
pts.push_back(Point(rand()%9-4, rand()%9-4));
pts.push_back(Point(rand()%9-4, rand()%9-4));
pts.push_back(Point(rand()%9-4, rand()%9-4));
polygon_data<Unit> poly2;
poly2.set(pts.begin(), pts.end());
stdcout << poly2 << std::endl;
si.insert(poly2, 444);
si2.insert(poly2, 444);
pts.clear();
pts.push_back(Point(rand()%9-4, rand()%9-4));
pts.push_back(Point(rand()%9-4, rand()%9-4));
pts.push_back(Point(rand()%9-4, rand()%9-4));
polygon_data<Unit> poly3;
poly3.set(pts.begin(), pts.end());
stdcout << poly3 << std::endl;
si.insert(poly3, 444);
si2.insert(poly3, 555);
result.clear();
std::map<std::set<property_type>, polygon_set_data<Unit> > result2;
si.merge(result);
si2.merge(result2);
stdcout << "merged result\n";
for(typename std::map<std::set<property_type>, polygon_set_data<Unit> >::iterator itr = result.begin();
itr != result.end(); ++itr) {
stdcout << "( ";
for(typename std::set<property_type>::const_iterator set_itr = (*itr).first.begin();
set_itr != (*itr).first.end(); ++set_itr) {
stdcout << (*set_itr) << " ";
} stdcout << ") \n";
polygon_set_data<Unit> psd = (*itr).second;
stdcout << psd << std::endl;
std::vector<polygon_data<Unit> > polys2;
psd.get(polys2);
for(std::size_t ii = 0; ii < polys2.size(); ++ii) {
stdcout << polys2[ii] << std::endl;
}
}
stdcout << "intersected pmd\n";
print(stdcout, si2.pmd) << std::endl;
stdcout << "intersected result\n";
for(typename std::map<std::set<property_type>, polygon_set_data<Unit> >::iterator itr = result2.begin();
itr != result2.end(); ++itr) {
stdcout << "( ";
for(typename std::set<property_type>::const_iterator set_itr = (*itr).first.begin();
set_itr != (*itr).first.end(); ++set_itr) {
stdcout << (*set_itr) << " ";
} stdcout << ") \n";
polygon_set_data<Unit> psd = (*itr).second;
stdcout << psd << std::endl;
std::vector<polygon_data<Unit> > polys2;
psd.get(polys2);
for(std::size_t ii = 0; ii < polys2.size(); ++ii) {
stdcout << polys2[ii] << std::endl;
}
}
si.clear();
for(typename std::map<std::set<property_type>, polygon_set_data<Unit> >::iterator itr = result2.begin();
itr != result2.end(); ++itr) {
polys.clear();
(*itr).second.get(polys);
for(std::size_t j = 0; j < polys.size(); ++j) {
si.insert(polys[j], 444);
}
}
result2.clear();
si.merge(result2);
stdcout << "remerged result\n";
for(typename std::map<std::set<property_type>, polygon_set_data<Unit> >::iterator itr = result2.begin();
itr != result2.end(); ++itr) {
stdcout << "( ";
for(typename std::set<property_type>::const_iterator set_itr = (*itr).first.begin();
set_itr != (*itr).first.end(); ++set_itr) {
stdcout << (*set_itr) << " ";
} stdcout << ") \n";
polygon_set_data<Unit> psd = (*itr).second;
stdcout << psd << std::endl;
std::vector<polygon_data<Unit> > polys2;
psd.get(polys2);
for(std::size_t ii = 0; ii < polys2.size(); ++ii) {
stdcout << polys2[ii] << std::endl;
}
}
std::vector<polygon_data<Unit> > polys2;
polys.clear();
(*(result.begin())).second.get(polys);
(*(result2.begin())).second.get(polys2);
if(!(polys == polys2)) {
stdcout << "failed intersection check # " << i << std::endl;
return false;
}
}
return true;
}
};
template <typename Unit>
class arbitrary_boolean_op : public scanline_base<Unit> {
private:
typedef int property_type;
typedef typename scanline_base<Unit>::Point Point;
//the first point is the vertex and and second point establishes the slope of an edge eminating from the vertex
//typedef std::pair<Point, Point> half_edge;
typedef typename scanline_base<Unit>::half_edge half_edge;
//scanline comparator functor
typedef typename scanline_base<Unit>::less_half_edge less_half_edge;
typedef typename scanline_base<Unit>::less_point less_point;
//this data structure assocates a property and count to a half edge
typedef std::pair<half_edge, std::pair<property_type, int> > vertex_property;
//this data type stores the combination of many half edges
typedef std::vector<vertex_property> property_merge_data;
//this is the data type used internally to store the combination of property counts at a given location
typedef std::vector<std::pair<property_type, int> > property_map;
//this data type is used internally to store the combined property data for a given half edge
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() : pack_() {}
less_vertex_data(typename scanline_base<Unit>::evalAtXforYPack* pack) : pack_(pack) {}
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;
Unit x = lvalue.first.first.get(HORIZONTAL);
int just_before_ = 0;
less_half_edge lhe(&x, &just_before_, pack_);
return lhe(lvalue.first, rvalue.first);
}
};
template <typename result_type, typename key_type, int op_type>
class boolean_output_functor {
public:
boolean_output_functor() {}
void operator()(result_type& result, const half_edge& edge, const key_type& left, const key_type& right) {
typename std::pair<half_edge, int> elem;
elem.first = edge;
elem.second = 1;
if(edge.second < edge.first) elem.second *= -1;
if(scanline_base<Unit>::is_vertical(edge)) elem.second *= -1;
#ifdef BOOST_POLYGON_MSVC
#pragma warning (disable: 4127)
#endif
if(op_type == 0) { //OR
if(!left.empty() && right.empty()) {
result.insert_clean(elem);
} else if(!right.empty() && left.empty()) {
elem.second *= -1;
result.insert_clean(elem);
}
} else if(op_type == 1) { //AND
if(left.size() == 2 && right.size() != 2) {
result.insert_clean(elem);
} else if(right.size() == 2 && left.size() != 2) {
elem.second *= -1;
result.insert_clean(elem);
}
} else if(op_type == 2) { //XOR
if(left.size() == 1 && right.size() != 1) {
result.insert_clean(elem);
} else if(right.size() == 1 && left.size() != 1) {
elem.second *= -1;
result.insert_clean(elem);
}
} else { //SUBTRACT
if(left.size() == 1) {
if((*(left.begin())) == 0) {
result.insert_clean(elem);
}
}
#ifdef BOOST_POLYGON_MSVC
#pragma warning (default: 4127)
#endif
if(right.size() == 1) {
if((*(right.begin())) == 0) {
elem.second *= -1;
result.insert_clean(elem);
}
}
}
}
};
inline void sort_property_merge_data() {
less_vertex_data<vertex_property> lvd(&evalAtXforYPack_);
gtlsort(pmd.begin(), pmd.end(), lvd);
}
public:
inline arbitrary_boolean_op() : pmd(), evalAtXforYPack_() {}
inline arbitrary_boolean_op(const arbitrary_boolean_op& pm) : pmd(pm.pmd), evalAtXforYPack_(pm.evalAtXforYPack_) {}
inline arbitrary_boolean_op& operator=(const arbitrary_boolean_op& pm) { pmd = pm.pmd; return *this; }
enum BOOLEAN_OP_TYPE {
BOOLEAN_OR = 0,
BOOLEAN_AND = 1,
BOOLEAN_XOR = 2,
BOOLEAN_NOT = 3
};
template <typename result_type, typename iT1, typename iT2>
inline void execute(result_type& result, iT1 b1, iT1 e1, iT2 b2, iT2 e2, int op) {
//intersect data
insert(b1, e1, 0);
insert(b2, e2, 1);
property_merge_data tmp_pmd;
//#define BOOST_POLYGON_DEBUG_FILE
#ifdef BOOST_POLYGON_DEBUG_FILE
std::fstream debug_file;
debug_file.open("gtl_debug.txt", std::ios::out);
property_merge<Unit, property_type, std::vector<property_type> >::print(debug_file, pmd);
debug_file.close();
#endif
if(pmd.empty())
return;
line_intersection<Unit>::validate_scan(tmp_pmd, pmd.begin(), pmd.end());
pmd.swap(tmp_pmd);
sort_property_merge_data();
scanline<Unit, property_type, std::vector<property_type> > sl;
if(op == BOOLEAN_OR) {
boolean_output_functor<result_type, std::vector<property_type>, 0> bof;
sl.scan(result, bof, pmd.begin(), pmd.end());
} else if(op == BOOLEAN_AND) {
boolean_output_functor<result_type, std::vector<property_type>, 1> bof;
sl.scan(result, bof, pmd.begin(), pmd.end());
} else if(op == BOOLEAN_XOR) {
boolean_output_functor<result_type, std::vector<property_type>, 2> bof;
sl.scan(result, bof, pmd.begin(), pmd.end());
} else if(op == BOOLEAN_NOT) {
boolean_output_functor<result_type, std::vector<property_type>, 3> bof;
sl.scan(result, bof, pmd.begin(), pmd.end());
}
}
inline void clear() {*this = arbitrary_boolean_op();}
private:
template <typename iT>
void insert(iT b, iT e, int id) {
for(;
b != e; ++b) {
pmd.push_back(vertex_property(half_edge((*b).first.first, (*b).first.second),
std::pair<property_type, int>(id, (*b).second)));
}
}
};
template <typename Unit, typename stream_type>
bool test_arbitrary_boolean_op(stream_type& stdcout) {
polygon_set_data<Unit> psd;
rectangle_data<Unit> rect;
set_points(rect, point_data<Unit>(0, 0), point_data<Unit>(10, 10));
psd.insert(rect);
polygon_set_data<Unit> psd2;
set_points(rect, point_data<Unit>(5, 5), point_data<Unit>(15, 15));
psd2.insert(rect);
std::vector<polygon_data<Unit> > pv;
pv.clear();
arbitrary_boolean_op<Unit> abo;
polygon_set_data<Unit> psd3;
abo.execute(psd3, psd.begin(), psd.end(), psd2.begin(), psd2.end(), arbitrary_boolean_op<Unit>::BOOLEAN_OR);
psd3.get(pv);
for(std::size_t i = 0; i < pv.size(); ++i) {
stdcout << pv[i] << std::endl;
}
pv.clear();
abo.clear();
psd3.clear();
abo.execute(psd3, psd.begin(), psd.end(), psd2.begin(), psd2.end(), arbitrary_boolean_op<Unit>::BOOLEAN_AND);
psd3.get(pv);
for(std::size_t i = 0; i < pv.size(); ++i) {
stdcout << pv[i] << std::endl;
}
pv.clear();
abo.clear();
psd3.clear();
abo.execute(psd3, psd.begin(), psd.end(), psd2.begin(), psd2.end(), arbitrary_boolean_op<Unit>::BOOLEAN_XOR);
psd3.get(pv);
for(std::size_t i = 0; i < pv.size(); ++i) {
stdcout << pv[i] << std::endl;
}
pv.clear();
abo.clear();
psd3.clear();
abo.execute(psd3, psd.begin(), psd.end(), psd2.begin(), psd2.end(), arbitrary_boolean_op<Unit>::BOOLEAN_NOT);
psd3.get(pv);
for(std::size_t i = 0; i < pv.size(); ++i) {
stdcout << pv[i] << std::endl;
}
return true;
}
template <typename Unit, typename property_type>
class arbitrary_connectivity_extraction : public scanline_base<Unit> {
private:
typedef typename scanline_base<Unit>::Point Point;
//the first point is the vertex and and second point establishes the slope of an edge eminating from the vertex
//typedef std::pair<Point, Point> half_edge;
typedef typename scanline_base<Unit>::half_edge half_edge;
//scanline comparator functor
typedef typename scanline_base<Unit>::less_half_edge less_half_edge;
typedef typename scanline_base<Unit>::less_point less_point;
//this data structure assocates a property and count to a half edge
typedef std::pair<half_edge, std::pair<property_type, int> > vertex_property;
//this data type stores the combination of many half edges
typedef std::vector<vertex_property> property_merge_data;
//this is the data type used internally to store the combination of property counts at a given location
typedef std::vector<std::pair<property_type, int> > property_map;
//this data type is used internally to store the combined property data for a given half edge
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() : pack_() {}
less_vertex_data(typename scanline_base<Unit>::evalAtXforYPack* pack) : pack_(pack) {}
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;
Unit x = lvalue.first.first.get(HORIZONTAL);
int just_before_ = 0;
less_half_edge lhe(&x, &just_before_, pack_);
return lhe(lvalue.first, rvalue.first);
}
};
template <typename cT>
static void process_previous_x(cT& output) {
std::map<point_data<Unit>, std::set<property_type> >& y_prop_map = output.first.second;
if(y_prop_map.empty()) return;
Unit x = output.first.first;
for(typename std::map<point_data<Unit>, std::set<property_type> >::iterator itr =
y_prop_map.begin(); itr != y_prop_map.end(); ++itr) {
if((*itr).first.x() < x) {
y_prop_map.erase(y_prop_map.begin(), itr);
continue;
}
for(typename std::set<property_type>::iterator inner_itr = itr->second.begin();
inner_itr != itr->second.end(); ++inner_itr) {
std::set<property_type>& output_edges = (*(output.second))[*inner_itr];
typename std::set<property_type>::iterator inner_inner_itr = inner_itr;
++inner_inner_itr;
for( ; inner_inner_itr != itr->second.end(); ++inner_inner_itr) {
output_edges.insert(output_edges.end(), *inner_inner_itr);
std::set<property_type>& output_edges_2 = (*(output.second))[*inner_inner_itr];
output_edges_2.insert(output_edges_2.end(), *inner_itr);
}
}
}
}
template <typename result_type, typename key_type>
class connectivity_extraction_output_functor {
public:
connectivity_extraction_output_functor() {}
void operator()(result_type& result, const half_edge& edge, const key_type& left, const key_type& right) {
Unit& x = result.first.first;
std::map<point_data<Unit>, std::set<property_type> >& y_prop_map = result.first.second;
point_data<Unit> pt = edge.first;
if(pt.x() != x) process_previous_x(result);
x = pt.x();
std::set<property_type>& output_set = y_prop_map[pt];
{
for(typename key_type::const_iterator itr1 =
left.begin(); itr1 != left.end(); ++itr1) {
output_set.insert(output_set.end(), *itr1);
}
for(typename key_type::const_iterator itr2 =
right.begin(); itr2 != right.end(); ++itr2) {
output_set.insert(output_set.end(), *itr2);
}
}
std::set<property_type>& output_set2 = y_prop_map[edge.second];
for(typename key_type::const_iterator itr1 =
left.begin(); itr1 != left.end(); ++itr1) {
output_set2.insert(output_set2.end(), *itr1);
}
for(typename key_type::const_iterator itr2 =
right.begin(); itr2 != right.end(); ++itr2) {
output_set2.insert(output_set2.end(), *itr2);
}
}
};
inline void sort_property_merge_data() {
less_vertex_data<vertex_property> lvd(&evalAtXforYPack_);
gtlsort(pmd.begin(), pmd.end(), lvd);
}
public:
inline arbitrary_connectivity_extraction() : pmd(), evalAtXforYPack_() {}
inline arbitrary_connectivity_extraction
(const arbitrary_connectivity_extraction& pm) : pmd(pm.pmd), evalAtXforYPack_(pm.evalAtXforYPack_) {}
inline arbitrary_connectivity_extraction& operator=
(const arbitrary_connectivity_extraction& pm) { pmd = pm.pmd; return *this; }
template <typename result_type>
inline void execute(result_type& result) {
//intersect data
property_merge_data tmp_pmd;
line_intersection<Unit>::validate_scan(tmp_pmd, pmd.begin(), pmd.end());
pmd.swap(tmp_pmd);
sort_property_merge_data();
scanline<Unit, property_type, std::vector<property_type> > sl;
std::pair<std::pair<Unit, std::map<point_data<Unit>, std::set<property_type> > >,
result_type*> output
(std::make_pair(std::make_pair((std::numeric_limits<Unit>::max)(),
std::map<point_data<Unit>,
std::set<property_type> >()), &result));
connectivity_extraction_output_functor<std::pair<std::pair<Unit,
std::map<point_data<Unit>, std::set<property_type> > >, result_type*>,
std::vector<property_type> > ceof;
sl.scan(output, ceof, pmd.begin(), pmd.end());
process_previous_x(output);
}
inline void clear() {*this = arbitrary_connectivity_extraction();}
template <typename iT>
void populateTouchSetData(iT begin, iT end,
property_type property) {
for( ; begin != end; ++begin) {
pmd.push_back(vertex_property(half_edge((*begin).first.first, (*begin).first.second),
std::pair<property_type, int>(property, (*begin).second)));
}
}
};
}
}
#endif