From: lucanus.j.simonson_at_[hidden]
Date: 2008-07-16 20:28:52
Author: ljsimons
Date: 2008-07-16 20:28:52 EDT (Wed, 16 Jul 2008)
New Revision: 47500
URL: http://svn.boost.org/trac/boost/changeset/47500
Log:
added partial implementation of arbitrary angle scanline property merge algorithm
Added:
sandbox/gtl/gtl/scan_arbitrary.hpp (contents, props changed)
Added: sandbox/gtl/gtl/scan_arbitrary.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/scan_arbitrary.hpp 2008-07-16 20:28:52 EDT (Wed, 16 Jul 2008)
@@ -0,0 +1,581 @@
+
+/*
+ Copyright 2008 Intel Corporation
+
+ Use, modification and distribution are subject to the Boost Software License,
+ Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt).
+*/
+#ifndef GTL_SCAN_ARBITRARY_HPP
+#define GTL_SCAN_ARBITRARY_HPP
+namespace gtl {
+
+ template <typename user_coordinate, typename internal_coordinate, typename property_type>
+ class scan_intersect {
+ public: //change to private when done testing
+ //definitions
+ typedef point_data<user_coordinate> user_point;
+ typedef point_data<internal_coordinate> internal_point;
+
+ typedef std::pair<user_point, user_point> user_edge;
+ typedef std::pair<internal_point, internal_point> internal_edge;
+
+ class less_scanline_edge;
+
+ typedef std::map<property_type, int> property_count;
+ typedef std::pair<internal_point, property_count> half_edge;
+ typedef std::vector<half_edge> half_edge_vector;
+ typedef std::pair<internal_point, half_edge_vector> vertex_data;
+ typedef std::map<property_type, int> property_data;
+ typedef std::pair<internal_edge, property_data> scanline_elment;
+ typedef std::map<internal_edge, property_data, less_scanline_edge> scanline_data;
+ typedef std::set<property_type> property_combination;
+ typedef std::pair<property_combination, internal_edge> output_element;
+ typedef std::set<internal_point> intersection_event_queue;
+ typedef std::vector<vertex_data> vertex_vector;
+
+ private:
+ //data memebers
+ internal_coordinate current_scanline_stop_;
+ bool handling_intersections_;
+ vertex_vector input_vertices_; //stores the input
+ vertex_vector output_vertices_; //stores the output
+ scanline_data scanline_;
+ intersection_event_queue intersections_; //intersection points that need to be processed
+ vertex_vector intersection_vertices_; //vertex events created by handling intersections
+ property_count vertical_count_; //count coming in from below due to vertical edges
+ public:
+ //interfaces
+ scan_intersect() : scanline_(less_scanline_edge(¤t_scanline_stop_, &handling_intersections_)) {}
+
+ template <typename geometry_type>
+ void insert(const geometry_type& geometry_object, const property_type& property_value, bool is_hole = false) {
+ insert(geometry_object, property_value, is_hole, typename geometry_concept<geometry_type>::type());
+ }
+
+ void scan() {
+ sort_input();
+ typename vertex_vector::iterator input_begin = input_vertices_.begin();
+ typename vertex_vector::iterator input_end = input_vertices_.end();
+ handling_intersections_ = false;
+ while(input_begin != input_end) {
+ internal_coordinate next_scanline_stop = point_concept::get((*input_begin).first, HORIZONTAL);
+ if(next_scanline_stop != current_scanline_stop_) {
+ //this call modifies current_scanline_stop to be the coordinate of the first intersection if any before the next input
+ if(handle_intersections(next_scanline_stop)) {
+ vertex_merge_iterator<typename vertex_vector::iterator, typename vertex_vector::const_iterator>
+ merge_begin(input_begin, input_end, intersection_vertices_.begin(), intersection_vertices_.end());
+ vertex_merge_iterator<typename vertex_vector::iterator, typename vertex_vector::const_iterator>
+ merge_end(input_begin, input_end, intersection_vertices_.begin(), intersection_vertices_.end());
+ while(merge_begin != merge_end && point_concept::get((*merge_begin).first, HORIZONTAL) == current_scanline_stop_) {
+ scan_element(*merge_begin);
+ ++merge_begin;
+ }
+ } else {
+ //no pending intersection events, so advance the scanline to the new stop
+ current_scanline_stop_ = next_scanline_stop;
+ }
+ } else {
+ scan_element(*input_begin);
+ ++input_begin;
+ }
+ }
+ }
+
+ //output is std::map<std::set<property_type>, back_intertable_container<geometry_type> >
+ //geometry_type is either polygon_type or polygon_with_holes_type
+ //back_insertable_container is any container that supports container.insert(container.end(), value_type)
+ template <typename T>
+ void getResult(T& output) {
+ //TODO
+ }
+
+ public: //change to private when done testing
+ //non-static member functions for internal use
+
+ inline void sort_input() {
+ less_vertex_data lessF;
+ std::sort(input_vertices_.begin(), input_vertices_.end(), lessF);
+ }
+
+ template <typename polygon_type>
+ void insert(const polygon_type& polygon_object, const property_type& property_value, bool is_hole,
+ polygon_concept tag) {
+ bool first_iteration = true;
+ bool second_iteration = true;
+ internal_point first_point;
+ internal_point second_point;
+ internal_point previous_previous_point;
+ internal_point previous_point;
+ internal_point current_point;
+ vertex_data current_vertex;
+ direction_1d winding = polygon_concept::winding(polygon_object);
+ for(typename polygon_traits<polygon_type>::iterator_type itr = polygon_concept::begin(polygon_object);
+ itr != polygon_concept::end(polygon_object); ++itr) {
+ point_concept::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(current_vertex, previous_previous_point, previous_point, current_point, winding,
+ is_hole, property_value);
+ input_vertices_.push_back(current_vertex);
+ 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(current_vertex, previous_previous_point, previous_point, current_point, winding,
+ is_hole, property_value);
+ input_vertices_.push_back(current_vertex);
+ previous_previous_point = previous_point;
+ previous_point = current_point;
+ }
+ current_point = second_point;
+ create_vertex(current_vertex, previous_previous_point, previous_point, current_point, winding,
+ is_hole, property_value);
+ input_vertices_.push_back(current_vertex);
+ previous_previous_point = previous_point;
+ previous_point = current_point;
+ }
+ }
+
+ template <typename polygon_with_holes_type>
+ void insert(const polygon_with_holes_type& polygon_with_holes_object, const property_type& property_value, bool is_hole,
+ polygon_with_holes_concept tag) {
+ insert(polygon_with_holes_object, property_value, is_hole, polygon_concept());
+ for(typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type itr =
+ polygon_with_holes_concept::begin_holes(polygon_with_holes_object);
+ itr != polygon_with_holes_concept::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 tag) {
+ polygon_90_data<user_coordinate> poly;
+ polygon_90_concept::set_rectangle(poly, rectangle_object);
+ insert(poly, property_value, is_hole, polygon_concept());
+ }
+
+ void scan_element(const vertex_data& vertex) {
+ for(typename half_edge_vector::const_iterator itr = vertex.second.begin(); itr != vertex.second.end(); ++itr) {
+ //scan_half_edge(vertex.first, *itr);
+ }
+ }
+
+ void handle_intersection(internal_coordinate intersection_intercept) {}
+
+ bool handle_intersections(internal_coordinate next_scanline_stop) {
+ if(intersections_.empty() || point_concept::get(*(intersections_.begin()), HORIZONTAL) > next_scanline_stop)
+ return false;
+ current_scanline_stop_ = point_concept::get(*(intersections_.begin()), HORIZONTAL);
+ handling_intersections_ = true;
+ do {
+ handle_intersection(point_concept::get(*(intersections_.begin()), VERTICAL));
+ intersections_.erase(intersections_.begin());
+ } while(current_scanline_stop_ == point_concept::get(*(intersections_.begin()), HORIZONTAL));
+ handling_intersections_ = false;
+ return true;
+ }
+
+
+
+ public: //change to private when done testing
+ //static helper functions and member classes
+
+ static inline void create_vertex(vertex_data& current_vertex,
+ const internal_point& previous_point,
+ const internal_point& current_point,
+ const internal_point& next_point,
+ direction_1d winding,
+ bool is_hole, const property_type& property) {
+ current_vertex.first = current_point;
+ current_vertex.second.clear();
+ int multiplier = 1;
+ if(winding == CLOCKWISE)
+ multiplier = -1;
+ if(is_hole)
+ multiplier *= -1;
+ half_edge he;
+ he.first = next_point;
+ he.second[property] = multiplier * (point_concept::distance(next_point, current_point, HORIZONTAL) == 0 ? -1: 1);
+ current_vertex.second.push_back(he);
+ he.second.clear();
+ he.first = previous_point;
+ he.second[property] = -1 * multiplier * (point_concept::distance(previous_point, current_point, HORIZONTAL) == 0 ? -1: 1);
+ current_vertex.second.push_back(he);
+ sort_vertex_half_edges(current_vertex);
+ }
+
+ static inline void sort_vertex_half_edges(vertex_data& vertex) {
+ less_half_edge_pair lessF(vertex.first);
+ std::sort(vertex.second.begin(), vertex.second.end(), lessF);
+ }
+
+ static inline internal_coordinate compute_intercept(const internal_coordinate& dy2,
+ const internal_coordinate& dx1,
+ const internal_coordinate& dx2) {
+ //intercept = dy2 * dx1 / dx2
+ typedef typename coordinate_traits<internal_coordinate>::area_type area_type;
+ //try to protect against potential overflow by casting to area type for multiplication computation
+ return (internal_coordinate)(((area_type)dy2 * (area_type)dx1) / (area_type)dx2);
+ }
+
+ static inline internal_coordinate compute_intercept(const internal_edge& edge, internal_coordinate& coordinate) {
+ const internal_point* pts[2] = {edge.first, edge.second};
+ if(*(pts[0]) > *(pts[1]))
+ std::swap(pts[0], pts[1]);
+ internal_coordinate dx = point_concept::distance(*(pts[0]), *(pts[1]), HORIZONTAL);
+ internal_coordinate dy = point_concept::distance(*(pts[0]), *(pts[1]), VERTICAL);
+ internal_coordinate dx_intercept = coordinate - point_concept::get(*(pts[0]), HORIZONTAL);
+ return point_concept::get(*(pts[0]), VERTICAL) + compute_intercept(dy, dx_intercept, dx);
+ }
+
+ static inline bool less_slope(const internal_coordinate& x, const internal_coordinate& y,
+ const internal_point& pt1, const internal_point& pt2) {
+ const internal_point* pts[2] = {&pt1, &pt2};
+ //compute y value on edge from pt_ to pts[1] at the x value of pts[0]
+ internal_coordinate dy2 = pts[1]->get(VERTICAL) - y;
+ internal_coordinate dy1 = pts[0]->get(VERTICAL) - y;
+ internal_coordinate dx2 = pts[1]->get(HORIZONTAL) - x;
+ internal_coordinate dx1 = pts[0]->get(HORIZONTAL) - x;
+ if(dx1 < 0) {
+ dy1 *= -1;
+ dx1 *= -1;
+ }
+ if(dx2 < 0) {
+ dy2 *= -1;
+ dx2 *= -1;
+ }
+ if(dx1 < dx2)
+ return (dy1 < compute_intercept(dy2, dx1, dx2));
+ else
+ return (dy2 > compute_intercept(dy1, dx2, dx1));
+ }
+
+ class less_vertex_data {
+ public:
+ less_vertex_data() {}
+ bool operator()(const vertex_data& lvalue, const vertex_data& rvalue) {
+ return lvalue.first < rvalue.first;
+ }
+ };
+
+ class less_scanline_edge {
+ private:
+ internal_coordinate* scanline_stop;
+ bool* processing_intersections;
+ public:
+ less_scanline_edge(internal_coordinate* stop, bool* flag) :
+ scanline_stop(stop), processing_intersections(flag) {}
+ bool operator()(const internal_edge& lvalue, const internal_edge& rvalue) {
+ internal_coordinate ly1 = lvalue.first.get(VERTICAL);
+ internal_coordinate ly2 = lvalue.second.get(VERTICAL);
+ internal_coordinate ry1 = rvalue.first.get(VERTICAL);
+ internal_coordinate ry2 = rvalue.second.get(VERTICAL);
+ if(std::max(ly1, ly2) < std::min(ry1, ry2))
+ return true;
+ if(std::min(ly1, ly2) > std::max(ry1, ry2))
+ return false;
+ //the edges have overlapping range in y
+ //it is assumed that the edges overlap the scanline stop
+ //it is futher assumed that neither edge is vertical
+ internal_coordinate ly = compute_intercept(lvalue, *scanline_stop);
+ internal_coordinate ry = compute_intercept(lvalue, *scanline_stop);
+ if(ly < ry) return true;
+ if(ly > ry) return false;
+ //the two edges have the same y value at the scanline stop
+ return *processing_intersections ^
+ less_slope(*scanline_stop, ly, lvalue.first, rvalue.first);
+ }
+ };
+
+ static inline void merge_count(property_count& lvalue, const property_count& rvalue) {
+ for(typename property_count::const_iterator itr = rvalue.begin(); itr != rvalue.end(); ++itr) {
+ //double check that default initialization of element of map to int results in zero value
+ lvalue[(*itr).first] += (*itr).second;
+ }
+ }
+
+ //checks if two property counts that are adjacenet in the scanline are equivilent
+ //for the purposes of determining if there should be an output generated along their boundary or not
+ static inline bool equivalent(const property_count& lvalue, const property_count& rvalue) {
+ typename property_count::const_iterator itr1 = lvalue.begin();
+ typename property_count::const_iterator itr2 = rvalue.begin();
+ while(itr1 != lvalue.end() || itr2 != rvalue.end()) {
+ while(itr1 != lvalue.end() && (*itr1).second <= 0) ++itr1;
+ while(itr2 != rvalue.end() && (*itr2).second <= 0) ++itr2;
+ if(itr1 != lvalue.end()) {
+ if(itr2 != rvalue.end() && *itr1.first != *itr2.first) return false;
+ } else if(itr2 != rvalue.end())
+ return false;
+ }
+ }
+
+ static inline void set_unqiue_property(property_combination& unqiue_property, const property_count& property) {
+ unqiue_property.clear();
+ for(typename property_count::const_iterator itr = property.begin(); itr != property.end(); ++itr) {
+ if(*itr.second > 0)
+ unqiue_property.insert(unqiue_property.end(), *itr.first);
+ }
+ }
+
+ class less_half_edge_pair {
+ private:
+ internal_point pt_;
+ public:
+ less_half_edge_pair(const internal_point& pt) : pt_(pt) {}
+ bool operator()(const half_edge& e1, const half_edge& e2) {
+ const internal_point& pt1 = e1.first;
+ const internal_point& pt2 = e2.first;
+ if(point_concept::get(pt1, HORIZONTAL) ==
+ point_concept::get(pt_, HORIZONTAL)) {
+ //vertical edge is always largest
+ return false;
+ }
+ if(point_concept::get(pt2, HORIZONTAL) ==
+ point_concept::get(pt_, HORIZONTAL)) {
+ //if half edge 1 is not vertical its slope is less than that of half edge 2
+ return point_concept::get(pt1, HORIZONTAL) != point_concept::get(pt2, HORIZONTAL);
+ }
+ return less_slope(point_concept::get(pt_, HORIZONTAL),
+ point_concept::get(pt_, VERTICAL), pt1, pt2);
+ }
+ };
+
+ template <typename iterator1, typename iterator2>
+ class vertex_merge_iterator {
+ private:
+ iterator1 begin1_, end1_;
+ iterator2 begin2_, end2_;
+ vertex_data merged_vertex_;
+ unsigned int state_;
+ public:
+ typedef std::forward_iterator_tag iterator_category;
+ typedef vertex_data value_type;
+ typedef std::ptrdiff_t difference_type;
+ typedef const value_type* pointer; //immutable
+ typedef const value_type& reference; //immutable
+ vertex_merge_iterator(iterator1 begin1, iterator1 end1, iterator2 begin2, iterator2 end2) :
+ begin1_(begin1), end1_(end1), begin2_(begin2), end2_(end2) {
+ set_state();
+ if(state_ == 0)
+ handle_equal();
+ }
+
+ bool operator==(const vertex_merge_iterator& that) {
+ return begin1_ == that.begin1_ && begin2_ == that.begin2_;
+ }
+ bool operator!=(const vertex_merge_iterator& that) {
+ return !((*this) == that);
+ }
+
+ reference operator*() {
+ if(state_ == 1) return *begin1_;
+ if(state_ == 2) return *begin2_;
+ if(state_ == 3) return merged_vertex_;
+ //assert this return statement should not be used
+ return merged_vertex_;
+ }
+
+ inline vertex_merge_iterator& operator++() {
+ if(state_ == 1) ++begin1_;
+ if(state_ == 2) ++begin1_;
+ set_state();
+ if(state_ == 0)
+ handle_equal();
+ return *this;
+ }
+ inline vertex_merge_iterator operator++(int) {
+ vertex_merge_iterator tmp(*this);
+ ++(*this);
+ return tmp;
+ }
+
+ void handle_equal() {
+ half_edge_vector half_edges;
+ merged_vertex_.first = (*begin1_).first;
+ while(begin1_ != end1_ && (*begin1_).first == merged_vertex_.first) {
+ half_edges.insert(half_edges.end(), (*begin1_).second.begin(), (*begin1_).second.end());
+ ++begin1_;
+ }
+ while(begin2_ != end2_ && (*begin2_).first == merged_vertex_.first) {
+ half_edges.insert(half_edges.end(), (*begin2_).second.begin(), (*begin2_).second.end());
+ ++begin2_;
+ }
+ less_half_edge_pair lessF(merged_vertex_.first);
+ std::sort(half_edges.begin(), half_edges.end(), lessF);
+ merged_vertex_.second.push_back(half_edges.front());
+ for(unsigned int i = 1; i < half_edges.size(); ++i) {
+ if(!lessF(merged_vertex_.second.back(), half_edges[i])) {
+ merge_count(merged_vertex_.second.back().second, half_edges[i].second);
+ } else {
+ merged_vertex_.second.push_back(half_edges[i]);
+ }
+ }
+ state_ = 3;
+ }
+
+ void set_state() {
+ if(begin1_ == end1_) {
+ if(begin2_ == end2_) {
+ state_ = 4;
+ } else {
+ state_ = 2;
+ }
+ } else if(begin2_ == end2_) {
+ state_ = 1;
+ } else {
+ if((*begin1_).first == (*begin2_).first) {
+ state_ = 0;
+ } else if((*begin1_).first < (*begin2_).first) {
+ state_ = 1;
+ } else {
+ state_ = 2;
+ }
+ }
+ }
+ };
+
+ public:
+ //test functions
+ static std::ostream& print (std::ostream& o, const property_count& c)
+ {
+ o << "count: {";
+ for(typename property_count::const_iterator itr = c.begin(); itr != c.end(); ++itr) {
+ o << ((*itr).first) << ":" << ((*itr).second) << " ";
+ }
+ return o << "} ";
+ }
+
+ static std::ostream& print (std::ostream& o, const half_edge& he)
+ {
+ return print(o << "half edge: (" << (he.first) << ", ", (he.second)) << ") ";
+ }
+
+ static std::ostream& print (std::ostream& o, const half_edge_vector& hev)
+ {
+ o << "half edges: {";
+ for(unsigned int i = 0; i < hev.size(); ++i) {
+ print(o, (hev[i])) << " ";
+ }
+ return o << "} ";
+ }
+
+ static std::ostream& print (std::ostream& o, const vertex_data& v)
+ {
+ return print(o << "vertex: <" << (v.first) << ", ", (v.second)) << "> ";
+ }
+
+ static std::ostream& print (std::ostream& o, const vertex_vector& vv)
+ {
+ o << "vertices: {";
+ for(unsigned int i = 0; i < vv.size(); ++i) {
+ print(o, (vv[i])) << " ";
+ }
+ return o << "} ";
+ }
+
+
+
+ static inline bool test_insertion() {
+ scan_intersect si;
+ rectangle_data<user_coordinate> rect;
+ rectangle_concept::xl(rect, 0);
+ rectangle_concept::yl(rect, 1);
+ rectangle_concept::xh(rect, 10);
+ rectangle_concept::yh(rect, 11);
+
+ si.insert(rect, 333);
+ print(std::cout, si.input_vertices_) << std::endl;
+
+ user_point pts[4] = {user_point(0, 0), user_point(10,-3), user_point(13, 8), user_point(0, 0) };
+ polygon_data<user_coordinate> poly;
+ scan_intersect si2;
+ poly.set(pts, pts+3);
+ si2.insert(poly, 444);
+ si2.sort_input();
+ print(std::cout, si2.input_vertices_) << std::endl;
+ scan_intersect si3;
+ poly.set(pts, pts+4);
+ si3.insert(poly, 444);
+ si3.sort_input();
+ std::cout << (si2.input_vertices_ == si3.input_vertices_) << std::endl;
+ std::reverse(pts, pts+4);
+ scan_intersect si4;
+ poly.set(pts, pts+4);
+ si4.insert(poly, 444);
+ si4.sort_input();
+ std::cout << (si2.input_vertices_ == si4.input_vertices_) << std::endl;
+ std::reverse(pts, pts+3);
+ scan_intersect si5;
+ poly.set(pts, pts+4);
+ si5.insert(poly, 444);
+ si5.sort_input();
+ std::cout << (si2.input_vertices_ == si5.input_vertices_) << std::endl;
+
+ return true;
+ }
+
+
+
+ static inline bool test_less_slope() {
+ internal_coordinate x = 0;
+ internal_coordinate y = 0;
+ internal_point pt1(10, 10);
+ internal_point pt2(10, 10);
+ if(less_slope(x, y, pt1, pt2)) {
+ std::cout << "fail1\n";
+ return false;
+ }
+ if(less_slope(x, y, pt2, pt1)) {
+ std::cout << "fail2\n";
+ return false;
+ }
+ pt1.set(HORIZONTAL, 11);
+ if(!less_slope(x, y, pt1, pt2)) {
+ std::cout << "fail3\n";
+ return false;
+ }
+ if(less_slope(x, y, pt2, pt1)) {
+ std::cout << "fail4\n";
+ return false;
+ }
+ pt1 = internal_point(-10, -10);
+ if(less_slope(x, y, pt1, pt2)) {
+ std::cout << "fail5\n";
+ return false;
+ }
+ if(less_slope(x, y, pt2, pt1)) {
+ std::cout << "fail6\n";
+ return false;
+ }
+ pt1.set(HORIZONTAL, -11);
+ if(!less_slope(x, y, pt1, pt2)) {
+ std::cout << "fail7\n";
+ return false;
+ }
+ if(less_slope(x, y, pt2, pt1)) {
+ std::cout << "fail8\n";
+ return false;
+ }
+ return true;
+ }
+
+ };
+
+}
+#endif
+