|
|
Boost-Commit : |
From: lucanus.j.simonson_at_[hidden]
Date: 2008-05-12 19:15:40
Author: ljsimons
Date: 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
New Revision: 45311
URL: http://svn.boost.org/trac/boost/changeset/45311
Log:
re-implemented polygons with holes and ported boolean op algorithm
Added:
sandbox/gtl/gtl/boolean_op.h (contents, props changed)
sandbox/gtl/gtl/iterator_compact_to_points.h (contents, props changed)
sandbox/gtl/gtl/iterator_points_to_compact.h (contents, props changed)
sandbox/gtl/gtl/polygon_with_holes_concept.h (contents, props changed)
sandbox/gtl/gtl/polygon_with_holes_data.h (contents, props changed)
sandbox/gtl/gtl/polygon_with_holes_traits.h (contents, props changed)
Text files modified:
sandbox/gtl/gtl/geometry_traits.h | 7 ++
sandbox/gtl/gtl/gtl.h | 25 +++++++++
sandbox/gtl/gtl/interval_concept.h | 7 ++
sandbox/gtl/gtl/interval_data.h | 19 +++++++
sandbox/gtl/gtl/interval_traits.h | 7 ++
sandbox/gtl/gtl/isotropy.h | 7 ++
sandbox/gtl/gtl/point_3d_concept.h | 7 ++
sandbox/gtl/gtl/point_3d_data.h | 7 ++
sandbox/gtl/gtl/point_3d_traits.h | 7 ++
sandbox/gtl/gtl/point_concept.h | 7 ++
sandbox/gtl/gtl/point_data.h | 7 ++
sandbox/gtl/gtl/point_traits.h | 7 ++
sandbox/gtl/gtl/polygon_concept.h | 106 ++++++---------------------------------
sandbox/gtl/gtl/polygon_data.h | 7 ++
sandbox/gtl/gtl/polygon_traits.h | 7 ++
sandbox/gtl/gtl/post_concept_definitions.h | 7 ++
sandbox/gtl/gtl/post_geometry_traits_definitions.h | 7 ++
sandbox/gtl/gtl/rectangle_concept.h | 7 ++
sandbox/gtl/gtl/rectangle_data.h | 7 ++
sandbox/gtl/gtl/rectangle_traits.h | 7 ++
20 files changed, 180 insertions(+), 89 deletions(-)
Added: sandbox/gtl/gtl/boolean_op.h
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/boolean_op.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -0,0 +1,680 @@
+/*
+ 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());
+ }
+
+};
Modified: sandbox/gtl/gtl/geometry_traits.h
==============================================================================
--- sandbox/gtl/gtl/geometry_traits.h (original)
+++ sandbox/gtl/gtl/geometry_traits.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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>
Modified: sandbox/gtl/gtl/gtl.h
==============================================================================
--- sandbox/gtl/gtl/gtl.h (original)
+++ sandbox/gtl/gtl/gtl.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,6 +1,18 @@
+/*
+ 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 <list>
#include <iostream>
+#include <algorithm>
+#include <limits>
//isotropy types
#include "isotropy.h"
@@ -11,6 +23,7 @@
#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"
@@ -18,13 +31,21 @@
#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"
@@ -35,6 +56,9 @@
//defintions
#include "post_geometry_traits_definitions.h"
+//manhattan boolean op algorithm
+#include "boolean_op.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) {
typename geometry_traits<geometry_type_1>::geometry_concept().contains(geometry_object, contained_geometry_object);
@@ -68,3 +92,4 @@
return assign(lvalue, rvalue);
}
+
Modified: sandbox/gtl/gtl/interval_concept.h
==============================================================================
--- sandbox/gtl/gtl/interval_concept.h (original)
+++ sandbox/gtl/gtl/interval_concept.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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() {}
Modified: sandbox/gtl/gtl/interval_data.h
==============================================================================
--- sandbox/gtl/gtl/interval_data.h (original)
+++ sandbox/gtl/gtl/interval_data.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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:
@@ -17,6 +24,12 @@
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;
}
@@ -24,3 +37,9 @@
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);
+}
Modified: sandbox/gtl/gtl/interval_traits.h
==============================================================================
--- sandbox/gtl/gtl/interval_traits.h (original)
+++ sandbox/gtl/gtl/interval_traits.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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;
Modified: sandbox/gtl/gtl/isotropy.h
==============================================================================
--- sandbox/gtl/gtl/isotropy.h (original)
+++ sandbox/gtl/gtl/isotropy.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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 orientation_2d_enum { HORIZONTAL = 0, VERTICAL = 1 };
enum direction_1d_enum { LOW = 0, HIGH = 1 };
enum orientation_3d_enum { PROXIMAL = 2 };
Added: sandbox/gtl/gtl/iterator_compact_to_points.h
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/iterator_compact_to_points.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -0,0 +1,55 @@
+/*
+ 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:
+ 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 const point_type& operator*() const { return pt_; }
+};
Added: sandbox/gtl/gtl/iterator_points_to_compact.h
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/iterator_points_to_compact.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -0,0 +1,37 @@
+/*
+ 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 coordinate_type>
+class iterator_points_to_compact {
+private:
+ iT iter_;
+ orientation_2d orient_;
+public:
+ 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 coordinate_type operator*() { return (*iter_).get(orient_); }
+};
Modified: sandbox/gtl/gtl/point_3d_concept.h
==============================================================================
--- sandbox/gtl/gtl/point_3d_concept.h (original)
+++ sandbox/gtl/gtl/point_3d_concept.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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_3d_concept() {}
Modified: sandbox/gtl/gtl/point_3d_data.h
==============================================================================
--- sandbox/gtl/gtl/point_3d_data.h (original)
+++ sandbox/gtl/gtl/point_3d_data.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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:
Modified: sandbox/gtl/gtl/point_3d_traits.h
==============================================================================
--- sandbox/gtl/gtl/point_3d_traits.h (original)
+++ sandbox/gtl/gtl/point_3d_traits.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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;
Modified: sandbox/gtl/gtl/point_concept.h
==============================================================================
--- sandbox/gtl/gtl/point_concept.h (original)
+++ sandbox/gtl/gtl/point_concept.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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() {}
Modified: sandbox/gtl/gtl/point_data.h
==============================================================================
--- sandbox/gtl/gtl/point_data.h (original)
+++ sandbox/gtl/gtl/point_data.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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:
Modified: sandbox/gtl/gtl/point_traits.h
==============================================================================
--- sandbox/gtl/gtl/point_traits.h (original)
+++ sandbox/gtl/gtl/point_traits.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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;
Modified: sandbox/gtl/gtl/polygon_concept.h
==============================================================================
--- sandbox/gtl/gtl/polygon_concept.h (original)
+++ sandbox/gtl/gtl/polygon_concept.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,85 +1,13 @@
+/*
+ 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 <class iterator_type, class point_type>
- class iterator_points {
- private:
- iterator_type iter_;
- iterator_type iter_end_;
- point_type pt_;
- typename point_traits<point_type>::coordinate_type firstX_;
- orientation_2d orient_;
- public:
- inline iterator_points() {}
- inline iterator_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_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_points operator++(int) {
- iterator_points tmp(*this);
- ++(*this);
- return tmp;
- }
- inline bool operator==(const iterator_points& that) const {
- return (iter_ == that.iter_);
- }
- inline bool operator!=(const iterator_points& that) const {
- return (iter_ != that.iter_);
- }
- inline const point_type& operator*() const { return pt_; }
- };
-
- template <class iT, typename coordinate_type>
- class iterator_points_to_coords {
- private:
- iT iter_;
- orientation_2d orient_;
- public:
- inline iterator_points_to_coords() {}
- inline iterator_points_to_coords(iT iter) : iter_(iter), orient_(HORIZONTAL) {}
- inline iterator_points_to_coords(const iterator_points_to_coords& that) :
- iter_(that.iter_), orient_(that.orient_) {}
- //use bitwise copy and assign provided by the compiler
- inline iterator_points_to_coords& operator++() {
- ++iter_;
- orient_.turn_90();
- return *this;
- }
- inline iterator_points_to_coords operator++(int) {
- iT tmp(*this);
- ++(*this);
- return tmp;
- }
- inline bool operator==(const iterator_points_to_coords& that) const {
- return (iter_ == that.iter_);
- }
- inline bool operator!=(const iterator_points_to_coords& that) const {
- return (iter_ != that.iter_);
- }
- inline coordinate_type operator*() { return (*iter_).get(orient_); }
- };
-
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);
@@ -95,9 +23,9 @@
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_coords<point_iterator_type,
+ return set(iterator_points_to_compact<point_iterator_type,
typename polygon_traits<polygon_type>::coordinate_type>(begin_point),
- iterator_points_to_coords<point_iterator_type,
+ iterator_points_to_compact<point_iterator_type,
typename polygon_traits<polygon_type>::coordinate_type>(end_point));
}
@@ -112,18 +40,18 @@
}
template <typename polygon_type>
- static iterator_points<typename polygon_traits<polygon_type>::iterator_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_points<typename polygon_traits<polygon_type>::iterator_type,
+ 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_points<typename polygon_traits<polygon_type>::iterator_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_points<typename polygon_traits<polygon_type>::iterator_type,
+ 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));
}
@@ -248,13 +176,13 @@
return retval >= 0 ? retval : -retval;
}
- /// get the perimeter of the rectangle
+ /// 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_points<iterator_type, point_data<coordinate_type> > iterator;
+ 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);
@@ -279,7 +207,7 @@
bool consider_touch = true) {
typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
typedef typename polygon_traits<polygon_type>::iterator_type iterator_type;
- typedef iterator_points<iterator_type, point_data<coordinate_type> > iterator;
+ 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);
@@ -371,7 +299,7 @@
bool pingpong = true;
for(typename polygon_traits<polygon_type>::iterator_type iter = begin(polygon);
iter != end(polygon); ++iter) {
- coords.push_back((*iter) + predicated_value(pingpong, x_displacement, y_displacement));
+ coords.push_back((*iter) + (pingpong ? x_displacement : y_displacement));
pingpong = !pingpong;
}
set(polygon, coords.begin(), coords.end());
Modified: sandbox/gtl/gtl/polygon_data.h
==============================================================================
--- sandbox/gtl/gtl/polygon_data.h (original)
+++ sandbox/gtl/gtl/polygon_data.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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:
Modified: sandbox/gtl/gtl/polygon_traits.h
==============================================================================
--- sandbox/gtl/gtl/polygon_traits.h (original)
+++ sandbox/gtl/gtl/polygon_traits.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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;
Added: sandbox/gtl/gtl/polygon_with_holes_concept.h
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/polygon_with_holes_concept.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -0,0 +1,257 @@
+/*
+ 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 {
+public:
+
+ template<typename polygon_with_holes_type, typename iterator_type>
+ static void set(polygon_with_holes_type& polygon, iterator_type input_begin, iterator_type input_end) {
+ polygon_traits<polygon_with_holes_type>::set(polygon, input_begin, input_end);
+ }
+
+ template<typename polygon_with_holes_type, typename rectangle_type>
+ static void set(polygon_with_holes_type& polygon, const rectangle_type& rect) {
+ typename polygon_traits<polygon_with_holes_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_with_holes_type, typename point_iterator_type>
+ static void set_points(polygon_with_holes_type& polygon, point_iterator_type begin_point, point_iterator_type end_point) {
+ return set(iterator_points_to_compact<point_iterator_type,
+ typename polygon_traits<polygon_with_holes_type>::coordinate_type>(begin_point),
+ iterator_points_to_compact<point_iterator_type,
+ typename polygon_traits<polygon_with_holes_type>::coordinate_type>(end_point));
+ }
+
+ 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_traits<polygon_with_holes_type>::iterator_type begin(const polygon_with_holes_type& polygon) {
+ return polygon_traits<polygon_with_holes_type>::begin(polygon);
+ }
+
+ template <typename polygon_with_holes_type>
+ static typename polygon_traits<polygon_with_holes_type>::iterator_type end(const polygon_with_holes_type& polygon) {
+ return polygon_traits<polygon_with_holes_type>::end(polygon);
+ }
+
+ 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>
+ static iterator_compact_to_points<typename polygon_traits<polygon_with_holes_type>::iterator_type,
+ point_data<typename polygon_traits<polygon_with_holes_type>::coordinate_type> >
+ begin_points(const polygon_with_holes_type& polygon) {
+ return iterator_compact_to_points<typename polygon_traits<polygon_with_holes_type>::iterator_type,
+ point_data<typename polygon_traits<polygon_with_holes_type>::coordinate_type> > (begin(polygon), end(polygon));
+ }
+
+ template <typename polygon_with_holes_type>
+ static iterator_compact_to_points<typename polygon_traits<polygon_with_holes_type>::iterator_type,
+ point_data<typename polygon_traits<polygon_with_holes_type>::coordinate_type> >
+ end_points(const polygon_with_holes_type& polygon) {
+ return iterator_compact_to_points<typename polygon_traits<polygon_with_holes_type>::iterator_type,
+ point_data<typename polygon_traits<polygon_with_holes_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_with_holes_type, typename rectangle_type>
+ static polygon_with_holes_type construct_from_rectangle(const rectangle_type& rect) {
+ polygon_with_holes_type poly;
+ set(poly, rect);
+ return poly;
+ }
+
+ 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(const polygon_with_holes_type& polygon) {
+ return polygon_traits<polygon_with_holes_type>::size(polygon);
+ }
+
+ 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, begin(rvalue), end(rvalue));
+ set_holes(lvalue, begin_holes(rvalue), end_holes(rvalue));
+ return lvalue;
+ }
+
+ template <typename polygon_with_holes_type>
+ static rectangle_data<typename polygon_traits<polygon_with_holes_type>::coordinate_type>
+ bounding_box(const polygon_with_holes_type& polygon) {
+ return polygon_concept::bounding_box(polygon);
+ }
+
+ template <typename polygon_with_holes_type>
+ static direction_1d winding(const polygon_with_holes_type& polygon){
+ return polygon_concept::winding(polygon);
+ }
+
+ 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_point(const polygon_with_holes_type& polygon, const point_type& point,
+ bool consider_touch = true) {
+ 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_point(*b, point, !consider_touch)) {
+ return false;
+ }
+ }
+ return polygon_concept::contains_point(polygon, point, consider_touch);
+ }
+
+ /// 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_point(pwh, point_data<T>(1, 11))
+ << " " ;
+ std::cout << polygon_with_holes_concept::contains_point(pwh, point_data<T>(10, 10))
+ << " " ;
+ std::cout << polygon_with_holes_concept::contains_point(pwh, point_data<T>(10, 90))
+ << " " ;
+ std::cout << polygon_with_holes_concept::contains_point(pwh, point_data<T>(90, 90))
+ << " " ;
+ std::cout << polygon_with_holes_concept::contains_point(pwh, point_data<T>(90, 10))
+ << " " ;
+ std::cout << polygon_with_holes_concept::contains_point(pwh, point_data<T>(90, 80))
+ << " " ;
+ std::cout << polygon_with_holes_concept::contains_point(pwh, point_data<T>(12, 12))
+ << " " ;
+ std::cout << polygon_with_holes_concept::contains_point(pwh, point_data<T>(10, 10), false)
+ << " " ;
+ std::cout << polygon_with_holes_concept::contains_point(pwh, point_data<T>(10, 90), false)
+ << " " ;
+ std::cout << polygon_with_holes_concept::contains_point(pwh, point_data<T>(90, 90), false)
+ << " " ;
+ std::cout << polygon_with_holes_concept::contains_point(pwh, point_data<T>(90, 10), false)
+ << " " ;
+ std::cout << polygon_with_holes_concept::contains_point(pwh, point_data<T>(90, 80), false)
+ << "\n";
+
+ polygon_with_holes_concept::move(pwh, 5, 5);
+}
Added: sandbox/gtl/gtl/polygon_with_holes_data.h
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/polygon_with_holes_data.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -0,0 +1,82 @@
+/*
+ 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_;
+};
Added: sandbox/gtl/gtl/polygon_with_holes_traits.h
==============================================================================
--- (empty file)
+++ sandbox/gtl/gtl/polygon_with_holes_traits.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -0,0 +1,37 @@
+/*
+ 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();
+ }
+
+};
Modified: sandbox/gtl/gtl/post_concept_definitions.h
==============================================================================
--- sandbox/gtl/gtl/post_concept_definitions.h (original)
+++ sandbox/gtl/gtl/post_concept_definitions.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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) {
Modified: sandbox/gtl/gtl/post_geometry_traits_definitions.h
==============================================================================
--- sandbox/gtl/gtl/post_geometry_traits_definitions.h (original)
+++ sandbox/gtl/gtl/post_geometry_traits_definitions.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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 rectangle_type, typename geometry_type>
bool rectangle_concept::contains(const rectangle_type& rectangle, const geometry_type& contained_geometry_object) {
return rectangle_concept::contains_dispatch(rectangle, contained_geometry_object, typename geometry_traits<geometry_type>::geometry_concept());
Modified: sandbox/gtl/gtl/rectangle_concept.h
==============================================================================
--- sandbox/gtl/gtl/rectangle_concept.h (original)
+++ sandbox/gtl/gtl/rectangle_concept.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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() {}
Modified: sandbox/gtl/gtl/rectangle_data.h
==============================================================================
--- sandbox/gtl/gtl/rectangle_data.h (original)
+++ sandbox/gtl/gtl/rectangle_data.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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:
Modified: sandbox/gtl/gtl/rectangle_traits.h
==============================================================================
--- sandbox/gtl/gtl/rectangle_traits.h (original)
+++ sandbox/gtl/gtl/rectangle_traits.h 2008-05-12 19:15:37 EDT (Mon, 12 May 2008)
@@ -1,3 +1,10 @@
+/*
+ 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;
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