Subject: [Boost-commit] svn:boost r54951 - in sandbox/gtl: boost/polygon boost/polygon/detail doc gtl
From: lucanus.j.simonson_at_[hidden]
Date: 2009-07-14 14:22:44
Author: ljsimons
Date: 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
New Revision: 54951
URL: http://svn.boost.org/trac/boost/changeset/54951
Log:
added general trapezoidization and connectivity extraction and 45-degree map overlay/property merge and updated documentation
Added:
sandbox/gtl/doc/gtl_connectivity_extraction.htm (contents, props changed)
sandbox/gtl/doc/gtl_property_merge_45.htm (contents, props changed)
Removed:
sandbox/gtl/gtl/
Text files modified:
sandbox/gtl/boost/polygon/detail/polygon_45_set_view.hpp | 4
sandbox/gtl/boost/polygon/detail/polygon_90_set_view.hpp | 8
sandbox/gtl/boost/polygon/detail/polygon_arbitrary_formation.hpp | 688 +++++++++++++++++++++++++++++++++++++++
sandbox/gtl/boost/polygon/detail/scan_arbitrary.hpp | 157 +++++++++
sandbox/gtl/boost/polygon/gtl_boost_unit_test.cpp | 193 +++++++++++
sandbox/gtl/boost/polygon/polygon_set_concept.hpp | 54 ++
sandbox/gtl/boost/polygon/polygon_set_data.hpp | 112 ++++++
sandbox/gtl/doc/gtl_connectivity_extraction_45.htm | 2
sandbox/gtl/doc/gtl_connectivity_extraction_90.htm | 2
sandbox/gtl/doc/gtl_coordinate_concept.htm | 2
sandbox/gtl/doc/gtl_custom_point.htm | 7
sandbox/gtl/doc/gtl_custom_polygon.htm | 3
sandbox/gtl/doc/gtl_custom_polygon_set.htm | 4
sandbox/gtl/doc/gtl_design_overview.htm | 16
sandbox/gtl/doc/gtl_interval_concept.htm | 2
sandbox/gtl/doc/gtl_isotropy.htm | 5
sandbox/gtl/doc/gtl_point_3d_concept.htm | 2
sandbox/gtl/doc/gtl_point_concept.htm | 2
sandbox/gtl/doc/gtl_point_usage.htm | 3
sandbox/gtl/doc/gtl_polygon_45_concept.htm | 11
sandbox/gtl/doc/gtl_polygon_45_set_concept.htm | 18
sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm | 14
sandbox/gtl/doc/gtl_polygon_90_concept.htm | 11
sandbox/gtl/doc/gtl_polygon_90_set_concept.htm | 2
sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm | 12
sandbox/gtl/doc/gtl_polygon_concept.htm | 13
sandbox/gtl/doc/gtl_polygon_set_concept.htm | 129 +++++++
sandbox/gtl/doc/gtl_polygon_set_usage.htm | 7
sandbox/gtl/doc/gtl_polygon_usage.htm | 3
sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm | 16
sandbox/gtl/doc/gtl_property_merge.htm | 8
sandbox/gtl/doc/gtl_property_merge_90.htm | 8
sandbox/gtl/doc/gtl_property_merge_usage.htm | 3
sandbox/gtl/doc/gtl_rectangle_concept.htm | 2
sandbox/gtl/doc/index.htm | 29 +
35 files changed, 1498 insertions(+), 54 deletions(-)
Modified: sandbox/gtl/boost/polygon/detail/polygon_45_set_view.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/polygon_45_set_view.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/polygon_45_set_view.hpp 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -205,7 +205,7 @@
}
struct y_ps45_a : gtl_yes {};
-#if 0
+
template <typename geometry_type_1, typename geometry_type_2>
typename enable_if< typename gtl_and_4< y_ps45_a, typename is_polygon_45_or_90_set_type<geometry_type_1>::type,
typename is_polygon_45_or_90_set_type<geometry_type_2>::type,
@@ -215,7 +215,7 @@
return polygon_45_set_view<geometry_type_1, geometry_type_2, 1>
(lvalue, rvalue);
}
-#endif
+
struct y_ps45_x : gtl_yes {};
template <typename geometry_type_1, typename geometry_type_2>
Modified: sandbox/gtl/boost/polygon/detail/polygon_90_set_view.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/polygon_90_set_view.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/polygon_90_set_view.hpp 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -267,11 +267,11 @@
}
struct y_ps90_a : gtl_yes {};
-#if 0
+
template <typename geometry_type_1, typename geometry_type_2>
- typename enable_if< typename gtl_if<typename gtl_and_3< y_ps90_a,
+ typename enable_if< typename gtl_and_3< y_ps90_a,
typename is_polygon_90_set_type<geometry_type_1>::type,
- typename is_polygon_90_set_type<geometry_type_2>::type>::type>::type,
+ typename is_polygon_90_set_type<geometry_type_2>::type>::type,
polygon_90_set_view<geometry_type_1, geometry_type_2, boolean_op::BinaryAnd> >::type
operator&(const geometry_type_1& lvalue, const geometry_type_2& rvalue) {
return polygon_90_set_view<geometry_type_1, geometry_type_2, boolean_op::BinaryAnd>
@@ -279,7 +279,7 @@
polygon_90_set_traits<geometry_type_1>::orient(lvalue),
boolean_op::BinaryAnd());
}
-#endif
+
struct y_ps90_x : gtl_yes {};
template <typename geometry_type_1, typename geometry_type_2>
Modified: sandbox/gtl/boost/polygon/detail/polygon_arbitrary_formation.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/polygon_arbitrary_formation.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/polygon_arbitrary_formation.hpp 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -590,7 +590,7 @@
};
class active_tail_arbitrary {
- private:
+ protected:
//data
poly_line_arbitrary* tailp_;
active_tail_arbitrary *otherTailp_;
@@ -1012,7 +1012,7 @@
// return o;
// }
- private:
+ protected:
//definitions
typedef std::map<vertex_half_edge, active_tail_arbitrary*, less_vertex_half_edge> scanline_data;
typedef typename scanline_data::iterator iterator;
@@ -1029,7 +1029,7 @@
less_vertex_half_edge lessElm(&x_, &justBefore_);
scanData_ = scanline_data(lessElm);
}
- inline polygon_arbitrary_formation(bool fractureHoles = false) :
+ inline polygon_arbitrary_formation(bool fractureHoles) :
scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false), fractureHoles_(fractureHoles) {
less_vertex_half_edge lessElm(&x_, &justBefore_);
scanData_ = scanline_data(lessElm);
@@ -1066,7 +1066,7 @@
//std::cout << "scan line size: " << scanData_.size() << std::endl;
}
- private:
+ protected:
//functions
template <class cT, class cT2>
inline std::pair<std::pair<Point, int>, active_tail_arbitrary*> processPoint_(cT& output, cT2& elements, Point point,
@@ -1931,6 +1931,686 @@
return *this;
}
};
+
+ template <typename Unit>
+ class trapezoid_arbitrary_formation : public polygon_arbitrary_formation<Unit> {
+ private:
+ typedef typename scanline_base<Unit>::Point Point;
+ typedef typename scanline_base<Unit>::half_edge half_edge;
+ typedef typename scanline_base<Unit>::vertex_half_edge vertex_half_edge;
+ typedef typename scanline_base<Unit>::less_vertex_half_edge less_vertex_half_edge;
+
+ typedef typename polygon_arbitrary_formation<Unit>::poly_line_arbitrary poly_line_arbitrary;
+
+ typedef typename polygon_arbitrary_formation<Unit>::active_tail_arbitrary active_tail_arbitrary;
+
+ typedef std::vector<std::pair<Point, int> > vertex_arbitrary_count;
+
+ typedef typename polygon_arbitrary_formation<Unit>::less_half_edge_count less_half_edge_count;
+
+ typedef std::vector<std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*> > incoming_count;
+
+ typedef typename polygon_arbitrary_formation<Unit>::less_incoming_count less_incoming_count;
+
+ typedef typename polygon_arbitrary_formation<Unit>::vertex_arbitrary_compact vertex_arbitrary_compact;
+
+ private:
+ //definitions
+ typedef std::map<vertex_half_edge, active_tail_arbitrary*, less_vertex_half_edge> scanline_data;
+ typedef typename scanline_data::iterator iterator;
+ typedef typename scanline_data::const_iterator const_iterator;
+
+ //data
+ public:
+ inline trapezoid_arbitrary_formation() : polygon_arbitrary_formation<Unit>() {}
+ inline trapezoid_arbitrary_formation(const trapezoid_arbitrary_formation& that) : polygon_arbitrary_formation<Unit>(that) {}
+ inline trapezoid_arbitrary_formation& operator=(const trapezoid_arbitrary_formation& that) {
+ * static_cast<polygon_arbitrary_formation<Unit>*>(this) = * static_cast<polygon_arbitrary_formation<Unit>*>(&that);
+ }
+
+ //cT is an output container of Polygon45 or Polygon45WithHoles
+ //iT is an iterator over vertex_half_edge elements
+ //inputBegin - inputEnd is a range of sorted iT that represents
+ //one or more scanline stops worth of data
+ template <class cT, class iT>
+ void scan(cT& output, iT inputBegin, iT inputEnd) {
+ //std::cout << "1\n";
+ while(inputBegin != inputEnd) {
+ //std::cout << "2\n";
+ polygon_arbitrary_formation<Unit>::x_ = (*inputBegin).pt.get(HORIZONTAL);
+ //std::cout << "SCAN FORMATION " << x_ << std::endl;
+ //std::cout << "x_ = " << x_ << std::endl;
+ //std::cout << "scan line size: " << scanData_.size() << std::endl;
+ inputBegin = processEvent_(output, inputBegin, inputEnd);
+ }
+ //std::cout << "scan line size: " << scanData_.size() << std::endl;
+ }
+
+ private:
+ //functions
+ inline void getVerticalPair_(std::pair<active_tail_arbitrary*,
+ active_tail_arbitrary*>& verticalPair,
+ iterator previter) {
+ active_tail_arbitrary* iterTail = (*previter).second;
+ Point prevPoint(polygon_arbitrary_formation<Unit>::x_,
+ previter->first.evalAtX(polygon_arbitrary_formation<Unit>::x_));
+ iterTail->pushPoint(prevPoint);
+ std::pair<active_tail_arbitrary*, active_tail_arbitrary*> tailPair =
+ active_tail_arbitrary::createActiveTailsAsPair(prevPoint, true, 0, false);
+ verticalPair.first = iterTail;
+ verticalPair.second = tailPair.first;
+ (*previter).second = tailPair.second;
+ }
+
+ template <class cT, class cT2>
+ inline std::pair<std::pair<Point, int>, active_tail_arbitrary*>
+ processPoint_(cT& output, cT2& elements,
+ std::pair<active_tail_arbitrary*, active_tail_arbitrary*>& verticalPair,
+ iterator previter, Point point, incoming_count& counts_from_scanline,
+ vertex_arbitrary_count& incoming_count) {
+ //std::cout << "\nAT POINT: " << point << std::endl;
+ //join any closing solid corners
+ std::vector<int> counts;
+ std::vector<int> incoming;
+ std::vector<active_tail_arbitrary*> tails;
+ counts.reserve(counts_from_scanline.size());
+ tails.reserve(counts_from_scanline.size());
+ incoming.reserve(incoming_count.size());
+ for(std::size_t i = 0; i < counts_from_scanline.size(); ++i) {
+ counts.push_back(counts_from_scanline[i].first.second);
+ tails.push_back(counts_from_scanline[i].second);
+ }
+ for(std::size_t i = 0; i < incoming_count.size(); ++i) {
+ incoming.push_back(incoming_count[i].second);
+ if(incoming_count[i].first < point) {
+ incoming.back() = 0;
+ }
+ }
+
+ active_tail_arbitrary* returnValue = 0;
+ std::pair<active_tail_arbitrary*, active_tail_arbitrary*> verticalPairOut;
+ verticalPairOut.first = 0;
+ verticalPairOut.second = 0;
+ std::pair<Point, int> returnCount(Point(0, 0), 0);
+ int i_size_less_1 = (int)(incoming.size()) -1;
+ int c_size_less_1 = (int)(counts.size()) -1;
+ int i_size = incoming.size();
+ int c_size = counts.size();
+
+ bool have_vertical_tail_from_below = false;
+ if(c_size &&
+ is_vertical(counts_from_scanline.back().first.first)) {
+ have_vertical_tail_from_below = true;
+ }
+ //assert size = size_less_1 + 1
+ //std::cout << tails.size() << " " << incoming.size() << " " << counts_from_scanline.size() << " " << incoming_count.size() << std::endl;
+ // for(std::size_t i = 0; i < counts.size(); ++i) {
+ // std::cout << counts_from_scanline[i].first.first.first.get(HORIZONTAL) << ",";
+ // std::cout << counts_from_scanline[i].first.first.first.get(VERTICAL) << " ";
+ // std::cout << counts_from_scanline[i].first.first.second.get(HORIZONTAL) << ",";
+ // std::cout << counts_from_scanline[i].first.first.second.get(VERTICAL) << ":";
+ // std::cout << counts_from_scanline[i].first.second << " ";
+ // } std::cout << std::endl;
+ // print(incoming_count);
+ {
+ for(int i = 0; i < c_size_less_1; ++i) {
+ //std::cout << i << std::endl;
+ if(counts[i] == -1) {
+ //std::cout << "fixed i\n";
+ for(int j = i + 1; j < c_size; ++j) {
+ //std::cout << j << std::endl;
+ if(counts[j]) {
+ if(counts[j] == 1) {
+ //std::cout << "case1: " << i << " " << j << std::endl;
+ //if a figure is closed it will be written out by this function to output
+ active_tail_arbitrary::joinChains(point, tails[i], tails[j], true, output);
+ counts[i] = 0;
+ counts[j] = 0;
+ tails[i] = 0;
+ tails[j] = 0;
+ }
+ break;
+ }
+ }
+ }
+ }
+ }
+ //find any pairs of incoming edges that need to create pair for leading solid
+ //std::cout << "checking case2\n";
+ {
+ for(int i = 0; i < i_size_less_1; ++i) {
+ //std::cout << i << std::endl;
+ if(incoming[i] == 1) {
+ //std::cout << "fixed i\n";
+ for(int j = i + 1; j < i_size; ++j) {
+ //std::cout << j << std::endl;
+ if(incoming[j]) {
+ //std::cout << incoming[j] << std::endl;
+ if(incoming[j] == -1) {
+ //std::cout << "case2: " << i << " " << j << std::endl;
+ //std::cout << "creating active tail pair\n";
+ std::pair<active_tail_arbitrary*, active_tail_arbitrary*> tailPair =
+ active_tail_arbitrary::createActiveTailsAsPair(point, true, 0, polygon_arbitrary_formation<Unit>::fractureHoles_);
+ //tailPair.first->print();
+ //tailPair.second->print();
+ if(j == i_size_less_1 && incoming_count[j].first.get(HORIZONTAL) == point.get(HORIZONTAL)) {
+ //vertical active tail becomes return value
+ returnValue = tailPair.first;
+ returnCount.first = point;
+ returnCount.second = 1;
+ } else {
+ //std::cout << "new element " << j-1 << " " << -1 << std::endl;
+ //std::cout << point << " " << incoming_count[j].first << std::endl;
+ elements.push_back(std::pair<vertex_half_edge,
+ active_tail_arbitrary*>(vertex_half_edge(point,
+ incoming_count[j].first, -1), tailPair.first));
+ }
+ //std::cout << "new element " << i-1 << " " << 1 << std::endl;
+ //std::cout << point << " " << incoming_count[i].first << std::endl;
+ elements.push_back(std::pair<vertex_half_edge,
+ active_tail_arbitrary*>(vertex_half_edge(point,
+ incoming_count[i].first, 1), tailPair.second));
+ incoming[i] = 0;
+ incoming[j] = 0;
+ }
+ break;
+ }
+ }
+ }
+ }
+ }
+ //find any active tail that needs to pass through to an incoming edge
+ //we expect to find no more than two pass through
+
+ //find pass through with solid on top
+ {
+ //std::cout << "checking case 3\n";
+ for(int i = 0; i < c_size; ++i) {
+ //std::cout << i << std::endl;
+ if(counts[i] != 0) {
+ if(counts[i] == 1) {
+ //std::cout << "fixed i\n";
+ for(int j = i_size_less_1; j >= 0; --j) {
+ if(incoming[j] != 0) {
+ if(incoming[j] == 1) {
+ //std::cout << "case3: " << i << " " << j << std::endl;
+ //tails[i]->print();
+ //pass through solid on top
+ tails[i]->pushPoint(point);
+ //std::cout << "after push\n";
+ if(j == i_size_less_1 && incoming_count[j].first.get(HORIZONTAL) == point.get(HORIZONTAL)) {
+ returnValue = tails[i];
+ returnCount.first = point;
+ returnCount.second = -1;
+ } else {
+ std::pair<active_tail_arbitrary*, active_tail_arbitrary*> tailPair =
+ active_tail_arbitrary::createActiveTailsAsPair(point, true, 0, false);
+ verticalPairOut.first = tails[i];
+ verticalPairOut.second = tailPair.first;
+ elements.push_back(std::pair<vertex_half_edge,
+ active_tail_arbitrary*>(vertex_half_edge(point,
+ incoming_count[j].first, incoming[j]), tailPair.second));
+ }
+ tails[i] = 0;
+ counts[i] = 0;
+ incoming[j] = 0;
+ }
+ break;
+ }
+ }
+ }
+ break;
+ }
+ }
+ }
+ //std::cout << "checking case 4\n";
+ //find pass through with solid on bottom
+ {
+ for(int i = c_size_less_1; i >= 0; --i) {
+ //std::cout << "i = " << i << " with count " << counts[i] << std::endl;
+ if(counts[i] != 0) {
+ if(counts[i] == -1) {
+ for(int j = 0; j < i_size; ++j) {
+ if(incoming[j] != 0) {
+ if(incoming[j] == -1) {
+ //std::cout << "case4: " << i << " " << j << std::endl;
+ //pass through solid on bottom
+
+ //if count from scanline is vertical
+ if(i == c_size_less_1 &&
+ counts_from_scanline[i].first.first.first.get(HORIZONTAL) ==
+ point.get(HORIZONTAL)) {
+ //if incoming count is vertical
+ if(j == i_size_less_1 &&
+ incoming_count[j].first.get(HORIZONTAL) == point.get(HORIZONTAL)) {
+ returnValue = tails[i];
+ returnCount.first = point;
+ returnCount.second = 1;
+ } else {
+ tails[i]->pushPoint(point);
+ elements.push_back(std::pair<vertex_half_edge,
+ active_tail_arbitrary*>(vertex_half_edge(point,
+ incoming_count[j].first, incoming[j]), tails[i]));
+ }
+ } else if(j == i_size_less_1 &&
+ incoming_count[j].first.get(HORIZONTAL) ==
+ point.get(HORIZONTAL)) {
+ if(verticalPair.first == 0) {
+ getVerticalPair_(verticalPair, previter);
+ }
+ active_tail_arbitrary::joinChains(point, tails[i], verticalPair.first, true, output);
+ returnValue = verticalPair.second;
+ returnCount.first = point;
+ returnCount.second = 1;
+ } else {
+ //neither is vertical
+ if(verticalPair.first == 0) {
+ getVerticalPair_(verticalPair, previter);
+ }
+ active_tail_arbitrary::joinChains(point, tails[i], verticalPair.first, true, output);
+ verticalPair.second->pushPoint(point);
+ elements.push_back(std::pair<vertex_half_edge,
+ active_tail_arbitrary*>(vertex_half_edge(point,
+ incoming_count[j].first, incoming[j]), verticalPair.second));
+ }
+ tails[i] = 0;
+ counts[i] = 0;
+ incoming[j] = 0;
+ }
+ break;
+ }
+ }
+ }
+ break;
+ }
+ }
+ }
+ //find the end of a hole or the beginning of a hole
+
+ //find end of a hole
+ {
+ for(int i = 0; i < c_size_less_1; ++i) {
+ if(counts[i] != 0) {
+ for(int j = i+1; j < c_size; ++j) {
+ if(counts[j] != 0) {
+ //std::cout << "case5: " << i << " " << j << std::endl;
+ //we are ending a hole and may potentially close a figure and have to handle the hole
+ tails[i]->pushPoint(point);
+ verticalPairOut.first = tails[i];
+ if(j == c_size_less_1 &&
+ counts_from_scanline[j].first.first.first.get(HORIZONTAL) ==
+ point.get(HORIZONTAL)) {
+ verticalPairOut.second = tails[j];
+ } else {
+ //need to close a trapezoid below
+ if(verticalPair.first == 0) {
+ getVerticalPair_(verticalPair, previter);
+ }
+ active_tail_arbitrary::joinChains(point, tails[j], verticalPair.first, true, output);
+ verticalPairOut.second = verticalPair.second;
+ }
+ tails[i] = 0;
+ tails[j] = 0;
+ counts[i] = 0;
+ counts[j] = 0;
+ break;
+ }
+ }
+ break;
+ }
+ }
+ }
+ //find beginning of a hole
+ {
+ for(int i = 0; i < i_size_less_1; ++i) {
+ if(incoming[i] != 0) {
+ for(int j = i+1; j < i_size; ++j) {
+ if(incoming[j] != 0) {
+ //std::cout << "case6: " << i << " " << j << std::endl;
+ //we are beginning a empty space
+ if(verticalPair.first == 0) {
+ getVerticalPair_(verticalPair, previter);
+ }
+ verticalPair.second->pushPoint(point);
+ if(j == i_size_less_1 &&
+ incoming_count[j].first.get(HORIZONTAL) == point.get(HORIZONTAL)) {
+ returnValue = verticalPair.first;
+ returnCount.first = point;
+ returnCount.second = -1;
+ } else {
+ std::pair<active_tail_arbitrary*, active_tail_arbitrary*> tailPair =
+ active_tail_arbitrary::createActiveTailsAsPair(point, false, 0, false);
+ elements.push_back(std::pair<vertex_half_edge,
+ active_tail_arbitrary*>(vertex_half_edge(point,
+ incoming_count[j].first, incoming[j]), tailPair.second));
+ verticalPairOut.second = tailPair.first;
+ verticalPairOut.first = verticalPair.first;
+ }
+ elements.push_back(std::pair<vertex_half_edge,
+ active_tail_arbitrary*>(vertex_half_edge(point,
+ incoming_count[i].first, incoming[i]), verticalPair.second));
+ incoming[i] = 0;
+ incoming[j] = 0;
+ break;
+ }
+ }
+ break;
+ }
+ }
+ }
+ if(have_vertical_tail_from_below) {
+ if(tails.back()) {
+ tails.back()->pushPoint(point);
+ returnValue = tails.back();
+ returnCount.first = point;
+ returnCount.second = counts.back();
+ }
+ }
+ verticalPair = verticalPairOut;
+ //assert that tails, counts and incoming are all null
+ return std::pair<std::pair<Point, int>, active_tail_arbitrary*>(returnCount, returnValue);
+ }
+
+ static inline void print(const vertex_arbitrary_count& count) {
+ for(unsigned i = 0; i < count.size(); ++i) {
+ //std::cout << count[i].first.get(HORIZONTAL) << ",";
+ //std::cout << count[i].first.get(VERTICAL) << ":";
+ //std::cout << count[i].second << " ";
+ } //std::cout << std::endl;
+ }
+
+ static inline void print(const scanline_data& data) {
+ for(typename scanline_data::const_iterator itr = data.begin(); itr != data.end(); ++itr){
+ //std::cout << itr->first.pt << ", " << itr->first.other_pt << "; ";
+ } //std::cout << std::endl;
+ }
+
+ template <class cT, class iT>
+ inline iT processEvent_(cT& output, iT inputBegin, iT inputEnd) {
+ typedef typename high_precision_type<Unit>::type high_precision;
+ //std::cout << "processEvent_\n";
+ polygon_arbitrary_formation<Unit>::justBefore_ = true;
+ //collect up all elements from the tree that are at the y
+ //values of events in the input queue
+ //create vector of new elements to add into tree
+ active_tail_arbitrary* verticalTail = 0;
+ std::pair<active_tail_arbitrary*, active_tail_arbitrary*> verticalPair;
+ std::pair<Point, int> verticalCount(Point(0, 0), 0);
+ iT currentIter = inputBegin;
+ std::vector<iterator> elementIters;
+ std::vector<std::pair<vertex_half_edge, active_tail_arbitrary*> > elements;
+ while(currentIter != inputEnd && currentIter->pt.get(HORIZONTAL) == polygon_arbitrary_formation<Unit>::x_) {
+ //std::cout << "loop\n";
+ Unit currentY = (*currentIter).pt.get(VERTICAL);
+ //std::cout << "current Y " << currentY << std::endl;
+ //std::cout << "scanline size " << scanData_.size() << std::endl;
+ //print(scanData_);
+ iterator iter = lookUp_(currentY);
+ //std::cout << "found element in scanline " << (iter != scanData_.end()) << std::endl;
+ //int counts[4] = {0, 0, 0, 0};
+ incoming_count counts_from_scanline;
+ //std::cout << "finding elements in tree\n";
+ //if(iter != scanData_.end())
+ // std::cout << "first iter y is " << iter->first.evalAtX(x_) << std::endl;
+ iterator previter = iter;
+ if(previter != polygon_arbitrary_formation<Unit>::scanData_.end() &&
+ previter->first.evalAtX(polygon_arbitrary_formation<Unit>::x_) >= currentY &&
+ previter != polygon_arbitrary_formation<Unit>::scanData_.begin())
+ --previter;
+ while(iter != polygon_arbitrary_formation<Unit>::scanData_.end() &&
+ iter->first.evalAtX(polygon_arbitrary_formation<Unit>::x_) == (high_precision)currentY) {
+ //std::cout << "loop2\n";
+ elementIters.push_back(iter);
+ counts_from_scanline.push_back(std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*>
+ (std::pair<std::pair<Point, Point>, int>(std::pair<Point, Point>(iter->first.pt,
+ iter->first.other_pt),
+ iter->first.count),
+ iter->second));
+ ++iter;
+ }
+ Point currentPoint(polygon_arbitrary_formation<Unit>::x_, currentY);
+ //std::cout << "counts_from_scanline size " << counts_from_scanline.size() << std::endl;
+ sort_incoming_count(counts_from_scanline, currentPoint);
+
+ vertex_arbitrary_count incoming;
+ //std::cout << "aggregating\n";
+ do {
+ //std::cout << "loop3\n";
+ const vertex_half_edge& elem = *currentIter;
+ incoming.push_back(std::pair<Point, int>(elem.other_pt, elem.count));
+ ++currentIter;
+ } while(currentIter != inputEnd && currentIter->pt.get(VERTICAL) == currentY &&
+ currentIter->pt.get(HORIZONTAL) == polygon_arbitrary_formation<Unit>::x_);
+ //print(incoming);
+ sort_vertex_arbitrary_count(incoming, currentPoint);
+ //std::cout << currentPoint.get(HORIZONTAL) << "," << currentPoint.get(VERTICAL) << std::endl;
+ //print(incoming);
+ //std::cout << "incoming counts from input size " << incoming.size() << std::endl;
+ //compact_vertex_arbitrary_count(currentPoint, incoming);
+ vertex_arbitrary_count tmp;
+ tmp.reserve(incoming.size());
+ for(std::size_t i = 0; i < incoming.size(); ++i) {
+ if(currentPoint < incoming[i].first) {
+ tmp.push_back(incoming[i]);
+ }
+ }
+ incoming.swap(tmp);
+ //std::cout << "incoming counts from input size " << incoming.size() << std::endl;
+ //now counts_from_scanline has the data from the left and
+ //incoming has the data from the right at this point
+ //cancel out any end points
+ if(verticalTail) {
+ //std::cout << "adding vertical tail to counts from scanline\n";
+ //std::cout << -verticalCount.second << std::endl;
+ counts_from_scanline.push_back(std::pair<std::pair<std::pair<Point, Point>, int>, active_tail_arbitrary*>
+ (std::pair<std::pair<Point, Point>, int>(std::pair<Point, Point>(verticalCount.first,
+ currentPoint),
+ -verticalCount.second),
+ verticalTail));
+ }
+ if(!incoming.empty() && incoming.back().first.get(HORIZONTAL) == polygon_arbitrary_formation<Unit>::x_) {
+ //std::cout << "inverted vertical event\n";
+ incoming.back().second *= -1;
+ }
+ //std::cout << "calling processPoint_\n";
+ std::pair<std::pair<Point, int>, active_tail_arbitrary*> result = processPoint_(output, elements, verticalPair, previter, Point(polygon_arbitrary_formation<Unit>::x_, currentY), counts_from_scanline, incoming);
+ verticalCount = result.first;
+ verticalTail = result.second;
+ if(verticalPair.first != 0 && iter != polygon_arbitrary_formation<Unit>::scanData_.end() &&
+ (currentIter == inputEnd || currentIter->pt.x() != polygon_arbitrary_formation<Unit>::x_ ||
+ currentIter->pt.y() > (*iter).first.evalAtX(polygon_arbitrary_formation<Unit>::x_))) {
+ //splice vertical pair into edge above
+ active_tail_arbitrary* tailabove = (*iter).second;
+ Point point(polygon_arbitrary_formation<Unit>::x_, (*iter).first.evalAtX(polygon_arbitrary_formation<Unit>::x_));
+ verticalPair.second->pushPoint(point);
+ active_tail_arbitrary::joinChains(point, tailabove, verticalPair.first, true, output);
+ (*iter).second = verticalPair.second;
+ verticalPair.first = 0;
+ verticalPair.second = 0;
+ }
+ }
+ //std::cout << "erasing\n";
+ //erase all elements from the tree
+ for(typename std::vector<iterator>::iterator iter = elementIters.begin();
+ iter != elementIters.end(); ++iter) {
+ //std::cout << "erasing loop\n";
+ polygon_arbitrary_formation<Unit>::scanData_.erase(*iter);
+ }
+ //switch comparison tie breaking policy
+ polygon_arbitrary_formation<Unit>::justBefore_ = false;
+ //add new elements into tree
+ //std::cout << "inserting\n";
+ for(typename std::vector<std::pair<vertex_half_edge, active_tail_arbitrary*> >::iterator iter = elements.begin();
+ iter != elements.end(); ++iter) {
+ //std::cout << "inserting loop\n";
+ polygon_arbitrary_formation<Unit>::scanData_.insert(polygon_arbitrary_formation<Unit>::scanData_.end(), *iter);
+ }
+ //std::cout << "end processEvent\n";
+ return currentIter;
+ }
+ public:
+ template <typename stream_type>
+ static inline bool testTrapezoidArbitraryFormationRect(stream_type& stdcout) {
+ stdcout << "testing trapezoid formation\n";
+ trapezoid_arbitrary_formation pf;
+ std::vector<polygon_data<Unit> > polys;
+ std::vector<vertex_half_edge> data;
+ data.push_back(vertex_half_edge(Point(0, 0), Point(10, 0), 1));
+ data.push_back(vertex_half_edge(Point(0, 0), Point(0, 10), 1));
+ data.push_back(vertex_half_edge(Point(0, 10), Point(0, 0), -1));
+ data.push_back(vertex_half_edge(Point(0, 10), Point(10, 10), -1));
+ data.push_back(vertex_half_edge(Point(10, 0), Point(0, 0), -1));
+ data.push_back(vertex_half_edge(Point(10, 0), Point(10, 10), -1));
+ data.push_back(vertex_half_edge(Point(10, 10), Point(10, 0), 1));
+ data.push_back(vertex_half_edge(Point(10, 10), Point(0, 10), 1));
+ std::sort(data.begin(), data.end());
+ pf.scan(polys, data.begin(), data.end());
+ stdcout << "result size: " << polys.size() << std::endl;
+ for(std::size_t i = 0; i < polys.size(); ++i) {
+ stdcout << polys[i] << std::endl;
+ }
+ stdcout << "done testing trapezoid formation\n";
+ return true;
+ }
+ template <typename stream_type>
+ static inline bool testTrapezoidArbitraryFormationP1(stream_type& stdcout) {
+ stdcout << "testing trapezoid formation P1\n";
+ trapezoid_arbitrary_formation pf;
+ std::vector<polygon_data<Unit> > polys;
+ std::vector<vertex_half_edge> data;
+ data.push_back(vertex_half_edge(Point(0, 0), Point(10, 10), 1));
+ data.push_back(vertex_half_edge(Point(0, 0), Point(0, 10), 1));
+ data.push_back(vertex_half_edge(Point(0, 10), Point(0, 0), -1));
+ data.push_back(vertex_half_edge(Point(0, 10), Point(10, 20), -1));
+ data.push_back(vertex_half_edge(Point(10, 10), Point(0, 0), -1));
+ data.push_back(vertex_half_edge(Point(10, 10), Point(10, 20), -1));
+ data.push_back(vertex_half_edge(Point(10, 20), Point(10, 10), 1));
+ data.push_back(vertex_half_edge(Point(10, 20), Point(0, 10), 1));
+ std::sort(data.begin(), data.end());
+ pf.scan(polys, data.begin(), data.end());
+ stdcout << "result size: " << polys.size() << std::endl;
+ for(std::size_t i = 0; i < polys.size(); ++i) {
+ stdcout << polys[i] << std::endl;
+ }
+ stdcout << "done testing trapezoid formation\n";
+ return true;
+ }
+ template <typename stream_type>
+ static inline bool testTrapezoidArbitraryFormationP2(stream_type& stdcout) {
+ stdcout << "testing trapezoid formation P2\n";
+ trapezoid_arbitrary_formation pf;
+ std::vector<polygon_data<Unit> > polys;
+ std::vector<vertex_half_edge> data;
+ data.push_back(vertex_half_edge(Point(-3, 1), Point(2, -4), 1));
+ data.push_back(vertex_half_edge(Point(-3, 1), Point(-2, 2), -1));
+ data.push_back(vertex_half_edge(Point(-2, 2), Point(2, 4), -1));
+ data.push_back(vertex_half_edge(Point(-2, 2), Point(-3, 1), 1));
+ data.push_back(vertex_half_edge(Point(2, -4), Point(-3, 1), -1));
+ data.push_back(vertex_half_edge(Point(2, -4), Point(2, 4), -1));
+ data.push_back(vertex_half_edge(Point(2, 4), Point(-2, 2), 1));
+ data.push_back(vertex_half_edge(Point(2, 4), Point(2, -4), 1));
+ std::sort(data.begin(), data.end());
+ pf.scan(polys, data.begin(), data.end());
+ stdcout << "result size: " << polys.size() << std::endl;
+ for(std::size_t i = 0; i < polys.size(); ++i) {
+ stdcout << polys[i] << std::endl;
+ }
+ stdcout << "done testing trapezoid formation\n";
+ return true;
+ }
+
+ template <typename stream_type>
+ static inline bool testTrapezoidArbitraryFormationPolys(stream_type& stdcout) {
+ stdcout << "testing trapezoid formation polys\n";
+ trapezoid_arbitrary_formation pf;
+ std::vector<polygon_with_holes_data<Unit> > polys;
+ //trapezoid_arbitrary_formation pf2(true);
+ //std::vector<polygon_with_holes_data<Unit> > polys2;
+ std::vector<vertex_half_edge> data;
+ data.push_back(vertex_half_edge(Point(0, 0), Point(100, 1), 1));
+ data.push_back(vertex_half_edge(Point(0, 0), Point(1, 100), -1));
+ data.push_back(vertex_half_edge(Point(1, 100), Point(0, 0), 1));
+ data.push_back(vertex_half_edge(Point(1, 100), Point(101, 101), -1));
+ data.push_back(vertex_half_edge(Point(100, 1), Point(0, 0), -1));
+ data.push_back(vertex_half_edge(Point(100, 1), Point(101, 101), 1));
+ data.push_back(vertex_half_edge(Point(101, 101), Point(100, 1), -1));
+ data.push_back(vertex_half_edge(Point(101, 101), Point(1, 100), 1));
+
+ data.push_back(vertex_half_edge(Point(2, 2), Point(10, 2), -1));
+ data.push_back(vertex_half_edge(Point(2, 2), Point(2, 10), -1));
+ data.push_back(vertex_half_edge(Point(2, 10), Point(2, 2), 1));
+ data.push_back(vertex_half_edge(Point(2, 10), Point(10, 10), 1));
+ data.push_back(vertex_half_edge(Point(10, 2), Point(2, 2), 1));
+ data.push_back(vertex_half_edge(Point(10, 2), Point(10, 10), 1));
+ data.push_back(vertex_half_edge(Point(10, 10), Point(10, 2), -1));
+ data.push_back(vertex_half_edge(Point(10, 10), Point(2, 10), -1));
+
+ data.push_back(vertex_half_edge(Point(2, 12), Point(10, 12), -1));
+ data.push_back(vertex_half_edge(Point(2, 12), Point(2, 22), -1));
+ data.push_back(vertex_half_edge(Point(2, 22), Point(2, 12), 1));
+ data.push_back(vertex_half_edge(Point(2, 22), Point(10, 22), 1));
+ data.push_back(vertex_half_edge(Point(10, 12), Point(2, 12), 1));
+ data.push_back(vertex_half_edge(Point(10, 12), Point(10, 22), 1));
+ data.push_back(vertex_half_edge(Point(10, 22), Point(10, 12), -1));
+ data.push_back(vertex_half_edge(Point(10, 22), Point(2, 22), -1));
+
+ std::sort(data.begin(), data.end());
+ pf.scan(polys, data.begin(), data.end());
+ stdcout << "result size: " << polys.size() << std::endl;
+ for(std::size_t i = 0; i < polys.size(); ++i) {
+ stdcout << polys[i] << std::endl;
+ }
+ //pf2.scan(polys2, data.begin(), data.end());
+ //stdcout << "result size: " << polys2.size() << std::endl;
+ //for(std::size_t i = 0; i < polys2.size(); ++i) {
+ // stdcout << polys2[i] << std::endl;
+ //}
+ stdcout << "done testing trapezoid formation\n";
+ return true;
+ }
+
+ template <typename stream_type>
+ static inline bool testTrapezoidArbitraryFormationSelfTouch1(stream_type& stdcout) {
+ stdcout << "testing trapezoid formation self touch 1\n";
+ trapezoid_arbitrary_formation pf;
+ std::vector<polygon_data<Unit> > polys;
+ std::vector<vertex_half_edge> data;
+ data.push_back(vertex_half_edge(Point(0, 0), Point(10, 0), 1));
+ data.push_back(vertex_half_edge(Point(0, 0), Point(0, 10), 1));
+
+ data.push_back(vertex_half_edge(Point(0, 10), Point(0, 0), -1));
+ data.push_back(vertex_half_edge(Point(0, 10), Point(5, 10), -1));
+
+ data.push_back(vertex_half_edge(Point(10, 0), Point(0, 0), -1));
+ data.push_back(vertex_half_edge(Point(10, 0), Point(10, 5), -1));
+
+ data.push_back(vertex_half_edge(Point(10, 5), Point(10, 0), 1));
+ data.push_back(vertex_half_edge(Point(10, 5), Point(5, 5), 1));
+
+ data.push_back(vertex_half_edge(Point(5, 10), Point(5, 5), 1));
+ data.push_back(vertex_half_edge(Point(5, 10), Point(0, 10), 1));
+
+ data.push_back(vertex_half_edge(Point(5, 2), Point(5, 5), -1));
+ data.push_back(vertex_half_edge(Point(5, 2), Point(7, 2), -1));
+
+ data.push_back(vertex_half_edge(Point(5, 5), Point(5, 10), -1));
+ data.push_back(vertex_half_edge(Point(5, 5), Point(5, 2), 1));
+ data.push_back(vertex_half_edge(Point(5, 5), Point(10, 5), -1));
+ data.push_back(vertex_half_edge(Point(5, 5), Point(7, 2), 1));
+
+ data.push_back(vertex_half_edge(Point(7, 2), Point(5, 5), -1));
+ data.push_back(vertex_half_edge(Point(7, 2), Point(5, 2), 1));
+
+ std::sort(data.begin(), data.end());
+ pf.scan(polys, data.begin(), data.end());
+ stdcout << "result size: " << polys.size() << std::endl;
+ for(std::size_t i = 0; i < polys.size(); ++i) {
+ stdcout << polys[i] << std::endl;
+ }
+ stdcout << "done testing trapezoid formation\n";
+ return true;
+ }
+ };
template <typename T>
struct PolyLineArbitraryByConcept<T, polygon_with_holes_concept> { typedef poly_line_arbitrary_polygon_data<T> type; };
Modified: sandbox/gtl/boost/polygon/detail/scan_arbitrary.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/scan_arbitrary.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/scan_arbitrary.hpp 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -2542,6 +2542,163 @@
return true;
}
+
+
+
+
+
+
+
+
+
+
+
+
+
+ template <typename Unit, typename property_type>
+ class arbitrary_connectivity_extraction : public scanline_base<Unit> {
+ private:
+
+ typedef typename scanline_base<Unit>::Point Point;
+
+ //the first point is the vertex and and second point establishes the slope of an edge eminating from the vertex
+ //typedef std::pair<Point, Point> half_edge;
+ typedef typename scanline_base<Unit>::half_edge half_edge;
+
+ //scanline comparator functor
+ typedef typename scanline_base<Unit>::less_half_edge less_half_edge;
+ typedef typename scanline_base<Unit>::less_point less_point;
+
+ //this data structure assocates a property and count to a half edge
+ typedef std::pair<half_edge, std::pair<property_type, int> > vertex_property;
+ //this data type stores the combination of many half edges
+ typedef std::vector<vertex_property> property_merge_data;
+
+ //this is the data type used internally to store the combination of property counts at a given location
+ typedef std::vector<std::pair<property_type, int> > property_map;
+ //this data type is used internally to store the combined property data for a given half edge
+ typedef std::pair<half_edge, property_map> vertex_data;
+
+ property_merge_data pmd;
+
+ template<typename vertex_data_type>
+ class less_vertex_data {
+ public:
+ less_vertex_data() {}
+ bool operator()(const vertex_data_type& lvalue, const vertex_data_type& rvalue) {
+ less_point lp;
+ if(lp(lvalue.first.first, rvalue.first.first)) return true;
+ if(lp(rvalue.first.first, lvalue.first.first)) return false;
+ Unit x = lvalue.first.first.get(HORIZONTAL);
+ int just_before_ = 0;
+ less_half_edge lhe(&x, &just_before_);
+ return lhe(lvalue.first, rvalue.first);
+ }
+ };
+
+
+ template <typename cT>
+ static void process_previous_x(cT& output) {
+ std::map<point_data<Unit>, std::set<property_type> >& y_prop_map = output.first.second;
+ if(y_prop_map.empty()) return;
+ Unit x = output.first.first;
+ for(typename std::map<point_data<Unit>, std::set<property_type> >::iterator itr =
+ y_prop_map.begin(); itr != y_prop_map.end(); ++itr) {
+ if((*itr).first.x() != x) {
+ y_prop_map.erase(y_prop_map.begin(), itr);
+ break;
+ }
+ for(typename std::set<property_type>::iterator inner_itr = itr->second.begin();
+ inner_itr != itr->second.end(); ++inner_itr) {
+ std::set<property_type>& output_edges = (*(output.second))[*inner_itr];
+ typename std::set<property_type>::iterator inner_inner_itr = inner_itr;
+ ++inner_inner_itr;
+ for( ; inner_inner_itr != itr->second.end(); ++inner_inner_itr) {
+ output_edges.insert(output_edges.end(), *inner_inner_itr);
+ std::set<property_type>& output_edges_2 = (*(output.second))[*inner_inner_itr];
+ output_edges_2.insert(output_edges_2.end(), *inner_itr);
+ }
+ }
+ }
+ }
+
+ template <typename result_type, typename key_type>
+ class connectivity_extraction_output_functor {
+ public:
+ connectivity_extraction_output_functor() {}
+ void operator()(result_type& result, const half_edge& edge, const key_type& left, const key_type& right) {
+ Unit& x = result.first.first;
+ std::map<point_data<Unit>, std::set<property_type> >& y_prop_map = result.first.second;
+ point_data<Unit> pt = edge.first;
+ if(pt.x() != x) process_previous_x(result);
+ x = pt.x();
+ std::set<property_type>& output_set = y_prop_map[pt];
+ {
+ for(typename key_type::const_iterator itr1 =
+ left.begin(); itr1 != left.end(); ++itr1) {
+ output_set.insert(output_set.end(), *itr1);
+ }
+ for(typename key_type::const_iterator itr2 =
+ right.begin(); itr2 != right.end(); ++itr2) {
+ output_set.insert(output_set.end(), *itr2);
+ }
+ }
+ std::set<property_type>& output_set2 = y_prop_map[edge.second];
+ for(typename key_type::const_iterator itr1 =
+ left.begin(); itr1 != left.end(); ++itr1) {
+ output_set2.insert(output_set2.end(), *itr1);
+ }
+ for(typename key_type::const_iterator itr2 =
+ right.begin(); itr2 != right.end(); ++itr2) {
+ output_set2.insert(output_set2.end(), *itr2);
+ }
+ }
+ };
+
+ inline void sort_property_merge_data() {
+ less_vertex_data<vertex_property> lvd;
+ std::sort(pmd.begin(), pmd.end(), lvd);
+ }
+ public:
+ inline arbitrary_connectivity_extraction() : pmd() {}
+ inline arbitrary_connectivity_extraction
+ (const arbitrary_connectivity_extraction& pm) : pmd(pm.pmd) {}
+ inline arbitrary_connectivity_extraction& operator=
+ (const arbitrary_connectivity_extraction& pm) { pmd = pm.pmd; return *this; }
+
+ template <typename result_type>
+ inline void execute(result_type& result) {
+ //intersect data
+ property_merge_data tmp_pmd;
+ line_intersection<Unit>::validate_scan(tmp_pmd, pmd.begin(), pmd.end());
+ pmd.swap(tmp_pmd);
+ sort_property_merge_data();
+ scanline<Unit, property_type, std::vector<property_type> > sl;
+ std::pair<std::pair<Unit, std::map<point_data<Unit>, std::set<property_type> > >,
+ result_type*> output
+ (std::make_pair(std::make_pair((std::numeric_limits<Unit>::max)(),
+ std::map<point_data<Unit>,
+ std::set<property_type> >()), &result));
+ connectivity_extraction_output_functor<std::pair<std::pair<Unit,
+ std::map<point_data<Unit>, std::set<property_type> > >, result_type*>,
+ std::vector<property_type> > ceof;
+ sl.scan(output, ceof, pmd.begin(), pmd.end());
+ process_previous_x(output);
+ }
+
+ inline void clear() {*this = arbitrary_connectivity_extraction();}
+
+ template <typename iT>
+ void populateTouchSetData(iT begin, iT end,
+ property_type property) {
+ for( ; begin != end; ++begin) {
+ pmd.push_back(vertex_property(half_edge((*begin).first.first, (*begin).first.second),
+ std::pair<property_type, int>(property, (*begin).second)));
+ }
+ }
+
+ };
+
}
}
#endif
Modified: sandbox/gtl/boost/polygon/gtl_boost_unit_test.cpp
==============================================================================
--- sandbox/gtl/boost/polygon/gtl_boost_unit_test.cpp (original)
+++ sandbox/gtl/boost/polygon/gtl_boost_unit_test.cpp 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -1291,6 +1291,143 @@
return true;
}
+bool test_aa_touch() {
+ using namespace gtl;
+ connectivity_extraction<int> ce;
+ rectangle_data<int> rect1(0, 0, 10, 10);
+ rectangle_data<int> rect2(5, 5, 15, 15);
+ rectangle_data<int> rect3(5, 20, 15, 25);
+ ce.insert(rect1);
+ ce.insert(rect2);
+ ce.insert(rect3);
+ std::vector<std::set<int> > graph(3);
+ ce.extract(graph);
+ if(graph[0].size() == 1 && graph[1].size() == 1 && graph[2].size() == 0) {
+ std::set<int>::iterator itr = graph[0].begin();
+ std::cout << *itr << std::endl;
+ std::set<int>::iterator itr1 = graph[1].begin();
+ std::cout << *itr1 << std::endl;
+ return true;
+ }
+ std::cout << "test failed\n";
+ return false;
+}
+
+bool test_aa_touch_ur() {
+ using namespace gtl;
+ connectivity_extraction<int> ce;
+ rectangle_data<int> rect1(0, 0, 5, 5);
+ rectangle_data<int> rect2(5, 5, 10, 10);
+ ce.insert(rect1);
+ ce.insert(rect2);
+ std::vector<std::set<int> > graph(2);
+ ce.extract(graph);
+ if(graph[0].size() == 1 && graph[1].size() == 1) {
+ std::set<int>::iterator itr = graph[0].begin();
+ std::cout << *itr << std::endl;
+ std::set<int>::iterator itr1 = graph[1].begin();
+ std::cout << *itr1 << std::endl;
+ return true;
+ }
+ std::cout << "test failed\n";
+ return false;
+}
+
+bool test_aa_touch_ur2() {
+ using namespace gtl;
+ connectivity_extraction<int> ce;
+ rectangle_data<int> rect2(5, 5, 10, 10);
+ point_data<int> pts[3] = {
+ point_data<int>(0, 0),
+ point_data<int>(5, 5),
+ point_data<int>(0, 5)
+ };
+ polygon_data<int> poly;
+ poly.set(pts, pts+3);
+ ce.insert(poly);
+ ce.insert(rect2);
+ std::vector<std::set<int> > graph(2);
+ ce.extract(graph);
+ if(graph[0].size() == 1 && graph[1].size() == 1) {
+ std::set<int>::iterator itr = graph[0].begin();
+ std::cout << *itr << std::endl;
+ std::set<int>::iterator itr1 = graph[1].begin();
+ std::cout << *itr1 << std::endl;
+ return true;
+ }
+ std::cout << "test failed\n";
+ return false;
+}
+
+bool test_aa_touch_r() {
+ using namespace gtl;
+ connectivity_extraction<int> ce;
+ rectangle_data<int> rect1(0, 0, 5, 5);
+ rectangle_data<int> rect2(5, 0, 10, 5);
+ ce.insert(rect1);
+ ce.insert(rect2);
+ std::vector<std::set<int> > graph(2);
+ ce.extract(graph);
+ if(graph[0].size() == 1 && graph[1].size() == 1) {
+ std::set<int>::iterator itr = graph[0].begin();
+ std::cout << *itr << std::endl;
+ std::set<int>::iterator itr1 = graph[1].begin();
+ std::cout << *itr1 << std::endl;
+ return true;
+ }
+ std::cout << "test failed\n";
+ return false;
+}
+
+bool test_aa_touch_boundaries() {
+ using namespace gtl;
+ connectivity_extraction<int> ce;
+ rectangle_data<int> rect1(0, 0, 10, 10);
+ rectangle_data<int> rect2(10, 0, 20, 10);
+ rectangle_data<int> rect3(20, 0, 30, 10);
+ rectangle_data<int> rect4(0, 10, 10, 20);
+ rectangle_data<int> rect5(10, 10, 20, 20);
+ rectangle_data<int> rect6(20, 10, 30, 20);
+ rectangle_data<int> rect7(0, 20, 10, 30);
+ rectangle_data<int> rect8(10, 20, 20, 30);
+ rectangle_data<int> rect9(20, 20, 30, 30);
+ ce.insert(rect1);
+ ce.insert(rect2);
+ ce.insert(rect3);
+ ce.insert(rect4);
+ ce.insert(rect5);
+ ce.insert(rect6);
+ ce.insert(rect7);
+ ce.insert(rect8);
+ ce.insert(rect9);
+ std::vector<std::set<int> > graph(9);
+ ce.extract(graph);
+ for(unsigned int i = 0; i < 9; ++i) {
+ std::cout << i << ": ";
+ for(std::set<int>::iterator itr = graph[i].begin(); itr != graph[i].end(); ++itr) {
+ std::cout << *itr << " ";
+ } std::cout << std::endl;
+ }
+ if(graph[0].size() == 3 && graph[1].size() == 5 && graph[2].size() == 3 &&
+ graph[3].size() == 5 && graph[4].size() == 8 && graph[5].size() == 5 &&
+ graph[6].size() == 3 && graph[7].size() == 5 && graph[8].size() == 3) {
+ return true;
+ }
+ std::cout << "test failed\n";
+ return false;
+}
+
+bool test_aa_concept_interact() {
+ using namespace gtl;
+ std::vector<polygon_data<int> > polys;
+ polys += rectangle_data<int>(10, 10, 20, 20);
+ polys += rectangle_data<int>(15, 15, 25, 25);
+ polys += rectangle_data<int>(5, 25, 10, 35);
+ interact(polys, rectangle_data<int>(0, 0, 13, 13));
+ if(polys.size() != 1) return false;
+ return true;
+}
+
bool test_get_rectangles() {
using namespace gtl;
polygon_90_set_data<int> ps(VERTICAL);
@@ -3089,7 +3226,7 @@
int i = 0;
for(std::map<std::set<int>, polygon_45_set_data<int> >::iterator itr = result.begin();
itr != result.end(); ++itr) {
- for(std::set<int>::iterator itr2 = (*itr).first.begin();
+ for(std::set<int>::const_iterator itr2 = (*itr).first.begin();
itr2 != (*itr).first.end(); ++itr2) {
std::cout << *itr2 << " ";
} std::cout << " : ";
@@ -3138,6 +3275,60 @@
++i;
}
}
+ {
+ std::cout << trapezoid_arbitrary_formation<int>::testTrapezoidArbitraryFormationRect(std::cout) << std::endl;
+ std::cout << trapezoid_arbitrary_formation<int>::testTrapezoidArbitraryFormationP1(std::cout) << std::endl;
+ std::cout << trapezoid_arbitrary_formation<int>::testTrapezoidArbitraryFormationP2(std::cout) << std::endl;
+ std::cout << trapezoid_arbitrary_formation<int>::testTrapezoidArbitraryFormationPolys(std::cout) << std::endl;
+ std::cout << polygon_arbitrary_formation<int>::testPolygonArbitraryFormationSelfTouch1(std::cout) << std::endl;
+ std::cout << trapezoid_arbitrary_formation<int>::testTrapezoidArbitraryFormationSelfTouch1(std::cout) << std::endl;
+ typedef rectangle_data<int> Rectangle;
+ polygon_set_data<int> ps;
+ ps += Rectangle(0, 1, 10, 11);
+ ps += Rectangle(5, 6, 15, 16);
+ std::vector<polygon_data<int> > polys;
+ ps.get_trapezoids(polys);
+ for(unsigned int i = 0; i < polys.size(); ++i) {
+ std::cout << polys[i] << std::endl;
+ }
+ ps.transform(axis_transformation(axis_transformation::FLIP_X));
+ polys.clear();
+ ps.get_trapezoids(polys);
+ for(unsigned int i = 0; i < polys.size(); ++i) {
+ std::cout << polys[i] << std::endl;
+ }
+ polys.clear();
+ ps.get_trapezoids(polys, HORIZONTAL);
+ for(unsigned int i = 0; i < polys.size(); ++i) {
+ std::cout << polys[i] << std::endl;
+ }
+ }
+
+ if(!test_aa_touch()) {
+ std::cout << "test_aa_touch failed\n";
+ return 1;
+ }
+ if(!test_aa_touch_ur()) {
+ std::cout << "test_aa_touch_ur failed\n";
+ return 1;
+ }
+ if(!test_aa_touch_ur2()) {
+ std::cout << "test_aa_touch_ur failed\n";
+ return 1;
+ }
+ if(!test_aa_touch_r()) {
+ std::cout << "test_aa_touch_r failed\n";
+ return 1;
+ }
+ if(!test_aa_touch_boundaries()) {
+ std::cout << "test_aa_touch_boundaries failed\n";
+ return 1;
+ }
+ if(!test_aa_concept_interact()) {
+ std::cout << "test_aa_concept_interact failed\n";
+ return 1;
+ }
+
std::cout << "ALL TESTS COMPLETE\n";
return 0;
}
Modified: sandbox/gtl/boost/polygon/polygon_set_concept.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_set_concept.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_set_concept.hpp 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -59,17 +59,28 @@
return lvalue;
}
- // //get trapezoids
- // template <typename output_container_type, typename polygon_set_type>
- // typename enable_if< typename gtl_if<typename is_polygon_set_type<polygon_set_type>::type>::type,
- // void>::type
- // get_trapezoids(output_container_type& output, const polygon_set_type& polygon_set) {
- // //TODO
- // // clean(polygon_set);
- // // polygon_set_data<typename polygon_set_traits<polygon_set_type>::coordinate_type> ps;
- // // assign(ps, polygon_set);
- // // ps.get_trapezoids(output);
- // }
+ //get trapezoids
+ template <typename output_container_type, typename polygon_set_type>
+ template <typename polygon_set_type>
+ typename enable_if< typename is_mutable_polygon_set_type<polygon_set_type>::type,
+ void>::type
+ get_trapezoids(output_container_type& output, const polygon_set_type& polygon_set) {
+ polygon_set_data<typename polygon_set_traits<polygon_set_type>::coordinate_type> ps;
+ assign(ps, polygon_set);
+ ps.get_trapezoids(output);
+ }
+
+ //get trapezoids
+ template <typename output_container_type, typename polygon_set_type>
+ template <typename polygon_set_type>
+ typename enable_if< typename is_mutable_polygon_set_type<polygon_set_type>::type,
+ void>::type
+ get_trapezoids(output_container_type& output, const polygon_set_type& polygon_set,
+ orientation_2d orient) {
+ polygon_set_data<typename polygon_set_traits<polygon_set_type>::coordinate_type> ps;
+ assign(ps, polygon_set);
+ ps.get_trapezoids(output, orient);
+ }
//equivalence
template <typename polygon_set_type_1, typename polygon_set_type_2>
@@ -139,6 +150,23 @@
return retval;
}
+ //interact
+ template <typename polygon_set_type_1, typename polygon_set_type_2>
+ typename enable_if< typename gtl_and_3 <
+ typename is_any_polygon_set_type<polygon_set_type_1>::type,
+ typename is_any_polygon_set_type<polygon_set_type_2>::type,
+ typename is_either_polygon_set_type<polygon_set_type_1, polygon_set_type_2>::type>::type,
+ polygon_set_type_1>::type&
+ interact(polygon_set_type_1& polygon_set_1, const polygon_set_type_2& polygon_set_2) {
+ polygon_set_data<typename polygon_set_traits<polygon_set_type_1>::coordinate_type> ps1;
+ assign(ps1, polygon_set_1);
+ polygon_set_data<typename polygon_set_traits<polygon_set_type_2>::coordinate_type> ps2;
+ assign(ps2, polygon_set_2);
+ ps1.interact(ps2);
+ assign(polygon_set_1, ps1);
+ return polygon_set_1;
+ }
+
template <typename polygon_set_type>
typename enable_if< typename is_mutable_polygon_set_type<polygon_set_type>::type,
polygon_set_type>::type &
@@ -258,7 +286,7 @@
}
struct yes_ps_oa : gtl_yes {};
-#if 0
+
template <typename geometry_type_1, typename geometry_type_2>
typename enable_if< typename gtl_and_4 < yes_ps_oa,
typename is_any_polygon_set_type<geometry_type_1>::type,
@@ -269,7 +297,7 @@
return polygon_set_view<geometry_type_1, geometry_type_2, 1>
(lvalue, rvalue);
}
-#endif
+
struct yes_ps_ox : gtl_yes {};
template <typename geometry_type_1, typename geometry_type_2>
Modified: sandbox/gtl/boost/polygon/polygon_set_data.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/polygon_set_data.hpp (original)
+++ sandbox/gtl/boost/polygon/polygon_set_data.hpp 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -205,6 +205,40 @@
get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type());
}
+ // append to the container cT with polygons of three or four verticies
+ // slicing orientation is vertical
+ template <class cT>
+ void get_trapezoids(cT& container) const {
+ clean();
+ trapezoid_arbitrary_formation<coordinate_type> pf;
+ typedef typename polygon_arbitrary_formation<coordinate_type>::vertex_half_edge vertex_half_edge;
+ std::vector<vertex_half_edge> data;
+ for(iterator_type itr = data_.begin(); itr != data_.end(); ++itr){
+ data.push_back(vertex_half_edge((*itr).first.first, (*itr).first.second, (*itr).second));
+ data.push_back(vertex_half_edge((*itr).first.second, (*itr).first.first, -1 * (*itr).second));
+ }
+ std::sort(data.begin(), data.end());
+ pf.scan(container, data.begin(), data.end());
+ //std::cout << "DONE FORMING POLYGONS\n";
+ }
+
+ // append to the container cT with polygons of three or four verticies
+ template <class cT>
+ void get_trapezoids(cT& container, orientation_2d slicing_orientation) const {
+ if(slicing_orientation == VERTICAL) {
+ get_trapezoids(container);
+ } else {
+ polygon_set_data<T> ps(*this);
+ ps.transform(axis_transformation(axis_transformation::SWAP_XY));
+ cT result;
+ ps.get_trapezoids(result);
+ for(typename cT::iterator itr = result.begin(); itr != result.end(); ++itr) {
+ ::boost::polygon::transform(*itr, axis_transformation(axis_transformation::SWAP_XY));
+ }
+ container.insert(container.end(), result.begin(), result.end());
+ }
+ }
+
// equivalence operator
inline bool operator==(const polygon_set_data& p) const {
clean();
@@ -296,9 +330,12 @@
template <typename transform_type>
inline polygon_set_data&
transform(const transform_type& tr) {
- for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) {
- ::boost::polygon::transform((*itr).first.first, tr);
- ::boost::polygon::transform((*itr).first.second, tr);
+ std::vector<polygon_with_holes_data<T> > polys;
+ get(polys);
+ clear();
+ for(std::size_t i = 0 ; i < polys.size(); ++i) {
+ ::boost::polygon::transform(polys[i], tr);
+ insert(polys[i]);
}
unsorted_ = true;
dirty_ = true;
@@ -337,6 +374,9 @@
return *this;
}
+ inline polygon_set_data&
+ interact(const polygon_set_data& that);
+
inline bool downcast(polygon_45_set_data<coordinate_type>& result) const {
if(!is_45_) return false;
for(iterator_type itr = begin(); itr != end(); ++itr) {
@@ -415,8 +455,6 @@
}
};
-
-
struct polygon_set_concept;
template <typename T>
struct geometry_concept<polygon_set_data<T> > {
@@ -425,6 +463,70 @@
}
}
#include "detail/scan_arbitrary.hpp"
+
+namespace boost { namespace polygon {
+ //ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and
+ //polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap
+ template <typename coordinate_type>
+ class connectivity_extraction{
+ private:
+ typedef arbitrary_connectivity_extraction<coordinate_type, int> ce;
+ ce ce_;
+ unsigned int nodeCount_;
+ public:
+ inline connectivity_extraction() : ce_(), nodeCount_(0) {}
+ inline connectivity_extraction(const connectivity_extraction& that) : ce_(that.ce_),
+ nodeCount_(that.nodeCount_) {}
+ inline connectivity_extraction& operator=(const connectivity_extraction& that) {
+ ce_ = that.ce_;
+ nodeCount_ = that.nodeCount_; {}
+ return *this;
+ }
+
+ //insert a polygon set graph node, the value returned is the id of the graph node
+ inline unsigned int insert(const polygon_set_data<coordinate_type>& ps) {
+ ps.clean();
+ ce_.populateTouchSetData(ps.begin(), ps.end(), nodeCount_);
+ return nodeCount_++;
+ }
+ template <class GeoObjT>
+ inline unsigned int insert(const GeoObjT& geoObj) {
+ polygon_set_data<coordinate_type> ps;
+ ps.insert(geoObj);
+ return insert(ps);
+ }
+
+ //extract connectivity and store the edges in the graph
+ //graph must be indexable by graph node id and the indexed value must be a std::set of
+ //graph node id
+ template <class GraphT>
+ inline void extract(GraphT& graph) {
+ ce_.execute(graph);
+ }
+ };
+
+ template <typename T>
+ polygon_set_data<T>&
+ polygon_set_data<T>::interact(const polygon_set_data<T>& that) {
+ connectivity_extraction<coordinate_type> ce;
+ std::vector<polygon_with_holes_data<T> > polys;
+ get(polys);
+ clear();
+ for(std::size_t i = 0; i < polys.size(); ++i) {
+ ce.insert(polys[i]);
+ }
+ int id = ce.insert(that);
+ std::vector<std::set<int> > graph(id+1);
+ ce.extract(graph);
+ for(std::set<int>::iterator itr = graph[id].begin();
+ itr != graph[id].end(); ++itr) {
+ insert(polys[*itr]);
+ }
+ return *this;
+ }
+}
+}
+
#include "polygon_set_traits.hpp"
#include "detail/polygon_set_view.hpp"
Added: sandbox/gtl/doc/gtl_connectivity_extraction.htm
==============================================================================
--- (empty file)
+++ sandbox/gtl/doc/gtl_connectivity_extraction.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -0,0 +1,120 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en" xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:(null)1="http://www.w3.org/TR/REC-html40"><head><!--
+ Copyright 2009-2010 Intel Corporation
+ license banner
+-->
+<title>Boost Polygon Library: Connectivity Extraction 45</title>
+ <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1">
+ <!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> -->
+<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0"><tbody><tr>
+<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <div style="padding: 5px;" align="center">
+ <img border="0" src="images/boost.png" width="277" height="86"><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;">
+ </a>
+ </div>
+ <div style="margin: 5px;">
+ <h3 class="navbar">Contents</h3>
+ <ul>
+ <li>Polygon Library Main Page</li>
+ <li><a href="gtl_design_overview.htm">Polygon
+ Library Design Overview</a></li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li>Polygon 90 With Holes Concept</li>
+ <li>Polygon 45 Concept</li>
+ <li>Polygon 45 With Holes Concept</li>
+ <li>Polygon Concept</li>
+ <li>Polygon With Holes Concept</li>
+ <li>Polygon 90 Set Concept</li>
+ <li>Polygon 45 Set Concept</li>
+ <li>Polygon Set Concept</li>
+ <li>Connectivity Extraction 90</li>
+ <li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
+ <li>Property Merge 90</li>
+ <li>Property Merge_45</li>
+ <li>Property Merge</li>
+ </ul>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+ Presentation</a></li>
+ </ul>
+ </div>
+ <h3 class="navbar">Polygon Sponsor</h3>
+ <div style="padding: 5px;" align="center">
+ <img border="0" src="images/intlogo.gif" width="127" height="51"><a title="www.adobe.com home page" href="http://www.adobe.com/" tabindex="2" style="border: medium none ;">
+ </a>
+ </div>
+</td>
+<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+
+<!-- End Header -->
+
+<br>
+<p>
+</p><h1>Connectivity Extraction</h1>
+
+<p>
+<p>The connectivity extraction algorithm constructs the connectivity graph where
+input polygon sets are modeled as graph nodes and assigned node ids and
+overlap/touching between input polygon sets is modeled as graph edges. One
+supported graph formats is std::vector<std::set<int> > where node ids index into
+the vector and the sets of integers at each index are the ids of nodes for which
+an edge exists in the graph. It is required that such vector pre-allocate
+sufficient elements to store the graph generated by the algorithm, because only
+the operator[] is used internally to access the graph The other
+supported graph format is std::map<std::set<int> > which is slightly easier to
+work with, but potentially more expensive. Improving the interface to
+support more generic graph concepts is deferred to future work.<p>The following
+is the declaration of the connectivity extraction algorithm.<p>
+<font face="Courier New">template <typename coordinate_type><br>
+class connectivity_extraction;</font><p>
+Example code connectivity_extraction_usage.cpp
+ demonstrates using the connectivity extraction algorithm to build a
+connectivity graph on geometry.<h2>Member Functions</h2>
+<table border="1" width="100%" id="table1">
+ <tr>
+ <td width="586"><b><font face="Courier New">connectivity_extraction</font></b><font face="Courier New">()</font></td>
+ <td>Default constructor. </td>
+ </tr>
+ <tr>
+ <td width="586"><b><font face="Courier New">connectivity_extraction</font></b><font face="Courier New">(<br> const
+ connectivity_extraction& that)</font></td>
+ <td>Copy construct.</td>
+ </tr>
+ <tr>
+ <td width="586">
+<font face="Courier New">unsigned int <br><b>insert</b>(const polygon_set_data<coordinate_type>& ps)</font></td>
+ <td>I<font face="Times New Roman">nsert a polygon set graph node, the
+ value returned is the id of the graph node.</font></td>
+ </tr>
+ <tr>
+ <td width="586">
+<font face="Courier New">
+template <class GeoObjT><br>
+unsigned int <b>insert</b>(const GeoObjT& geoObj)</font></td>
+ <td>Insert a geometry object that is a refinement of polygon set as a
+ graph node, the return value is the id of the graph node.</td>
+ </tr>
+ <tr>
+ <td width="586">
+<font face="Courier New">
+template <class GraphT><br>
+void <b>extract</b>(GraphT& graph)</font></td>
+ <td>Accepts a graph object that conforms to the expectations defined
+ above. Performs connectivity extraction and populates the graph
+ object.</td>
+ </tr>
+ </table>
+ <tr>
+<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ </td>
+<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+
+ </html>
\ No newline at end of file
Modified: sandbox/gtl/doc/gtl_connectivity_extraction_45.htm
==============================================================================
--- sandbox/gtl/doc/gtl_connectivity_extraction_45.htm (original)
+++ sandbox/gtl/doc/gtl_connectivity_extraction_45.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
Modified: sandbox/gtl/doc/gtl_connectivity_extraction_90.htm
==============================================================================
--- sandbox/gtl/doc/gtl_connectivity_extraction_90.htm (original)
+++ sandbox/gtl/doc/gtl_connectivity_extraction_90.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
Modified: sandbox/gtl/doc/gtl_coordinate_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_coordinate_concept.htm (original)
+++ sandbox/gtl/doc/gtl_coordinate_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
Modified: sandbox/gtl/doc/gtl_custom_point.htm
==============================================================================
--- sandbox/gtl/doc/gtl_custom_point.htm (original)
+++ sandbox/gtl/doc/gtl_custom_point.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -7,8 +7,11 @@
<body>
-<p><font face="Courier New">#include <boost/gtl/gtl.hpp><br>#include <cassert><br>
-<br>//lets make the body of main from point_usage.cpp<br>//a generic function parameterized by point type<br>template <typename Point><br>void test_point() {<br>
+<p><font face="Courier New">#include <boost/polygon/polygon.hpp><br>
+#include <cassert><br>
+namespace gtl = boost::polygon;<br>
+<br>
+//lets make the body of main from point_usage.cpp<br>//a generic function parameterized by point type<br>template <typename Point><br>void test_point() {<br>
//constructing a gtl point<br>
int x = 10;<br>
int y = 20;<br>
Modified: sandbox/gtl/doc/gtl_custom_polygon.htm
==============================================================================
--- sandbox/gtl/doc/gtl_custom_polygon.htm (original)
+++ sandbox/gtl/doc/gtl_custom_polygon.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -7,9 +7,10 @@
<body>
-<p><font face="Courier New">#include <boost/gtl/gtl.hpp><br>
+<p><font face="Courier New">#include <boost/polygon/polygon.hpp><br>
#include <cassert><br>
#include <list><br>
+namespace gtl = boost::polygon;<br>
<br>
//first lets turn our polygon usage code into a generic<br>
//function parameterized by polygon type<br>
Modified: sandbox/gtl/doc/gtl_custom_polygon_set.htm
==============================================================================
--- sandbox/gtl/doc/gtl_custom_polygon_set.htm (original)
+++ sandbox/gtl/doc/gtl_custom_polygon_set.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -7,11 +7,13 @@
<body>
-<p><font face="Courier New">#include <boost/gtl/gtl.hpp><br>
+<p><font face="Courier New">#include <boost/polygon/polygon.hpp><br>
+#include <list><br>
#include <time.h><br>
#include <cassert><br>
#include <deque><br>
#include <iostream><br>
+namespace gtl = boost::polygon;<br>
<br>
//once again we make our usage of the library generic<br>
//and parameterize it on the polygon set type<br>
Modified: sandbox/gtl/doc/gtl_design_overview.htm
==============================================================================
--- sandbox/gtl/doc/gtl_design_overview.htm (original)
+++ sandbox/gtl/doc/gtl_design_overview.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -132,7 +134,19 @@
registered as a polygon_concept and the read only traits but not the mutable
traits defined for that triangle type. This would allow the triangle type
to be passed into any API that expects a const reference to an object that models
-polygon. <tr>
+polygon.
+<p>An object that is a model of a given concept can usually be viewed as a model of any of its
+refinements if it is determined at runtime to conform to the restrictions of
+those concepts. This concept casting is accomplished through the
+<font face="Courier New">view_as<>()</font> function. For example if
+an object of conceptual type polygon 90 has four sides it must be a rectangle,
+and can be viewed as a rectangle with the following syntax:</p>
+<p><font face="Courier New">view_as<rectangle_concept>(polygon_90_object)</font></p>
+<p>The return value of <font face="Courier New">view_as<>()</font> can be
+passed into any interface that expects an object of the conceptual type
+specified in its template parameter. The exception to this ability to
+concept cast geometric objects is that polygon set objects cannot be viewed as
+individual polygons or rectangles.</p> <tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
</td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
Modified: sandbox/gtl/doc/gtl_interval_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_interval_concept.htm (original)
+++ sandbox/gtl/doc/gtl_interval_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
Modified: sandbox/gtl/doc/gtl_isotropy.htm
==============================================================================
--- sandbox/gtl/doc/gtl_isotropy.htm (original)
+++ sandbox/gtl/doc/gtl_isotropy.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -64,8 +66,7 @@
colors="#ffffff,#000000,#808080,#000000,#bbe0e3,#333399,#009999,#99cc00" />
<div class="O" style="TEXT-ALIGN: center; mso-line-spacing: '90 0 0'; mso-margin-left-alt: 216; mso-char-wrap: 1; mso-kinsoku-overflow: 1" v:shape="_x0000_s1026">
<p style="TEXT-ALIGN: left">
- <span style="COLOR: red; mso-bidi-font-family: Arial">Isotropy</span><span style="mso-bidi-font-family: Arial">
- "I-s&-'trO-pik, -'trä- Function: <i>adjective</i> Etymology: International
+ <span style="mso-bidi-font-family: Arial">Isotropy - Function: <i>adjective</i> Etymology: International
Scientific Vocabulary<br>
<b>:</b> exhibiting properties (as velocity of light transmission) with the
same values when measured along axes in all directions <an <i>isotropic</i>
Modified: sandbox/gtl/doc/gtl_point_3d_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_point_3d_concept.htm (original)
+++ sandbox/gtl/doc/gtl_point_3d_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
Modified: sandbox/gtl/doc/gtl_point_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_point_concept.htm (original)
+++ sandbox/gtl/doc/gtl_point_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
Modified: sandbox/gtl/doc/gtl_point_usage.htm
==============================================================================
--- sandbox/gtl/doc/gtl_point_usage.htm (original)
+++ sandbox/gtl/doc/gtl_point_usage.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -7,8 +7,9 @@
<body>
-<p><font face="Courier New">#include <boost/gtl/gtl.hpp><br>
+<p><font face="Courier New">#include <boost/polygon/polygon.hpp><br>
#include <cassert><br>
+namespace gtl = boost::polygon;<br>
<br>
int main() {<br>
//constructing a gtl point<br>
Modified: sandbox/gtl/doc/gtl_polygon_45_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_45_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_45_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -35,6 +35,7 @@
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -126,6 +127,16 @@
return t;<br>
}<br>
};</font></p>
+<p>An object that is a model of <font face="Courier New">
+polygon_45_concept</font> can be viewed as a model of any of its
+refinements if it is determined at runtime to conform to the restriction of
+those concepts. This concept casting is accomplished through the
+<font face="Courier New">view_as<>()</font> function.</p>
+<p><font face="Courier New">view_as<rectangle_concept>(polygon_45_object)</font><br>
+<font face="Courier New">view_as<polygon_90_concept>(polygon_45_object)</font></p>
+<p>The return value of <font face="Courier New">view_as<>()</font> can be
+passed into any interface that expects an object of the conceptual type
+specified in its template parameter.</p>
<h2>Functions</h2>
<table border="1" width="100%" id="table1">
<tr>
Modified: sandbox/gtl/doc/gtl_polygon_45_set_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_45_set_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_45_set_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -85,6 +87,17 @@
domains in which Manhattan and 45-degree geometry are a common special case.</font><p>Users are recommended to use std::vector and std::list of user defined polygons
or library provided polygon_45_set_data<coordinate_type> objects. Lists
and vectors of models of polygon_45_concept or polygon_45_with_holes_concept are automatically models of polygon_45_set_concept.</p>
+<p>An object that is a model of <font face="Courier New">
+polygon_45_set_concept</font> can be viewed as a model of <font face="Courier New">
+polygon_90_set_concept</font> if it is determined at runtime to conform to the
+restriction that all edges are axis-parallel. This concept casting is
+accomplished through the <font face="Courier New">view_as<>()</font> function.</p>
+<p><font face="Courier New">view_as<polygon_90_set_concept>(polygon_set_object)</font></p>
+<p>The return value of <font face="Courier New">view_as<>()</font> can be passed
+into any interface that expects an object of the conceptual type specified in
+its template parameter. Polygon sets cannot be viewed as single polygons
+or rectangles since it generally cannot be known whether a polygon set contains
+only a single polygon without converting to polygons.</p>
<h2>Operators</h2>
<p>The return type of some operators is the <font face="Courier New">polygon_45_set_view</font>
operator template type. This type is itself a model of the polygon 90 set
@@ -568,9 +581,8 @@
<tr>
<td width="586"><font face="Courier New">
polygon_45_set_data&<br>
-<b>resize</b>(T& polygon_set, coord_type resizing,<br>
-
- RoundingOption rounding = CLOSEST, <br> CornerOption
+<b>resize</b>(coord_type resizing,<br>
+ RoundingOption rounding = CLOSEST, <br> CornerOption
corner = INTERSECTION)</font></td>
<td>Same as bloat if resizing is positive, same as shrink if resizing is
negative. RoundingOption is an enum that controls snapping of
Modified: sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -103,6 +105,18 @@
return t;<br>
}<br>
};</font></p>
+<p>An object that is a model of <font face="Courier New">
+polygon_45_with_holes_concept</font> can be viewed as a model of any of its
+refinements if it is determined at runtime to conform to the restriction of
+those concepts. This concept casting is accomplished through the
+<font face="Courier New">view_as<>()</font> function.</p>
+<p><font face="Courier New">view_as<rectangle_concept>(polygon_45_with_holes_object)</font><br>
+<font face="Courier New">view_as<polygon_90_concept>(polygon_45_with_holes_object)</font><br>
+<font face="Courier New">view_as<polygon_90_with_holes_concept>(polygon_45_with_holes_object)</font><br>
+<font face="Courier New">view_as<polygon_45_concept>(polygon_45_with_holes_object)</font></p>
+<p>The return value of <font face="Courier New">view_as<>()</font> can be
+passed into any interface that expects an object of the conceptual type
+specified in its template parameter. </p>
<h2>Functions</h2>
<table border="1" width="100%" id="table1">
<tr>
Modified: sandbox/gtl/doc/gtl_polygon_90_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_90_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_90_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -113,6 +115,15 @@
return t;<br>
}</font><br>
<font face="Courier New">};</font></p>
+<p>An object that is a model of <font face="Courier New">
+polygon_90_concept</font> can be viewed as a model of any of its
+refinements if it is determined at runtime to conform to the restriction of
+those concepts. This concept casting is accomplished through the
+<font face="Courier New">view_as<>()</font> function.</p>
+<p><font face="Courier New">view_as<rectangle_concept>(polygon_90_object)</font></p>
+<p>The return value of <font face="Courier New">view_as<>()</font> can be
+passed into any interface that expects an object of the conceptual type
+specified in its template parameter.</p>
<h2>Functions</h2>
<table border="1" width="100%" id="table1">
<tr>
Modified: sandbox/gtl/doc/gtl_polygon_90_set_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_90_set_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_90_set_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
Modified: sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -103,6 +105,16 @@
return t;<br>
}<br>
};</font></p>
+<p>An object that is a model of <font face="Courier New">
+polygon_90_with_holes_concept</font> can be viewed as a model of any of its
+refinements if it is determined at runtime to conform to the restriction of
+those concepts. This concept casting is accomplished through the
+<font face="Courier New">view_as<>()</font> function.</p>
+<p><font face="Courier New">view_as<rectangle_concept>(polygon_90_with_holes_object)</font><br>
+<font face="Courier New">view_as<polygon_90_concept>(polygon_90_with_holes_object)</font></p>
+<p>The return value of <font face="Courier New">view_as<>()</font> can be
+passed into any interface that expects an object of the conceptual type
+specified in its template parameter.</p>
<h2>Functions</h2>
<table border="1" width="100%" id="table1">
<tr>
Modified: sandbox/gtl/doc/gtl_polygon_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -128,6 +130,17 @@
<p>Example code custom_polygon.cpp
demonstrates mapping a
user defined polygon class to the library polygon_concept</p>
+<p>An object that is a model of <font face="Courier New">
+polygon_concept</font> can be viewed as a model of any of its
+refinements if it is determined at runtime to conform to the restriction of
+those concepts. This concept casting is accomplished through the
+<font face="Courier New">view_as<>()</font> function.</p>
+<p><font face="Courier New">view_as<rectangle_concept>(polygon_object)</font><br>
+<font face="Courier New">view_as<polygon_90_concept>(polygon_object)</font><br>
+<font face="Courier New">view_as<polygon_45_concept>(polygon_object)</font></p>
+<p>The return value of <font face="Courier New">view_as<>()</font> can be
+passed into any interface that expects an object of the conceptual type
+specified in its template parameter. </p>
<h2>Functions</h2>
<table border="1" width="100%" id="table1">
<tr>
Modified: sandbox/gtl/doc/gtl_polygon_set_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_set_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_set_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -79,6 +81,19 @@
and vectors of models of polygon_concept or polygon_with_holes_concept are automatically models of polygon_set_concept.</p>
<p>Example code custom_polygon_set.cpp
demonstrates mapping a user defined class to the library polygon_set_concept</p>
+<p>An object that is a model of <font face="Courier New">
+polygon_set_concept</font> can be viewed as a model of <font face="Courier New">
+polygon_90_set_concept</font> or <font face="Courier New">
+polygon_45_set_concept</font> if it is determined at runtime to conform to the
+restrictions of those concepts. This concept casting is accomplished
+through the <font face="Courier New">view_as<>()</font> function.</p>
+<p><font face="Courier New">view_as<polygon_90_set_concept>(polygon_set_object)<br>
+view_as<polygon_45_set_concept>(polygon_set_object)</font></p>
+<p>The return value of <font face="Courier New">view_as<>()</font> can be passed
+into any interface that expects an object of the conceptual type specified in
+its template parameter. Polygon sets cannot be viewed as single polygons
+or rectangles since it generally cannot be known whether a polygon set contains
+only a single polygon without converting to polygons.</p>
<h2>Operators</h2>
<p>The return type of some operators is the <font face="Courier New">polygon_set_view</font>
operator template type. This type is itself a model of the polygon 90 set
@@ -173,6 +188,37 @@
<td>Same as operator-, but with self assignment, left operand must model
polygon_set and not one of it's refinements.</td>
</tr>
+ <tr>
+ <td width="586"><font face="Courier New">template <typename T1><br>
+ T1 <b>operator</b>+(const T1&, coordinate_type bloating)</font></td>
+ <td>Performs resize operation, inflating by bloating ammount. If
+ negative the result is a shrink instead of bloat. Note: returns
+ result by value.</td>
+ </tr>
+ <tr>
+ <td width="586"><font face="Courier New">template <typename T1, typename
+ T2><br>
+ T1 <b>operator</b>-(const T1&, coordinate_type shrinking)</font></td>
+ <td>Performs resize operation, deflating by bloating ammount. If
+ negative the result is a bloat instead of shrink. Note: returns
+ result by value.</td>
+ </tr>
+ <tr>
+ <td width="586"><font face="Courier New">template <typename T1, typename
+ T2><br>
+ T1& <b>operator</b>+=(const T1&, coordinate_type bloating)</font></td>
+ <td>Performs resize operation, inflating by bloating ammount. If
+ negative the result is a shrink instead of bloat. Returns
+ reference to modified argument.</td>
+ </tr>
+ <tr>
+ <td width="586"><font face="Courier New">template <typename T1, typename
+ T2><br>
+ T1& <b>operator</b>-=(const T1&, coordinate_type shrinking)</font></td>
+ <td>Performs resize operation, deflating by bloating ammount. If
+ negative the result is a bloat instead of shrink. Returns
+ reference to modified argument.</td>
+ </tr>
</table>
<h2>Functions</h2>
<table border="1" width="100%" id="table6">
@@ -195,6 +241,30 @@
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename
+ output_container_type, typename T><br>
+ void <b>get_trapezoids</b>(output_container_type& output, <br>
+
+ const T& polygon_set)</font></td>
+ <td>Output container is expected to be a standard container.
+ Slices geometry of an object that models polygon_set or one of its
+ refinements into non overlapping trapezoids along a vertical slicing
+ orientation and appends them to the
+ output, which must have a value type that models polygon or polygon_with_holes. </td>
+ </tr>
+ <tr>
+ <td width="586"><font face="Courier New">template <typename
+ output_container_type, typename T><br>
+ void <b>get_trapezoids</b>(output_container_type& output, <br>
+
+ const T& polygon_set,<br> orientation_2d orient)</font></td>
+ <td>Output container is expected to be a standard container.
+ Slices geometry of an object that models polygon_set or one of its
+ refinements into non overlapping trapezoids along a the specified slicing
+ orientation and appends them to the
+ output, which must have a value type that models polygon or polygon_with_holes. </td>
+ </tr>
+ <tr>
+ <td width="586"><font face="Courier New">template <typename
polygon_set_type><br>
void <b>clear</b>(polygon_set_type& polygon_set)</font></td>
<td>Makes the object empty of geometry.</td>
@@ -225,6 +295,32 @@
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
+ T& <b>bloat</b>(T& polygon_set, unsigned_area_type bloating)</font></td>
+ <td>Same as getting all the polygons, bloating them and putting them
+ back.</td>
+ </tr>
+ <tr>
+ <td width="586"><font face="Courier New">template <typename T><br>
+ T& <b>shrink</b>(T& polygon_set, unsigned_area_type shrinking)</font></td>
+ <td>Same as getting all the polygons, shrinking them and overwriting
+ the polygon set with the resulting regions.</td>
+ </tr>
+ <tr>
+ <td width="586"><font face="Courier New">template <typename T, typename
+ coord_type><br>
+ T& <b>resize</b>(T& polygon_set, coord_type resizing,<br>
+
+ bool corner_fill_arc = false, <br>
+ unsigned int num_circle_segments = 0)</font></td>
+ <td>Same as bloat if resizing is positive, same as shrink if resizing is
+ negative. Original topology at acute angle vertices is preserved
+ by default, segmented circular arcs are inserted if corner_fill_arc is
+ true. num_circle_segments specifies number of segments to
+ introduce on a full circle when filling acute angle corners with
+ circular arcs.</td>
+ </tr>
+ <tr>
+ <td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_up</b>(T& polygon_set, unsigned_area_type factor)</font></td>
<td>Scales geometry up by unsigned factor..</td>
</tr>
@@ -358,6 +454,25 @@
boundary introduced by this fracture will be truncated downward.</td>
</tr>
<tr>
+ <td width="586"><font face="Courier New">
+template <typename output_container><br>
+void <b>get_trapezoids</b>(output_container& output) const</font></td>
+ <td>Expects a standard container of polygon objects. Will scan
+ and eliminate overlaps. Slices polygon set geometry to trapezoids
+ vertically and appends them to the container.</td>
+ </tr>
+ <tr>
+ <td width="586">
+<font face="Courier New">
+template <typename output_container><br>
+void <b>get_trapezoids</b>(output_container& output, <br> orientation_2d
+slicing_orientation) const </font>
+ </td>
+ <td>Expects a standard container of polygon objects. Will scan
+ and eliminate overlaps. Slices polygon set geometry to trapezoids
+ along the given orientation and appends them to the container.</td>
+ </tr>
+ <tr>
<td width="586">
<font face="Courier New">
bool <b>operator==</b>(const polygon_set_data& p) const</font></td>
@@ -406,6 +521,20 @@
</tr>
<tr>
<td width="586"><font face="Courier New">
+polygon_set_data&<br>
+<b>resize</b>(coord_type resizing,<br>
+ bool corner_fill_arc = false, <br>
+ unsigned int num_circle_segments = 0)</font></td>
+ <td>Inflates if resizing is positive, deflates if resizing is
+ negative. Original topology at acute angle vertices is preserved
+ by default, segmented circular arcs are inserted if corner_fill_arc is
+ true. num_circle_segments specifies number of segments to
+ introduce on a full circle when filling acute angle corners with
+ circular arcs. Specifying zero for num_circle_segments results in
+ only a single segment being inserted at acute corners.</td>
+ </tr>
+ <tr>
+ <td width="586"><font face="Courier New">
template <typename transformation_type><br>
polygon_set_data& <br><b>transform</b>(const transformation_type& transformation) </font>
</td>
Modified: sandbox/gtl/doc/gtl_polygon_set_usage.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_set_usage.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_set_usage.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -7,8 +7,11 @@
<body>
-<p><font face="Courier New">#include <boost/gtl/gtl.hpp><br>#include <cassert><br>
-<br>int main() {<br>
+<p><font face="Courier New">#include <boost/polygon/polygon.hpp><br>
+#include <cassert><br>
+namespace gtl = boost::polygon;<br>
+<br>
+int main() {<br>
//lets declare ourselves a polygon set<br>
using namespace gtl; //because of operators<br>
typedef std::vector<polygon_data<int> > PolygonSet;<br>
Modified: sandbox/gtl/doc/gtl_polygon_usage.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_usage.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_usage.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -7,8 +7,9 @@
<body>
-<p><font face="Courier New">#include <boost/gtl/gtl.hpp><br>
+<p><font face="Courier New">#include <boost/polygon/polygon.hpp><br>
#include <cassert><br>
+namespace gtl = boost::polygon;<br>
<br>
int main() {<br>
//lets construct a 10x10 rectangle shaped polygon<br>
Modified: sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -104,6 +106,20 @@
return t;<br>
}<br>
};</font></p>
+<p>An object that is a model of <font face="Courier New">
+polygon_with_holes_concept</font> can be viewed as a model of any of its
+refinements if it is determined at runtime to conform to the restriction of
+those concepts. This concept casting is accomplished through the
+<font face="Courier New">view_as<>()</font> function.</p>
+<p><font face="Courier New">view_as<rectangle_concept>(polygon_with_holes_object)</font><br>
+<font face="Courier New">view_as<polygon_90_concept>(polygon_with_holes_object)</font><br>
+<font face="Courier New">view_as<polygon_90_with_holes_concept>(polygon_with_holes_object)</font><br>
+<font face="Courier New">view_as<polygon_45_concept>(polygon_with_holes_object)</font><br>
+<font face="Courier New">view_as<polygon_45_with_holes_concept>(polygon_with_holes_object)</font><br>
+<font face="Courier New">view_as<polygon_concept>(polygon_with_holes_object)</font></p>
+<p>The return value of <font face="Courier New">view_as<>()</font> can be
+passed into any interface that expects an object of the conceptual type
+specified in its template parameter. </p>
<h2>Functions</h2>
<table border="1" width="100%" id="table1">
<tr>
Modified: sandbox/gtl/doc/gtl_property_merge.htm
==============================================================================
--- sandbox/gtl/doc/gtl_property_merge.htm (original)
+++ sandbox/gtl/doc/gtl_property_merge.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -65,14 +67,14 @@
class property_merge;</font><p>The property algorithm computes the n-layer
map overlay of input polygon sets. Each input geometry is inserted along
with a property value. The property type can be anything suitable for use
-as an element of a std::set. Multiple geometry objects can be seperately
+as an element of a std::set. Multiple geometry objects can be separately
inserted with the same property value. To store the result of this
operation a fairly complex container is required. Resulting geometries are
associated with unique subsets of property values of the input geometry.
Two suitable containers for storing the result of a property merge operation
-are:<p>std::map<std::set<property_type>, polygon_set_data<coordiante_type>
+are:<p><font face="Courier New">std::map<std::set<property_type>, polygon_set_data<coordiante_type>
><br>
-std::map<std::vector<property_type>, polygon_set_data<coordiante_type> ><p>
+std::map<std::vector<property_type>, polygon_set_data<coordiante_type> ></font><p>
Example code property_merge_usage.cpp
demonstrates using the n-layer map-overlay algorithm on polygon data.<h2>Member Functions</h2>
<table border="1" width="100%" id="table1">
Added: sandbox/gtl/doc/gtl_property_merge_45.htm
==============================================================================
--- (empty file)
+++ sandbox/gtl/doc/gtl_property_merge_45.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -0,0 +1,124 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en" xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:(null)1="http://www.w3.org/TR/REC-html40"><head><!--
+ Copyright 2009-2010 Intel Corporation
+ license banner
+-->
+<title>Boost Polygon Library: Property Merge 90</title>
+ <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1">
+ <!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> -->
+<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0"><tbody><tr>
+<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <div style="padding: 5px;" align="center">
+ <img border="0" src="images/boost.png" width="277" height="86"><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;">
+ </a>
+ </div>
+ <div style="margin: 5px;">
+ <h3 class="navbar">Contents</h3>
+ <ul>
+ <li>Polygon Library Main Page</li>
+ <li><a href="gtl_design_overview.htm">Polygon
+ Library Design Overview</a></li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li>Polygon 90 With Holes Concept</li>
+ <li>Polygon 45 Concept</li>
+ <li>Polygon 45 With Holes Concept</li>
+ <li>Polygon Concept</li>
+ <li>Polygon With Holes Concept</li>
+ <li>Polygon 90 Set Concept</li>
+ <li>Polygon 45 Set Concept</li>
+ <li>Polygon Set Concept</li>
+ <li>Connectivity Extraction 90</li>
+ <li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
+ <li>Property Merge_90</li>
+ <li>Property Merge 45</li>
+ <li>Property Merge</li>
+ </ul>
+ <p> </p>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+ Presentation</a></li>
+ </ul>
+ </div>
+ <h3 class="navbar">Polygon Sponsor</h3>
+ <div style="padding: 5px;" align="center">
+ <img border="0" src="images/intlogo.gif" width="127" height="51"><a title="www.adobe.com home page" href="http://www.adobe.com/" tabindex="2" style="border: medium none ;">
+ </a>
+ </div>
+</td>
+<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+
+<!-- End Header -->
+
+<br>
+<p>
+</p><h1>Property Merge 45</h1>
+
+<p>
+<p>The following is the declaration of the property merge algorithm.<p>
+<font face="Courier New">template <typename coordinate_type, typename
+property_type><br>
+class property_merge_45;</font><p>The property algorithm computes the n-layer
+map overlay of input polygon sets. Each input geometry is inserted along
+with a property value. The property type can be anything suitable for use
+as an element of a std::set. Multiple geometry objects can be separately
+inserted with the same property value. To store the result of this
+operation a fairly complex container is required. Resulting geometries are
+associated with unique subsets of property values of the input geometry.
+Two suitable containers for storing the result of a property merge operation
+are:<p><font face="Courier New">std::map<std::set<property_type>, polygon_set_data<coordiante_type>
+><br>
+std::map<std::vector<property_type>, polygon_set_data<coordiante_type> ></font><p>
+Example code property_merge_usage.cpp
+ demonstrates using the n-layer map-overlay algorithm on polygon 90 data.<h2>Member Functions</h2>
+<table border="1" width="100%" id="table1">
+ <tr>
+ <td width="586"><b><font face="Courier New">property_merge_45</font></b><font face="Courier New">()</font></td>
+ <td>Default constructor. </td>
+ </tr>
+ <tr>
+ <td width="586"><b><font face="Courier New">property_merge_45</font></b><font face="Courier New">(const
+ property_merge_90& that)</font></td>
+ <td>Copy construct.</td>
+ </tr>
+ <tr>
+ <td width="586">
+<font face="Courier New">void <br><b>insert</b>(const polygon_45_set_data<coordinate_type>& ps,<br>
+
+const property_type& property)</font></td>
+ <td>I<font face="Times New Roman">nsert a polygon set with an associated
+ property.</font></td>
+ </tr>
+ <tr>
+ <td width="586">
+<font face="Courier New">
+template <class GeoObjT><br>
+void <b>insert</b>(const GeoObjT& geoObj,<br>
+
+const property_type& property)</font></td>
+ <td>Insert a geometry object that is a refinement of polygon 45 set with
+ an associated property.</td>
+ </tr>
+ <tr>
+ <td width="586">
+<font face="Courier New">
+template <typename result_type><br>
+void <b>merge</b>(result_tyep& result)</font></td>
+ <td>Accepts a container object that conforms to the expectations defined
+ above. Performs property merge and populates the container
+ object.</td>
+ </tr>
+ </table>
+ <tr>
+<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ </td>
+<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+
+ </html>
\ No newline at end of file
Modified: sandbox/gtl/doc/gtl_property_merge_90.htm
==============================================================================
--- sandbox/gtl/doc/gtl_property_merge_90.htm (original)
+++ sandbox/gtl/doc/gtl_property_merge_90.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -65,14 +67,14 @@
class property_merge_90;</font><p>The property algorithm computes the n-layer
map overlay of input polygon sets. Each input geometry is inserted along
with a property value. The property type can be anything suitable for use
-as an element of a std::set. Multiple geometry objects can be seperately
+as an element of a std::set. Multiple geometry objects can be separately
inserted with the same property value. To store the result of this
operation a fairly complex container is required. Resulting geometries are
associated with unique subsets of property values of the input geometry.
Two suitable containers for storing the result of a property merge operation
-are:<p> std::map<std::set<property_type>, polygon_90_set_data<coordiante_type>
+are:<p><font face="Courier New">std::map<std::set<property_type>, polygon_90_set_data<coordiante_type>
><br>
-std::map<std::vector<property_type>, polygon_90_set_data<coordiante_type> ><p>
+std::map<std::vector<property_type>, polygon_90_set_data<coordiante_type> ></font><p>
Example code property_merge_usage.cpp
demonstrates using the n-layer map-overlay algorithm on polygon 90 data.<h2>Member Functions</h2>
<table border="1" width="100%" id="table1">
Modified: sandbox/gtl/doc/gtl_property_merge_usage.htm
==============================================================================
--- sandbox/gtl/doc/gtl_property_merge_usage.htm (original)
+++ sandbox/gtl/doc/gtl_property_merge_usage.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -7,8 +7,9 @@
<body>
-<p><font face="Courier New">#include <boost/gtl/gtl.hpp><br>
+<p><font face="Courier New">#include <boost/polygon/polygon.hpp><br>
#include <cassert><br>
+namespace gtl = boost::polygon;<br>
<br>
//just a little meta-programming to get things off on the right foot<br>
template <typename T><br>
Modified: sandbox/gtl/doc/gtl_rectangle_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_rectangle_concept.htm (original)
+++ sandbox/gtl/doc/gtl_rectangle_concept.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -34,7 +34,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
Modified: sandbox/gtl/doc/index.htm
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2009-07-14 14:22:40 EDT (Tue, 14 Jul 2009)
@@ -35,7 +35,9 @@
<li>Polygon Set Concept</li>
<li>Connectivity Extraction 90</li>
<li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
<li>Property Merge 90</li>
+ <li>Property Merge_45</li>
<li>Property Merge</li>
</ul>
<h3 class="navbar">Other Resources</h3>
@@ -57,9 +59,7 @@
<br>
<p>
-</p><h1>Polygon Library Documentation</h1>
-
-<p>
+</p><h1>THE BOOST POLYGON LIBRARY</h1>
<p>The boost polygon library provides algorithms focused on manipulating planar
polygon geometry data. Specific algorithms provided are the polygon set
operations (intersection, union, difference, disjoint-union) and related
@@ -108,7 +108,7 @@
<nobr>
<span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New">
<span style="mso-spacerun:yes"> </span>
- using namespace gtl; </span></nobr></div>
+ using namespace boost::polygon; </span></nobr></div>
<div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1">
<nobr>
<span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New">
@@ -173,6 +173,27 @@
</ul>
+<table class="docinfo" rules="none" frame="void" id="table1">
+ <colgroup>
+ <col class="docinfo-name"><col class="docinfo-content">
+ </colgroup>
+ <tbody vAlign="top">
+ <tr>
+ <th class="docinfo-name">Copyright:</th>
+ <td>Copyright © Intel Corporation 2008-2009.</td>
+ </tr>
+ <tr class="field">
+ <th class="docinfo-name">License:</th>
+ <td class="field-body">Distributed under the Boost Software License,
+ Version 1.0. (See accompanying file <tt class="literal">
+ <span class="pre">LICENSE_1_0.txt</span></tt> or copy at
+ <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
+ http://www.boost.org/LICENSE_1_0.txt>)</td>
+ </tr>
+</table>
+<p>
+
+
</body><tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
</td>