|
|
Boost-Commit : |
From: lucanus.j.simonson_at_[hidden]
Date: 2008-05-29 17:48:48
Author: ljsimons
Date: 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
New Revision: 45926
URL: http://svn.boost.org/trac/boost/changeset/45926
Log:
changing filenames to hpp
Added:
sandbox/gtl/gtl/boolean_op.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/boolean_op.h
sandbox/gtl/gtl/geometry_traits.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/geometry_traits.h
sandbox/gtl/gtl/gtl.hpp
- copied unchanged from r45925, /sandbox/gtl/gtl/gtl.h
sandbox/gtl/gtl/interval_concept.hpp
- copied unchanged from r45925, /sandbox/gtl/gtl/interval_concept.h
sandbox/gtl/gtl/interval_data.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/interval_data.h
sandbox/gtl/gtl/interval_traits.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/interval_traits.h
sandbox/gtl/gtl/isotropy.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/isotropy.h
sandbox/gtl/gtl/iterator_compact_to_points.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/iterator_compact_to_points.h
sandbox/gtl/gtl/iterator_geometry_to_set.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/iterator_geometry_to_set.h
sandbox/gtl/gtl/iterator_points_to_compact.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/iterator_points_to_compact.h
sandbox/gtl/gtl/iterator_vertex_orient_conversion.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/iterator_vertex_orient_conversion.h
sandbox/gtl/gtl/point_3d_concept.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/point_3d_concept.h
sandbox/gtl/gtl/point_3d_data.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/point_3d_data.h
sandbox/gtl/gtl/point_3d_traits.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/point_3d_traits.h
sandbox/gtl/gtl/point_concept.hpp
- copied unchanged from r45925, /sandbox/gtl/gtl/point_concept.h
sandbox/gtl/gtl/point_data.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/point_data.h
sandbox/gtl/gtl/point_traits.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/point_traits.h
sandbox/gtl/gtl/polygon_concept.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/polygon_concept.h
sandbox/gtl/gtl/polygon_data.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/polygon_data.h
sandbox/gtl/gtl/polygon_formation.hpp
- copied unchanged from r45925, /sandbox/gtl/gtl/polygon_formation.h
sandbox/gtl/gtl/polygon_set_data.hpp
- copied unchanged from r45925, /sandbox/gtl/gtl/polygon_set_data.h
sandbox/gtl/gtl/polygon_set_traits.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/polygon_set_traits.h
sandbox/gtl/gtl/polygon_set_view.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/polygon_set_view.h
sandbox/gtl/gtl/polygon_set_wrapper.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/polygon_set_wrapper.h
sandbox/gtl/gtl/polygon_traits.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/polygon_traits.h
sandbox/gtl/gtl/polygon_with_holes_concept.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/polygon_with_holes_concept.h
sandbox/gtl/gtl/polygon_with_holes_data.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/polygon_with_holes_data.h
sandbox/gtl/gtl/polygon_with_holes_traits.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/polygon_with_holes_traits.h
sandbox/gtl/gtl/post_concept_definitions.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/post_concept_definitions.h
sandbox/gtl/gtl/post_geometry_traits_definitions.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/post_geometry_traits_definitions.h
sandbox/gtl/gtl/rectangle_concept.hpp
- copied unchanged from r45925, /sandbox/gtl/gtl/rectangle_concept.h
sandbox/gtl/gtl/rectangle_data.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/rectangle_data.h
sandbox/gtl/gtl/rectangle_formation.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/rectangle_formation.h
sandbox/gtl/gtl/rectangle_traits.hpp
- copied unchanged from r45924, /sandbox/gtl/gtl/rectangle_traits.h
Removed:
sandbox/gtl/gtl/boolean_op.h
sandbox/gtl/gtl/geometry_traits.h
sandbox/gtl/gtl/gtl.h
sandbox/gtl/gtl/interval_concept.h
sandbox/gtl/gtl/interval_data.h
sandbox/gtl/gtl/interval_traits.h
sandbox/gtl/gtl/isotropy.h
sandbox/gtl/gtl/iterator_compact_to_points.h
sandbox/gtl/gtl/iterator_geometry_to_set.h
sandbox/gtl/gtl/iterator_points_to_compact.h
sandbox/gtl/gtl/iterator_vertex_orient_conversion.h
sandbox/gtl/gtl/point_3d_concept.h
sandbox/gtl/gtl/point_3d_data.h
sandbox/gtl/gtl/point_3d_traits.h
sandbox/gtl/gtl/point_concept.h
sandbox/gtl/gtl/point_data.h
sandbox/gtl/gtl/point_traits.h
sandbox/gtl/gtl/polygon_concept.h
sandbox/gtl/gtl/polygon_data.h
sandbox/gtl/gtl/polygon_formation.h
sandbox/gtl/gtl/polygon_set_data.h
sandbox/gtl/gtl/polygon_set_traits.h
sandbox/gtl/gtl/polygon_set_view.h
sandbox/gtl/gtl/polygon_set_wrapper.h
sandbox/gtl/gtl/polygon_traits.h
sandbox/gtl/gtl/polygon_with_holes_concept.h
sandbox/gtl/gtl/polygon_with_holes_data.h
sandbox/gtl/gtl/polygon_with_holes_traits.h
sandbox/gtl/gtl/post_concept_definitions.h
sandbox/gtl/gtl/post_geometry_traits_definitions.h
sandbox/gtl/gtl/rectangle_concept.h
sandbox/gtl/gtl/rectangle_data.h
sandbox/gtl/gtl/rectangle_formation.h
sandbox/gtl/gtl/rectangle_traits.h
Deleted: sandbox/gtl/gtl/boolean_op.h
==============================================================================
--- sandbox/gtl/gtl/boolean_op.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,680 +0,0 @@
-/*
- 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).
-*/
-namespace boolean_op {
-
- template <typename Unit>
- class ScanEventNew{
- private:
- typedef std::vector<std::pair<Unit, int> > EventData;
- mutable EventData eventData_;
- mutable bool dirty_;
- class lessEventDataElement : public std::binary_function<const std::pair<Unit, int>&, const std::pair<Unit, int>&, bool> {
- public:
- inline lessEventDataElement() {}
- inline bool operator () (const std::pair<Unit, int>& elem1, const std::pair<Unit, int>& elem2) const {
- return elem1.first < elem2.first;
- }
- };
- public:
-
- // The ScanEvent::iterator is a lazy algorithm that accumulates
- // polygon intersection count as it is incremented through the
- // scan event data structure.
- // The iterator provides a forward iterator semantic only.
- class iterator {
- private:
- typename EventData::const_iterator i_;
- Unit prevPos_;
- int count_;
- public:
- inline iterator() {}
- inline iterator(typename EventData::const_iterator i,
- Unit prevPos, int count) : i_(i),
- prevPos_(prevPos),
- count_(count) {}
- inline iterator(const iterator& that) : i_(that.i_),
- prevPos_(that.prevPos_),
- count_(that.count_) {}
- inline iterator& operator=(const iterator& that) {
- //std::cout << "iterator assign\n";
- i_ = that.i_;
- prevPos_ = that.prevPos_;
- count_ = that.count_;
- return *this;
- }
- inline bool operator==(const iterator& that) { return i_ == that.i_; }
- inline bool operator!=(const iterator& that) { return i_ != that.i_; }
- inline iterator& operator++() {
- //std::cout << "iterator increment\n";
- prevPos_ = (*i_).first;
- count_ += (*i_).second;
- ++i_;
- return *this;
- }
- inline iterator operator++(int) {
- iterator tmp = *this;
- ++(*this);
- return tmp;
- }
- inline std::pair<interval_data<Unit>, int> operator*() {
- //std::cout << "iterator dereference\n";
- if(count_ == 0) ++(*this);
- std::pair<interval_data<Unit>, int> retVal;
- retVal.first = interval_data<Unit>(prevPos_, (*i_).first);
- retVal.second = count_;
- return retVal;
- }
- };
-
- inline ScanEventNew() {}
- template<class iT>
- inline ScanEventNew(iT begin, iT end){
- for( ; begin != end; ++begin){
- insert(*begin);
- }
- }
- inline ScanEventNew(const ScanEventNew& that) : eventData_(that.eventData_), dirty_(that.dirty_) {}
- inline ScanEventNew& operator=(const ScanEventNew& that) {
- if(that.dirty_) that.clean();
- eventData_ = that.eventData_;
- dirty_ = that.dirty_;
- return *this;
- }
-
- //Insert and interval intersection count change into the EventData
- inline void insert(const std::pair<interval_data<Unit>, int>& intervalCount) {
- insert(intervalCount.first.low(), intervalCount.second);
- insert(intervalCount.first.high(), -intervalCount.second);
- }
-
- //Insert and position and change int change in intersection count into EventData
- inline void insert(Unit pos, int count) {
- eventData_.push_back(std::pair<Unit, int>());
- eventData_.back().first = pos;
- eventData_.back().second = count;
- //std::cout << "Insert: " << eventData_.size() << std::endl;
- dirty_ = true;
- }
-
- //merge this scan event with that by inserting its data
- inline void insert(const ScanEventNew& that) {
- typename EventData::const_iterator itr;
- for(itr = that.eventData_.begin(); itr != that.eventData_.end(); ++itr) {
- insert((*itr).first, (*itr).second);
- }
- }
-
- inline void clean() const {
- //std::cout << "Clean\n";
- if(eventData_.empty()) return;
- std::sort(eventData_.begin(), eventData_.end(), lessEventDataElement());
- std::vector<std::pair<Unit, int> > collapse;
- collapse.reserve(eventData_.size());
- Unit pos = eventData_[0].first;
- int count = eventData_[0].second;
- unsigned int i = 1;
- for( ; i < eventData_.size(); ++i) {
- if(pos == eventData_[i].first) {
- count += eventData_[i].second;
- } else {
- if(count != 0) {
- //std::cout << "collapse insert\n";
- collapse.push_back(std::pair<Unit, int>());
- collapse.back().first = pos;
- collapse.back().second = count;
- }
- pos = eventData_[i].first;
- count = eventData_[i].second;
- }
- }
- //std::cout << "collapse insert\n";
- if(count != 0) {
- collapse.push_back(std::pair<Unit, int>());
- collapse.back().first = pos;
- collapse.back().second = count;
- }
- //std::cout << "data size: " << eventData_.size() << std::endl;
- //std::cout << "collapse size: " << collapse.size() << std::endl;
- eventData_ = std::vector<std::pair<Unit, int> >();
- eventData_.insert(eventData_.end(), collapse.begin(), collapse.end());
- dirty_ = false;
- }
-
- //Get the begin iterator over event data
- inline iterator begin() const {
- if(dirty_) clean();
- if(eventData_.empty()) return end();
- Unit pos = eventData_[0].first;
- int count = eventData_[0].second;
- typename EventData::const_iterator itr = eventData_.begin();
- ++itr;
- return iterator(itr, pos, count);
- }
-
- //Get the end iterator over event data
- inline iterator end() const {
- if(dirty_) clean();
- return iterator(eventData_.end(), 0, 0);
- }
-
- inline void clear() { eventData_.clear(); }
-
- inline interval_data<Unit> extents() const {
- if(eventData_.empty()) return interval_data<Unit>();
- return interval_data<Unit>((*(eventData_.begin())).first, (*(eventData_.rbegin())).first);
- }
- };
-
- //BooleanOp is the generic boolean operation scanline algorithm that provides
- //all the simple boolean set operations on manhattan data. By templatizing
- //the intersection count of the input and algorithm internals it is extensible
- //to multi-layer scans, properties and other advanced scanline operations above
- //and beyond simple booleans.
- //T must cast to int
- template <class T, typename Unit>
- class BooleanOp {
- public:
- typedef std::map<Unit, T> ScanData;
- typedef std::pair<Unit, T> ElementType;
- protected:
- ScanData scanData_;
- typename ScanData::iterator nextItr_;
- T nullT_;
- public:
- inline BooleanOp () { nextItr_ = scanData_.end(); nullT_ = 0; }
- inline BooleanOp (T nullT) : nullT_(nullT) { nextItr_ = scanData_.end(); }
- inline BooleanOp (const BooleanOp& that) : scanData_(that.scanData_),
- nullT_(that.nullT_) { nextItr_ = scanData_.begin(); }
- inline BooleanOp& operator=(const BooleanOp& that);
-
- //moves scanline forward
- inline void advanceScan() { nextItr_ = scanData_.begin(); }
-
- //proceses the given interval and T data
- //appends output edges to cT
- template <class cT>
- inline void processInterval(cT& outputContainer, interval_data<Unit> ivl, T deltaCount);
-
- private:
- inline typename ScanData::iterator lookup_(Unit pos){
- if(nextItr_ != scanData_.end() && nextItr_->first >= pos) {
- return nextItr_;
- }
- return nextItr_ = scanData_.lower_bound(pos);
- }
- inline typename ScanData::iterator insert_(Unit pos, T count){
- return nextItr_ = scanData_.insert(nextItr_, ElementType(pos, count));
- }
- template <class cT>
- inline void evaluateInterval_(cT& outputContainer, interval_data<Unit> ivl, T beforeCount, T afterCount);
- };
-
- class BinaryAnd {
- public:
- inline BinaryAnd() {}
- inline bool operator()(int a, int b) { return (a > 0) & (b > 0); }
- };
- class BinaryOr {
- public:
- inline BinaryOr() {}
- inline bool operator()(int a, int b) { return (a > 0) | (b > 0); }
- };
- class BinaryNot {
- public:
- inline BinaryNot() {}
- inline bool operator()(int a, int b) { return (a > 0) & !(b > 0); }
- };
- class BinaryXor {
- public:
- inline BinaryXor() {}
- inline bool operator()(int a, int b) { return (a > 0) ^ (b > 0); }
- };
-
- //BinaryCount is an array of two deltaCounts coming from two different layers
- //of scan event data. It is the merged count of the two suitable for consumption
- //as the template argument of the BooleanOp algorithm because BinaryCount casts to int.
- //T is a binary functor object that evaluates the array of counts and returns a logical
- //result of some operation on those values.
- //BinaryCount supports many of the operators that work with int, particularly the
- //binary operators, but cannot support less than or increment.
- template <class T>
- class BinaryCount {
- public:
- inline BinaryCount() { counts_[0] = counts_[1] = 0; }
- // constructs from two integers
- inline BinaryCount(int countL, int countR) { counts_[0] = countL, counts_[1] = countR; }
- inline BinaryCount& operator=(int count) { counts_[0] = count, counts_[1] = count; }
- inline BinaryCount& operator=(const BinaryCount& that);
- inline BinaryCount(const BinaryCount& that) { *this = that; }
- inline bool operator==(const BinaryCount& that) const;
- inline bool operator!=(const BinaryCount& that) const { return !((*this) == that);}
- inline BinaryCount& operator+=(const BinaryCount& that);
- inline BinaryCount& operator-=(const BinaryCount& that);
- inline BinaryCount operator+(const BinaryCount& that) const;
- inline BinaryCount operator-(const BinaryCount& that) const;
- inline BinaryCount operator-() const;
- inline int& operator[](bool index) { return counts_[index]; }
-
- //cast to int operator evaluates data using T binary functor
- inline operator int() const { return T()(counts_[0], counts_[1]); }
- private:
- int counts_[2];
- };
-
- template <class T, typename Unit>
- inline BooleanOp<T, Unit>& BooleanOp<T, Unit>::operator=(const BooleanOp& that) {
- scanData_ = that.scanData_;
- nextItr_ = scanData_.begin();
- nullT_ = that.nullT_;
- return *this;
- }
-
- //appends output edges to cT
- template <class T, typename Unit>
- template <class cT>
- inline void BooleanOp<T, Unit>::processInterval(cT& outputContainer, interval_data<Unit> ivl, T deltaCount) {
- typename ScanData::iterator lowItr = lookup_(ivl.low());
- typename ScanData::iterator highItr = lookup_(ivl.high());
- //add interval to scan data if it is past the end
- if(lowItr == scanData_.end()) {
- lowItr = insert_(ivl.low(), deltaCount);
- highItr = insert_(ivl.high(), nullT_);
- evaluateInterval_(outputContainer, ivl, nullT_, deltaCount);
- return;
- }
- //ensure that highItr points to the end of the ivl
- if(highItr == scanData_.end() || (*highItr).first > ivl.high()) {
- T value = nullT_;
- if(highItr != scanData_.begin()) {
- --highItr;
- value = highItr->second;
- }
- nextItr_ = highItr;
- highItr = insert_(ivl.high(), value);
- }
- //split the low interval if needed
- if(lowItr->first > ivl.low()) {
- if(lowItr != scanData_.begin()) {
- --lowItr;
- nextItr_ = lowItr;
- lowItr = insert_(ivl.low(), lowItr->second);
- } else {
- nextItr_ = lowItr;
- lowItr = insert_(ivl.low(), nullT_);
- }
- }
- //process scan data intersecting interval
- for(typename ScanData::iterator itr = lowItr; itr != highItr; ){
- T beforeCount = itr->second;
- T afterCount = itr->second += deltaCount;
- Unit low = itr->first;
- ++itr;
- Unit high = itr->first;
- evaluateInterval_(outputContainer, interval_data<Unit>(low, high), beforeCount, afterCount);
- }
- //merge the bottom interval with the one below if they have the same count
- if(lowItr != scanData_.begin()){
- typename ScanData::iterator belowLowItr = lowItr;
- --belowLowItr;
- if(belowLowItr->second == lowItr->second) {
- scanData_.erase(lowItr);
- }
- }
- //merge the top interval with the one above if they have the same count
- if(highItr != scanData_.begin()) {
- typename ScanData::iterator beforeHighItr = highItr;
- --beforeHighItr;
- if(beforeHighItr->second == highItr->second) {
- scanData_.erase(highItr);
- highItr = beforeHighItr;
- ++highItr;
- }
- }
- nextItr_ = highItr;
- }
-
- template <class T, typename Unit>
- template <class cT>
- inline void BooleanOp<T, Unit>::evaluateInterval_(cT& outputContainer, interval_data<Unit> ivl,
- T beforeCount, T afterCount) {
- bool before = (int)beforeCount > 0;
- bool after = (int)afterCount > 0;
- int value = (!before & after) - (before & !after);
- if(value) {
- outputContainer.insert(outputContainer.end(), std::pair<interval_data<Unit>, int>(ivl, value));
- }
- }
-
- template <class T>
- inline BinaryCount<T>& BinaryCount<T>::operator=(const BinaryCount<T>& that) {
- counts_[0] = that.counts_[0];
- counts_[1] = that.counts_[1];
- return *this;
- }
- template <class T>
- inline bool BinaryCount<T>::operator==(const BinaryCount<T>& that) const {
- return counts_[0] == that.counts_[0] &&
- counts_[1] == that.counts_[1];
- }
- template <class T>
- inline BinaryCount<T>& BinaryCount<T>::operator+=(const BinaryCount<T>& that) {
- counts_[0] += that.counts_[0];
- counts_[1] += that.counts_[1];
- return *this;
- }
- template <class T>
- inline BinaryCount<T>& BinaryCount<T>::operator-=(const BinaryCount<T>& that) {
- counts_[0] += that.counts_[0];
- counts_[1] += that.counts_[1];
- return *this;
- }
- template <class T>
- inline BinaryCount<T> BinaryCount<T>::operator+(const BinaryCount<T>& that) const {
- BinaryCount retVal(*this);
- retVal += that;
- return retVal;
- }
- template <class T>
- inline BinaryCount<T> BinaryCount<T>::operator-(const BinaryCount<T>& that) const {
- BinaryCount retVal(*this);
- retVal -= that;
- return retVal;
- }
- template <class T>
- inline BinaryCount<T> BinaryCount<T>::operator-() const {
- return BinaryCount<T>() - *this;
- }
-
- //self contained unit test for BooleanOr algorithm
- template <typename Unit>
- inline bool testBooleanOr() {
- BooleanOp<int, Unit> booleanOr;
- //test one rectangle
- std::vector<std::pair<interval_data<Unit>, int> > container;
- booleanOr.processInterval(container, interval_data<Unit>(0, 10), 1);
- booleanOr.advanceScan();
- booleanOr.processInterval(container, interval_data<Unit>(0, 10), -1);
- if(container.size() != 2) {
- std::cout << "Test one rectangle, wrong output size\n";
- return false;
- }
- if(container[0] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 10), 1)) {
- std::cout << "Test one rectangle, first output wrong: Interval(" <<
- container[0].first << "), " << container[0].second << std::endl;
- }
- if(container[1] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 10), -1)) {
- std::cout << "Test one rectangle, second output wrong: Interval(" <<
- container[1].first << "), " << container[1].second << std::endl;
- }
-
- //test two rectangles
- container.clear();
- booleanOr = BooleanOp<int, Unit>();
- booleanOr.processInterval(container, interval_data<Unit>(0, 10), 1);
- booleanOr.advanceScan();
- booleanOr.processInterval(container, interval_data<Unit>(5, 15), 1);
- booleanOr.advanceScan();
- booleanOr.processInterval(container, interval_data<Unit>(0, 10), -1);
- booleanOr.advanceScan();
- booleanOr.processInterval(container, interval_data<Unit>(5, 15), -1);
- if(container.size() != 4) {
- std::cout << "Test two rectangles, wrong output size\n";
- for(unsigned int i = 0; i < container.size(); ++i){
- std::cout << container[i].first << "), " << container[i].second << std::endl;
- }
- return false;
- }
- if(container[0] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 10), 1)) {
- std::cout << "Test two rectangles, first output wrong: Interval(" <<
- container[0].first << "), " << container[0].second << std::endl;
- }
- if(container[1] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(10, 15), 1)) {
- std::cout << "Test two rectangles, second output wrong: Interval(" <<
- container[1].first << "), " << container[1].second << std::endl;
- }
- if(container[2] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 5), -1)) {
- std::cout << "Test two rectangles, third output wrong: Interval(" <<
- container[2].first << "), " << container[2].second << std::endl;
- }
- if(container[3] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(5, 15), -1)) {
- std::cout << "Test two rectangles, fourth output wrong: Interval(" <<
- container[3].first << "), " << container[3].second << std::endl;
- }
-
- //test two rectangles
- container.clear();
- booleanOr = BooleanOp<int, Unit>();
- booleanOr.processInterval(container, interval_data<Unit>(5, 15), 1);
- booleanOr.advanceScan();
- booleanOr.processInterval(container, interval_data<Unit>(0, 10), 1);
- booleanOr.advanceScan();
- booleanOr.processInterval(container, interval_data<Unit>(5, 15), -1);
- booleanOr.advanceScan();
- booleanOr.processInterval(container, interval_data<Unit>(0, 10), -1);
- if(container.size() != 4) {
- std::cout << "Test other two rectangles, wrong output size\n";
- for(unsigned int i = 0; i < container.size(); ++i){
- std::cout << container[i].first << "), " << container[i].second << std::endl;
- }
- return false;
- }
- if(container[0] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(5, 15), 1)) {
- std::cout << "Test other two rectangles, first output wrong: Interval(" <<
- container[0].first << "), " << container[0].second << std::endl;
- }
- if(container[1] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 5), 1)) {
- std::cout << "Test other two rectangles, second output wrong: Interval(" <<
- container[1].first << "), " << container[1].second << std::endl;
- }
- if(container[2] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(10, 15), -1)) {
- std::cout << "Test other two rectangles, third output wrong: Interval(" <<
- container[2].first << "), " << container[2].second << std::endl;
- }
- if(container[3] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 10), -1)) {
- std::cout << "Test other two rectangles, fourth output wrong: Interval(" <<
- container[3].first << "), " << container[3].second << std::endl;
- }
-
- //test two nonoverlapping rectangles
- container.clear();
- booleanOr = BooleanOp<int, Unit>();
- booleanOr.processInterval(container, interval_data<Unit>(0, 10), 1);
- booleanOr.advanceScan();
- booleanOr.processInterval(container, interval_data<Unit>(15, 25), 1);
- booleanOr.advanceScan();
- booleanOr.processInterval(container, interval_data<Unit>(0, 10), -1);
- booleanOr.advanceScan();
- booleanOr.processInterval(container, interval_data<Unit>(15, 25), -1);
- if(container.size() != 4) {
- std::cout << "Test two nonoverlapping rectangles, wrong output size\n";
- return false;
- }
- if(container[0] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 10), 1)) {
- std::cout << "Test two nonoverlapping rectangles, first output wrong: Interval(" <<
- container[0].first << "), " << container[0].second << std::endl;
- }
- if(container[1] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(15, 25), 1)) {
- std::cout << "Test two nonoverlapping rectangles, second output wrong: Interval(" <<
- container[1].first << "), " << container[1].second << std::endl;
- }
- if(container[2] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(0, 10), -1)) {
- std::cout << "Test two nonoverlapping rectangles, third output wrong: Interval(" <<
- container[2].first << "), " << container[2].second << std::endl;
- }
- if(container[3] != std::pair<interval_data<Unit>, int>(interval_data<Unit>(15, 25), -1)) {
- std::cout << "Test two nonoverlapping rectangles, fourth output wrong: Interval(" <<
- container[3].first << "), " << container[3].second << std::endl;
- }
- return true;
- }
-
- template <class T, typename Unit>
- inline void applyBooleanBinaryOp(std::vector<std::pair<Unit, std::pair<Unit, int> > >& output,
- const std::vector<std::pair<Unit, std::pair<Unit, int> > >& input1,
- const std::vector<std::pair<Unit, std::pair<Unit, int> > >& input2,
- T defaultCount) {
- BooleanOp<T, Unit> boolean(defaultCount);
- typename std::vector<std::pair<Unit, std::pair<Unit, int> > >::const_iterator itr1 = input1.begin();
- typename std::vector<std::pair<Unit, std::pair<Unit, int> > >::const_iterator itr2 = input2.begin();
- std::vector<std::pair<interval_data<Unit>, int> > container;
- output.reserve(max(input1.size(), input2.size()));
-
- //consider eliminating dependecy on limits with bool flag for initial state
- Unit UnitMax = std::numeric_limits<Unit>::max();
- Unit prevCoord = UnitMax;
- Unit prevPosition = UnitMax;
- T count(defaultCount);
- //define the starting point
- if(itr1 != input1.end()) {
- prevCoord = (*itr1).first;
- prevPosition = (*itr1).second.first;
- count[0] += (*itr1).second.second;
- }
- if(itr2 != input2.end()) {
- if((*itr2).first < prevCoord ||
- ((*itr2).first == prevCoord && (*itr2).second.first < prevPosition)) {
- prevCoord = (*itr2).first;
- prevPosition = (*itr2).second.first;
- count = defaultCount;
- count[1] += (*itr2).second.second;
- ++itr2;
- } else if((*itr2).first == prevCoord && (*itr2).second.first == prevPosition) {
- count[1] += (*itr2).second.second;
- ++itr2;
- if(itr1 != input1.end())++itr1;
- } else {
- if(itr1 != input1.end())++itr1;
- }
- } else {
- if(itr1 != input1.end())++itr1;
- }
-
- while(itr1 != input1.end() || itr2 != input2.end()) {
- Unit curCoord = UnitMax;
- Unit curPosition = UnitMax;
- T curCount(defaultCount);
- if(itr1 != input1.end()) {
- curCoord = (*itr1).first;
- curPosition = (*itr1).second.first;
- curCount[0] += (*itr1).second.second;
- }
- if(itr2 != input2.end()) {
- if((*itr2).first < curCoord ||
- ((*itr2).first == curCoord && (*itr2).second.first < curPosition)) {
- curCoord = (*itr2).first;
- curPosition = (*itr2).second.first;
- curCount = defaultCount;
- curCount[1] += (*itr2).second.second;
- ++itr2;
- } else if((*itr2).first == curCoord && (*itr2).second.first == curPosition) {
- curCount[1] += (*itr2).second.second;
- ++itr2;
- if(itr1 != input1.end())++itr1;
- } else {
- if(itr1 != input1.end())++itr1;
- }
- } else {
- ++itr1;
- }
-
- if(prevCoord != curCoord) {
- boolean.advanceScan();
- prevCoord = curCoord;
- prevPosition = curPosition;
- count = curCount;
- continue;
- }
- if(curPosition != prevPosition && count != defaultCount) {
- interval_data<Unit> ivl(prevPosition, curPosition);
- container.clear();
- boolean.processInterval(container, ivl, count);
- for(unsigned int i = 0; i < container.size(); ++i) {
- std::pair<interval_data<Unit>, int>& element = container[i];
- if(!output.empty() && output.back().first == prevCoord &&
- output.back().second.first == element.first.low() &&
- output.back().second.second == element.second * -1) {
- output.pop_back();
- } else {
- output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevCoord, std::pair<Unit, int>(element.first.low(),
- element.second)));
- }
- output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevCoord, std::pair<Unit, int>(element.first.high(),
- element.second * -1)));
- }
- }
- prevPosition = curPosition;
- count += curCount;
- }
- }
-
- template <class T, typename Unit>
- inline void applyBooleanBinaryOp(std::vector<std::pair<Unit, std::pair<Unit, int> > >& inputOutput,
- const std::vector<std::pair<Unit, std::pair<Unit, int> > >& input2,
- T defaultCount) {
- std::vector<std::pair<Unit, std::pair<Unit, int> > > output;
- applyBooleanBinaryOp(output, inputOutput, input2, defaultCount);
- if(output.size() < inputOutput.size() / 2) {
- inputOutput = std::vector<std::pair<Unit, std::pair<Unit, int> > >();
- } else {
- inputOutput.clear();
- }
- inputOutput.insert(inputOutput.end(), output.begin(), output.end());
- }
-
- template <typename Unit>
- inline void applyBooleanOr(std::vector<std::pair<Unit, std::pair<Unit, int> > >& input) {
- BooleanOp<int, Unit> booleanOr;
- std::vector<std::pair<interval_data<Unit>, int> > container;
- std::vector<std::pair<Unit, std::pair<Unit, int> > > output;
- output.reserve(input.size());
- //consider eliminating dependecy on limits with bool flag for initial state
- Unit UnitMax = std::numeric_limits<Unit>::max();
- Unit prevPos = UnitMax;
- Unit prevY = UnitMax;
- int count = 0;
- for(typename std::vector<std::pair<Unit, std::pair<Unit, int> > >::iterator itr = input.begin();
- itr != input.end(); ++itr) {
- Unit pos = (*itr).first;
- Unit y = (*itr).second.first;
- if(pos != prevPos) {
- booleanOr.advanceScan();
- prevPos = pos;
- prevY = y;
- count = (*itr).second.second;
- continue;
- }
- if(y != prevY && count != 0) {
- interval_data<Unit> ivl(prevY, y);
- container.clear();
- booleanOr.processInterval(container, ivl, count);
- for(unsigned int i = 0; i < container.size(); ++i) {
- std::pair<interval_data<Unit>, int>& element = container[i];
- if(!output.empty() && output.back().first == prevPos &&
- output.back().second.first == element.first.low() &&
- output.back().second.second == element.second * -1) {
- output.pop_back();
- } else {
- output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevPos, std::pair<Unit, int>(element.first.low(),
- element.second)));
- }
- output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevPos, std::pair<Unit, int>(element.first.high(),
- element.second * -1)));
- }
- }
- prevY = y;
- count += (*itr).second.second;
- }
- if(output.size() < input.size() / 2) {
- input = std::vector<std::pair<Unit, std::pair<Unit, int> > >();
- } else {
- input.clear();
- }
- input.insert(input.end(), output.begin(), output.end());
- }
-
-};
Deleted: sandbox/gtl/gtl/geometry_traits.h
==============================================================================
--- sandbox/gtl/gtl/geometry_traits.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,95 +0,0 @@
-/*
- 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).
-*/
-struct no_type {};
-
-template <typename T>
-struct geometry_traits {
- typedef no_type geometry_concept;
-};
-
-template <>
-struct geometry_traits<point_data<int> > {
- typedef point_concept geometry_concept;
-};
-template <>
-struct geometry_traits<point_data<long long> > {
- typedef point_concept geometry_concept;
-};
-template <>
-struct geometry_traits<rectangle_data<int> > {
- typedef rectangle_concept geometry_concept;
-};
-template <>
-struct geometry_traits<rectangle_data<long long> > {
- typedef rectangle_concept geometry_concept;
-};
-template <>
-struct geometry_traits<interval_data<int> > {
- typedef interval_concept geometry_concept;
-};
-template <>
-struct geometry_traits<interval_data<long long> > {
- typedef interval_concept geometry_concept;
-};
-template <>
-struct geometry_traits<point_3d_data<int> > {
- typedef point_3d_concept geometry_concept;
-};
-template <>
-struct geometry_traits<point_3d_data<long long> > {
- typedef point_3d_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_data<int> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_data<long long> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_with_holes_data<int> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_with_holes_data<long long> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template<>
-struct geometry_traits<polygon_formation::PolyLinePolygonData<true, int> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template<>
-struct geometry_traits<polygon_formation::PolyLinePolygonData<false, int> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template<>
-struct geometry_traits<polygon_formation::PolyLinePolygonData<true, long long> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template<>
-struct geometry_traits<polygon_formation::PolyLinePolygonData<false, long long> > {
- typedef polygon_with_holes_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_formation::PolyLineHoleData<true, int> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_formation::PolyLineHoleData<false, int> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_formation::PolyLineHoleData<true, long long> > {
- typedef polygon_concept geometry_concept;
-};
-template <>
-struct geometry_traits<polygon_formation::PolyLineHoleData<false, long long> > {
- typedef polygon_concept geometry_concept;
-};
-
Deleted: sandbox/gtl/gtl/gtl.h
==============================================================================
--- sandbox/gtl/gtl/gtl.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,198 +0,0 @@
-/*
- 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).
-*/
-//external
-#include <vector>
-#include <deque>
-#include <map>
-#include <set>
-#include <list>
-#include <iostream>
-#include <algorithm>
-#include <limits>
-#include <iterator>
-
-//isotropy types
-#include "isotropy.h"
-
-//data types
-#include "point_data.h"
-#include "interval_data.h"
-#include "rectangle_data.h"
-#include "point_3d_data.h"
-#include "polygon_data.h"
-#include "polygon_with_holes_data.h"
-
-//traits types
-#include "point_traits.h"
-#include "interval_traits.h"
-#include "rectangle_traits.h"
-#include "point_3d_traits.h"
-#include "polygon_traits.h"
-#include "polygon_with_holes_traits.h"
-
-//concept types
-#include "point_concept.h"
-#include "interval_concept.h"
-#include "rectangle_concept.h"
-#include "point_3d_concept.h"
-
-//algorithms needed by polygon concepts
-#include "iterator_points_to_compact.h"
-#include "iterator_compact_to_points.h"
-
-//polygon concept types
-#include "polygon_concept.h"
-#include "polygon_with_holes_concept.h"
-
-//definitions
-#include "post_concept_definitions.h"
-
-//manhattan boolean op algorithms
-#include "boolean_op.h"
-#include "polygon_formation.h"
-#include "rectangle_formation.h"
-#include "iterator_vertex_orient_conversion.h"
-#include "iterator_geometry_to_set.h"
-
-//polygon set data types
-#include "polygon_set_data.h"
-//polygon set trait types
-#include "polygon_set_traits.h"
-//polygon set concepts
-#include "polygon_set_view.h"
-//geometry traits
-#include "geometry_traits.h"
-
-#include "polygon_set_wrapper.h"
-
-//defintions
-#include "post_geometry_traits_definitions.h"
-
-
-
-
-template <typename geometry_type_1, typename geometry_type_2>
-bool contains(const geometry_type_1& geometry_object, const geometry_type_2& contained_geometry_object,
- bool consider_touch = true) {
- return typename geometry_traits<geometry_type_1>::geometry_concept().contains(geometry_object, contained_geometry_object,
- consider_touch, typename geometry_traits<geometry_type_2>::geometry_concept());
-}
-
-template <typename geometry_type_1, typename geometry_type_2>
-bool equivalence(const geometry_type_1& lvalue, const geometry_type_2& rvalue) {
- typename geometry_traits<geometry_type_1>::geometry_concept concept_instantiation;
- return concept_instantiation.equivalence(lvalue, rvalue);
-}
-
-template <typename geometry_type>
-typename component_type<geometry_type>::type
-get(const geometry_type& geometry_object, orientation_2d orient) {
- return geometry_traits<geometry_type>::geometry_concept::get(geometry_object, orient);
-}
-
-template <typename geometry_type>
-typename component_type<geometry_type>::type
-get(const geometry_type& geometry_object, orientation_3d orient) {
- return geometry_traits<geometry_type>::geometry_concept::get(geometry_object, orient);
-}
-
-template <typename geometry_type_1, typename geometry_type_2>
-geometry_type_1& assign(geometry_type_1& lvalue, geometry_type_2& rvalue) {
- return geometry_traits<geometry_type_1>::geometry_concept::assign(lvalue, rvalue);
-}
-
-template <typename geometry_type_1, typename geometry_type_2>
-polygon_set_view<typename geometry_type_1::operator_arg_type,
- typename geometry_type_2::operator_arg_type,
- boolean_op::BinaryOr,
- typename geometry_type_1::operator_storage_tag,
- typename geometry_type_2::operator_storage_tag>
-operator|(const geometry_type_1& lvalue, const geometry_type_2& rvalue) {
- return polygon_set_view<geometry_type_1, geometry_type_2,
- boolean_op::BinaryOr,
- typename geometry_type_1::operator_storage_tag,
- typename geometry_type_2::operator_storage_tag>(lvalue, rvalue,
- polygon_set_traits<geometry_type_1>::orient(lvalue),
- boolean_op::BinaryOr());
-}
-
-template <typename geometry_type_1, typename geometry_type_2>
-polygon_set_view<typename geometry_type_1::operator_arg_type,
- typename geometry_type_2::operator_arg_type,
- boolean_op::BinaryOr,
- typename geometry_type_1::operator_storage_tag,
- typename geometry_type_2::operator_storage_tag>
-operator+(const geometry_type_1& lvalue, const geometry_type_2& rvalue) {
- return polygon_set_view<geometry_type_1, geometry_type_2,
- boolean_op::BinaryOr,
- typename geometry_type_1::operator_storage_tag,
- typename geometry_type_2::operator_storage_tag>(lvalue, rvalue,
- polygon_set_traits<geometry_type_1>::orient(lvalue),
- boolean_op::BinaryOr());
-}
-
-template <typename geometry_type_1, typename geometry_type_2>
-polygon_set_view<typename geometry_type_1::operator_arg_type,
- typename geometry_type_2::operator_arg_type,
- boolean_op::BinaryAnd,
- typename geometry_type_1::operator_storage_tag,
- typename geometry_type_2::operator_storage_tag>
-operator*(const geometry_type_1& lvalue, const geometry_type_2& rvalue) {
- return polygon_set_view<geometry_type_1, geometry_type_2,
- boolean_op::BinaryAnd,
- typename geometry_type_1::operator_storage_tag,
- typename geometry_type_2::operator_storage_tag>(lvalue, rvalue,
- polygon_set_traits<geometry_type_1>::orient(lvalue),
- boolean_op::BinaryAnd());
-}
-
-template <typename geometry_type_1, typename geometry_type_2>
-polygon_set_view<typename geometry_type_1::operator_arg_type,
- typename geometry_type_2::operator_arg_type,
- boolean_op::BinaryAnd,
- typename geometry_type_1::operator_storage_tag,
- typename geometry_type_2::operator_storage_tag>
-operator&(const geometry_type_1& lvalue, const geometry_type_2& rvalue) {
- return polygon_set_view<geometry_type_1, geometry_type_2,
- boolean_op::BinaryAnd,
- typename geometry_type_1::operator_storage_tag,
- typename geometry_type_2::operator_storage_tag>(lvalue, rvalue,
- polygon_set_traits<geometry_type_1>::orient(lvalue),
- boolean_op::BinaryAnd());
-}
-
-template <typename geometry_type_1, typename geometry_type_2>
-polygon_set_view<typename geometry_type_1::operator_arg_type,
- typename geometry_type_2::operator_arg_type,
- boolean_op::BinaryXor,
- typename geometry_type_1::operator_storage_tag,
- typename geometry_type_2::operator_storage_tag>
-operator^(const geometry_type_1& lvalue, const geometry_type_2& rvalue) {
- return polygon_set_view<geometry_type_1, geometry_type_2,
- boolean_op::BinaryXor,
- typename geometry_type_1::operator_storage_tag,
- typename geometry_type_2::operator_storage_tag>(lvalue, rvalue,
- polygon_set_traits<geometry_type_1>::orient(lvalue),
- boolean_op::BinaryXor());
-}
-
-template <typename geometry_type_1, typename geometry_type_2>
-polygon_set_view<typename geometry_type_1::operator_arg_type,
- typename geometry_type_2::operator_arg_type,
- boolean_op::BinaryNot,
- typename geometry_type_1::operator_storage_tag,
- typename geometry_type_2::operator_storage_tag>
-operator-(const geometry_type_1& lvalue, const geometry_type_2& rvalue) {
- return polygon_set_view<geometry_type_1, geometry_type_2,
- boolean_op::BinaryNot,
- typename geometry_type_1::operator_storage_tag,
- typename geometry_type_2::operator_storage_tag>(lvalue, rvalue,
- polygon_set_traits<geometry_type_1>::orient(lvalue),
- boolean_op::BinaryNot());
-}
-
Deleted: sandbox/gtl/gtl/interval_concept.h
==============================================================================
--- sandbox/gtl/gtl/interval_concept.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,82 +0,0 @@
-/*
- 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).
-*/
-struct interval_concept {
- interval_concept() {}
-
- template <direction_1d_enum dir, typename T>
- static inline typename interval_traits<T>::coordinate_type
- get(const T& interval) {
- return interval_traits<T>::get(interval, dir);
- }
-
- template <typename T>
- static inline typename interval_traits<T>::coordinate_type
- get(const T& interval, direction_1d dir) {
- return interval_traits<T>::get(interval, dir);
- }
-
- template <direction_1d_enum dir, typename T, typename coordinate_type>
- static inline void set(T& interval, coordinate_type value) {
- set(interval, dir, value);
- }
-
- template <typename T, typename coordinate_type>
- static inline void set(T& interval, direction_1d dir, coordinate_type value) {
- interval_traits<T>::set(interval, dir, value);
- if(get<HIGH>(interval) < get<LOW>(interval))
- interval_traits<T>::set(interval, dir.backward(), value);
- }
-
- template <typename T, typename coordinate_type1, typename coordinate_type2>
- static inline T construct(coordinate_type1 low_value, coordinate_type2 high_value) {
- if(low_value > high_value) std::swap(low_value, high_value);
- return interval_traits<T>::construct(low_value, high_value);
- }
-
- template <typename T, typename T2>
- static T copy_construct(const T2& interval) {
- return construct<T>
- (get(interval, LOW ),
- get(interval, HIGH));
- }
-
- template <typename interval_type_1, typename interval_type_2>
- static interval_type_1& assign(interval_type_1& lvalue, const interval_type_2& rvalue) {
- set(lvalue, LOW, get(rvalue, LOW));
- set(lvalue, HIGH, get(rvalue, HIGH));
- return lvalue;
- }
-
- template <typename T, typename T2>
- static bool equivalence(const T& interval1, const T2& interval2) {
- return get(interval1, LOW) ==
- get(interval2, LOW) &&
- get(interval1, HIGH) ==
- get(interval2, HIGH);
- }
-
- template <typename interval_type>
- static bool contains(const interval_type& interval,
- typename interval_traits<interval_type>::coordinate_type value, bool consider_touch) {
- if(consider_touch) {
- return value <= get<HIGH>(interval) && value >= get<LOW>(interval);
- } else {
- return value < get<HIGH>(interval) && value > get<LOW>(interval);
- }
- }
-
- template <typename interval_type, typename interval_type_2>
- static bool contains(const interval_type& interval,
- const interval_type_2& value, bool consider_touch, interval_concept tag) {
- return contains(interval, get(value, LOW), consider_touch) &&
- contains(interval, get(value, HIGH), consider_touch);
- }
-
-};
-
-
Deleted: sandbox/gtl/gtl/interval_data.h
==============================================================================
--- sandbox/gtl/gtl/interval_data.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,45 +0,0 @@
-/*
- 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).
-*/
-template <typename T>
-class interval_data {
-public:
- typedef T coordinate_type;
- inline interval_data(){}
- inline interval_data(coordinate_type low, coordinate_type high) {
- coords_[LOW] = low; coords_[HIGH] = high;
- }
- inline interval_data(const interval_data& that) {
- (*this) = that;
- }
- inline interval_data& operator=(const interval_data& that) {
- coords_[0] = that.coords_[0]; coords_[1] = that.coords_[1]; return *this;
- }
- template <typename T2>
- inline interval_data& operator=(const T2& rvalue);
- inline coordinate_type get(direction_1d dir) const {
- return coords_[dir.to_int()];
- }
- inline coordinate_type low() const { return coords_[0]; }
- inline coordinate_type high() const { return coords_[1]; }
- inline bool operator==(const interval_data& that) const {
- return low() == that.low() && high() == that.high(); }
- inline bool operator!=(const interval_data& that) const {
- return low() != that.low() || high() != that.high(); }
- inline void set(direction_1d dir, coordinate_type value) {
- coords_[dir.to_int()] = value;
- }
-private:
- coordinate_type coords_[2];
-};
-
-
-template <class T>
-std::ostream& operator << (std::ostream& o, const interval_data<T>& i)
-{
- return o << i.get(LOW) << ' ' << i.get(HIGH);
-}
Deleted: sandbox/gtl/gtl/interval_traits.h
==============================================================================
--- sandbox/gtl/gtl/interval_traits.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,24 +0,0 @@
-/*
- 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).
-*/
-template <typename T>
-struct interval_traits {
- typedef typename T::coordinate_type coordinate_type;
-
- static inline coordinate_type get(const T& interval, direction_1d dir) {
- return interval.get(dir);
- }
-
- static inline void set(T& interval, direction_1d dir, coordinate_type value) {
- interval.set(dir, value);
- }
-
- static inline T construct(coordinate_type low_value, coordinate_type high_value) {
- return T(low_value, high_value);
- }
-};
-
Deleted: sandbox/gtl/gtl/isotropy.h
==============================================================================
--- sandbox/gtl/gtl/isotropy.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,142 +0,0 @@
-/*
- 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).
-*/
-enum direction_1d_enum { LOW = 0, HIGH = 1 };
-enum orientation_2d_enum { HORIZONTAL = 0, VERTICAL = 1 };
-enum direction_2d_enum { WEST = 0, EAST = 1, SOUTH = 2, NORTH = 3 };
-enum orientation_3d_enum { PROXIMAL = 2 };
-enum winding_direction {
- counterclockwise_winding = 0,
- clockwise_winding = 1,
- unknown_winding = 2
-};
-
-class direction_2d;
-class orientation_2d;
-
-class direction_1d {
-private:
- unsigned int val_;
- explicit direction_1d(int d);
-public:
- direction_1d() { val_ = LOW; }
- direction_1d(const direction_1d& that) : val_(that.val_) {}
- direction_1d(const direction_1d_enum val) : val_(val) {}
- explicit direction_1d(const direction_2d& that);
- const direction_1d& operator = (const direction_1d& d) {
- val_ = d.val_; return * this; }
- bool operator==(direction_1d d) const { return (val_ == d.val_); }
- bool operator!=(direction_1d d) const { return !((*this) == d); }
- unsigned int to_int(void) const { return val_; }
- direction_1d& backward() { val_ ^= 1; return *this; }
-};
-
-class direction_2d;
-
-class orientation_2d {
-private:
- unsigned int val_;
- explicit orientation_2d(int o);
-public:
- orientation_2d() : val_(HORIZONTAL) {}
- orientation_2d(const orientation_2d& ori) : val_(ori.val_) {}
- orientation_2d(const orientation_2d_enum val) : val_(val) {}
- explicit orientation_2d(const direction_2d& that);
- const orientation_2d& operator=(const orientation_2d& ori) {
- val_ = ori.val_; return * this; }
- bool operator==(orientation_2d that) const { return (val_ == that.val_); }
- bool operator!=(orientation_2d that) const { return (val_ != that.val_); }
- unsigned int to_int() const { return (val_); }
- void turn_90() { val_ = val_^ 1; }
- orientation_2d get_perpendicular() const {
- orientation_2d retval = *this;
- retval.turn_90();
- return retval;
- }
- direction_2d get_direction(direction_1d dir) const;
-};
-
-class direction_2d {
-private:
- int val_;
-
-public:
-
- direction_2d() { val_ = WEST; }
-
- direction_2d(const direction_2d& that) : val_(that.val_) {}
-
- direction_2d(const direction_2d_enum val) : val_(val) {}
-
- const direction_2d& operator=(const direction_2d& d) {
- val_ = d.val_;
- return * this;
- }
-
- ~direction_2d() { }
-
- bool operator==(direction_2d d) const { return (val_ == d.val_); }
- bool operator!=(direction_2d d) const { return !((*this) == d); }
- bool operator< (direction_2d d) const { return (val_ < d.val_); }
- bool operator<=(direction_2d d) const { return (val_ <= d.val_); }
- bool operator> (direction_2d d) const { return (val_ > d.val_); }
- bool operator>=(direction_2d d) const { return (val_ >= d.val_); }
-
- /// Casting to int
- unsigned int to_int(void) const { return val_; }
-
- direction_2d backward() const {
- // flip the LSB, toggles 0 - 1 and 2 - 3
- return direction_2d(direction_2d_enum(val_ ^ 1));
- }
-
- /// Returns a direction 90 degree left (LOW) or right(HIGH) to this one
- direction_2d turn(direction_1d t) const {
- return direction_2d(direction_2d_enum(val_ ^ 3 ^ (val_ >> 1) ^ t.to_int()));
- }
-
- /// Returns a direction 90 degree left to this one
- direction_2d left() const {return turn(HIGH);}
-
- /// Returns a direction 90 degree right to this one
- direction_2d right() const {return turn(LOW);}
-
- /// N, E are positive, S, W are negative
- bool is_positive() const {return (val_ & 1);}
- bool is_negative() const {return !is_positive();}
- int get_sign() const {return ((is_positive()) << 1) -1;}
-
-};
-
-direction_1d::direction_1d(const direction_2d& that) {
- val_ = that.to_int() & 1;
-}
-orientation_2d::orientation_2d(const direction_2d& that) {
- val_ = that.to_int() >> 1;
-}
-
-direction_2d orientation_2d::get_direction(direction_1d dir) const {
- return direction_2d(direction_2d_enum((val_ << 1) + dir.to_int()));
-}
-
-class orientation_3d {
-private:
- unsigned int val_;
- explicit orientation_3d(int o);
-public:
- orientation_3d() : val_((int)HORIZONTAL) {}
- orientation_3d(const orientation_3d& ori) : val_(ori.val_) {}
- orientation_3d(const orientation_2d& ori) { val_ = ori.to_int(); }
- orientation_3d(const orientation_3d_enum val) : val_(val) {}
- ~orientation_3d() { }
- const orientation_3d& operator=(const orientation_3d& ori) {
- val_ = ori.val_; return * this; }
- bool operator==(orientation_3d that) const { return (val_ == that.val_); }
- bool operator!=(orientation_3d that) const { return (val_ != that.val_); }
- unsigned int to_int() const { return (val_); }
-};
-
Deleted: sandbox/gtl/gtl/iterator_compact_to_points.h
==============================================================================
--- sandbox/gtl/gtl/iterator_compact_to_points.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,61 +0,0 @@
-/*
- 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).
-*/
-template <class iterator_type, class point_type>
-class iterator_compact_to_points {
-private:
- iterator_type iter_;
- iterator_type iter_end_;
- point_type pt_;
- typename point_traits<point_type>::coordinate_type firstX_;
- orientation_2d orient_;
-public:
- typedef std::forward_iterator_tag iterator_category;
- typedef point_type value_type;
- typedef std::ptrdiff_t difference_type;
- typedef const point_type* pointer; //immutable
- typedef const point_type& reference; //immutable
-
- inline iterator_compact_to_points() {}
- inline iterator_compact_to_points(iterator_type iter, iterator_type iter_end) :
- iter_(iter), iter_end_(iter_end), orient_(HORIZONTAL) {
- if(iter_ != iter_end_) {
- firstX_ = *iter_;
- point_concept::set<HORIZONTAL>(pt_, firstX_);
- ++iter_;
- if(iter_ != iter_end_) {
- point_concept::set<VERTICAL>(pt_, *iter_);
- }
- }
- }
- //use bitwise copy and assign provided by the compiler
- inline iterator_compact_to_points& operator++() {
- ++iter_;
- if(iter_ == iter_end_) {
- if(point_concept::get<HORIZONTAL>(pt_) != firstX_) {
- --iter_;
- point_concept::set<HORIZONTAL>(pt_, firstX_);
- }
- } else {
- point_concept::set(pt_, orient_, *iter_);
- orient_.turn_90();
- }
- return *this;
- }
- inline iterator_compact_to_points operator++(int) {
- iterator_compact_to_points tmp(*this);
- ++(*this);
- return tmp;
- }
- inline bool operator==(const iterator_compact_to_points& that) const {
- return (iter_ == that.iter_);
- }
- inline bool operator!=(const iterator_compact_to_points& that) const {
- return (iter_ != that.iter_);
- }
- inline reference operator*() const { return pt_; }
-};
Deleted: sandbox/gtl/gtl/iterator_geometry_to_set.h
==============================================================================
--- sandbox/gtl/gtl/iterator_geometry_to_set.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,309 +0,0 @@
-/*
- 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).
-*/
-template <typename concept_type, typename geometry_type>
-class iterator_geometry_to_set {};
-
-template <typename concept_type, typename iterator_type>
-class iterator_geometry_range_to_set {
- typedef typename iterator_type::value_type geometry_type;
- typedef iterator_geometry_to_set<concept_type, geometry_type> internal_iterator_type;
- typedef typename internal_iterator_type::value_type value_type;
- typedef std::forward_iterator_tag iterator_category;
- typedef std::ptrdiff_t difference_type;
- typedef const value_type* pointer; //immutable
- typedef const value_type& reference; //immutable
-private:
- iterator_type itr_;
- mutable internal_iterator_type itrb_, itre_;
- mutable bool dereferenced_;
- orientation_2d orient_;
-public:
- iterator_geometry_range_to_set(iterator_type itr,
- orientation_2d orient = HORIZONTAL) :
- itr_(itr), dereferenced_(false), orient_(orient) {}
-
- inline iterator_geometry_range_to_set& operator++() {
- if(!dereferenced_) **this;
- if(itrb_ == itre_) {
- ++itr_;
- dereferenced_ = false;
- } else {
- ++itrb_;
- if(itrb_ == itre_) {
- ++itr_;
- dereferenced_ = false;
- }
- }
- return *this;
- }
- inline iterator_geometry_range_to_set operator++(int) {
- iterator_geometry_range_to_set tmp(*this);
- ++(*this);
- return tmp;
- }
- inline bool operator==(const iterator_geometry_range_to_set& that) const {
- return (itr_ == that.itr_);
- }
- inline bool operator!=(const iterator_geometry_range_to_set& that) const {
- return !(*this == that);
- }
- inline reference operator*() const {
- if(!dereferenced_) {
- itrb_ = iterator_geometry_to_set<concept_type, geometry_type>(*itr_, LOW, orient_);
- itre_ = iterator_geometry_to_set<concept_type, geometry_type>(*itr_, HIGH, orient_);
- dereferenced_ = true;
- }
- return *itrb_;
- }
-};
-
-template <typename rectangle_type>
-class iterator_geometry_to_set<rectangle_concept, rectangle_type> {
-public:
- typedef typename rectangle_traits<rectangle_type>::coordinate_type coordinate_type;
- typedef std::forward_iterator_tag iterator_category;
- typedef std::pair<coordinate_type, std::pair<coordinate_type, int> > value_type;
- typedef std::ptrdiff_t difference_type;
- typedef const value_type* pointer; //immutable
- typedef const value_type& reference; //immutable
-private:
- rectangle_data<coordinate_type> rectangle_;
- mutable value_type vertex_;
- unsigned int corner_;
- orientation_2d orient_;
-public:
- iterator_geometry_to_set() : corner_(4) {}
- iterator_geometry_to_set(const rectangle_type& rectangle, direction_1d dir,
- orientation_2d orient = HORIZONTAL) : corner_(0), orient_(orient) {
- rectangle_concept::assign(rectangle_, rectangle);
- if(dir == HIGH) corner_ = 4;
- }
- inline iterator_geometry_to_set& operator++() {
- ++corner_;
- return *this;
- }
- inline iterator_geometry_to_set operator++(int) {
- iterator_geometry_to_set tmp(*this);
- ++(*this);
- return tmp;
- }
- inline bool operator==(const iterator_geometry_to_set& that) const {
- return corner_ == that.corner_;
- }
- inline bool operator!=(const iterator_geometry_to_set& that) const {
- return !(*this == that);
- }
- inline reference operator*() const {
- if(corner_ == 0) {
- vertex_.first = interval_concept::get(rectangle_concept::get(rectangle_, orient_.get_perpendicular()), LOW);
- vertex_.second.first = interval_concept::get(rectangle_concept::get(rectangle_, orient_), LOW);
- vertex_.second.second = 1;
- } else if(corner_ == 1) {
- vertex_.second.first = interval_concept::get(rectangle_concept::get(rectangle_, orient_), HIGH);
- vertex_.second.second = -1;
- } else if(corner_ == 2) {
- vertex_.first = interval_concept::get(rectangle_concept::get(rectangle_, orient_.get_perpendicular()), HIGH);
- vertex_.second.first = interval_concept::get(rectangle_concept::get(rectangle_, orient_), LOW);
- } else {
- vertex_.second.first = interval_concept::get(rectangle_concept::get(rectangle_, orient_), HIGH);
- vertex_.second.second = 1;
- }
- return vertex_;
- }
-};
-
-template <typename polygon_type>
-class iterator_geometry_to_set<polygon_concept, polygon_type> {
-public:
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- typedef std::forward_iterator_tag iterator_category;
- typedef std::pair<coordinate_type, std::pair<coordinate_type, int> > value_type;
- typedef std::ptrdiff_t difference_type;
- typedef const value_type* pointer; //immutable
- typedef const value_type& reference; //immutable
- typedef typename polygon_traits<polygon_type>::iterator_type coord_iterator_type;
-private:
- value_type vertex_;
- iterator_compact_to_points<typename polygon_traits<polygon_type>::iterator_type,
- point_data<typename polygon_traits<polygon_type>::coordinate_type> > itrb, itre;
- bool last_vertex_;
- bool is_hole_;
- int multiplier_;
- point_data<coordinate_type> first_pt, second_pt, pts[3];
- bool use_wrap;
- orientation_2d orient_;
- int polygon_index;
-public:
- iterator_geometry_to_set() : polygon_index(-1) {}
- iterator_geometry_to_set(const polygon_type& polygon, direction_1d dir, orientation_2d orient = HORIZONTAL, bool is_hole = false) :
- is_hole_(is_hole), orient_(orient), polygon_index(0) {
- itrb = polygon_concept::begin_points(polygon);
- itre = polygon_concept::end_points(polygon);
- use_wrap = false;
- if(itrb == itre || dir == HIGH || polygon_concept::size(polygon) < 4) {
- polygon_index = -1;
- } else {
- direction_1d wdir = polygon_concept::winding(polygon);
- multiplier_ = wdir == LOW ? -1 : 1;
- if(is_hole_) multiplier_ *= -1;
- first_pt = pts[0] = *itrb;
- ++itrb;
- second_pt = pts[1] = *itrb;
- ++itrb;
- pts[2] = *itrb;
- }
- evaluate_();
- }
-
- inline iterator_geometry_to_set& operator++() {
- ++polygon_index;
- if(itrb == itre) {
- if(first_pt == pts[1]) polygon_index = -1;
- else {
- pts[0] = pts[1];
- pts[1] = pts[2];
- if(first_pt == pts[2]) {
- pts[2] = second_pt;
- } else {
- pts[2] = first_pt;
- }
- }
- } else {
- ++itrb;
- pts[0] = pts[1];
- pts[1] = pts[2];
- if(itrb == itre) {
- if(first_pt == pts[2]) {
- pts[2] = second_pt;
- } else {
- pts[2] = first_pt;
- }
- } else {
- pts[2] = *itrb;
- }
- }
- evaluate_();
- return *this;
- }
- inline iterator_geometry_to_set operator++(int) {
- iterator_geometry_to_set tmp(*this);
- ++(*this);
- return tmp;
- }
- inline bool operator==(const iterator_geometry_to_set& that) const {
- return polygon_index == that.polygon_index;
- }
- inline bool operator!=(const iterator_geometry_to_set& that) const {
- return !(*this == that);
- }
- inline reference operator*() const {
- return vertex_;
- }
-
- inline void evaluate_() {
- vertex_.first = pts[1].get(orient_.get_perpendicular());
- vertex_.second.first =pts[1].get(orient_);
- if(pts[0].get(HORIZONTAL) != pts[1].get(HORIZONTAL)) {
- vertex_.second.second = -1;
- } else {
- vertex_.second.second = 1;
- }
- vertex_.second.second *= multiplier_;
- }
-};
-
-template <typename polygon_with_holes_type>
-class iterator_geometry_to_set<polygon_with_holes_concept, polygon_with_holes_type> {
-public:
- typedef typename rectangle_traits<polygon_with_holes_type>::coordinate_type coordinate_type;
- typedef std::forward_iterator_tag iterator_category;
- typedef std::pair<coordinate_type, std::pair<coordinate_type, int> > value_type;
- typedef std::ptrdiff_t difference_type;
- typedef const value_type* pointer; //immutable
- typedef const value_type& reference; //immutable
-private:
- iterator_geometry_to_set<polygon_concept, polygon_with_holes_type> itrb, itre;
- iterator_geometry_to_set<polygon_concept, typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type> itrhib, itrhie;
- typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type itrhb, itrhe;
- orientation_2d orient_;
- bool started_holes;
-public:
- iterator_geometry_to_set() {}
- iterator_geometry_to_set(const polygon_with_holes_type& polygon, direction_1d dir,
- orientation_2d orient = HORIZONTAL) : orient_(orient) {
- itre = iterator_geometry_to_set<polygon_concept, polygon_with_holes_type>(polygon, HIGH, orient);
- itrhe = polygon_with_holes_concept::end_holes(polygon);
- if(dir == HIGH) {
- itrb = itre;
- itrhb = itrhe;
- started_holes = true;
- } else {
- itrb = iterator_geometry_to_set<polygon_concept, polygon_with_holes_type>(polygon, LOW, orient);
- itrhb = polygon_with_holes_concept::begin_holes(polygon);
- started_holes = false;
- }
- }
- inline iterator_geometry_to_set& operator++() {
- //this code can be folded with flow control factoring
- if(itrb == itre) {
- if(itrhib == itrhie) {
- if(itrhb != itrhe) {
- itrhib = iterator_geometry_to_set<polygon_concept,
- typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, LOW, orient_, true);
- itrhie = iterator_geometry_to_set<polygon_concept,
- typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, HIGH, orient_, true);
- ++itrhb;
- } else {
- itrhib = itrhie = iterator_geometry_to_set<polygon_concept,
- typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>();
- }
- } else {
- ++itrhib;
- if(itrhib == itrhie) {
- if(itrhb != itrhe) {
- itrhib = iterator_geometry_to_set<polygon_concept,
- typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, LOW, orient_, true);
- itrhie = iterator_geometry_to_set<polygon_concept,
- typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, HIGH, orient_, true);
- ++itrhb;
- } else {
- itrhib = itrhie = iterator_geometry_to_set<polygon_concept,
- typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>();
- }
- }
- }
- } else {
- ++itrb;
- if(itrb == itre) {
- if(itrhb != itrhe) {
- itrhib = iterator_geometry_to_set<polygon_concept,
- typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, LOW, orient_, true);
- itrhie = iterator_geometry_to_set<polygon_concept,
- typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type>(*itrhb, HIGH, orient_, true);
- ++itrhb;
- }
- }
- }
- return *this;
- }
- inline iterator_geometry_to_set operator++(int) {
- iterator_geometry_to_set tmp(*this);
- ++(*this);
- return tmp;
- }
- inline bool operator==(const iterator_geometry_to_set& that) const {
- return itrb == that.itrb && itrhb == that.itrhb && itrhib == that.itrhib;
- }
- inline bool operator!=(const iterator_geometry_to_set& that) const {
- return !(*this == that);
- }
- inline reference operator*() const {
- if(itrb != itre) return *itrb;
- return *itrhib;
- }
-};
Deleted: sandbox/gtl/gtl/iterator_points_to_compact.h
==============================================================================
--- sandbox/gtl/gtl/iterator_points_to_compact.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,43 +0,0 @@
-/*
- 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).
-*/
-template <class iT, typename point_type>
-class iterator_points_to_compact {
-private:
- iT iter_;
- orientation_2d orient_;
-public:
- typedef typename point_traits<point_type>::coordinate_type coordinate_type;
- typedef std::forward_iterator_tag iterator_category;
- typedef coordinate_type value_type;
- typedef std::ptrdiff_t difference_type;
- typedef const coordinate_type* pointer; //immutable
- typedef const coordinate_type& reference; //immutable
-
- inline iterator_points_to_compact() {}
- inline iterator_points_to_compact(iT iter) : iter_(iter), orient_(HORIZONTAL) {}
- inline iterator_points_to_compact(const iterator_points_to_compact& that) :
- iter_(that.iter_), orient_(that.orient_) {}
- //use bitwise copy and assign provided by the compiler
- inline iterator_points_to_compact& operator++() {
- ++iter_;
- orient_.turn_90();
- return *this;
- }
- inline iterator_points_to_compact operator++(int) {
- iT tmp(*this);
- ++(*this);
- return tmp;
- }
- inline bool operator==(const iterator_points_to_compact& that) const {
- return (iter_ == that.iter_);
- }
- inline bool operator!=(const iterator_points_to_compact& that) const {
- return (iter_ != that.iter_);
- }
- inline reference operator*() const { return point_concept::get(*iter_, orient_); }
-};
Deleted: sandbox/gtl/gtl/iterator_vertex_orient_conversion.h
==============================================================================
--- sandbox/gtl/gtl/iterator_vertex_orient_conversion.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,45 +0,0 @@
-/*
- 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).
-*/
-template <typename iterator_type>
-class iterator_vertex_orient_conversion {
-private:
- iterator_type iter_;
- typename iterator_type::value_type vertex_;
-public:
- typedef std::forward_iterator_tag iterator_category;
- typedef typename iterator_type::value_type value_type;
- typedef std::ptrdiff_t difference_type;
- typedef const value_type* pointer; //immutable
- typedef const value_type& reference; //immutable
- typedef typename value_type::first_type coordinate_type;
-
- inline iterator_vertex_orient_conversion() {}
- inline iterator_vertex_orient_conversion(iterator_type iter) :
- iter_(iter) {}
- inline iterator_vertex_orient_conversion& operator++() {
- ++iter_;
- return *this;
- }
- inline iterator_vertex_orient_conversion operator++(int) {
- iterator_vertex_orient_conversion tmp(*this);
- ++(*this);
- return tmp;
- }
- inline bool operator==(const iterator_vertex_orient_conversion& that) const {
- return (iter_ == that.iter_);
- }
- inline bool operator!=(const iterator_vertex_orient_conversion& that) const {
- return (iter_ != that.iter_);
- }
- inline reference operator*() const {
- vertex_.first = (*iter_).second.first;
- vertex_.second = std::pair<coordinate_type, int>((*iter_).first, (*iter_).second.second);
- return vertex_;
- }
-};
-
Deleted: sandbox/gtl/gtl/point_3d_concept.h
==============================================================================
--- sandbox/gtl/gtl/point_3d_concept.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,48 +0,0 @@
-/*
- 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).
-*/
-struct point_3d_concept : point_concept {
- point_3d_concept() {}
-
- template <typename point_3d_type>
- struct registration {
- typedef typename point_3d_traits<point_3d_type>::coordinate_type component_type;
- };
-
- template <orientation_3d_enum orient, typename T>
- static inline typename point_3d_traits<T>::coordinate_type get(const T& point) {
- return point_3d_traits<T>::get(point, orient); }
-
- template <typename T>
- static inline typename point_3d_traits<T>::coordinate_type get(const T& point, orientation_3d orient) {
- return point_3d_traits<T>::get(point, orient); }
-
- template <orientation_3d_enum orient, typename T, typename coordinate_type>
- static inline void set(T& point, coordinate_type value) {
- point_traits<T>::set(point, orient, value); }
- template <typename T, typename coordinate_type>
- static inline void set(T& point, orientation_3d orient, coordinate_type value) {
- point_traits<T>::set(point, orient, value); }
-
- template <typename T, typename coordinate_type1, typename coordinate_type2, typename coordinate_type3>
- static inline T construct(coordinate_type1 x_value,
- coordinate_type2 y_value,
- coordinate_type3 z_value) {
- return point_3d_traits<T>::construct(x_value, y_value, z_value); }
-
- template <typename point_3d_type_1, typename point_3d_type_2>
- static point_3d_type_1& assign(point_3d_type_1& lvalue, const point_3d_type_2& rvalue) {
- set(lvalue, HORIZONTAL, get(rvalue, HORIZONTAL));
- set(lvalue, VERTICAL, get(rvalue, VERTICAL));
- set(lvalue, PROXIMAL, get(rvalue, PROXIMAL));
- return lvalue;
- }
-
-
-};
-
-
Deleted: sandbox/gtl/gtl/point_3d_data.h
==============================================================================
--- sandbox/gtl/gtl/point_3d_data.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,30 +0,0 @@
-/*
- 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).
-*/
-template <typename T>
-class point_3d_data {
-public:
- typedef T coordinate_type;
- inline point_3d_data(){}
- inline point_3d_data(coordinate_type x, coordinate_type y) {
- coords_[HORIZONTAL] = x; coords_[VERTICAL] = y; coords_[PROXIMAL] = 0; }
- inline point_3d_data(coordinate_type x, coordinate_type y, coordinate_type z) {
- coords_[HORIZONTAL] = x; coords_[VERTICAL] = y; coords_[PROXIMAL] = z; }
- inline point_3d_data(const point_3d_data& that) { (*this) = that; }
- inline point_3d_data& operator=(const point_3d_data& that) {
- coords_[0] = that.coords_[0]; coords_[1] = that.coords_[1];
- coords_[2] = that.coords_[2]; return *this; }
- template <typename T2>
- inline point_3d_data& operator=(const T2& rvalue);
- inline coordinate_type get(orientation_3d orient) const {
- return coords_[orient.to_int()]; }
- inline void set(orientation_3d orient, coordinate_type value) {
- coords_[orient.to_int()] = value; }
-private:
- coordinate_type coords_[3];
-};
-
Deleted: sandbox/gtl/gtl/point_3d_traits.h
==============================================================================
--- sandbox/gtl/gtl/point_3d_traits.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,23 +0,0 @@
-/*
- 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).
-*/
-template <typename T>
-struct point_3d_traits {
- typedef typename T::coordinate_type coordinate_type;
-
- static inline coordinate_type get(const T& point, orientation_3d orient) {
- return point.get(orient); }
-
- static inline void set(T& point, orientation_3d orient, coordinate_type value) {
- point.set(orient, value); }
-
- static inline T construct(coordinate_type x_value,
- coordinate_type y_value,
- coordinate_type z_value) {
- return T(x_value, y_value, z_value); }
-};
-
Deleted: sandbox/gtl/gtl/point_concept.h
==============================================================================
--- sandbox/gtl/gtl/point_concept.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,93 +0,0 @@
-/*
- 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).
-*/
-struct point_concept {
- point_concept() {}
-
- template <typename point_type>
- struct registration {
- typedef typename point_traits<point_type>::coordinate_type component_type;
- };
-
- template <typename T>
- static inline typename point_traits<T>::coordinate_type get(const T& point, orientation_2d orient) {
- return point_traits<T>::get(point, orient);
- }
-
- template <orientation_2d_enum orient, typename T>
- static inline typename point_traits<T>::coordinate_type get(const T& point) {
- return get(point, orient);
- }
-
- template <typename T, typename coordinate_type>
- static inline void set(T& point, orientation_2d orient, coordinate_type value) {
- point_traits<T>::set(point, orient, value);
- }
-
- template <orientation_2d_enum orient, typename T, typename coordinate_type>
- static inline void set(T& point, coordinate_type value) {
- set(point, orient, value);
- }
-
- template <typename point_type>
- static void x(point_type& point) {
- return get<HORIZONTAL>(point);
- }
-
- template <typename point_type>
- static void y(point_type& point) {
- return get<VERTICAL>(point);
- }
-
- template <typename point_type, typename coordinate_type>
- static void x(point_type& point, coordinate_type value) {
- set<HORIZONTAL>(point, value);
- }
-
- template <typename point_type, typename coordinate_type>
- static void y(point_type& point, coordinate_type value) {
- set<VERTICAL>(point, value);
- }
-
- template <typename T, typename coordinate_type1, typename coordinate_type2>
- static inline T construct(coordinate_type1 x_value, coordinate_type2 y_value) {
- return point_traits<T>::construct(x_value, y_value);
- }
-
- template <typename point_type_1, typename point_type_2>
- static point_type_1& assign(point_type_1& lvalue, const point_type_2& rvalue) {
- set(lvalue, HORIZONTAL, get(rvalue, HORIZONTAL));
- set(lvalue, VERTICAL, get(rvalue, VERTICAL));
- return lvalue;
- }
-
- template <typename T, typename T2>
- static inline bool equivalence(const T& point1, const T2& point2) {
- typename point_traits<T>::coordinate_type x1 = get<HORIZONTAL>(point1);
- typename point_traits<T2>::coordinate_type x2 = get(point2, HORIZONTAL);
- typename point_traits<T>::coordinate_type y1 = get(point1, VERTICAL);
- typename point_traits<T2>::coordinate_type y2 = get<VERTICAL>(point2);
- return x1 == x2 && y1 == y2;
- }
-
- template <typename point_type_1, typename point_type_2>
- static typename point_traits<point_type_1>::coordinate_type
- manhattan_distance(const point_type_1& point1, const point_type_2& point2) {
- return distance(point1, point2, HORIZONTAL) + distance(point1, point2, VERTICAL);
- }
-
- template <typename point_type_1, typename point_type_2>
- static typename point_traits<point_type_1>::coordinate_type
- distance(const point_type_1& point1, const point_type_2& point2, orientation_2d orient) {
- typename point_traits<point_type_1>::coordinate_type return_value =
- get(point1, orient) - get(point2, orient);
- return return_value < 0 ? -return_value : return_value;
- }
-
-};
-
-
Deleted: sandbox/gtl/gtl/point_data.h
==============================================================================
--- sandbox/gtl/gtl/point_data.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,37 +0,0 @@
-/*
- 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).
-*/
-template <typename T>
-class point_data {
-public:
- typedef T coordinate_type;
- inline point_data(){}
- inline point_data(coordinate_type x, coordinate_type y) {
- coords_[HORIZONTAL] = x; coords_[VERTICAL] = y;
- }
- inline point_data(const point_data& that) { (*this) = that; }
- inline point_data& operator=(const point_data& that) {
- coords_[0] = that.coords_[0]; coords_[1] = that.coords_[1]; return *this;
- }
- template <typename T2>
- inline point_data& operator=(const T2& rvalue);
- inline bool operator==(const point_data& that) const {
- return coords_[0] == that.coords_[0] && coords_[1] == that.coords_[1];
- }
- inline bool operator!=(const point_data& that) const {
- return !((*this) == that);
- }
- inline coordinate_type get(orientation_2d orient) const {
- return coords_[orient.to_int()];
- }
- inline void set(orientation_2d orient, coordinate_type value) {
- coords_[orient.to_int()] = value;
- }
-private:
- coordinate_type coords_[2];
-};
-
Deleted: sandbox/gtl/gtl/point_traits.h
==============================================================================
--- sandbox/gtl/gtl/point_traits.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,22 +0,0 @@
-/*
- 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).
-*/
-template <typename T>
-struct point_traits {
- typedef typename T::coordinate_type coordinate_type;
-
- static inline coordinate_type get(const T& point, orientation_2d orient) {
- return point.get(orient);
- }
- static inline void set(T& point, orientation_2d orient, coordinate_type value) {
- point.set(orient, value);
- }
- static inline T construct(coordinate_type x_value, coordinate_type y_value) {
- return T(x_value, y_value);
- }
-};
-
Deleted: sandbox/gtl/gtl/polygon_concept.h
==============================================================================
--- sandbox/gtl/gtl/polygon_concept.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,324 +0,0 @@
-/*
- 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).
-*/
-struct polygon_concept {
- inline polygon_concept() {}
-
- template <typename polygon_type>
- struct registration {
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- };
-
-
- template<typename polygon_type, typename iterator_type>
- static void set(polygon_type& polygon, iterator_type input_begin, iterator_type input_end) {
- polygon_traits<polygon_type>::set(polygon, input_begin, input_end);
- }
-
- template<typename polygon_type, typename rectangle_type>
- static void set(polygon_type& polygon, const rectangle_type& rect) {
- typename polygon_traits<polygon_type>::coordinate_type coords[4] =
- {rectangle_concept::xl(rect), rectangle_concept::yl(rect),
- rectangle_concept::xh(rect), rectangle_concept::yh(rect)};
- set(polygon, coords, coords+4);
- }
-
- template<typename polygon_type, typename point_iterator_type>
- static void set_points(polygon_type& polygon, point_iterator_type begin_point, point_iterator_type end_point) {
- return set(iterator_points_to_compact<point_iterator_type, typename point_iterator_type::value_type>(begin_point),
- iterator_points_to_compact<point_iterator_type, typename point_iterator_type::value_type>(end_point));
- }
-
- template <typename polygon_type>
- static typename polygon_traits<polygon_type>::iterator_type begin(const polygon_type& polygon) {
- return polygon_traits<polygon_type>::begin(polygon);
- }
-
- template <typename polygon_type>
- static typename polygon_traits<polygon_type>::iterator_type end(const polygon_type& polygon) {
- return polygon_traits<polygon_type>::end(polygon);
- }
-
- template <typename polygon_type>
- static iterator_compact_to_points<typename polygon_traits<polygon_type>::iterator_type,
- point_data<typename polygon_traits<polygon_type>::coordinate_type> >
- begin_points(const polygon_type& polygon) {
- return iterator_compact_to_points<typename polygon_traits<polygon_type>::iterator_type,
- point_data<typename polygon_traits<polygon_type>::coordinate_type> > (begin(polygon), end(polygon));
- }
-
- template <typename polygon_type>
- static iterator_compact_to_points<typename polygon_traits<polygon_type>::iterator_type,
- point_data<typename polygon_traits<polygon_type>::coordinate_type> >
- end_points(const polygon_type& polygon) {
- return iterator_compact_to_points<typename polygon_traits<polygon_type>::iterator_type,
- point_data<typename polygon_traits<polygon_type>::coordinate_type> > (end(polygon), end(polygon));
- }
-
- template<typename T, class iT>
- static T construct(iT inputBegin, iT inputEnd) { return polygon_traits<T>::construct(inputBegin, inputEnd); }
-
- template<typename polygon_type, typename rectangle_type>
- static polygon_type construct_from_rectangle(const rectangle_type& rect) {
- polygon_type poly;
- set(poly, rect);
- return poly;
- }
-
- template <typename polygon_type, typename polygon_type2>
- static polygon_type copy_construct(const polygon_type2& polygon) {
- return construct(polygon_concept::begin(polygon), polygon_concept::end(polygon));
- }
-
- template <typename polygon_type>
- static std::size_t size(const polygon_type& polygon) {
- return polygon_traits<polygon_type>::size(polygon);
- }
-
- template <typename polygon_type_1, typename polygon_type_2>
- static polygon_type_1& assign(polygon_type_1& lvalue, const polygon_type_2& rvalue) {
- set(lvalue, begin(rvalue), end(rvalue));
- return lvalue;
- }
-
- template <typename polygon_type>
- static direction_1d winding(const polygon_type& polygon){
- winding_direction wd = polygon_traits<polygon_type>::winding(polygon);
- if(wd != unknown_winding) {
- return wd == clockwise_winding ? LOW: HIGH;
- }
- direction_1d dir = HIGH;
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- typedef typename polygon_traits<polygon_type>::iterator_type iterator;
- iterator itr = begin(polygon);
- coordinate_type firstx = *itr;
- coordinate_type minX = firstx;
- ++itr;
- iterator end_itr = end(polygon);
- if(itr == end_itr) return dir;
- coordinate_type prevy = *itr;
- coordinate_type firsty = *itr;
- ++itr;
- for( ; itr != end_itr; ++itr) {
- coordinate_type x = *itr;
- ++itr;
- if(itr == end_itr) break;
- coordinate_type y = *itr;
- if(x <= minX) {
- minX = x;
- //edge directed downward on left side of figure is counterclockwise
- dir = y < prevy ? HIGH : LOW;
- }
- prevy = y;
- }
- if(firstx <= minX) {
- dir = firsty < prevy ? HIGH : LOW;
- }
- return dir;
- }
-
- template <typename polygon_type>
- static rectangle_data<typename polygon_traits<polygon_type>::coordinate_type>
- bounding_box(const polygon_type& polygon) {
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- typedef typename polygon_traits<polygon_type>::iterator_type iterator;
- coordinate_type xmin = 0;
- coordinate_type ymin = 0;
- coordinate_type xmax = 0;
- coordinate_type ymax = 0;
- bool first_iteration = true;
- iterator itr_end = end(polygon);
- for(iterator itr = begin(polygon); itr != itr_end; ++itr) {
- coordinate_type x = *itr;
- ++itr;
- if(itr == itr_end) break;
- coordinate_type y = *itr;
- if(first_iteration) {
- xmin = xmax = x;
- ymin = ymax = x;
- first_iteration = false;
- }
- xmin = std::min(xmin, x);
- xmax = std::max(xmax, x);
- ymin = std::min(ymin, y);
- ymax = std::max(ymax, y);
- }
- typedef rectangle_data<coordinate_type> rectangle_type;
- rectangle_type return_value = rectangle_concept::construct<rectangle_type>(xmin, ymin, xmax, ymax);
- return return_value;
- }
-
- template <typename polygon_type>
- static typename polygon_traits<polygon_type>::coordinate_type
- area(const polygon_type& polygon) {
- //for (long i = 2; i < _size; i += 2) res += ((double)_vertex[i-1])*((double)(_vertex[i-2] - _vertex[i]));
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- typedef typename polygon_traits<polygon_type>::iterator_type iterator;
- coordinate_type retval = 0;
- iterator itr = begin(polygon);
- iterator end_itr = end(polygon);
- coordinate_type firstx = *itr;
- coordinate_type prevx = *itr;
- ++itr;
- if(itr == end_itr) return 0;
- coordinate_type prevy = *itr;
- ++itr;
- for( ; itr != end_itr; ++itr) {
- coordinate_type x = *itr;
- ++itr;
- if(itr == end_itr) break;
- coordinate_type y = *itr;
- retval += (prevy * (prevx - x));
- prevy = y;
- prevx = x;
- }
- retval += (prevy * (prevx - firstx));
- return retval >= 0 ? retval : -retval;
- }
-
- /// get the perimeter of the polygon
- template <typename polygon_type>
- static typename polygon_traits<polygon_type>::coordinate_type
- perimeter(const polygon_type& polygon) {
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- typedef typename polygon_traits<polygon_type>::iterator_type iterator_type;
- typedef iterator_compact_to_points<iterator_type, point_data<coordinate_type> > iterator;
- coordinate_type return_value = 0;
- point_data<coordinate_type> previous_point, first_point;
- iterator itr = begin_points(polygon);
- iterator itr_end = end_points(polygon);
- if(itr == itr_end) return return_value;
- previous_point = first_point = *itr;
- ++itr;
- for( ; itr != itr_end; ++itr) {
- ++itr;
- if(itr == itr_end) break;
- point_data<coordinate_type> current_point = *itr;
- return_value += point_concept::manhattan_distance(current_point, previous_point);
- previous_point = current_point;
- }
- return_value += point_concept::manhattan_distance(previous_point, first_point);
- return return_value;
- }
-
- /// check if point is inside polygon
- template <typename polygon_type, typename point_type>
- static bool contains(const polygon_type& polygon, const point_type& point,
- bool consider_touch, point_concept pc) {
- typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
- typedef typename polygon_traits<polygon_type>::iterator_type iterator_type;
- typedef iterator_compact_to_points<iterator_type, point_data<coordinate_type> > iterator;
- iterator iter, iter_end;
- iter_end = end_points(polygon);
- iter = begin_points(polygon);
- point_data<coordinate_type> prev_pt = *iter;
- unsigned int num = size(polygon);
- unsigned int counts[2] = {0, 0};
- for(unsigned int i = 0; i < num; ++i) {
- if(i == num-1) iter = begin_points(polygon);
- else ++iter;
- point_data<coordinate_type> current_pt = *iter;
- if(point_concept::get<HORIZONTAL>(current_pt) ==
- point_concept::get<HORIZONTAL>(prev_pt)) {
- unsigned int index = point_concept::get<HORIZONTAL>(current_pt) >
- point_concept::get<HORIZONTAL>(point);
- unsigned int increment = 0;
- interval_data<coordinate_type> ivl =
- interval_concept::construct<interval_data<coordinate_type> >(point_concept::get<VERTICAL>(current_pt),
- point_concept::get<VERTICAL>(prev_pt));
- if(interval_concept::contains(ivl, point_concept::get<VERTICAL>(point), true)) {
- if(point_concept::get<HORIZONTAL>(current_pt) ==
- point_concept::get<HORIZONTAL>(point)) return consider_touch;
- ++increment;
- if(point_concept::get<VERTICAL>(current_pt) !=
- point_concept::get<VERTICAL>(point) &&
- point_concept::get<VERTICAL>(prev_pt) !=
- point_concept::get<VERTICAL>(point)) {
- ++increment;
- }
- counts[index] += increment;
- }
- }
- prev_pt = current_pt;
- }
- //odd count implies boundary condition
- if(counts[0] % 2 || counts[1] % 2) return consider_touch;
- //an odd number of edges to the left implies interior pt
- return counts[0] % 4;
- }
-
-// //awaiting re-implementation of iterator_edges and edge concept
-// template <typename polygon_type, typename point_type>
-// static point_type project(const polygon_type& polygon, const point_type& point) const {
-// point_type return_value;
-// typedef iterator_edges<typename polygon_traits<polygon_type>::iterator_type,
-// edge_data<typename polygon_traits<polygon_type>::coordinate_type> > iterator;
-// iterator iter = begin_edges();
-// iterator iter_end = end_edges();
-// double dist = 0;
-// bool first_segment = true;
-// for( ; iter != iter_end; ++iter) {
-// point_type segement_point = segment_concept::project_point(*iter, point);
-// double seg_dist = point_concept::euclidian_distance(point, segment_point);
-// if(first_segment || seg_dist < dist) {
-// dist = seg_dist;
-// return_value = segment_point;
-// }
-// }
-// return return_value;
-// }
-
-// //awaiting re-implementation of iterator_edges and edge concept
-// template <typename polygon_type, typename point_type>
-// static point_type project(point_type& result, const polygon_type& polygon,
-// const point_type& point, direction_2d dir) {
-// typedef iterator_edges<typename polygon_traits<polygon_type>::iterator_type,
-// edge_data<typename polygon_traits<polygon_type>::coordinate_type> > iterator;
-// iterator iter = begin_edges();
-// iterator iter_end = end_edges();
-// double dist = 0;
-// bool found = false;
-// bool first_segment = true;
-// for( ; iter != iter_end; ++iter) {
-// point_type segement_point;
-// if(segment_concept::project_point(segment_point, *iter, point, dir)) {
-// found = true;
-// double seg_dist = point_concept::euclidian_distance(point, segment_point);
-// if(first_segment || seg_dist < dist) {
-// dist = seg_dist;
-// result = segment_point;
-// }
-// }
-// return found;
-// }
-
- template <typename polygon_type, typename coordinate_type_1, typename coordinate_type_2>
- static void move(polygon_type& polygon, coordinate_type_1 x_displacement, coordinate_type_2 y_displacement) {
- std::vector<typename polygon_traits<polygon_type>::coordinate_type> coords;
- coords.reserve(size(polygon));
- bool pingpong = true;
- for(typename polygon_traits<polygon_type>::iterator_type iter = begin(polygon);
- iter != end(polygon); ++iter) {
- coords.push_back((*iter) + (pingpong ? x_displacement : y_displacement));
- pingpong = !pingpong;
- }
- set(polygon, coords.begin(), coords.end());
- }
-
- /// move polygon by delta in orient
- template <typename polygon_type, typename coordinate_type_1>
- static void move(polygon_type& polygon, orientation_2d orient, coordinate_type_1 displacement) {
- if(orient == HORIZONTAL) {
- move(displacement, 0);
- } else {
- move(0, displacement);
- }
- }
-
-};
-
-
Deleted: sandbox/gtl/gtl/polygon_data.h
==============================================================================
--- sandbox/gtl/gtl/polygon_data.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,51 +0,0 @@
-/*
- 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).
-*/
-template <typename T>
-class polygon_data {
-public:
- typedef T coordinate_type;
- typedef typename std::vector<coordinate_type>::const_iterator iterator_type;
-
- inline polygon_data(){;} //do nothing default constructor
-
- /// initialize a polygon from x,y values, it is assumed that the first is an x
- /// and that the input is a well behaved polygon
- template<class iT>
- inline polygon_data& set(iT input_begin, iT input_end) {
- coords_.clear(); //just in case there was some old data there
- while(input_begin != input_end) {
- coords_.insert(coords_.end(), *input_begin);
- ++input_begin;
- }
- return *this;
- }
-
- /// copy constructor (since we have dynamic memory)
- inline polygon_data(const polygon_data& that) : coords_(that.coords_) {}
-
- /// assignment operator (since we have dynamic memory do a deep copy)
- inline polygon_data& operator=(const polygon_data& that) {
- coords_ = that.coords_;
- return *this;
- }
-
- template <typename T2>
- inline polygon_data& operator=(const T2& rvalue);
-
- /// get begin iterator, returns a pointer to a const Unit
- inline iterator_type begin() const { return coords_.begin(); }
-
- /// get end iterator, returns a pointer to a const Unit
- inline iterator_type end() const { return coords_.end(); }
-
- inline std::size_t size() const { return coords_.size(); }
-
-private:
- std::vector<coordinate_type> coords_;
-};
-
Deleted: sandbox/gtl/gtl/polygon_formation.h
==============================================================================
--- sandbox/gtl/gtl/polygon_formation.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,1675 +0,0 @@
-/*
- 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).
-*/
-
-namespace polygon_formation {
-
- /**
- * @brief End has two states, HEAD and TAIL as is represented by a bool
- */
- typedef bool End;
-
- /**
- * @brief HEAD End is represented as false because it is the lesser state
- */
- const End HEAD = false;
-
- /**
- * @brief TAIL End is represented by true because TAIL comes after head and 1 after 0
- */
- const End TAIL = true;
-
- /**
- * @brief 2D turning direction, left and right sides (is a boolean value since it has two states.)
- */
- typedef bool Side;
-
- /**
- * @brief LEFT Side is 0 because we inuitively think left to right; left < right
- */
- const Side LEFT = false;
-
- /**
- * @brief RIGHT Side is 1 so that right > left
- */
- const Side RIGHT = true;
-
- /**
- * @brief The PolyLine class is data storage and services for building and representing partial polygons.
- * As the polyline is added to it extends its storage to accomodate the data.
- * PolyLines can be joined head-to-head/head-to-tail when it is determined that two polylines are
- * part of the same polygon.
- * PolyLines keep state information about what orientation their incomplete head and tail geometry have,
- * which side of the polyline is solid and whether the polyline is joined head-to-head and tail-to-head.
- * PolyLines have nothing whatsoever to do with holes.
- * It may be valuable to collect a histogram of PolyLine lengths used by an algorithm on its typical data
- * sets and tune the allocation of the initial vector of coordinate data to be greater than or equal to
- * the mean, median, mode, or mean plus some number of standard deviation, or just generally large enough
- * to prevent too much unnecesary reallocations, but not too big that it wastes a lot of memory and degrades cache
- * performance.
- */
- template <typename Unit>
- class PolyLine {
- private:
- //data
-
- /**
- * @brief ptdata_ a vector of coordiantes
- * if VERTICAL_HEAD, first coordiante is an X
- * else first coordinate is a Y
- */
- std::vector<Unit> ptdata_;
-
- /**
- * @brief head and tail points to other polylines before and after this in a chain
- */
- PolyLine* headp_;
- PolyLine* tailp_;
-
- /**
- * @brief state bitmask
- * bit zero is orientation, 0 H, 1 V
- * bit 1 is head connectivity, 0 for head, 1 for tail
- * bit 2 is tail connectivity, 0 for head, 1 for tail
- * bit 3 is solid to left of PolyLine when 1, right when 0
- */
- int state_;
-
- public:
- /**
- * @brief default constructor (for preallocation)
- */
- PolyLine();
-
- /**
- * @brief constructor that takes the orientation, coordiante and side to which there is solid
- */
- PolyLine(orientation_2d orient, Unit coord, Side side);
-
- //copy constructor
- PolyLine(const PolyLine& pline);
-
- //destructor
- ~PolyLine();
-
- //assignment operator
- PolyLine& operator=(const PolyLine& that);
-
- //equivalence operator
- bool operator==(const PolyLine& b) const;
-
- /**
- * @brief valid PolyLine (only default constructed polylines are invalid.)
- */
- bool isValid() const;
-
- /**
- * @brief Orientation of Head
- */
- orientation_2d headOrient() const;
-
- /**
- * @brief returns true if first coordinate is an X value (first segment is vertical)
- */
- bool verticalHead() const;
-
- /**
- * @brief returns the orientation_2d fo the tail
- */
- orientation_2d tailOrient() const;
-
- /**
- * @brief returns true if last coordinate is an X value (last segment is vertical)
- */
- bool verticalTail() const;
-
- /**
- * @brief retrun true if PolyLine has odd number of coordiantes
- */
- bool oddLength() const;
-
- /**
- * @brief retrun the End of the other polyline that the specified end of this polyline is connected to
- */
- End endConnectivity(End end) const;
-
- /**
- * @brief retrun true if the head of this polyline is connect to the tail of a polyline
- */
- bool headToTail() const;
- /**
- * @brief retrun true if the head of this polyline is connect to the head of a polyline
- */
- bool headToHead() const;
-
- /**
- * @brief retrun true if the tail of this polyline is connect to the tail of a polyline
- */
- bool tailToTail() const;
- /**
- * @brief retrun true if the tail of this polyline is connect to the head of a polyline
- */
- bool tailToHead() const;
-
- /**
- * @brief retrun the side on which there is solid for this polyline
- */
- Side solidSide() const;
-
- /**
- * @brief retrun true if there is solid to the right of this polyline
- */
- bool solidToRight() const;
-
- /**
- * @brief returns true if the polyline tail is not connected
- */
- bool active() const;
-
- /**
- * @brief adds a coordinate value to the end of the polyline changing the tail orientation
- */
- PolyLine& pushCoordinate(Unit coord);
-
- /**
- * @brief removes a coordinate value at the end of the polyline changing the tail orientation
- */
- PolyLine& popCoordinate();
-
- /**
- * @brief extends the tail of the polyline to include the point, changing orientation if needed
- */
- PolyLine& pushPoint(const point_data<Unit>& point);
-
- /**
- * @brief changes the last coordinate of the tail of the polyline by the amount of the delta
- */
- PolyLine& extendTail(Unit delta);
-
- /**
- * @brief join thisEnd of this polyline to that polyline's end
- */
- PolyLine& joinTo(End thisEnd, PolyLine& that, End end);
-
- /**
- * @brief join an end of this polyline to the tail of that polyline
- */
- PolyLine& joinToTail(PolyLine& that, End end);
-
- /**
- * @brief join an end of this polyline to the head of that polyline
- */
- PolyLine& joinToHead(PolyLine& that, End end);
-
- /**
- * @brief join the head of this polyline to the head of that polyline
- */
- //join this to that in the given way
- PolyLine& joinHeadToHead(PolyLine& that);
-
- /**
- * @brief join the head of this polyline to the tail of that polyline
- */
- PolyLine& joinHeadToTail(PolyLine& that);
-
- /**
- * @brief join the tail of this polyline to the head of that polyline
- */
- PolyLine& joinTailToHead(PolyLine& that);
-
- /**
- * @brief join the tail of this polyline to the tail of that polyline
- */
- PolyLine& joinTailToTail(PolyLine& that);
-
- /**
- * @brief dissconnect the tail at the end of the polygon
- */
- PolyLine& disconnectTails();
-
- /**
- * @brief get the coordinate at one end of this polyline, by default the tail end
- */
- Unit getEndCoord(End end = TAIL) const;
-
- /**
- * @brief get the point on the polyline at the given index (polylines have the same number of coordinates as points
- */
- point_data<Unit> getPoint(unsigned int index) const;
-
- /**
- * @brief get the point on one end of the polyline, by default the tail
- */
- point_data<Unit> getEndPoint(End end = TAIL) const;
-
- /**
- * @brief get the orientation of a segment by index
- */
- orientation_2d segmentOrient(unsigned int index = 0) const;
-
- /**
- * @brief get a coordinate by index using the square bracket operator
- */
- Unit operator[] (unsigned int index) const;
-
- /**
- * @brief get the number of segments/points/coordinates in the polyline
- */
- unsigned int numSegments() const;
-
- /**
- * @brief get the pointer to the next polyline at one end of this
- */
- PolyLine* next(End end) const;
-
- /**
- * @brief write out coordinates of this and all attached polylines to a single vector
- */
- PolyLine* writeOut(std::vector<Unit>& outVec, End startEnd = TAIL) const;
-
- private:
- //methods
- PolyLine& joinTo_(End thisEnd, PolyLine& that, End end);
- };
-
- //forward declaration
- template<bool orientT, typename Unit>
- class PolyLinePolygonData;
-
- /**
- * @brief ActiveTail represents an edge of an incomplete polygon.
- *
- * An ActiveTail object is the active tail end of a polyline object, which may (should) be the attached to
- * a chain of polyline objects through a pointer. The ActiveTail class provides an abstraction between
- * and algorithm that builds polygons and the PolyLine data representation of incomplete polygons that are
- * being built. It does this by providing an iterface to access the information about the last edge at the
- * tail of the PolyLine it is associated with. To a polygon constructing algorithm, an ActiveTail is a floating
- * edge of an incomplete polygon and has an orientation and coordinate value, as well as knowing which side of
- * that edge is supposed to be solid or space. Any incomplete polygon will have two active tails. Active tails
- * may be joined together to merge two incomplete polygons into a larger incomplete polygon. If two active tails
- * that are to be merged are the oppositve ends of the same incomplete polygon that indicates that the polygon
- * has been closed and is complete. The active tail keeps a pointer to the other active tail of its incomplete
- * polygon so that it is easy to check this condition. These pointers are updated when active tails are joined.
- * The active tail also keeps a list of pointers to active tail objects that serve as handles to closed holes. In
- * this way a hole can be associated to another incomplete polygon, which will eventually be its enclosing shell,
- * or reassociate the hole to another incomplete polygon in the case that it become a hole itself. Alternately,
- * the active tail may add a filiment to stitch a hole into a shell and "fracture" the hole out of the interior
- * of a polygon. The active tail maintains a static output buffer to temporarily write polygon data to when
- * it outputs a figure so that outputting a polygon does not require the allocation of a temporary buffer. This
- * static buffer should be destroyed whenever the program determines that it won't need it anymore and would prefer to
- * release the memory it has allocated back to the system.
- */
- template <typename Unit>
- class ActiveTail {
- private:
- //data
- PolyLine<Unit>* tailp_;
- ActiveTail *otherTailp_;
- std::list<ActiveTail*> holesList_;
- public:
-
- /**
- * @brief iterator over coordinates of the figure
- */
- class iterator {
- private:
- const PolyLine<Unit>* pLine_;
- const PolyLine<Unit>* pLineEnd_;
- unsigned int index_;
- unsigned int indexEnd_;
- End startEnd_;
- public:
- inline iterator() : pLine_(0), index_(0) {}
- inline iterator(const ActiveTail* at, bool isHole, orientation_2d orient) {
- //if it is a hole and orientation is vertical or it is not a hole and orientation is horizontal
- //we want to use this active tail, otherwise we want to use the other active tail
- startEnd_ = TAIL;
- if(!isHole ^ (orient == HORIZONTAL)) {
- //switch winding direction
- at = at->getOtherActiveTail();
- }
- //now we have the right winding direction
- //if it is horizontal we need to skip the first element
- pLine_ = at->getTail();
- index_ = at->getTail()->numSegments() - 1;
- if((at->getOrient() == HORIZONTAL) ^ (orient == HORIZONTAL)) {
- pLineEnd_ = at->getTail();
- indexEnd_ = pLineEnd_->numSegments() - 1;
- if(index_ == 0) {
- pLine_ = at->getTail()->next(HEAD);
- if(at->getTail()->endConnectivity(HEAD) == TAIL) {
- index_ = pLine_->numSegments() -1;
- } else {
- startEnd_ = HEAD;
- index_ = 0;
- }
- } else { --index_; }
- } else {
- pLineEnd_ = at->getOtherActiveTail()->getTail();
- indexEnd_ = pLineEnd_->numSegments() - 1;
- }
- at->getTail()->joinTailToTail(*(at->getOtherActiveTail()->getTail()));
- }
- //use bitwise copy and assign provided by the compiler
- inline iterator& operator++() {
- if(pLine_ == pLineEnd_ && index_ == indexEnd_) {
- pLine_ = 0;
- index_ = 0;
- return *this;
- }
- if(startEnd_ == HEAD) {
- ++index_;
- if(index_ == pLine_->numSegments()) {
- End end = pLine_->endConnectivity(TAIL);
- pLine_ = pLine_->next(TAIL);
- if(end == TAIL) {
- startEnd_ = TAIL;
- index_ = pLine_->numSegments() -1;
- } else {
- index_ = 0;
- }
- }
- } else {
- if(index_ == 0) {
- End end = pLine_->endConnectivity(HEAD);
- pLine_ = pLine_->next(HEAD);
- if(end == TAIL) {
- index_ = pLine_->numSegments() -1;
- } else {
- startEnd_ = HEAD;
- index_ = 0;
- }
- } else {
- --index_;
- }
- }
- return *this;
- }
- inline iterator operator++(int) {
- iterator tmp(*this);
- ++(*this);
- return tmp;
- }
- inline bool operator==(const iterator& that) const {
- return pLine_ == that.pLine_ && index_ == that.index_;
- }
- inline bool operator!=(const iterator& that) const {
- return pLine_ != that.pLine_ || index_ != that.index_;
- }
- inline Unit operator*() { return (*pLine_)[index_]; }
- };
-
- /**
- * @brief iterator over holes contained within the figure
- */
- typedef typename std::list<ActiveTail*>::const_iterator iteratorHoles;
-
- //default constructor
- ActiveTail();
-
- //constructor
- ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp);
-
- //constructor
- ActiveTail(PolyLine<Unit>* active, ActiveTail* otherTailp);
-
- //copy constructor
- ActiveTail(const ActiveTail& that);
-
- //destructor
- ~ActiveTail();
-
- //assignment operator
- ActiveTail& operator=(const ActiveTail& that);
-
- //equivalence operator
- bool operator==(const ActiveTail& b) const;
-
- /**
- * @brief comparison operators, ActiveTail objects are sortable by geometry
- */
- bool operator<(const ActiveTail& b) const;
- bool operator<=(const ActiveTail& b) const;
- bool operator>(const ActiveTail& b) const;
- bool operator>=(const ActiveTail& b) const;
-
- /**
- * @brief get the pointer to the polyline that this is an active tail of
- */
- PolyLine<Unit>* getTail() const;
-
- /**
- * @brief get the pointer to the polyline at the other end of the chain
- */
- PolyLine<Unit>* getOtherTail() const;
-
- /**
- * @brief get the pointer to the activetail at the other end of the chain
- */
- ActiveTail* getOtherActiveTail() const;
-
- /**
- * @brief test if another active tail is the other end of the chain
- */
- bool isOtherTail(const ActiveTail& b);
-
- /**
- * @brief update this end of chain pointer to new polyline
- */
- ActiveTail& updateTail(PolyLine<Unit>* newTail);
-
- /**
- * @brief associate a hole to this active tail by the specified policy
- */
- ActiveTail* addHole(ActiveTail* hole, bool fractureHoles);
-
- /**
- * @brief get the list of holes
- */
- const std::list<ActiveTail*>& getHoles() const;
-
- /**
- * @brief copy holes from that to this
- */
- void copyHoles(ActiveTail& that);
-
- /**
- * @brief find out if solid to right
- */
- bool solidToRight() const;
-
- /**
- * @brief get coordinate (getCoord and getCoordinate are aliases for eachother)
- */
- Unit getCoord() const;
- Unit getCoordinate() const;
-
- /**
- * @brief get the tail orientation
- */
- orientation_2d getOrient() const;
-
- /**
- * @brief add a coordinate to the polygon at this active tail end, properly handle degenerate edges by removing redundant coordinate
- */
- void pushCoordinate(Unit coord);
-
- /**
- * @brief write the figure that this active tail points to out to the temp buffer
- */
- void writeOutFigure(std::vector<Unit>& outVec, bool isHole = false) const;
-
- /**
- * @brief write the figure that this active tail points to out through iterators
- */
- void writeOutFigureItrs(iterator& beginOut, iterator& endOut, bool isHole = false, orientation_2d orient = VERTICAL) const;
- iterator begin(bool isHole, orientation_2d orient) const;
- iterator end() const;
-
- /**
- * @brief write the holes that this active tail points to out through iterators
- */
- void writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const;
- iteratorHoles beginHoles() const;
- iteratorHoles endHoles() const;
-
- /**
- * @brief joins the two chains that the two active tail tails are ends of
- * checks for closure of figure and writes out polygons appropriately
- * returns a handle to a hole if one is closed
- */
- static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, std::vector<Unit>& outBufferTmp);
- template <bool orientT>
- static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, typename std::vector<PolyLinePolygonData<orientT, Unit> >& outBufferTmp);
-
- /**
- * @brief deallocate temp buffer
- */
- static void destroyOutBuffer();
-
- /**
- * @brief deallocate all polygon data this active tail points to (deep delete, call only from one of a pair of active tails)
- */
- void destroyContents();
- };
-
- /** @brief allocate a polyline object */
- template <typename Unit>
- PolyLine<Unit>* createPolyLine(orientation_2d orient, Unit coord, Side side);
-
- /** @brief deallocate a polyline object */
- template <typename Unit>
- void destroyPolyLine(PolyLine<Unit>* pLine);
-
- /** @brief allocate an activetail object */
- template <typename Unit>
- ActiveTail<Unit>* createActiveTail();
-
- /** @brief deallocate an activetail object */
- template <typename Unit>
- void destroyActiveTail(ActiveTail<Unit>* aTail);
-
-
- template<bool orientT, typename Unit>
- class PolyLineHoleData {
- private:
- ActiveTail<Unit>* p_;
- public:
- typedef Unit coordinate_type;
- typedef typename ActiveTail<Unit>::iterator iterator_type;
- inline PolyLineHoleData() : p_(0) {}
- inline PolyLineHoleData(ActiveTail<Unit>* p) : p_(p) {}
- //use default copy and assign
- inline iterator_type begin() const { return p_->begin(true, (orientT ? VERTICAL : HORIZONTAL)); }
- inline iterator_type end() const { return p_->end(); }
- inline unsigned int size() const { return 0; }
- template<class iT>
- inline PolyLineHoleData& set(iT inputBegin, iT inputEnd) {
- return *this;
- }
-
- };
-
- template<bool orientT, typename Unit>
- class PolyLinePolygonData {
- private:
- ActiveTail<Unit>* p_;
- public:
- typedef Unit coordinate_type;
- typedef typename ActiveTail<Unit>::iterator iterator_type;
- typedef PolyLineHoleData<orientT, Unit> hole_type;
- class iteratorHoles {
- private:
- typename ActiveTail<Unit>::iteratorHoles itr_;
- public:
- inline iteratorHoles() {}
- inline iteratorHoles(typename ActiveTail<Unit>::iteratorHoles itr) : itr_(itr) {}
- //use bitwise copy and assign provided by the compiler
- inline iteratorHoles& operator++() {
- ++itr_;
- return *this;
- }
- inline iteratorHoles operator++(int) {
- iteratorHoles tmp(*this);
- ++(*this);
- return tmp;
- }
- inline bool operator==(const iteratorHoles& that) const {
- return itr_ == that.itr_;
- }
- inline bool operator!=(const iteratorHoles& that) const {
- return itr_ != that.itr_;
- }
- inline PolyLineHoleData<orientT, Unit> operator*() { return PolyLineHoleData<orientT, Unit>(*itr_);}
- };
- typedef iteratorHoles iterator_holes_type;
-
- inline PolyLinePolygonData() : p_(0) {}
- inline PolyLinePolygonData(ActiveTail<Unit>* p) : p_(p) {}
- //use default copy and assign
- inline iterator_type begin() const { return p_->begin(false, (orientT ? VERTICAL : HORIZONTAL)); }
- inline iterator_type end() const { return p_->end(); }
- inline iteratorHoles begin_holes() const { return iteratorHoles(p_->beginHoles()); }
- inline iteratorHoles end_holes() const { return iteratorHoles(p_->endHoles()); }
- inline ActiveTail<Unit>* yield() { return p_; }
- //stub out these four required functions that will not be used but are needed for the interface
- inline unsigned int size_holes() const { return 0; }
- inline unsigned int size() const { return 0; }
- template<class iT>
- inline PolyLinePolygonData& set(iT inputBegin, iT inputEnd) {
- return *this;
- }
-
- /// initialize a polygon from x,y values, it is assumed that the first is an x
- /// and that the input is a well behaved polygon
- template<class iT>
- inline PolyLinePolygonData& set_holes(iT inputBegin, iT inputEnd) {
- return *this;
- }
- };
-
-
- /**
- * @brief ScanLine does all the work of stitching together polygons from incoming vertical edges
- */
- template <bool orientT, typename Unit>
- class ScanLineToPolygonItrs {
- private:
- /** @brief a map of horizontal edges of incomplete polygons by their y value coordinate */
- std::map<Unit, ActiveTail<Unit>*> tailMap_;
- std::vector<PolyLinePolygonData<orientT, Unit> > outputPolygons_;
- bool fractureHoles_;
- public:
- typedef typename std::vector<PolyLinePolygonData<orientT, Unit> >::iterator iterator;
- inline ScanLineToPolygonItrs() {}
- /** @brief construct a scanline with the proper offsets, protocol and options */
- inline ScanLineToPolygonItrs(bool fractureHoles) : fractureHoles_(fractureHoles) {}
-
- ~ScanLineToPolygonItrs() { clearOutput_(); }
-
- /** @brief process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */
- void processEdges(iterator& beginOutput, iterator& endOutput,
- Unit currentX, std::vector<interval_data<Unit> >& leftEdges,
- std::vector<interval_data<Unit> >& rightEdges);
-
- private:
- void clearOutput_();
- };
-
- /**
- * @brief ScanLine does all the work of stitching together polygons from incoming vertical edges
- */
- template <typename Unit>
- class ScanLineToPolygons {
- private:
- ScanLineToPolygonItrs<true, Unit> scanline_;
- public:
- inline ScanLineToPolygons() : scanline_() {}
- /** @brief construct a scanline with the proper offsets, protocol and options */
- inline ScanLineToPolygons(bool fractureHoles) : scanline_(fractureHoles) {}
-
- /** @brief process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */
- inline void processEdges(std::vector<Unit>& outBufferTmp, Unit currentX, std::vector<interval_data<Unit> >& leftEdges,
- std::vector<interval_data<Unit> >& rightEdges) {
- typename ScanLineToPolygonItrs<true, Unit>::iterator itr, endItr;
- scanline_.processEdges(itr, endItr, currentX, leftEdges, rightEdges);
- //copy data into outBufferTmp
- while(itr != endItr) {
- typename PolyLinePolygonData<true, Unit>::iterator pditr;
- outBufferTmp.push_back(0);
- unsigned int sizeIndex = outBufferTmp.size() - 1;
- int count = 0;
- for(pditr = (*itr).begin(); pditr != (*itr).end(); ++pditr) {
- outBufferTmp.push_back(*pditr);
- ++count;
- }
- outBufferTmp[sizeIndex] = count;
- typename PolyLinePolygonData<true, Unit>::iteratorHoles pdHoleItr;
- for(pdHoleItr = (*itr).beginHoles(); pdHoleItr != (*itr).endHoles(); ++pdHoleItr) {
- outBufferTmp.push_back(0);
- unsigned int sizeIndex2 = outBufferTmp.size() - 1;
- int count2 = 0;
- for(pditr = (*pdHoleItr).begin(); pditr != (*pdHoleItr).end(); ++pditr) {
- outBufferTmp.push_back(*pditr);
- ++count2;
- }
- outBufferTmp[sizeIndex2] = -count;
- }
- ++itr;
- }
- }
- };
-
- const int VERTICAL_HEAD = 1, HEAD_TO_TAIL = 2, TAIL_TO_TAIL = 4, SOLID_TO_RIGHT = 8;
-
- //EVERY FUNCTION in this DEF file should be explicitly defined as inline
-
- //microsoft compiler improperly warns whenever you cast an integer to bool
- //call this function on an integer to convert it to bool without a warning
- template <class T>
- inline bool to_bool(const T& val) { return val != 0; }
-
- //default constructor (for preallocation)
- template <typename Unit>
- inline PolyLine<Unit>::PolyLine() : headp_(0), tailp_(0), state_(-1) {}
-
- //constructor
- template <typename Unit>
- inline PolyLine<Unit>::PolyLine(orientation_2d orient, Unit coord, Side side) :
- ptdata_(1, coord),
- headp_(0),
- tailp_(0),
- state_(orient.to_int() +
- (side << 3)) {}
-
- //copy constructor
- template <typename Unit>
- inline PolyLine<Unit>::PolyLine(const PolyLine<Unit>& pline) : ptdata_(pline.ptdata_),
- headp_(pline.headp_),
- tailp_(pline.tailp_),
- state_(pline.state_) {}
-
- //destructor
- template <typename Unit>
- inline PolyLine<Unit>::~PolyLine() {
- //clear out data just in case it is read later
- headp_ = tailp_ = 0;
- state_ = 0;
- }
-
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::operator=(const PolyLine<Unit>& that) {
- if(!(this == &that)) {
- headp_ = that.headp_;
- tailp_ = that.tailp_;
- ptdata_ = that.ptdata_;
- state_ = that.state_;
- }
- return *this;
- }
-
- template <typename Unit>
- inline bool PolyLine<Unit>::operator==(const PolyLine<Unit>& b) const {
- return this == &b || (state_ == b.state_ &&
- headp_ == b.headp_ &&
- tailp_ == b.tailp_);
- }
-
- //valid PolyLine
- template <typename Unit>
- inline bool PolyLine<Unit>::isValid() const {
- return state_ > -1; }
-
- //first coordinate is an X value
- //first segment is vertical
- template <typename Unit>
- inline bool PolyLine<Unit>::verticalHead() const {
- return state_ & VERTICAL_HEAD;
- }
-
- //retrun true is PolyLine has odd number of coordiantes
- template <typename Unit>
- inline bool PolyLine<Unit>::oddLength() const {
- return to_bool((ptdata_.size()-1) % 2);
- }
-
- //last coordiante is an X value
- //last segment is vertical
- template <typename Unit>
- inline bool PolyLine<Unit>::verticalTail() const {
- return to_bool(verticalHead() ^ oddLength());
- }
-
- template <typename Unit>
- inline orientation_2d PolyLine<Unit>::tailOrient() const {
- return (verticalTail() ? VERTICAL : HORIZONTAL);
- }
-
- template <typename Unit>
- inline orientation_2d PolyLine<Unit>::headOrient() const {
- return (verticalHead() ? VERTICAL : HORIZONTAL);
- }
-
- template <typename Unit>
- inline End PolyLine<Unit>::endConnectivity(End end) const {
- //Tail should be defined as true
- if(end) { return tailToTail(); }
- return headToTail();
- }
-
- template <typename Unit>
- inline bool PolyLine<Unit>::headToTail() const {
- return to_bool(state_ & HEAD_TO_TAIL);
- }
-
- template <typename Unit>
- inline bool PolyLine<Unit>::headToHead() const {
- return to_bool(!headToTail());
- }
-
- template <typename Unit>
- inline bool PolyLine<Unit>::tailToHead() const {
- return to_bool(!tailToTail());
- }
-
- template <typename Unit>
- inline bool PolyLine<Unit>::tailToTail() const {
- return to_bool(state_ & TAIL_TO_TAIL);
- }
-
- template <typename Unit>
- inline Side PolyLine<Unit>::solidSide() const {
- return solidToRight(); }
-
- template <typename Unit>
- inline bool PolyLine<Unit>::solidToRight() const {
- return to_bool(state_ & SOLID_TO_RIGHT) != 0;
- }
-
- template <typename Unit>
- inline bool PolyLine<Unit>::active() const {
- return !to_bool(tailp_);
- }
-
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::pushCoordinate(Unit coord) {
- ptdata_.push_back(coord);
- return *this;
- }
-
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::popCoordinate() {
- ptdata_.pop_back();
- return *this;
- }
-
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::pushPoint(const point_data<Unit>& point) {
- point_data<Unit> endPt = getEndPoint();
- //vertical is true, horizontal is false
- if((tailOrient().to_int() ? point.get(VERTICAL) == endPt.get(VERTICAL) : point.get(HORIZONTAL) == endPt.get(HORIZONTAL))) {
- //we were pushing a colinear segment
- return popCoordinate();
- }
- return pushCoordinate(tailOrient().to_int() ? point.get(VERTICAL) : point.get(HORIZONTAL));
- }
-
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::extendTail(Unit delta) {
- ptdata_.back() += delta;
- return *this;
- }
-
- //private member function that creates a link from this PolyLine to that
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::joinTo_(End thisEnd, PolyLine<Unit>& that, End end) {
- if(thisEnd){
- tailp_ = &that;
- state_ &= ~TAIL_TO_TAIL; //clear any previous state_ of bit (for safety)
- state_ |= (end << 2); //place bit into mask
- } else {
- headp_ = &that;
- state_ &= ~HEAD_TO_TAIL; //clear any previous state_ of bit (for safety)
- state_ |= (end << 1); //place bit into mask
- }
- return *this;
- }
-
- //join two PolyLines (both ways of the association)
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::joinTo(End thisEnd, PolyLine<Unit>& that, End end) {
- joinTo_(thisEnd, that, end);
- that.joinTo_(end, *this, thisEnd);
- return *this;
- }
-
- //convenience functions for joining PolyLines
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::joinToTail(PolyLine<Unit>& that, End end) {
- return joinTo(TAIL, that, end);
- }
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::joinToHead(PolyLine<Unit>& that, End end) {
- return joinTo(HEAD, that, end);
- }
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::joinHeadToHead(PolyLine<Unit>& that) {
- return joinToHead(that, HEAD);
- }
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::joinHeadToTail(PolyLine<Unit>& that) {
- return joinToHead(that, TAIL);
- }
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::joinTailToHead(PolyLine<Unit>& that) {
- return joinToTail(that, HEAD);
- }
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::joinTailToTail(PolyLine<Unit>& that) {
- return joinToTail(that, TAIL);
- }
-
- template <typename Unit>
- inline PolyLine<Unit>& PolyLine<Unit>::disconnectTails() {
- next(TAIL)->state_ &= !TAIL_TO_TAIL;
- next(TAIL)->tailp_ = 0;
- state_ &= !TAIL_TO_TAIL;
- tailp_ = 0;
- return *this;
- }
-
- template <typename Unit>
- inline Unit PolyLine<Unit>::getEndCoord(End end) const {
- if(end)
- return ptdata_.back();
- return ptdata_.front();
- }
-
- template <typename Unit>
- inline orientation_2d PolyLine<Unit>::segmentOrient(unsigned int index) const {
- return (to_bool((unsigned int)verticalHead() ^ (index % 2)) ? VERTICAL : HORIZONTAL);
- }
-
- template <typename Unit>
- inline point_data<Unit> PolyLine<Unit>::getPoint(unsigned int index) const {
- //assert(isValid() && headp_->isValid()) ("PolyLine: headp_ must be valid");
- point_data<Unit> pt;
- pt.set(HORIZONTAL, ptdata_[index]);
- pt.set(VERTICAL, ptdata_[index]);
- Unit prevCoord;
- if(index == 0) {
- prevCoord = headp_->getEndCoord(headToTail());
- } else {
- prevCoord = ptdata_[index-1];
- }
- pt.set(segmentOrient(index), prevCoord);
- return pt;
- }
-
- template <typename Unit>
- inline point_data<Unit> PolyLine<Unit>::getEndPoint(End end) const {
- return getPoint((end ? numSegments() - 1 : (unsigned int)0));
- }
-
- template <typename Unit>
- inline Unit PolyLine<Unit>::operator[] (unsigned int index) const {
- //assert(ptdata_.size() > index) ("PolyLine: out of bounds index");
- return ptdata_[index];
- }
-
- template <typename Unit>
- inline unsigned int PolyLine<Unit>::numSegments() const {
- return ptdata_.size();
- }
-
- template <typename Unit>
- inline PolyLine<Unit>* PolyLine<Unit>::next(End end) const {
- return (end ? tailp_ : headp_);
- }
-
- template <typename Unit>
- inline ActiveTail<Unit>::ActiveTail() : tailp_(0), otherTailp_(0) {}
-
- template <typename Unit>
- inline ActiveTail<Unit>::ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp) {
- tailp_ = createPolyLine(orient, coord, solidToRight);
- otherTailp_ = otherTailp;
- }
-
- template <typename Unit>
- inline ActiveTail<Unit>::ActiveTail(PolyLine<Unit>* active, ActiveTail<Unit>* otherTailp) :
- tailp_(active), otherTailp_(otherTailp) {}
-
- //copy constructor
- template <typename Unit>
- inline ActiveTail<Unit>::ActiveTail(const ActiveTail<Unit>& that) : tailp_(that.tailp_), otherTailp_(that.otherTailp_) {}
-
- //destructor
- template <typename Unit>
- inline ActiveTail<Unit>::~ActiveTail() {
- //clear them in case the memory is read later
- tailp_ = 0; otherTailp_ = 0;
- }
-
- template <typename Unit>
- inline ActiveTail<Unit>& ActiveTail<Unit>::operator=(const ActiveTail<Unit>& that) {
- //self assignment is safe in this case
- tailp_ = that.tailp_;
- otherTailp_ = that.otherTailp_;
- return *this;
- }
-
- template <typename Unit>
- inline bool ActiveTail<Unit>::operator==(const ActiveTail<Unit>& b) const {
- return tailp_ == b.tailp_ && otherTailp_ == b.otherTailp_;
- }
-
- template <typename Unit>
- inline bool ActiveTail<Unit>::operator<(const ActiveTail<Unit>& b) const {
- return tailp_->getEndPoint().get(VERTICAL) < b.tailp_->getEndPoint().get(VERTICAL);
- }
-
- template <typename Unit>
- inline bool ActiveTail<Unit>::operator<=(const ActiveTail<Unit>& b) const {
- return !(*this > b); }
-
- template <typename Unit>
- inline bool ActiveTail<Unit>::operator>(const ActiveTail<Unit>& b) const {
- return b < (*this); }
-
- template <typename Unit>
- inline bool ActiveTail<Unit>::operator>=(const ActiveTail<Unit>& b) const {
- return !(*this < b); }
-
- template <typename Unit>
- inline PolyLine<Unit>* ActiveTail<Unit>::getTail() const {
- return tailp_; }
-
- template <typename Unit>
- inline PolyLine<Unit>* ActiveTail<Unit>::getOtherTail() const {
- return otherTailp_->tailp_; }
-
- template <typename Unit>
- inline ActiveTail<Unit>* ActiveTail<Unit>::getOtherActiveTail() const {
- return otherTailp_; }
-
- template <typename Unit>
- inline bool ActiveTail<Unit>::isOtherTail(const ActiveTail<Unit>& b) {
- // assert( (tailp_ == b.getOtherTail() && getOtherTail() == b.tailp_) ||
- // (tailp_ != b.getOtherTail() && getOtherTail() != b.tailp_))
- // ("ActiveTail: Active tails out of sync");
- return otherTailp_ == &b;
- }
-
- template <typename Unit>
- inline ActiveTail<Unit>& ActiveTail<Unit>::updateTail(PolyLine<Unit>* newTail) {
- tailp_ = newTail;
- return *this;
- }
-
- template <typename Unit>
- inline ActiveTail<Unit>* ActiveTail<Unit>::addHole(ActiveTail<Unit>* hole, bool fractureHoles) {
- if(!fractureHoles){
- holesList_.push_back(hole);
- copyHoles(*hole);
- copyHoles(*(hole->getOtherActiveTail()));
- return this;
- }
- ActiveTail<Unit>* h, *v;
- ActiveTail<Unit>* other = hole->getOtherActiveTail();
- if(other->getOrient() == VERTICAL) {
- //assert that hole.getOrient() == HORIZONTAL
- //this case should never happen
- h = hole;
- v = other;
- } else {
- //assert that hole.getOrient() == VERTICAL
- h = other;
- v = hole;
- }
- h->pushCoordinate(v->getCoordinate());
- //assert that h->getOrient() == VERTICAL
- //v->pushCoordinate(getCoordinate());
- //assert that v->getOrient() == VERTICAL
- //I can't close a figure by adding a hole, so pass zero for xMin and yMin
- std::vector<Unit> tmpVec;
- ActiveTail<Unit>::joinChains(this, h, false, tmpVec);
- return v;
- }
-
- template <typename Unit>
- inline const std::list<ActiveTail<Unit>*>& ActiveTail<Unit>::getHoles() const {
- return holesList_;
- }
-
- template <typename Unit>
- inline void ActiveTail<Unit>::copyHoles(ActiveTail<Unit>& that) {
- holesList_.splice(holesList_.end(), that.holesList_); //splice the two lists together
- }
-
- template <typename Unit>
- inline bool ActiveTail<Unit>::solidToRight() const {
- return getTail()->solidToRight(); }
-
- template <typename Unit>
- inline Unit ActiveTail<Unit>::getCoord() const {
- return getTail()->getEndCoord(); }
-
- template <typename Unit>
- inline Unit ActiveTail<Unit>::getCoordinate() const {
- return getCoord(); }
-
- template <typename Unit>
- inline orientation_2d ActiveTail<Unit>::getOrient() const {
- return getTail()->tailOrient(); }
-
- template <typename Unit>
- inline void ActiveTail<Unit>::pushCoordinate(Unit coord) {
- //appropriately handle any co-linear polyline segments by calling push point internally
- point_data<Unit> p;
- p.set(HORIZONTAL, coord);
- p.set(VERTICAL, coord);
- //if we are vertical assign the last coordinate (an X) to p.x, else to p.y
- p.set(getOrient().get_perpendicular(), getCoordinate());
- tailp_->pushPoint(p);
- }
-
-
- //global utility functions
- template <typename Unit>
- inline PolyLine<Unit>* createPolyLine(orientation_2d orient, Unit coord, Side side) {
- return new PolyLine<Unit>(orient, coord, side);
- }
-
- template <typename Unit>
- inline void destroyPolyLine(PolyLine<Unit>* pLine) {
- delete pLine;
- }
-
- template <typename Unit>
- inline ActiveTail<Unit>* createActiveTail() {
- //consider replacing system allocator with ActiveTail memory pool
- return new ActiveTail<Unit>();
- }
-
- template <typename Unit>
- inline void destroyActiveTail(ActiveTail<Unit>* aTail) {
- delete aTail;
- }
-
-
- //no recursion, to prevent max recursion depth errors
- template <typename Unit>
- inline void ActiveTail<Unit>::destroyContents() {
- tailp_->disconnectTails();
- PolyLine<Unit>* nextPolyLinep = tailp_->next(HEAD);
- End end = tailp_->endConnectivity(HEAD);
- destroyPolyLine(tailp_);
- while(nextPolyLinep) {
- End nextEnd = nextPolyLinep->endConnectivity(!end); //get the direction of next polyLine
- PolyLine<Unit>* nextNextPolyLinep = nextPolyLinep->next(!end); //get the next polyline
- destroyPolyLine(nextPolyLinep); //destroy the current polyline
- end = nextEnd;
- nextPolyLinep = nextNextPolyLinep;
- }
- }
-
- template <typename Unit>
- inline typename ActiveTail<Unit>::iterator ActiveTail<Unit>::begin(bool isHole, orientation_2d orient) const {
- return iterator(this, isHole, orient);
- }
-
- template <typename Unit>
- inline typename ActiveTail<Unit>::iterator ActiveTail<Unit>::end() const {
- return iterator();
- }
-
- template <typename Unit>
- inline typename ActiveTail<Unit>::iteratorHoles ActiveTail<Unit>::beginHoles() const {
- return holesList_.begin();
- }
-
- template <typename Unit>
- inline typename ActiveTail<Unit>::iteratorHoles ActiveTail<Unit>::endHoles() const {
- return holesList_.end();
- }
-
- template <typename Unit>
- inline void ActiveTail<Unit>::writeOutFigureItrs(iterator& beginOut, iterator& endOut, bool isHole, orientation_2d orient) const {
- beginOut = begin(isHole, orient);
- endOut = end();
- }
-
- template <typename Unit>
- inline void ActiveTail<Unit>::writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const {
- beginOut = beginHoles();
- endOut = endHoles();
- }
-
- template <typename Unit>
- inline void ActiveTail<Unit>::writeOutFigure(std::vector<Unit>& outVec, bool isHole) const {
- //we start writing out the polyLine that this active tail points to at its tail
- unsigned int size = outVec.size();
- outVec.push_back(0); //place holder for size
- PolyLine<Unit>* nextPolyLinep = 0;
- if(!isHole){
- nextPolyLinep = otherTailp_->tailp_->writeOut(outVec);
- } else {
- nextPolyLinep = tailp_->writeOut(outVec);
- }
- Unit firsty = outVec[size + 1];
- if((getOrient() == HORIZONTAL) ^ !isHole) {
- //our first coordinate is a y value, so we need to rotate it to the end
- typename std::vector<Unit>::iterator tmpItr = outVec.begin();
- tmpItr += size;
- outVec.erase(++tmpItr); //erase the 2nd element
- }
- End startEnd = tailp_->endConnectivity(HEAD);
- if(isHole) startEnd = otherTailp_->tailp_->endConnectivity(HEAD);
- while(nextPolyLinep) {
- bool nextStartEnd = nextPolyLinep->endConnectivity(!startEnd);
- nextPolyLinep = nextPolyLinep->writeOut(outVec, startEnd);
- startEnd = nextStartEnd;
- }
- if((getOrient() == HORIZONTAL) ^ !isHole) {
- //we want to push the y value onto the end since we ought to have ended with an x
- outVec.push_back(firsty); //should never be executed because we want first value to be an x
- }
- //the vector contains the coordinates of the linked list of PolyLines in the correct order
- //first element is supposed to be the size
- outVec[size] = outVec.size() - 1 - size; //number of coordinates in vector
- //assert outVec[size] % 2 == 0 //it should be even
- //make the size negative for holes
- outVec[size] *= (isHole ? -1 : 1);
- }
-
- //no recursion to prevent max recursion depth errors
- template <typename Unit>
- inline PolyLine<Unit>* PolyLine<Unit>::writeOut(std::vector<Unit>& outVec, End startEnd) const {
- if(startEnd == HEAD){
- //forward order
- outVec.insert(outVec.end(), ptdata_.begin(), ptdata_.end());
- return tailp_;
- }else{
- //reverse order
- //do not reserve because we expect outVec to be large enough already
- for(int i = ptdata_.size() - 1; i >= 0; --i){
- outVec.push_back(ptdata_[i]);
- }
- //NT didn't know about this version of the API....
- //outVec.insert(outVec.end(), ptdata_.rbegin(), ptdata_.rend());
- return headp_;
- }
- }
-
- //solid indicates if it was joined by a solit or a space
- template <typename Unit>
- inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, std::vector<Unit>& outBufferTmp)
- {
- //checks to see if we closed a figure
- if(at1->isOtherTail(*at2)){
- //value of solid tells us if we closed solid or hole
- //and output the solid or handle the hole appropriately
- //if the hole needs to fracture across horizontal partition boundary we need to notify
- //the calling context to do so
- if(solid) {
- //the chains are being joined because there is solid to the right
- //this means that if the figure is closed at this point it must be a hole
- //because otherwise it would have to have another vertex to the right of this one
- //and would not be closed at this point
- return at1;
- } else {
- //assert pG != 0
- //the figure that was closed is a shell
- at1->writeOutFigure(outBufferTmp);
- //process holes of the polygon
- at1->copyHoles(*at2); //there should not be holes on at2, but if there are, copy them over
- const std::list<ActiveTail<Unit>*>& holes = at1->getHoles();
- for(typename std::list<ActiveTail<Unit>*>::const_iterator litr = holes.begin(); litr != holes.end(); ++litr) {
- (*litr)->writeOutFigure(outBufferTmp, true);
- //delete the hole
- (*litr)->destroyContents();
- destroyActiveTail((*litr)->getOtherActiveTail());
- destroyActiveTail((*litr));
- }
- //delete the polygon
- at1->destroyContents();
- //at2 contents are the same as at1, so it should not destroy them
- destroyActiveTail(at1);
- destroyActiveTail(at2);
- }
- return 0;
- }
- //join the two partial polygons into one large partial polygon
- at1->getTail()->joinTailToTail(*(at2->getTail()));
- *(at1->getOtherActiveTail()) = ActiveTail(at1->getOtherTail(), at2->getOtherActiveTail());
- *(at2->getOtherActiveTail()) = ActiveTail(at2->getOtherTail(), at1->getOtherActiveTail());
- at1->getOtherActiveTail()->copyHoles(*at1);
- at1->getOtherActiveTail()->copyHoles(*at2);
- destroyActiveTail(at1);
- destroyActiveTail(at2);
- return 0;
- }
-
- //solid indicates if it was joined by a solit or a space
- template <typename Unit>
- template <bool orientT>
- inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid,
- std::vector<PolyLinePolygonData<orientT, Unit> >& outBufferTmp) {
- //checks to see if we closed a figure
- if(at1->isOtherTail(*at2)){
- //value of solid tells us if we closed solid or hole
- //and output the solid or handle the hole appropriately
- //if the hole needs to fracture across horizontal partition boundary we need to notify
- //the calling context to do so
- if(solid) {
- //the chains are being joined because there is solid to the right
- //this means that if the figure is closed at this point it must be a hole
- //because otherwise it would have to have another vertex to the right of this one
- //and would not be closed at this point
- return at1;
- } else {
- //assert pG != 0
- //the figure that was closed is a shell
- outBufferTmp.push_back(at1);
- at1->copyHoles(*at2); //there should not be holes on at2, but if there are, copy them over
- }
- return 0;
- }
- //join the two partial polygons into one large partial polygon
- at1->getTail()->joinTailToTail(*(at2->getTail()));
- *(at1->getOtherActiveTail()) = ActiveTail<Unit>(at1->getOtherTail(), at2->getOtherActiveTail());
- *(at2->getOtherActiveTail()) = ActiveTail<Unit>(at2->getOtherTail(), at1->getOtherActiveTail());
- at1->getOtherActiveTail()->copyHoles(*at1);
- at1->getOtherActiveTail()->copyHoles(*at2);
- destroyActiveTail(at1);
- destroyActiveTail(at2);
- return 0;
- }
-
- template <class TKey, class T> inline typename std::map<TKey, T>::iterator findAtNext(std::map<TKey, T>& theMap,
- typename std::map<TKey, T>::iterator pos, const TKey& key)
- {
- if(pos == theMap.end()) return theMap.find(key);
- //if they match the mapItr is pointing to the correct position
- if(pos->first < key) {
- return theMap.find(key);
- }
- if(pos->first > key) {
- return theMap.end();
- }
- //else they are equal and no need to do anything to the iterator
- return pos;
- }
-
- // createActiveTailsAsPair is called in these two end cases of geometry
- // 1. lower left concave corner
- // ###|
- // ###|
- // ###|###
- // ###|###
- // 2. lower left convex corner
- // |###
- // |###
- // |
- // |
- // In case 1 there may be a hole propigated up from the bottom. If the fracture option is enabled
- // the two active tails that form the filament fracture line edges can become the new active tail pair
- // by pushing x and y onto them. Otherwise the hole simply needs to be associated to one of the new active tails
- // with add hole
- template <typename Unit>
- inline std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> createActiveTailsAsPair(Unit x, Unit y, bool solid, ActiveTail<Unit>* phole, bool fractureHoles) {
- ActiveTail<Unit>* at1;
- ActiveTail<Unit>* at2;
- if(!phole || !fractureHoles){
- at1 = createActiveTail<Unit>();
- at2 = createActiveTail<Unit>();
- (*at1) = ActiveTail<Unit>(VERTICAL, x, solid, at2);
- (*at2) = ActiveTail<Unit>(HORIZONTAL, y, !solid, at1);
- //provide a function through activeTail class to provide this
- at1->getTail()->joinHeadToHead(*(at2->getTail()));
- if(phole)
- at1->addHole(phole, fractureHoles); //assert fractureHoles == false
- return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2);
- }
- //assert phole is not null
- //assert fractureHoles is true
- if(phole->getOrient() == VERTICAL) {
- at2 = phole;
- } else {
- at2 = phole->getOtherActiveTail(); //should never be executed since orientation is expected to be vertical
- }
- //assert solid == false, we should be creating a corner with solid below and to the left if there was a hole
- at1 = at2->getOtherActiveTail();
- //assert at1 is horizontal
- at1->pushCoordinate(x);
- //assert at2 is vertical
- at2->pushCoordinate(y);
- return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2);
- }
-
- //Process edges connects vertical input edges (right or left edges of figures) to horizontal edges stored as member
- //data of the scanline object. It also creates now horizontal edges as needed to construct figures from edge data.
- //
- //There are only 12 geometric end cases where the scanline intersects a horizontal edge and even fewer unique
- //actions to take:
- // 1. Solid on both sides of the vertical partition after the current position and space on both sides before
- // ###|###
- // ###|###
- // |
- // |
- // This case does not need to be handled because there is no vertical edge at the current x coordinate.
- //
- // 2. Solid on both sides of the vertical partition before the current position and space on both sides after
- // |
- // |
- // ###|###
- // ###|###
- // This case does not need to be handled because there is no vertical edge at the current x coordinate.
- //
- // 3. Solid on the left of the vertical partition after the current position and space elsewhere
- // ###|
- // ###|
- // |
- // |
- // The horizontal edge from the left is found and turns upward because of the vertical right edge to become
- // the currently active vertical edge.
- //
- // 4. Solid on the left of the vertical partion before the current position and space elsewhere
- // |
- // |
- // ###|
- // ###|
- // The horizontal edge from the left is found and joined to the currently active vertical edge.
- //
- // 5. Solid to the right above and below and solid to the left above current position.
- // ###|###
- // ###|###
- // |###
- // |###
- // The horizontal edge from the left is found and joined to the currently active vertical edge,
- // potentially closing a hole.
- //
- // 6. Solid on the left of the vertical partion before the current position and solid to the right above and below
- // |###
- // |###
- // ###|###
- // ###|###
- // The horizontal edge from the left is found and turns upward because of the vertical right edge to become
- // the currently active vertical edge.
- //
- // 7. Solid on the right of the vertical partition after the current position and space elsewhere
- // |###
- // |###
- // |
- // |
- // Create two new ActiveTails, one is added to the horizontal edges and the other becomes the vertical currentTail
- //
- // 8. Solid on the right of the vertical partion before the current position and space elsewhere
- // |
- // |
- // |###
- // |###
- // The currentTail vertical edge turns right and is added to the horizontal edges data
- //
- // 9. Solid to the right above and solid to the left above and below current position.
- // ###|###
- // ###|###
- // ###|
- // ###|
- // The currentTail vertical edge turns right and is added to the horizontal edges data
- //
- // 10. Solid on the left of the vertical partion above and below the current position and solid to the right below
- // ###|
- // ###|
- // ###|###
- // ###|###
- // Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail
- //
- // 11. Solid to the right above and solid to the left below current position.
- // |###
- // |###
- // ###|
- // ###|
- // The currentTail vertical edge joins the horizontal edge from the left (may close a polygon)
- // Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail
- //
- // 12. Solid on the left of the vertical partion above the current position and solid to the right below
- // ###|
- // ###|
- // |###
- // |###
- // The currentTail vertical edge turns right and is added to the horizontal edges data.
- // The horizontal edge from the left turns upward and becomes the currentTail vertical edge
- //
- template <bool orientT, typename Unit>
- inline void ScanLineToPolygonItrs<orientT, Unit>::
- processEdges(iterator& beginOutput, iterator& endOutput,
- Unit currentX, std::vector<interval_data<Unit> >& leftEdges,
- std::vector<interval_data<Unit> >& rightEdges) {
- clearOutput_();
- typename std::map<Unit, ActiveTail<Unit>*>::iterator nextMapItr = tailMap_.begin();
- //foreach edge
- unsigned int leftIndex = 0;
- unsigned int rightIndex = 0;
- bool bottomAlreadyProcessed = false;
- ActiveTail<Unit>* currentTail = 0;
- bool holePassThrough = false;
- const Unit UnitMax = std::numeric_limits<Unit>::max();
- while(leftIndex < leftEdges.size() || rightIndex < rightEdges.size()) {
- interval_data<Unit> edges[2] = {interval_data<Unit> (UnitMax, UnitMax), interval_data<Unit> (UnitMax, UnitMax)};
- bool haveNextEdge = true;
- if(leftIndex < leftEdges.size())
- edges[0] = leftEdges[leftIndex];
- else
- haveNextEdge = false;
- if(rightIndex < rightEdges.size())
- edges[1] = rightEdges[rightIndex];
- else
- haveNextEdge = false;
- bool trailingEdge = edges[1].get(LOW) < edges[0].get(LOW);
- interval_data<Unit> & edge = edges[trailingEdge];
- interval_data<Unit> & nextEdge = edges[!trailingEdge];
- //process this edge
- if(!bottomAlreadyProcessed) {
- //assert currentTail = 0 || holePassThrough == true
-
- //process the bottom end of this edge
- typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(LOW));
- if(thisMapItr != tailMap_.end()) {
- //there is an edge in the map at the low end of this edge
- //it needs to turn upward and become the current tail
- ActiveTail<Unit>* tail = thisMapItr->second;
- if(currentTail) {
- //assert holePassThrough == true
- //stitch currentTail into this tail
- currentTail = tail->addHole(currentTail, fractureHoles_);
- holePassThrough = false;
- if(!fractureHoles_)
- currentTail->pushCoordinate(currentX);
- } else {
- currentTail = tail;
- currentTail->pushCoordinate(currentX);
- }
- //assert currentTail->getOrient() == VERTICAL
- nextMapItr = thisMapItr; //set nextMapItr to the next position after this one
- ++nextMapItr;
- //remove thisMapItr from the map
- tailMap_.erase(thisMapItr);
- } else {
- //there is no edge in the map at the low end of this edge
- //we need to create one and another one to be the current vertical tail
- //if this is a trailing edge then there is space to the right of the vertical edge
- //so pass the inverse of trailingEdge to indicate solid to the right
- std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair =
- createActiveTailsAsPair(currentX, edge.get(LOW), !trailingEdge, currentTail, fractureHoles_);
- currentTail = tailPair.first;
- tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(LOW), tailPair.second));
- // leave nextMapItr unchanged
- }
-
- }
- if(haveNextEdge && edge.get(HIGH) == nextEdge.get(LOW)) {
- //the top of this edge is equal to the bottom of the next edge, process them both
- bottomAlreadyProcessed = true;
- typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(HIGH));
- if(thisMapItr == tailMap_.end()) //assert this should never happen
- return;
- if(trailingEdge) {
- //geometry at this position
- // |##
- // |##
- // -----
- // ##|
- // ##|
- //current tail should join thisMapItr tail
- ActiveTail<Unit>* tail = thisMapItr->second;
- //pass false because they are being joined because space is to the right and it will close a solid figure
- ActiveTail<Unit>::joinChains(currentTail, tail, false, outputPolygons_);
- //two new tails are created, the vertical becomes current tail, the horizontal becomes thisMapItr tail
- //pass true becuase they are created at the lower left corner of some solid
- //pass null because there is no hole pointer possible
- std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair =
- createActiveTailsAsPair<Unit>(currentX, edge.get(HIGH), true, 0, fractureHoles_);
- currentTail = tailPair.first;
- thisMapItr->second = tailPair.second;
- } else {
- //geometry at this position
- // ##|
- // ##|
- // -----
- // |##
- // |##
- //current tail should turn right
- currentTail->pushCoordinate(edge.get(HIGH));
- //thisMapItr tail should turn up
- thisMapItr->second->pushCoordinate(currentX);
- //thisMapItr tail becomes current tail and current tail becomes thisMapItr tail
- std::swap(currentTail, thisMapItr->second);
- }
- nextMapItr = thisMapItr; //set nextMapItr to the next position after this one
- ++nextMapItr;
- } else {
- //there is a gap between the top of this edge and the bottom of the next, process the top of this edge
- bottomAlreadyProcessed = false;
- //process the top of this edge
- typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(HIGH));
- if(thisMapItr != tailMap_.end()) {
- //thisMapItr is pointing to a horizontal edge in the map at the top of this vertical edge
- //we need to join them and potentially close a figure
- //assert currentTail != 0
- //assert holePassThrough = false
- ActiveTail<Unit>* tail = thisMapItr->second;
- //pass the opositve of trailing edge to mean that they are joined because of solid to the right
- currentTail = ActiveTail<Unit>::joinChains(currentTail, tail, !trailingEdge, outputPolygons_);
- nextMapItr = thisMapItr; //set nextMapItr to the next position after this one
- ++nextMapItr;
- if(currentTail) {
- Unit nextItrY = UnitMax;
- if(nextMapItr != tailMap_.end()) {
- nextItrY = nextMapItr->first;
- }
- //for it to be a hole this must have been a left edge
- Unit leftY = UnitMax;
- if(leftIndex + 1 < leftEdges.size())
- leftY = leftEdges[leftIndex+1].get(LOW);
- Unit rightY = nextEdge.get(LOW);
- if(!haveNextEdge || (nextItrY < leftY && nextItrY < rightY)) {
- //we need to add it to the next edge above it in the map
- tail = nextMapItr->second;
- tail = tail->addHole(currentTail, fractureHoles_);
- if(fractureHoles_) {
- //some small additional work stitching in the filament
- tail->pushCoordinate(nextItrY);
- nextMapItr->second = tail;
- }
- //set current tail to null
- currentTail = 0;
- }
- }
- //delete thisMapItr from the map
- tailMap_.erase(thisMapItr);
- } else {
- //currentTail must turn right and be added into the map
- currentTail->pushCoordinate(edge.get(HIGH));
- //assert currentTail->getOrient() == HORIZONTAL
- tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(HIGH), currentTail));
- //set currentTail to null
- currentTail = 0;
- //leave nextMapItr unchanged, it is still next
- }
- }
-
- //increment index
- leftIndex += !trailingEdge;
- rightIndex += trailingEdge;
- } //end while
- beginOutput = outputPolygons_.begin();
- endOutput = outputPolygons_.end();
- } //end function
-
- template<bool orientT, typename Unit>
- inline void ScanLineToPolygonItrs<orientT, Unit>::clearOutput_() {
- for(unsigned int i = 0; i < outputPolygons_.size(); ++i) {
- ActiveTail<Unit>* at1 = outputPolygons_[i].yield();
- const std::list<ActiveTail<Unit>*>& holes = at1->getHoles();
- for(typename std::list<ActiveTail<Unit>*>::const_iterator litr = holes.begin(); litr != holes.end(); ++litr) {
- //delete the hole
- (*litr)->destroyContents();
- destroyActiveTail((*litr)->getOtherActiveTail());
- destroyActiveTail((*litr));
- }
- //delete the polygon
- at1->destroyContents();
- //at2 contents are the same as at1, so it should not destroy them
- destroyActiveTail((at1)->getOtherActiveTail());
- destroyActiveTail(at1);
- }
- outputPolygons_.clear();
- }
-
-}; //polygon_formation namespace
Deleted: sandbox/gtl/gtl/polygon_set_data.h
==============================================================================
--- sandbox/gtl/gtl/polygon_set_data.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,133 +0,0 @@
-/*
- 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).
-*/
-struct operator_provides_storage {};
-struct operator_requires_copy {};
-
-template <typename T>
-class polygon_set_data {
-public:
- typedef T coordinate_type;
- typedef std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > > value_type;
- typedef typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::const_iterator iterator_type;
- typedef polygon_set_data operator_arg_type;
- typedef operator_provides_storage operator_storage_tag;
-
- /// default constructor
- inline polygon_set_data() : orient_(HORIZONTAL), dirty_(false), unsorted_(false) {}
-
- /// constructor
- inline polygon_set_data(orientation_2d orient) : orient_(orient), dirty_(false), unsorted_(false) {}
-
- /// constructor from an iterator pair over vertex data
- template <class iT>
- inline polygon_set_data(orientation_2d orient, iT input_begin, iT input_end) {
- dirty_ = true;
- unsorted_ = true;
- for( ; input_begin != input_end; ++input_begin) { data_.push_back(*input_begin); }
- }
-
- /// copy constructor
- inline polygon_set_data(const polygon_set_data& that) :
- orient_(that.orient_), data_(that.data_), dirty_(that.dirty), unsorted_(that.unsorted_) {}
-
- /// copy with orientation change constructor
- inline polygon_set_data(orientation_2d orient, const polygon_set_data& that) :
- orient_(orient), dirty_(false), unsorted_(false) {
- if(that.orient() == orient) { (*this) = that; }
- else if(!that.data_.empty()) {
- dirty_ = unsorted_ = true;
- iterator_vertex_orient_conversion<iterator_type> itr1(that.data_.begin()), iter2(that.data_.end());
- data_.resize(that.data_.size());
- for( ; itr1 != iter2; ++itr1) {
- data_.push_back(*itr1);
- }
- }
- }
-
- /// destructor
- inline ~polygon_set_data() {}
-
- /// assignement operator
- inline polygon_set_data& operator=(const polygon_set_data& that) {
- if(this == &that) return *this;
- orient_ = that.orient_;
- data_ = that.data_;
- dirty_ = that.dirty_;
- unsorted_ = that.unsorted_;
- return *this;
- }
-
- /// equivalence operator
- inline bool operator==(const polygon_set_data& p) const {
- if(orient_ == p.orient()) {
- clean();
- p.clean();
- return data_ == p.data_;
- } else {
- return false;
- }
- }
-
- /// inequivalence operator
- inline bool operator!=(const polygon_set_data& p) const {
- return !((*this) == p);
- }
-
- /// get iterator to begin vertex data
- inline iterator_type begin() const {
- return data_.begin();
- }
-
- /// get iterator to end vertex data
- inline iterator_type end() const {
- return data_.end();
- }
-
- const value_type& value() const {
- return data_;
- }
-
- /// clear the contents of the polygon_set_data
- inline void clear() { data_.clear(); dirty_ = unsorted_ = false; }
-
- /// find out if Polygon set is empty
- inline bool empty() const { return data_.empty(); }
-
- /// find out if Polygon set is sorted
- inline bool sorted() const { return !unsorted_; }
-
- /// find out if Polygon set is clean
- inline bool dirty() const { return dirty_; }
-
- /// get the scanline orientation of the polygon set
- inline orientation_2d orient() const { return orient_; }
-
- void clean() const {
- if(unsorted_) sort();
- if(dirty_) {
- applyBooleanOr(data_);
- dirty_ = false;
- }
- }
-
- void sort() const{
- std::sort(data_.begin(), data_.end());
- unsorted_ = false;
- }
-
- void set(const value_type& value, orientation_2d orient) {
- data_ = value;
- orient_ = orient;
- }
-private:
- orientation_2d orient_;
- mutable value_type data_;
- mutable bool dirty_;
- mutable bool unsorted_;
-
-};
Deleted: sandbox/gtl/gtl/polygon_set_traits.h
==============================================================================
--- sandbox/gtl/gtl/polygon_set_traits.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,35 +0,0 @@
-/*
- 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).
-*/
-
-template <typename T>
-struct polygon_set_traits {
- typedef typename T::coordinate_type coordinate_type;
- typedef typename T::iterator_type iterator_type;
- typedef typename T::operator_arg_type operator_arg_type;
-
- static inline iterator_type begin(const T& polygon_set) {
- return polygon_set.begin();
- }
-
- static inline iterator_type end(const T& polygon_set) {
- return polygon_set.end();
- }
-
- static inline void set(T& polygon_set, const std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >& value,
- orientation_2d orient) {
- polygon_set.set(value, orient);
- }
-
- static inline orientation_2d orient(const T& polygon_set) { return polygon_set.orient(); }
-
- static inline bool dirty(const T& polygon_set) { return polygon_set.dirty(); }
-
- static inline bool sorted(const T& polygon_set) { return polygon_set.sorted(); }
-
-};
-
Deleted: sandbox/gtl/gtl/polygon_set_view.h
==============================================================================
--- sandbox/gtl/gtl/polygon_set_view.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,233 +0,0 @@
-/*
- 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).
-*/
-
-template <typename value_type, typename arg_type>
-inline void insert_into_view_arg(value_type& dest, const arg_type& arg, orientation_2d orient) {
- typedef typename polygon_set_traits<arg_type>::iterator_type literator;
- literator itr1, itr2;
- itr1 = polygon_set_traits<arg_type>::begin(arg);
- itr2 = polygon_set_traits<arg_type>::end(arg);
- if(polygon_set_traits<arg_type>::orient(arg) == orient) {
- for( ; itr1 != itr2; ++itr1) {
- dest.push_back(*itr1);
- }
- if(!polygon_set_traits<arg_type>::sorted(arg)) std::sort(dest.begin(), dest.end());
- } else {
- iterator_vertex_orient_conversion<literator> citr2(itr2);
- for(iterator_vertex_orient_conversion<literator> citr1(itr1); citr1 != citr2; ++citr1) {
- dest.push_back(*citr1);
- }
- std::sort(dest.begin(), dest.end());
- }
-}
-
-
-template <typename ltype, typename rtype, typename op_type, typename ltag, typename rtag>
-class polygon_set_view {
-public:
- typedef typename polygon_set_traits<ltype>::coordinate_type coordinate_type;
- typedef std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > > value_type;
- typedef typename value_type::iterator iterator_type;
- typedef polygon_set_view operator_arg_type;
- typedef operator_provides_storage operator_storage_tag;
-private:
- const ltype& lvalue_;
- const rtype& rvalue_;
- op_type op_;
- orientation_2d orient_;
- mutable value_type output_;
-public:
- polygon_set_view(const ltype& lvalue,
- const rtype& rvalue,
- orientation_2d orient,
- op_type op) :
- lvalue_(lvalue), rvalue_(rvalue), orient_(orient), op_(op) {}
-
- /// get iterator to begin vertex data
- const value_type& value() const {
- if(output_.empty()) {
- value_type linput_;
- value_type rinput_;
- insert_into_view_arg(linput_, lvalue_, orient_);
- insert_into_view_arg(rinput_, rvalue_, orient_);
- boolean_op::applyBooleanBinaryOp(output_, linput_, rinput_, boolean_op::BinaryCount<op_type>());
- }
- return output_;
- }
-
- orientation_2d orient() const { return orient_; }
- bool dirty() const { return false; } //result of a boolean is clean
- bool sorted() const { return true; } //result of a boolean is sorted
-
- //insert is not inteded to be called because a view is read only
- void insert(const value_type& value,
- orientation_2d orient) const {
- //throw a helpful exception
- }
- void sort() const {} //is always sorted
-};
-
-template <typename ltype, typename rtype, typename op_type>
-class polygon_set_view<ltype, rtype, op_type, operator_provides_storage, operator_provides_storage> {
-public:
- typedef typename polygon_set_traits<ltype>::coordinate_type coordinate_type;
- typedef std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > > value_type;
- typedef typename value_type::iterator iterator_type;
- typedef polygon_set_view operator_arg_type;
- typedef operator_provides_storage operator_storage_tag;
-private:
- const ltype& lvalue_;
- const rtype& rvalue_;
- op_type op_;
- orientation_2d orient_;
- mutable value_type output_;
-public:
- polygon_set_view(const ltype& lvalue,
- const rtype& rvalue,
- orientation_2d orient,
- op_type op) :
- lvalue_(lvalue), rvalue_(rvalue), op_(op), orient_(orient) {}
-
- /// get iterator to begin vertex data
- const value_type& value() const {
- if(output_.empty()) {
- value_type linput_;
- value_type rinput_;
- if(orient_ != lvalue_.orient()) {
- insert_into_view_arg(linput_, lvalue_, orient_);
- if(orient_ != rvalue_.orient()) {
- insert_into_view_arg(rinput_, rvalue_, orient_);
- boolean_op::applyBooleanBinaryOp(output_, linput_, rinput_, boolean_op::BinaryCount<op_type>());
- } else {
- boolean_op::applyBooleanBinaryOp(output_, linput_, rvalue_.value(), boolean_op::BinaryCount<op_type>());
- }
- } else {
- if(!lvalue_.sorted()) lvalue_.sort();
- if(orient_ != rvalue_.orient()) {
- insert_into_view_arg(rinput_, rvalue_, orient_);
- boolean_op::applyBooleanBinaryOp(output_, lvalue_.value(), rinput_, boolean_op::BinaryCount<op_type>());
- } else {
- if(!rvalue_.sorted()) rvalue_.sort();
- boolean_op::applyBooleanBinaryOp(output_, lvalue_.value(), rvalue_.value(), boolean_op::BinaryCount<op_type>());
- }
- }
- }
- return output_;
- }
-
- orientation_2d orient() const { return orient_; }
- bool dirty() const { return false; } //result of a boolean is clean
- bool sorted() const { return true; } //result of a boolean is sorted
-
- //insert is not inteded to be called because a view is read only
- void insert(const value_type& value,
- orientation_2d orient) const {
- //throw a helpful exception
- }
- void sort() const {} //is always sorted
-};
-
-template <typename ltype, typename rtype, typename op_type, typename rtag>
-class polygon_set_view<ltype, rtype, op_type, operator_provides_storage, rtag> {
-public:
- typedef typename polygon_set_traits<ltype>::coordinate_type coordinate_type;
- typedef std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > > value_type;
- typedef typename value_type::iterator iterator_type;
- typedef polygon_set_view operator_arg_type;
- typedef operator_provides_storage operator_storage_tag;
-private:
- const ltype& lvalue_;
- const rtype& rvalue_;
- op_type op_;
- orientation_2d orient_;
- mutable value_type output_;
-public:
- polygon_set_view(const ltype& lvalue,
- const rtype& rvalue,
- orientation_2d orient,
- op_type op) :
- lvalue_(lvalue), rvalue_(rvalue), op_(op) , orient_(orient) {}
-
- /// get iterator to begin vertex data
- const value_type& value() const {
- if(output_.empty()) {
- value_type linput_;
- value_type rinput_;
- insert_into_view_arg(rinput_, rvalue_, orient_);
- if(orient_ != lvalue_.orient()) {
- insert_into_view_arg(linput_, lvalue_, orient_);
- boolean_op::applyBooleanBinaryOp(output_, linput_, rinput_, boolean_op::BinaryCount<op_type>());
- } else {
- if(!lvalue_.sorted()) lvalue_.sort();
- boolean_op::applyBooleanBinaryOp(output_, lvalue_.value(), rinput_, boolean_op::BinaryCount<op_type>());
- }
- }
- return output_;
- }
-
- orientation_2d orient() const { return orient_; }
- bool dirty() const { return false; } //result of a boolean is clean
- bool sorted() const { return true; } //result of a boolean is sorted
-
- //insert is not inteded to be called because a view is read only
- void insert(const value_type& value,
- orientation_2d orient) const {
- //throw a helpful exception
- }
- void sort() const {} //is always sorted
-};
-
-template <typename ltype, typename rtype, typename op_type, typename ltag>
-class polygon_set_view<ltype, rtype, op_type, ltag, operator_provides_storage> {
-public:
- typedef typename polygon_set_traits<ltype>::coordinate_type coordinate_type;
- typedef std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > > value_type;
- typedef typename value_type::iterator iterator_type;
- typedef polygon_set_view operator_arg_type;
-private:
- const ltype& lvalue_;
- const rtype& rvalue_;
- op_type op_;
- orientation_2d orient_;
- mutable value_type output_;
- mutable value_type linput_;
-public:
- polygon_set_view(const ltype& lvalue,
- const rtype& rvalue,
- orientation_2d orient,
- op_type op) :
- lvalue_(lvalue), rvalue_(rvalue), op_(op), orient_(orient) {}
-
- /// get iterator to begin vertex data
- const value_type& value() const {
- if(output_.empty()) {
- value_type linput_;
- value_type rinput_;
- insert_into_view_arg(linput_, lvalue_, orient_);
- if(orient_ != lvalue_.orient()) {
- insert_into_view_arg(rinput_, rvalue_, orient_);
- boolean_op::applyBooleanBinaryOp(output_, linput_, rinput_, boolean_op::BinaryCount<op_type>());
- } else {
- if(!rvalue_.sorted()) rvalue_.sort();
- boolean_op::applyBooleanBinaryOp(output_, linput_, rvalue_.value(), boolean_op::BinaryCount<op_type>());
- }
- }
- return output_;
- }
-
- orientation_2d orient() const { return orient_; }
- bool dirty() const { return false; } //result of a boolean is clean
- bool sorted() const { return true; } //result of a boolean is sorted
-
- //insert is not inteded to be called because a view is read only
- void insert(const value_type& value,
- orientation_2d orient) const {
- //throw a helpful exception
- }
- void sort() const {} //is always sorted
-};
Deleted: sandbox/gtl/gtl/polygon_set_wrapper.h
==============================================================================
--- sandbox/gtl/gtl/polygon_set_wrapper.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,80 +0,0 @@
-/*
- 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).
-*/
-template <typename T>
-class polygon_set_const_wrapper {
-private:
- const T& t_;
-public:
- typedef typename T::value_type geometry_type;
- typedef typename geometry_traits<geometry_type>::geometry_concept geometry_concept;
- typedef typename geometry_concept::template registration<geometry_type>::coordinate_type coordinate_type;
- typedef iterator_geometry_range_to_set<geometry_concept, typename T::const_iterator> iterator_type;
- typedef polygon_set_const_wrapper operator_arg_type;
- typedef operator_requires_copy operator_storage_tag;
-
- polygon_set_const_wrapper(const T& t) : t_(t) {}
-
- inline iterator_type begin() const {
- return iterator_type(t_.begin());
- }
-
- inline iterator_type end(const T& polygon_set) const {
- return iterator_type(t_.end());
- }
-
- inline orientation_2d orient() const { return HORIZONTAL; }
-
- inline bool dirty(const T& polygon_set) const { return true; }
-
- inline bool sorted(const T& polygon_set) const { return false; }
-
-};
-
-template <typename T>
-polygon_set_const_wrapper<T> wrap_const(const T& t) {
- return polygon_set_const_wrapper<T>(t);
-}
-
-template <typename T>
-class polygon_set_wrapper {
-private:
- T& t_;
-public:
- typedef typename T::value_type geometry_type;
- typedef typename geometry_traits<geometry_type>::geometry_concept geometry_concept;
- typedef typename geometry_concept::template registration<geometry_type>::coordinate_type coordinate_type;
- typedef iterator_geometry_range_to_set<geometry_concept, typename T::const_iterator> iterator_type;
- typedef polygon_set_wrapper operator_arg_type;
- typedef operator_requires_copy operator_storage_tag;
-
- inline polygon_set_wrapper(T& t) : t_(t) {}
-
- inline iterator_type begin() const {
- return iterator_type(t_.begin());
- }
-
- inline iterator_type end(const T& polygon_set) const {
- return iterator_type(t_.end());
- }
-
- inline void set(const std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >& value,
- orientation_2d orient) {
- }
-
- inline orientation_2d orient() const { return HORIZONTAL; }
-
- inline bool dirty(const T& polygon_set) const { return true; }
-
- inline bool sorted(const T& polygon_set) const { return false; }
-
-};
-
-template <typename T>
-polygon_set_const_wrapper<T> wrap(const T& t) {
- return polygon_set_wrapper<T>(t);
-}
Deleted: sandbox/gtl/gtl/polygon_traits.h
==============================================================================
--- sandbox/gtl/gtl/polygon_traits.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,40 +0,0 @@
-/*
- 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).
-*/
-template <class T>
-struct polygon_traits {
- typedef typename T::coordinate_type coordinate_type;
- typedef typename T::iterator_type iterator_type;
-
- /// Get the begin iterator
- static inline iterator_type begin(const T& t) {
- return t.begin();
- }
-
- /// Get the end iterator
- static inline iterator_type end(const T& t) {
- return t.end();
- }
-
- /// Set the data of a polygon with the unique coordinates in an iterator, starting with an x
- template <class iT>
- static inline T& set(T& t, iT input_begin, iT input_end) {
- t.set(input_begin, input_end);
- return t;
- }
-
- /// Get the number of sides of the polygon
- static inline unsigned int size(const T& t) {
- return t.size();
- }
-
- /// Get the winding direction of the polygon
- static inline winding_direction winding(const T& t) {
- return unknown_winding;
- }
-};
-
Deleted: sandbox/gtl/gtl/polygon_with_holes_concept.h
==============================================================================
--- sandbox/gtl/gtl/polygon_with_holes_concept.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,184 +0,0 @@
-/*
- 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).
-*/
-
-struct polygon_with_holes_concept : polygon_concept {
-public:
-
- template<typename polygon_with_holes_type, typename hole_iterator_type>
- static void set_holes(polygon_with_holes_type& polygon, hole_iterator_type holes_begin, hole_iterator_type holes_end) {
- polygon_with_holes_traits<polygon_with_holes_type>::set_holes(polygon, holes_begin, holes_end);
- }
-
- template <typename polygon_with_holes_type>
- static typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type begin_holes(const polygon_with_holes_type& polygon) {
- return polygon_with_holes_traits<polygon_with_holes_type>::begin_holes(polygon);
- }
-
- template <typename polygon_with_holes_type>
- static typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type end_holes(const polygon_with_holes_type& polygon) {
- return polygon_with_holes_traits<polygon_with_holes_type>::end_holes(polygon);
- }
-
- template <typename polygon_with_holes_type_1, typename polygon_with_holes_type_2>
- static polygon_with_holes_type_1 copy_construct(const polygon_with_holes_type_2& polygon) {
- polygon_with_holes_type_1 retval;
- set(retval, polygon_concept::begin(polygon), polygon_concept::end(polygon));
- set_holes(retval, polygon_with_holes_concept::begin_holes(polygon), polygon_with_holes_concept::end_holes(polygon));
- return retval;
- }
-
- template <typename polygon_with_holes_type>
- static std::size_t size_holes(const polygon_with_holes_type& polygon) {
- return polygon_with_holes_traits<polygon_with_holes_type>::size_holes(polygon);
- }
-
- template <typename polygon_with_holes_type_1, typename polygon_with_holes_type_2>
- static polygon_with_holes_type_1& assign(polygon_with_holes_type_1& lvalue, const polygon_with_holes_type_2& rvalue) {
- set(lvalue, polygon_concept::begin(rvalue), polygon_concept::end(rvalue));
- set_holes(lvalue, begin_holes(rvalue), end_holes(rvalue));
- return lvalue;
- }
-
- template <typename polygon_with_holes_type>
- static typename polygon_with_holes_traits<polygon_with_holes_type>::coordinate_type
- area(const polygon_with_holes_type& polygon) {
- typename polygon_traits<polygon_with_holes_type>::coordinate_type retval = polygon_concept::area(polygon);
- typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
- e = end_holes(polygon);
- for(b = begin_holes(polygon); b != e; ++b) {
- retval -= polygon_concept::area(*b);
- }
- }
-
- /// check if point is inside polygon
- template <typename polygon_with_holes_type, typename point_type>
- static bool contains(const polygon_with_holes_type& polygon, const point_type& point,
- bool consider_touch, point_concept pc) {
- typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
- e = end_holes(polygon);
- for(b = begin_holes(polygon); b != e; ++b) {
- if(polygon_concept::contains(*b, point, !consider_touch, pc)) {
- return false;
- }
- }
- return polygon_concept::contains(polygon, point, consider_touch, pc);
- }
-
- /// get the perimeter of the polygon
- template <typename polygon_with_holes_type>
- static typename polygon_traits<polygon_with_holes_type>::coordinate_type
- perimeter(const polygon_with_holes_type& polygon) {
- typename polygon_traits<polygon_with_holes_type>::coordinate_type retval = polygon_concept::perimeter(polygon);
- typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
- e = end_holes(polygon);
- for(b = begin_holes(polygon); b != e; ++b) {
- retval -= polygon_concept::perimeter(*b);
- }
- }
-
- // //awaiting re-implementation of iterator_edges and edge concept
- // template <typename polygon_with_holes_type, typename point_type>
- // static point_type project(const polygon_with_holes_type& polygon, const point_type& point) const {
- // typedef point_data<typename polygon_with_holes_traits<polygon_with_holes_type>::coordinate_type> point_type_2;
- // point_type_2 retval = polygon_concept::project(polygon, point);
- // double dist = point_concept::euclidian_distance(point retval);
- // polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
- // e = end_holes(polygon);
- // for(b = begin_holes(polygon); b != e; ++b) {
- // point_type_2 hole_point = polygon_concept::project(*b, point);
- // double hole_dist = point_concept::euclidian_distance(point hole_point);
- // if(hole_dist < dist) {
- // retval = hole_point;
- // dist = hole_dist;
- // }
- // }
- // return retval;
- // }
-
- // //awaiting re-implementation of iterator_edges and edge concept
- // template <typename polygon_with_holes_type, typename point_type>
- // static point_type project(point_type& result, const polygon_with_holes_type& polygon,
- // const point_type& point, direction_2d dir) {
- // typedef point_data<typename polygon_with_holes_traits<polygon_with_holes_type>::coordinate_type> point_type_2;
- // point_type_2 retval = polygon_concept::project(polygon, point, dir);
- // double dist = point_concept::euclidian_distance(point retval);
- // polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
- // e = end_holes(polygon);
- // for(b = begin_holes(polygon); b != e; ++b) {
- // point_type_2 hole_point = polygon_concept::project(*b, point, dir);
- // double hole_dist = point_concept::euclidian_distance(point hole_point);
- // if(hole_dist < dist) {
- // retval = hole_point;
- // dist = hole_dist;
- // }
- // }
- // return retval;
- // }
-
- template <typename polygon_with_holes_type, typename coordinate_type_1, typename coordinate_type_2>
- static void move(polygon_with_holes_type& polygon, coordinate_type_1 x_displacement, coordinate_type_2 y_displacement) {
- typedef typename polygon_with_holes_traits<polygon_with_holes_type>::hole_type hole_type;
- std::vector<hole_type> holes;
- holes.resize(size_holes(polygon));
- typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type b, e;
- e = end_holes(polygon);
- for(b = begin_holes(polygon); b != e; ++b) {
- holes.push_back(*b);
- polygon_concept::move(holes.back(), x_displacement, y_displacement);
- }
- set_holes(polygon, holes.begin(), holes.end());
- polygon_concept::move(polygon, x_displacement, y_displacement);
- }
-
- /// move polygon by delta in orient
- template <typename polygon_with_holes_type, typename coordinate_type_1>
- static void move(polygon_with_holes_type& polygon, orientation_2d orient, coordinate_type_1 displacement) {
- if(orient == HORIZONTAL) {
- move(polygon, displacement, 0);
- } else {
- move(polygon, 0, displacement);
- }
- }
-};
-
-template <typename T>
-inline void testPolygonWithHolesImpl() {
- rectangle_data<T> rect = rectangle_concept::construct<rectangle_data<T> >(0, 0, 100, 100);
- polygon_data<T> polyHole = polygon_concept::construct_from_rectangle<polygon_data<T> >(rectangle_concept::construct<rectangle_data<T> >(10, 10, 90, 90));
- polygon_with_holes_data<T> pwh = polygon_with_holes_concept::construct_from_rectangle<polygon_with_holes_data<T> >(rect);
- polygon_with_holes_concept::set_holes(pwh, &polyHole, (&polyHole)+1);
- //std::cout << pwh << std::endl;
- std::cout << "PolygonWithHoles test pattern 1 1 1 1 1 1 0 0 0 0 0 0\n";
- std::cout << "PolygonWithHoles test pattern ";
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(1, 11), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(10, 10), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(10, 90), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(90, 90), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(90, 10), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(90, 80), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(12, 12), true, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(10, 10), false, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(10, 90), false, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(90, 90), false, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(90, 10), false, point_concept())
- << " " ;
- std::cout << polygon_with_holes_concept::contains(pwh, point_data<T>(90, 80), false, point_concept())
- << "\n";
-
- polygon_with_holes_concept::move(pwh, 5, 5);
-}
Deleted: sandbox/gtl/gtl/polygon_with_holes_data.h
==============================================================================
--- sandbox/gtl/gtl/polygon_with_holes_data.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,82 +0,0 @@
-/*
- 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).
-*/
-
-template <typename T>
-class polygon_with_holes_data {
-public:
- typedef T coordinate_type;
- typedef typename std::vector<coordinate_type>::const_iterator iterator_type;
- typedef typename std::list<polygon_data<coordinate_type> >::const_iterator iterator_holes_type;
- typedef polygon_data<coordinate_type> hole_type;
-
- /// default constructor of point does not initialize x and y
- inline polygon_with_holes_data(){;} //do nothing default constructor
-
- /// initialize a polygon from x,y values, it is assumed that the first is an x
- /// and that the input is a well behaved polygon
- template<class iT>
- inline polygon_with_holes_data& set(iT input_begin, iT input_end) {
- self_.set(input_begin, input_end);
- return *this;
- }
-
- /// initialize a polygon from x,y values, it is assumed that the first is an x
- /// and that the input is a well behaved polygon
- template<class iT>
- inline polygon_with_holes_data& set_holes(iT input_begin, iT input_end) {
- holes_.clear(); //just in case there was some old data there
- for( ; input_begin != input_end; ++ input_begin) {
- holes_.push_back(hole_type());
- holes_.back().set((*input_begin).begin(), (*input_begin).end());
- }
- return *this;
- }
-
- /// copy constructor (since we have dynamic memory)
- inline polygon_with_holes_data(const polygon_with_holes_data& that) : self_(that.self_),
- holes_(that.holes_) {}
-
- /// assignment operator (since we have dynamic memory do a deep copy)
- inline polygon_with_holes_data& operator=(const polygon_with_holes_data& that) {
- self_ = that.self_;
- holes_ = that.holes_;
- return *this;
- }
-
- /// get begin iterator, returns a pointer to a const coordinate_type
- inline const iterator_type begin() const {
- return self_.begin();
- }
-
- /// get end iterator, returns a pointer to a const coordinate_type
- inline const iterator_type end() const {
- return self_.end();
- }
-
- inline unsigned int size() const {
- return self_.size();
- }
-
- /// get begin iterator, returns a pointer to a const polygon
- inline const iterator_holes_type begin_holes() const {
- return holes_.begin();
- }
-
- /// get end iterator, returns a pointer to a const polygon
- inline const iterator_holes_type end_holes() const {
- return holes_.end();
- }
-
- inline unsigned int size_holes() const {
- return holes_.size();
- }
-
-private:
- polygon_data<coordinate_type> self_;
- std::list<hole_type> holes_;
-};
Deleted: sandbox/gtl/gtl/polygon_with_holes_traits.h
==============================================================================
--- sandbox/gtl/gtl/polygon_with_holes_traits.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,37 +0,0 @@
-/*
- 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).
-*/
-
-template <class T>
-struct polygon_with_holes_traits {
- typedef typename T::coordinate_type coordinate_type;
- typedef typename T::iterator_holes_type iterator_holes_type;
- typedef typename T::hole_type hole_type;
-
- /// Get the begin iterator
- static inline iterator_holes_type begin_holes(const T& t) {
- return t.begin_holes();
- }
-
- /// Get the end iterator
- static inline iterator_holes_type end_holes(const T& t) {
- return t.end_holes();
- }
-
- /// Set the data of a polygon with the unique coordinates in an iterator, starting with an x
- template <class iT>
- static inline T& set_holes(T& t, iT inputBegin, iT inputEnd) {
- t.set_holes(inputBegin, inputEnd);
- return t;
- }
-
- /// Get the number of holes
- static inline unsigned int size_holes(const T& t) {
- return t.size_holes();
- }
-
-};
Deleted: sandbox/gtl/gtl/post_concept_definitions.h
==============================================================================
--- sandbox/gtl/gtl/post_concept_definitions.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,49 +0,0 @@
-/*
- 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).
-*/
-template <typename T>
-template <typename interval_type>
-inline void rectangle_data<T>::set(orientation_2d orient, const interval_type& interval) {
- ranges_[orient.to_int()].set(LOW, interval_concept::get(interval, LOW));
- ranges_[orient.to_int()].set(HIGH, interval_concept::get(interval, HIGH));
-}
-
-template <class T>
-template <class T2>
-point_data<T>& point_data<T>::operator=(const T2& rvalue) {
- point_concept::assign(*this, rvalue);
- return *this;
-}
-
-template <class T>
-template <class T2>
-interval_data<T>& interval_data<T>::operator=(const T2& rvalue) {
- interval_concept::assign(*this, rvalue);
- return *this;
-}
-
-template <class T>
-template <class T2>
-rectangle_data<T>& rectangle_data<T>::operator=(const T2& rvalue) {
- rectangle_concept::assign(*this, rvalue);
- return *this;
-}
-
-template <class T>
-template <class T2>
-point_3d_data<T>& point_3d_data<T>::operator=(const T2& rvalue) {
- point_3d_concept::assign(*this, rvalue);
- return *this;
-}
-
-template <class T>
-template <class T2>
-polygon_data<T>& polygon_data<T>::operator=(const T2& rvalue) {
- polygon_concept::assign(*this, rvalue);
- return *this;
-}
-
Deleted: sandbox/gtl/gtl/post_geometry_traits_definitions.h
==============================================================================
--- sandbox/gtl/gtl/post_geometry_traits_definitions.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,14 +0,0 @@
-/*
- 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).
-*/
-
-template <typename geometry_type>
-struct component_type {
- typedef typename geometry_traits<geometry_type>::geometry_concept::template
- registration<geometry_type>::component_type type;
-};
-
Deleted: sandbox/gtl/gtl/rectangle_concept.h
==============================================================================
--- sandbox/gtl/gtl/rectangle_concept.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,143 +0,0 @@
-/*
- 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).
-*/
-struct rectangle_concept {
- rectangle_concept() {}
-
- template <typename rectangle_type>
- struct registration {
- typedef typename rectangle_traits<rectangle_type>::coordinate_type coordinate_type;
- typedef interval_data<coordinate_type> component_type;
- };
-
- template <orientation_2d_enum orient, typename T>
- static inline typename rectangle_traits<T>::interval_type
- get(const T& rectangle) {
- return rectangle_traits<T>::get(rectangle, orient);
- }
-
- template <typename T>
- static inline typename rectangle_traits<T>::interval_type
- get(const T& rectangle, orientation_2d orient) {
- return rectangle_traits<T>::get(rectangle, orient);
- }
-
- template <orientation_2d_enum orient, typename T, typename T2>
- static inline void set(T& rectangle, const T2& interval) {
- rectangle_traits<T>::set(rectangle, orient, interval);
- }
-
- template <typename T, typename T2>
- static inline void set(T& rectangle, orientation_2d orient, const T2& interval) {
- rectangle_traits<T>::set(rectangle, orient, interval);
- }
-
- template <typename T, typename T2, typename T3>
- static inline T construct(const T2& interval_horizontal,
- const T3& interval_vertical) {
- return rectangle_traits<T>::construct(interval_horizontal, interval_vertical); }
-
- template <typename T, typename coordinate_type>
- static inline T construct(coordinate_type xl, coordinate_type yl, coordinate_type xh, coordinate_type yh) {
- return rectangle_traits<T>::construct(interval_data<coordinate_type>(xl, xh),
- interval_data<coordinate_type>(yl, yh));
- }
-
- template <typename T, typename T2>
- static T copy_construct(const T2& rectangle) {
- return construct<T>
- (get(rectangle, HORIZONTAL),
- get(rectangle, VERTICAL));
- }
-
- template <typename rectangle_type_1, typename rectangle_type_2>
- static rectangle_type_1& assign(rectangle_type_1& lvalue, const rectangle_type_2& rvalue) {
- set(lvalue, HORIZONTAL, get(rvalue, HORIZONTAL));
- set(lvalue, VERTICAL, get(rvalue, VERTICAL));
- return lvalue;
- }
-
- template <typename T, typename T2>
- static bool equivalence(const T& rect1, const T2& rect2) {
- return interval_concept::equivalence(get(rect1, HORIZONTAL),
- get(rect2, HORIZONTAL)) &&
- interval_concept::equivalence(get(rect1, VERTICAL),
- get(rect2, VERTICAL));
- }
-
- template <typename rectangle_type>
- static typename rectangle_traits<rectangle_type>::coordinate_type
- xl(const rectangle_type& rectangle) {
- return interval_concept::get<LOW>(get<HORIZONTAL>(rectangle));
- }
-
- template <typename rectangle_type>
- static typename rectangle_traits<rectangle_type>::coordinate_type
- xh(const rectangle_type& rectangle) {
- return interval_concept::get<HIGH>(get<HORIZONTAL>(rectangle));
- }
-
- template <typename rectangle_type>
- static typename rectangle_traits<rectangle_type>::coordinate_type
- yl(const rectangle_type& rectangle) {
- return interval_concept::get<LOW>(get<VERTICAL>(rectangle));
- }
-
- template <typename rectangle_type>
- static typename rectangle_traits<rectangle_type>::coordinate_type
- yh(const rectangle_type& rectangle) {
- return interval_concept::get<HIGH>(get<VERTICAL>(rectangle));
- }
-
- template <typename rectangle_type, typename rectangle_type2>
- static bool contains(const rectangle_type& rectangle, const rectangle_type2 rectangle_contained,
- bool consider_touch, rectangle_concept tag) {
- return interval_concept::contains(get<HORIZONTAL>(rectangle), get<HORIZONTAL>(rectangle_contained), consider_touch, interval_concept()) &&
- interval_concept::contains(get<VERTICAL>(rectangle), get<VERTICAL>(rectangle_contained), consider_touch, interval_concept());
- }
- template <typename rectangle_type, typename point_type>
- static bool contains(const rectangle_type& rectangle, const point_type point_contained,
- bool consider_touch, point_concept tag) {
- return interval_concept::contains(get<HORIZONTAL>(rectangle), point_concept::get<HORIZONTAL>(point_contained), consider_touch) &&
- interval_concept::contains(get<VERTICAL>(rectangle), point_concept::get<VERTICAL>(point_contained), consider_touch);
- }
-
- template <typename rectangle_type_1, typename rectangle_type_2>
- class less : public std::binary_function<const rectangle_type_1&, const rectangle_type_2&, bool> {
- private:
- orientation_2d orient_;
- public:
- inline less(orientation_2d orient = VERTICAL) : orient_(orient) {}
- inline bool operator () (const rectangle_type_1& a,
- const rectangle_type_2& b) const {
- typedef typename rectangle_traits<rectangle_type_1>::coordinate_type Unit;
- Unit vl1 = interval_concept::get(get(a, orient_), LOW);
- Unit vl2 = interval_concept::get(get(b, orient_), LOW);
- if(vl1 > vl2) return false;
- if(vl1 == vl2) {
- orientation_2d perp = orient_.get_perpendicular();
- Unit hl1 = interval_concept::get(get(a, perp), LOW);
- Unit hl2 = interval_concept::get(get(b, perp), LOW);
- if(hl1 > hl2) return false;
- if(hl1 == hl2) {
- Unit vh1 = interval_concept::get(get(a, orient_), HIGH);
- Unit vh2 = interval_concept::get(get(b, orient_), HIGH);
- if(vh1 > vh2) return false;
- if(vh1 == vh2) {
- Unit hh1 = interval_concept::get(get(a, perp), HIGH);
- Unit hh2 = interval_concept::get(get(b, perp), HIGH);
- return hh1 < hh2;
- }
- }
- }
- return true;
- }
-
- };
-};
-
-
Deleted: sandbox/gtl/gtl/rectangle_data.h
==============================================================================
--- sandbox/gtl/gtl/rectangle_data.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,39 +0,0 @@
-/*
- 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).
-*/
-template <typename T>
-class rectangle_data {
-public:
- typedef T coordinate_type;
- inline rectangle_data() {}
- template <typename interval_type_1, typename interval_type_2>
- inline rectangle_data(const interval_type_1& hrange,
- const interval_type_2& vrange) {
- set(HORIZONTAL, hrange); set(VERTICAL, vrange); }
-
- inline rectangle_data(const rectangle_data& that) { (*this) = that; }
-
- inline rectangle_data& operator=(const rectangle_data& that) {
- ranges_[0] = that.ranges_[0]; ranges_[1] = that.ranges_[1]; return *this;
- }
- template <typename T2>
- inline rectangle_data& operator=(const T2& rvalue);
-
- inline interval_data<coordinate_type> get(orientation_2d orient) const {
- return ranges_[orient.to_int()]; }
- inline coordinate_type get(direction_2d dir) const {
- return ranges_[orientation_2d(dir).to_int()].get(direction_1d(dir));
- }
- inline void set(direction_2d dir, coordinate_type value) {
- return ranges_[orientation_2d(dir).to_int()].set(direction_1d(dir), value);
- }
- template <typename interval_type>
- inline void set(orientation_2d orient, const interval_type& interval);
-private:
- interval_data<coordinate_type> ranges_[2];
-};
-
Deleted: sandbox/gtl/gtl/rectangle_formation.h
==============================================================================
--- sandbox/gtl/gtl/rectangle_formation.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,228 +0,0 @@
-/*
- 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).
-*/
-
-namespace rectangle_formation {
- template <class T>
- class ScanLineToRects {
- public:
- typedef T rectangle_type;
- typedef typename rectangle_traits<T>::coordinate_type coordinate_type;
- typedef rectangle_data<coordinate_type> scan_rect_type;
- private:
-
- typedef std::set<scan_rect_type, rectangle_concept::less<scan_rect_type, scan_rect_type> > ScanData;
- ScanData scanData_;
- bool haveCurrentRect_;
- scan_rect_type currentRect_;
- orientation_2d orient_;
- typename rectangle_traits<T>::coordinate_type currentCoordinate_;
- public:
- inline ScanLineToRects() {}
-
- inline ScanLineToRects(orientation_2d orient, rectangle_type model) :
- scanData_(orientation_2d(orient.to_int() ? VERTICAL : HORIZONTAL)),
- haveCurrentRect_(false), orient_(orient) {
- rectangle_concept::assign(currentRect_, model);
- currentCoordinate_ = std::numeric_limits<coordinate_type>::max();
- }
-
- template <typename CT>
- inline ScanLineToRects& processEdge(CT& rectangles, const interval_data<coordinate_type>& edge);
-
- inline ScanLineToRects& nextMajorCoordinate(coordinate_type currentCoordinate) {
- if(haveCurrentRect_) {
- scanData_.insert(scanData_.end(), currentRect_);
- haveCurrentRect_ = false;
- }
- currentCoordinate_ = currentCoordinate;
- return *this;
- }
-
- };
-
- template <class CT, class ST, class rectangle_type, typename interval_type, typename coordinate_type> inline CT&
- processEdge_(CT& rectangles, ST& scanData, const interval_type& edge,
- bool& haveCurrentRect, rectangle_type& currentRect, coordinate_type currentCoordinate, orientation_2d orient)
- {
- typedef typename CT::value_type result_type;
- bool edgeProcessed = false;
- if(!scanData.empty()) {
-
- //process all rectangles in the scanData that touch the edge
- typename ST::iterator dataIter = scanData.lower_bound(rectangle_type(edge, edge));
- //decrement beginIter until its low is less than edge's low
- while((dataIter == scanData.end() || (*dataIter).get(orient).get(LOW) > edge.get(LOW)) &&
- dataIter != scanData.begin())
- {
- --dataIter;
- }
- //process each rectangle until the low end of the rectangle
- //is greater than the high end of the edge
- while(dataIter != scanData.end() &&
- (*dataIter).get(orient).get(LOW) <= edge.get(HIGH))
- {
- const rectangle_type& rect = *dataIter;
- //if the rectangle data intersects the edge at all
- if(rect.get(orient).get(HIGH) >= edge.get(LOW)) {
- if(interval_concept::contains(rect.get(orient), edge, true, interval_concept())) {
- //this is a closing edge
- //we need to write out the intersecting rectangle and
- //insert between 0 and 2 rectangles into the scanData
- //write out rectangle
- rectangle_type tmpRect = rect;
-
- if(rect.get(orient.get_perpendicular()).get(LOW) < currentCoordinate) {
- //set the high coordinate perpedicular to slicing orientation
- //to the current coordinate of the scan event
- tmpRect.set(orient.get_perpendicular().get_direction(HIGH),
- currentCoordinate);
- result_type result;
- rectangle_concept::assign(result, tmpRect);
- rectangles.insert(rectangles.end(), result);
- }
- //erase the rectangle from the scan data
- typename ST::iterator nextIter = dataIter;
- ++nextIter;
- scanData.erase(dataIter);
- if(tmpRect.get(orient).get(LOW) < edge.get(LOW)) {
- //insert a rectangle for the overhang of the bottom
- //of the rectangle back into scan data
- rectangle_type lowRect(tmpRect);
- lowRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
- currentCoordinate));
- lowRect.set(orient.get_direction(HIGH), edge.get(LOW));
- scanData.insert(nextIter, lowRect);
- }
- if(tmpRect.get(orient).get(HIGH) > edge.get(HIGH)) {
- //insert a rectangle for the overhang of the top
- //of the rectangle back into scan data
- rectangle_type highRect(tmpRect);
- highRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
- currentCoordinate));
- highRect.set(orient.get_direction(LOW), edge.get(HIGH));
- scanData.insert(nextIter, highRect);
- }
- //we are done with this edge
- edgeProcessed = true;
- break;
- } else {
- //it must be an opening edge
- //assert that rect does not overlap the edge but only touches
- //write out rectangle
- rectangle_type tmpRect = rect;
- //set the high coordinate perpedicular to slicing orientation
- //to the current coordinate of the scan event
- if(tmpRect.get(orient.get_perpendicular().get_direction(LOW)) < currentCoordinate) {
- tmpRect.set(orient.get_perpendicular().get_direction(HIGH),
- currentCoordinate);
- result_type result;
- rectangle_concept::assign(result, tmpRect);
- rectangles.insert(rectangles.end(), result);
- }
- //erase the rectangle from the scan data
- typename ST::iterator nextIter = dataIter;
- ++nextIter;
- scanData.erase(dataIter);
- dataIter = nextIter;
- if(haveCurrentRect) {
- if(currentRect.get(orient).get(HIGH) >= edge.get(LOW)){
- if(!edgeProcessed && currentRect.get(orient.get_direction(HIGH)) > edge.get(LOW)){
- rectangle_type tmpRect2(currentRect);
- tmpRect2.set(orient.get_direction(HIGH), edge.get(LOW));
- scanData.insert(nextIter, tmpRect2);
- if(currentRect.get(orient.get_direction(HIGH)) > edge.get(HIGH)) {
- currentRect.set(orient, interval_data<coordinate_type>(edge.get(HIGH), currentRect.get(orient.get_direction(HIGH))));
- } else {
- haveCurrentRect = false;
- }
- } else {
- //extend the top of current rect
- currentRect.set(orient.get_direction(HIGH),
- std::max(edge.get(HIGH),
- tmpRect.get(orient.get_direction(HIGH))));
- }
- } else {
- //insert current rect into the scanData
- scanData.insert(nextIter, currentRect);
- //create a new current rect
- currentRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
- currentCoordinate));
- currentRect.set(orient, interval_data<coordinate_type>(std::min(tmpRect.get(orient).get(LOW),
- edge.get(LOW)),
- std::max(tmpRect.get(orient).get(HIGH),
- edge.get(HIGH))));
- }
- } else {
- haveCurrentRect = true;
- currentRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
- currentCoordinate));
- currentRect.set(orient, interval_data<coordinate_type>(std::min(tmpRect.get(orient).get(LOW),
- edge.get(LOW)),
- std::max(tmpRect.get(orient).get(HIGH),
- edge.get(HIGH))));
- }
- //skip to nextIter position
- edgeProcessed = true;
- continue;
- }
- edgeProcessed = true;
- }
- ++dataIter;
- } //end while edge intersects rectangle data
-
- }
- if(!edgeProcessed) {
- if(haveCurrentRect) {
- if(currentRect.get(orient.get_perpendicular().get_direction(HIGH))
- == currentCoordinate &&
- currentRect.get(orient.get_direction(HIGH)) >= edge.get(LOW))
- {
- if(currentRect.get(orient.get_direction(HIGH)) > edge.get(LOW)){
- rectangle_type tmpRect(currentRect);
- tmpRect.set(orient.get_direction(HIGH), edge.get(LOW));
- scanData.insert(scanData.end(), tmpRect);
- if(currentRect.get(orient.get_direction(HIGH)) > edge.get(HIGH)) {
- currentRect.set(orient,
- interval_data<coordinate_type>(edge.get(HIGH),
- currentRect.get(orient.get_direction(HIGH))));
- return rectangles;
- } else {
- haveCurrentRect = false;
- return rectangles;
- }
- }
- //extend current rect
- currentRect.set(orient.get_direction(HIGH), edge.get(HIGH));
- return rectangles;
- }
- scanData.insert(scanData.end(), currentRect);
- haveCurrentRect = false;
- }
- rectangle_type tmpRect(currentRect);
- tmpRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
- currentCoordinate));
- tmpRect.set(orient, edge);
- scanData.insert(tmpRect);
- return rectangles;
- }
- return rectangles;
-
- }
-
- template <class T>
- template <class CT>
- inline
- ScanLineToRects<T>& ScanLineToRects<T>::processEdge(CT& rectangles, const interval_data<coordinate_type>& edge)
- {
- processEdge_(rectangles, scanData_, edge, haveCurrentRect_, currentRect_, currentCoordinate_, orient_);
- return *this;
- }
-
-
-}; //namespace rectangle_formation
-
Deleted: sandbox/gtl/gtl/rectangle_traits.h
==============================================================================
--- sandbox/gtl/gtl/rectangle_traits.h 2008-05-29 17:48:45 EDT (Thu, 29 May 2008)
+++ (empty file)
@@ -1,25 +0,0 @@
-/*
- 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).
-*/
-template <typename T>
-struct rectangle_traits {
- typedef typename T::coordinate_type coordinate_type;
- typedef interval_data<coordinate_type> interval_type;
-
- static inline interval_type get(const T& rectangle, orientation_2d orient) {
- return rectangle.get(orient); }
-
- template <typename T2>
- static inline void set(T& rectangle, orientation_2d orient, const T2& interval) {
- rectangle.set(orient, interval); }
-
- template <typename T2, typename T3>
- static inline T construct(const T2& interval_horizontal,
- const T3& interval_vertical) {
- return T(interval_horizontal, interval_vertical); }
-};
-
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk