EVOLUTION-MANAGER

Edit File: scan_arbitrary.hpp

/* 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)); } polygon_sort(ends.begin(), ends.end()); histogram.reserve(ends.size()); histogram.push_back(std::make_pair(ends.front().first, std::make_pair(0, 0))); for(typename std::vector<std::pair<Unit, int> >::iterator itr = ends.begin(); itr != ends.end(); ++itr) { 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_; polygon_sort(data.begin(), data.end()); //find all intersection points for(typename std::vector<std::pair<half_edge, segment_id> >::iterator outer = data.begin(); outer != data.end(); ++outer) { 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) { 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); } } } } polygon_sort(pts.begin(), pts.end()); typename std::vector<Point>::iterator newend = std::unique(pts.begin(), pts.end()); typename std::vector<Point>::iterator lfinger = pts.begin(); //find all segments that interact with intersection points 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 << "\n"; // 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 << "\n"; // 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); } } polygon_sort(data.begin(), data.end()); for(typename std::vector<std::pair<half_edge, segment_id> >::iterator outer = data.begin(); outer != data.end(); ++outer) { const half_edge& he1 = (*outer).first; 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() << "\n"; return false; } } } return true; } class less_point_down_slope { public: typedef Point first_argument_type; typedef Point second_argument_type; typedef bool result_type; 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; polygon_sort(tmpPts.begin(), tmpPts.end(), lpds); segment_edge(output_segments, he, id, tmpPts.begin(), tmpPts.end()); } else { segment_edge(output_segments, he, id, pts.begin(), pts.end()); } //} } } // //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 // polygon_sort(sloping_ends.begin(), sloping_ends.end()); // std::map<Unit, std::set<iterator> > sloping_elements; // std::set<iterator> merge_elements; // for(typename std::vector<std::pair<Unit, iterator> >::iterator slop_iter = sloping_ends.begin(); // slop_iter == sloping_ends.end(); ++slop_iter) { // //merge into sloping elements // typename std::set<iterator>::iterator merge_iterator = merge_elements.find((*slop_iter).second); // if(merge_iterator == merge_elements.end()) { // merge_elements.insert((*slop_iter).second); // } else { // merge_elements.erase(merge_iterator); // } // sloping_elements[(*slop_iter).first] = merge_elements; // } // //scan intersection points // typename std::map<Unit, std::set<segment_id> >::iterator vertical_iter = vertical_data_.begin(); // typename std::map<Unit, std::set<iterator> >::iterator sloping_iter = sloping_elements.begin(); // for(typename std::set<Unit>::iterator position_iter = intersection_locations.begin(); // position_iter == intersection_locations.end(); ++position_iter) { // //look for vertical segments that intersect this point and update them // Unit y = *position_iter; // Point pt(x_, y); // //handle vertical segments // if(vertical_iter != vertical_data_.end()) { // typename std::map<Unit, std::set<segment_id> >::iterator next_vertical = vertical_iter; // for(++next_vertical; next_vertical != vertical_data_.end() && // (*next_vertical).first < y; ++next_vertical) { // vertical_iter = next_vertical; // } // if((*vertical_iter).first < y && !(*vertical_iter).second.empty()) { // update_segments(intersection_points, (*vertical_iter).second, pt); // ++vertical_iter; // if(vertical_iter != vertical_data_.end() && (*vertical_iter).first == y) // update_segments(intersection_points, (*vertical_iter).second, pt); // } // } // //handle sloping segments // if(sloping_iter != sloping_elements.end()) { // typename std::map<Unit, std::set<iterator> >::iterator next_sloping = sloping_iter; // for(++next_sloping; next_sloping != sloping_elements.end() && // (*next_sloping).first < y; ++next_sloping) { // sloping_iter = next_sloping; // } // if((*sloping_iter).first < y && !(*sloping_iter).second.empty()) { // for(typename std::set<iterator>::iterator element_iter = (*sloping_iter).second.begin(); // element_iter != (*sloping_iter).second.end(); ++element_iter) { // const half_edge& he = (*element_iter).first; // if(intersects_grid(pt, he)) { // update_segments(intersection_points, (*element_iter).second, pt); // } // } // ++sloping_iter; // if(sloping_iter != sloping_elements.end() && (*sloping_iter).first == y && // !(*sloping_iter).second.empty()) { // for(typename std::set<iterator>::iterator element_iter = (*sloping_iter).second.begin(); // element_iter != (*sloping_iter).second.end(); ++element_iter) { // const half_edge& he = (*element_iter).first; // if(intersects_grid(pt, he)) { // update_segments(intersection_points, (*element_iter).second, pt); // } // } // } // } // } // } // //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() << "\n"; 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 << "\n"; } 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 << "\n"; 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 (push) #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 (pop) #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 << "\n"; //} 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)); } polygon_sort(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 << "\n"; 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 << "\n"; 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 << "\n"; 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 << "\n"; 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 << "\n"; 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 << "\n"; 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 << "\n"; 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 << "\n"; 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_); polygon_sort(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 << "\n"; 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); } polygon_sort(pts.begin(), pts.end()); for(std::size_t i = 0; i < pts.size(); i+=2) { if(pts[i] != pts[i+1]) { //stdcout << "Non-closed figures after line intersection!\n"; 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) { 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); polygon_sort(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) << "\n"; 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) << "\n"; property_merge si3; poly.set(pts, pts+4); si3.insert(poly, 444); si3.sort_property_merge_data(); stdcout << (si2.pmd == si3.pmd) << "\n"; 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) << "\n"; stdcout << (si2.pmd == si4.pmd) << "\n"; 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) << "\n"; 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) << "\n"; 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]) << "\n"; 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) << "\n"; psd = (*(result.begin())).second; stdcout << psd << "\n"; 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) << "\n"; psd = (*(result.begin())).second; stdcout << psd << "\n"; 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) << "\n"; psd = (*(result.begin())).second; stdcout << psd << "\n"; polys.clear(); psd.get(polys); if(polys.size() != 1) { stdcout << "fail merge 4\n"; return false; } stdcout << (polys[0]) << "\n"; 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) << "\n"; psd = (*(result.begin())).second; stdcout << psd << "\n"; 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) << "\n"; if(!result.empty()) { psd = (*(result.begin())).second; stdcout << psd << "\n"; polys.clear(); psd.get(polys); if(polys.size() != 1) { stdcout << "fail merge 6\n"; return false; } stdcout << (polys[0]) << "\n"; } 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) << "\n"; if(!result.empty()) { psd = (*(result.begin())).second; stdcout << psd << "\n"; polys.clear(); psd.get(polys); if(polys.size() == 0) { stdcout << "fail merge 7\n"; return false; } stdcout << (polys[0]) << "\n"; } 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) << "\n"; if(!result.empty()) { psd = (*(result.begin())).second; stdcout << psd << "\n"; polys.clear(); psd.get(polys); if(polys.size() == 0) { stdcout << "fail merge 8\n"; return false; } stdcout << (polys[0]) << "\n"; } 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) << "\n"; if(!result.empty()) { psd = (*(result.begin())).second; stdcout << psd << "\n"; polys.clear(); psd.get(polys); if(polys.size() == 0) { stdcout << "fail merge 9\n"; return false; } stdcout << (polys[0]) << "\n"; } 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) << "\n"; if(!result.empty()) { psd = (*(result.begin())).second; stdcout << psd << "\n"; 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); } polygon_sort(outpts.begin(), outpts.end()); for(std::size_t i = 0; i < outpts.size(); i+=2) { if(outpts[i] != outpts[i+1]) { stdcout << "Polygon set not a closed figure\n"; stdcout << i << "\n"; stdcout << outpts[i] << " " << outpts[i+1] << "\n"; return 0; } } polys.clear(); psd.get(polys); if(polys.size() == 0) { stdcout << "fail merge 10\n"; return false; } stdcout << (polys[0]) << "\n"; } for(unsigned int i = 0; i < 10; ++i) { stdcout << "random case # " << i << "\n"; 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 << "\n"; 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 << "\n"; si.insert(poly2, 444); result.clear(); si.merge(result); print(stdcout, si.pmd) << "\n"; if(!result.empty()) { psd = (*(result.begin())).second; stdcout << psd << "\n"; 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 << "\n"; return false; } } } if(!polys.empty()) stdcout << polys.size() << ": " << (polys[0]) << "\n"; } 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 << "\n"; si.insert(rect2, 222); si90.insert(rect2, 222); stdcout << rect2 << "\n"; si.insert(rect3, 333); si90.insert(rect3, 333); stdcout << rect3 << "\n"; 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 << "\n"; for(std::size_t j = 0; j < polys.size(); ++j) { stdcout << polys[j] << "\n"; } stdcout << "reference\n"; for(std::size_t j = 0; j < polys90.size(); ++j) { stdcout << polys90[j] << "\n"; } return 0; } bool failed = false; for(std::size_t j = 0; j < polys.size(); ++j) { stdcout << polys[j] << "\n"; stdcout << polys90[j] << "\n"; #ifdef BOOST_POLYGON_ICC #pragma warning (push) #pragma warning (disable:1572) #endif if(area(polys[j]) != area(polys90[j])) { #ifdef BOOST_POLYGON_ICC #pragma warning (pop) #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 << "\n"; 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) << "\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 << "\n"; std::vector<polygon_data<Unit> > polys; psd.get(polys); for(std::size_t i = 0; i < polys.size(); ++i) { stdcout << polys[i] << "\n"; } } 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 << "\n"; 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 << "\n"; 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 << "\n"; 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 << "\n"; 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 << "\n"; std::vector<polygon_data<Unit> > polys2; psd.get(polys2); for(std::size_t ii = 0; ii < polys2.size(); ++ii) { stdcout << polys2[ii] << "\n"; } } stdcout << "intersected pmd\n"; print(stdcout, si2.pmd) << "\n"; 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 << "\n"; std::vector<polygon_data<Unit> > polys2; psd.get(polys2); for(std::size_t ii = 0; ii < polys2.size(); ++ii) { stdcout << polys2[ii] << "\n"; } } 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 << "\n"; std::vector<polygon_data<Unit> > polys2; psd.get(polys2); for(std::size_t ii = 0; ii < polys2.size(); ++ii) { stdcout << polys2[ii] << "\n"; } } 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 << "\n"; 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 (push) #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 (pop) #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_); polygon_sort(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] << "\n"; } 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] << "\n"; } 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] << "\n"; } 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] << "\n"; } 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_); polygon_sort(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