polygon/detail/max_cover.hpp

0001 /*
0002   Copyright 2008 Intel Corporation
0003
0004   Use, modification and distribution are subject to the Boost Software License,
0005   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006   http://www.boost.org/LICENSE_1_0.txt).
0007 */
0008 #ifndef BOOST_POLYGON_MAX_COVER_HPP
0009 #define BOOST_POLYGON_MAX_COVER_HPP
0010 namespace boost { namespace polygon{
0011
0012   template <typename Unit>
0013   struct MaxCover {
0014     typedef interval_data<Unit> Interval;
0015     typedef rectangle_data<Unit> Rectangle;
0016
0017     class Node {
0018     private:
0019       std::vector<Node*> children_;
0020       std::set<Interval> tracedPaths_;
0021     public:
0022       Rectangle rect;
0023       Node() : children_(), tracedPaths_(), rect() {}
0024       Node(const Rectangle rectIn) : children_(), tracedPaths_(), rect(rectIn) {}
0025       typedef typename std::vector<Node*>::iterator iterator;
0026       inline iterator begin() { return children_.begin(); }
0027       inline iterator end() { return children_.end(); }
0028       inline void add(Node* child) { children_.push_back(child); }
0029       inline bool tracedPath(const Interval& ivl) const {
0030         return tracedPaths_.find(ivl) != tracedPaths_.end();
0031       }
0032       inline void addPath(const Interval& ivl) {
0033         tracedPaths_.insert(tracedPaths_.end(), ivl);
0034       }
0035     };
0036
0037     typedef std::pair<std::pair<Unit, Interval>, Node* > EdgeAssociation;
0038
0039     class lessEdgeAssociation {
0040     public:
0041       typedef const EdgeAssociation& first_argument_type;
0042       typedef const EdgeAssociation& second_argument_type;
0043       typedef bool result_type;
0044       inline lessEdgeAssociation() {}
0045       inline bool operator () (const EdgeAssociation& elem1, const EdgeAssociation& elem2) const {
0046         if(elem1.first.first < elem2.first.first) return true;
0047         if(elem1.first.first > elem2.first.first) return false;
0048         return elem1.first.second < elem2.first.second;
0049       }
0050     };
0051
0052     template <class cT>
0053     static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient) {
0054       Interval rectIvl = node->rect.get(orient);
0055       if(node->tracedPath(rectIvl)) {
0056         return;
0057       }
0058       node->addPath(rectIvl);
0059       if(node->begin() == node->end()) {
0060         //std::cout << "WRITE OUT 3: " << node->rect << std::endl;
0061         outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(node->rect));
0062         return;
0063       }
0064       bool writeOut = true;
0065       for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
0066         getMaxCover(outputContainer, *itr, orient, node->rect); //get rectangles down path
0067         Interval nodeIvl = (*itr)->rect.get(orient);
0068         if(contains(nodeIvl, rectIvl, true)) writeOut = false;
0069       }
0070       if(writeOut) {
0071         //std::cout << "WRITE OUT 2: " << node->rect << std::endl;
0072         outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(node->rect));
0073       }
0074     }
0075
0076     struct stack_element {
0077       inline stack_element() :
0078         node(), rect(), itr() {}
0079       inline stack_element(Node* n,
0080                            const Rectangle& r,
0081                            typename Node::iterator i) :
0082         node(n), rect(r), itr(i) {}
0083       Node* node;
0084       Rectangle rect;
0085       typename Node::iterator itr;
0086     };
0087
0088     template <class cT>
0089     static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient,
0090                                    Rectangle rect) {
0091       //std::cout << "New Root\n";
0092       std::vector<stack_element> stack;
0093       typename Node::iterator itr = node->begin();
0094       do {
0095         //std::cout << "LOOP\n";
0096         //std::cout << node->rect << std::endl;
0097         Interval rectIvl = rect.get(orient);
0098         Interval nodeIvl = node->rect.get(orient);
0099         bool iresult = intersect(rectIvl, nodeIvl, false);
0100         bool tresult = !node->tracedPath(rectIvl);
0101         //std::cout << (itr != node->end()) << " " << iresult << " " << tresult << std::endl;
0102         Rectangle nextRect1 = Rectangle(rectIvl, rectIvl);
0103         Unit low = rect.get(orient.get_perpendicular()).low();
0104         Unit high = node->rect.get(orient.get_perpendicular()).high();
0105         nextRect1.set(orient.get_perpendicular(), Interval(low, high));
0106         if(iresult && tresult) {
0107           node->addPath(rectIvl);
0108           bool writeOut = true;
0109           //check further visibility beyond this node
0110           for(typename Node::iterator itr2 = node->begin(); itr2 != node->end(); ++itr2) {
0111             Interval nodeIvl3 = (*itr2)->rect.get(orient);
0112             //if a child of this node can contain the interval then we can extend through
0113             if(contains(nodeIvl3, rectIvl, true)) writeOut = false;
0114             //std::cout << "child " << (*itr2)->rect << std::endl;
0115           }
0116           Rectangle nextRect2 = Rectangle(rectIvl, rectIvl);
0117           Unit low2 = rect.get(orient.get_perpendicular()).low();
0118           Unit high2 = node->rect.get(orient.get_perpendicular()).high();
0119           nextRect2.set(orient.get_perpendicular(), Interval(low2, high2));
0120           if(writeOut) {
0121             //std::cout << "write out " << nextRect << std::endl;
0122             outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect2));
0123           } else {
0124             //std::cout << "suppress " << nextRect << std::endl;
0125           }
0126         }
0127         if(itr != node->end() && iresult && tresult) {
0128           //std::cout << "recurse into child\n";
0129           stack.push_back(stack_element(node, rect, itr));
0130           rect = nextRect1;
0131           node = *itr;
0132           itr = node->begin();
0133         } else {
0134           if(!stack.empty()) {
0135             //std::cout << "recurse out of child\n";
0136             node = stack.back().node;
0137             rect = stack.back().rect;
0138             itr = stack.back().itr;
0139             stack.pop_back();
0140           } else {
0141             //std::cout << "empty stack\n";
0142             //if there were no children of the root node
0143 //             Rectangle nextRect = Rectangle(rectIvl, rectIvl);
0144 //             Unit low = rect.get(orient.get_perpendicular()).low();
0145 //             Unit high = node->rect.get(orient.get_perpendicular()).high();
0146 //             nextRect.set(orient.get_perpendicular(), Interval(low, high));
0147 //             outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect));
0148           }
0149           //std::cout << "increment " << (itr != node->end()) << std::endl;
0150           if(itr != node->end()) {
0151             ++itr;
0152             if(itr != node->end()) {
0153               //std::cout << "recurse into next child.\n";
0154               stack.push_back(stack_element(node, rect, itr));
0155               Interval rectIvl2 = rect.get(orient);
0156               Interval nodeIvl2 = node->rect.get(orient);
0157               /*bool iresult =*/ intersect(rectIvl2, nodeIvl2, false);
0158               Rectangle nextRect2 = Rectangle(rectIvl2, rectIvl2);
0159               Unit low2 = rect.get(orient.get_perpendicular()).low();
0160               Unit high2 = node->rect.get(orient.get_perpendicular()).high();
0161               nextRect2.set(orient.get_perpendicular(), Interval(low2, high2));
0162               rect = nextRect2;
0163               //std::cout << "rect for next child" << rect << std::endl;
0164               node = *itr;
0165               itr = node->begin();
0166             }
0167           }
0168         }
0169       } while(!stack.empty() || itr != node->end());
0170     }
0171
0172     /*  Function recursive version of getMaxCover
0173         Because the code is so much simpler than the loop algorithm I retain it for clarity
0174
0175     template <class cT>
0176     static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient,
0177                                    const Rectangle& rect) {
0178       Interval rectIvl = rect.get(orient);
0179       Interval nodeIvl = node->rect.get(orient);
0180       if(!intersect(rectIvl, nodeIvl, false)) {
0181         return;
0182       }
0183       if(node->tracedPath(rectIvl)) {
0184         return;
0185       }
0186       node->addPath(rectIvl);
0187       Rectangle nextRect(rectIvl, rectIvl);
0188       Unit low = rect.get(orient.get_perpendicular()).low();
0189       Unit high = node->rect.get(orient.get_perpendicular()).high();
0190       nextRect.set(orient.get_perpendicular(), Interval(low, high));
0191       bool writeOut = true;
0192       rectIvl = nextRect.get(orient);
0193       for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
0194         nodeIvl = (*itr)->rect.get(orient);
0195         if(contains(nodeIvl, rectIvl, true)) writeOut = false;
0196       }
0197       if(writeOut) {
0198         outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect));
0199       }
0200       for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
0201         getMaxCover(outputContainer, *itr, orient, nextRect);
0202       }
0203     }
0204     */
0205
0206     //iterator range is assummed to be in topological order meaning all node's trailing
0207     //edges are in sorted order
0208     template <class iT>
0209     static inline void computeDag(iT beginNode, iT endNode, orientation_2d orient,
0210                                   std::size_t size) {
0211       std::vector<EdgeAssociation> leadingEdges;
0212       leadingEdges.reserve(size);
0213       for(iT iter = beginNode; iter != endNode; ++iter) {
0214         Node* nodep = &(*iter);
0215         Unit leading = nodep->rect.get(orient.get_perpendicular()).low();
0216         Interval rectIvl = nodep->rect.get(orient);
0217         leadingEdges.push_back(EdgeAssociation(std::pair<Unit, Interval>(leading, rectIvl), nodep));
0218       }
0219       polygon_sort(leadingEdges.begin(), leadingEdges.end(), lessEdgeAssociation());
0220       typename std::vector<EdgeAssociation>::iterator leadingBegin = leadingEdges.begin();
0221       iT trailingBegin = beginNode;
0222       while(leadingBegin != leadingEdges.end()) {
0223         EdgeAssociation& leadingSegment = (*leadingBegin);
0224         Unit trailing = (*trailingBegin).rect.get(orient.get_perpendicular()).high();
0225         Interval ivl = (*trailingBegin).rect.get(orient);
0226         std::pair<Unit, Interval> trailingSegment(trailing, ivl);
0227         if(leadingSegment.first.first < trailingSegment.first) {
0228           ++leadingBegin;
0229           continue;
0230         }
0231         if(leadingSegment.first.first > trailingSegment.first) {
0232           ++trailingBegin;
0233           continue;
0234         }
0235         if(leadingSegment.first.second.high() <= trailingSegment.second.low()) {
0236           ++leadingBegin;
0237           continue;
0238         }
0239         if(trailingSegment.second.high() <= leadingSegment.first.second.low()) {
0240           ++trailingBegin;
0241           continue;
0242         }
0243         //leading segment intersects trailing segment
0244         (*trailingBegin).add((*leadingBegin).second);
0245         if(leadingSegment.first.second.high() > trailingSegment.second.high()) {
0246           ++trailingBegin;
0247           continue;
0248         }
0249         if(trailingSegment.second.high() > leadingSegment.first.second.high()) {
0250           ++leadingBegin;
0251           continue;
0252         }
0253         ++leadingBegin;
0254         ++trailingBegin;
0255       }
0256     }
0257
0258     template <class cT>
0259     static inline void getMaxCover(cT& outputContainer,
0260                                    const std::vector<Rectangle>& rects, orientation_2d orient) {
0261       if(rects.empty()) return;
0262       std::vector<Node> nodes;
0263       {
0264         if(rects.size() == 1) {
0265           outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(rects[0]));
0266           return;
0267         }
0268         nodes.reserve(rects.size());
0269         for(std::size_t i = 0; i < rects.size(); ++i) { nodes.push_back(Node(rects[i])); }
0270       }
0271       computeDag(nodes.begin(), nodes.end(), orient, nodes.size());
0272       for(std::size_t i = 0; i < nodes.size(); ++i) {
0273         getMaxCover(outputContainer, &(nodes[i]), orient);
0274       }
0275     }
0276
0277   };
0278 }
0279 }
0280
0281 #endif