Chris@16: /*
Chris@16:   Copyright 2008 Intel Corporation
Chris@16: 
Chris@16:   Use, modification and distribution are subject to the Boost Software License,
Chris@16:   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:   http://www.boost.org/LICENSE_1_0.txt).
Chris@16: */
Chris@16: #ifndef BOOST_POLYGON_MAX_COVER_HPP
Chris@16: #define BOOST_POLYGON_MAX_COVER_HPP
Chris@16: namespace boost { namespace polygon{
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   struct MaxCover {
Chris@16:     typedef interval_data<Unit> Interval;
Chris@16:     typedef rectangle_data<Unit> Rectangle;
Chris@16: 
Chris@16:     class Node {
Chris@16:     private:
Chris@16:       std::vector<Node*> children_;
Chris@16:       std::set<Interval> tracedPaths_;
Chris@16:     public:
Chris@16:       Rectangle rect;
Chris@16:       Node() : children_(), tracedPaths_(), rect() {}
Chris@16:       Node(const Rectangle rectIn) : children_(), tracedPaths_(), rect(rectIn) {}
Chris@16:       typedef typename std::vector<Node*>::iterator iterator;
Chris@16:       inline iterator begin() { return children_.begin(); }
Chris@16:       inline iterator end() { return children_.end(); }
Chris@16:       inline void add(Node* child) { children_.push_back(child); }
Chris@16:       inline bool tracedPath(const Interval& ivl) const {
Chris@16:         return tracedPaths_.find(ivl) != tracedPaths_.end();
Chris@16:       }
Chris@16:       inline void addPath(const Interval& ivl) {
Chris@16:         tracedPaths_.insert(tracedPaths_.end(), ivl);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     typedef std::pair<std::pair<Unit, Interval>, Node* > EdgeAssociation;
Chris@16: 
Chris@16:     class lessEdgeAssociation : public std::binary_function<const EdgeAssociation&, const EdgeAssociation&, bool> {
Chris@16:     public:
Chris@16:       inline lessEdgeAssociation() {}
Chris@16:       inline bool operator () (const EdgeAssociation& elem1, const EdgeAssociation& elem2) const {
Chris@16:         if(elem1.first.first < elem2.first.first) return true;
Chris@16:         if(elem1.first.first > elem2.first.first) return false;
Chris@16:         return elem1.first.second < elem2.first.second;
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <class cT>
Chris@16:     static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient) {
Chris@16:       Interval rectIvl = node->rect.get(orient);
Chris@16:       if(node->tracedPath(rectIvl)) {
Chris@16:         return;
Chris@16:       }
Chris@16:       node->addPath(rectIvl);
Chris@16:       if(node->begin() == node->end()) {
Chris@16:         //std::cout << "WRITE OUT 3: " << node->rect << std::endl;
Chris@16:         outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(node->rect));
Chris@16:         return;
Chris@16:       }
Chris@16:       bool writeOut = true;
Chris@16:       for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
Chris@16:         getMaxCover(outputContainer, *itr, orient, node->rect); //get rectangles down path
Chris@16:         Interval nodeIvl = (*itr)->rect.get(orient);
Chris@16:         if(contains(nodeIvl, rectIvl, true)) writeOut = false;
Chris@16:       }
Chris@16:       if(writeOut) {
Chris@16:         //std::cout << "WRITE OUT 2: " << node->rect << std::endl;
Chris@16:         outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(node->rect));
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     struct stack_element {
Chris@16:       inline stack_element() :
Chris@16:         node(), rect(), itr() {}
Chris@16:       inline stack_element(Node* n,
Chris@16:                            const Rectangle& r,
Chris@16:                            typename Node::iterator i) :
Chris@16:         node(n), rect(r), itr(i) {}
Chris@16:       Node* node;
Chris@16:       Rectangle rect;
Chris@16:       typename Node::iterator itr;
Chris@16:     };
Chris@16: 
Chris@16:     template <class cT>
Chris@16:     static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient,
Chris@16:                                    Rectangle rect) {
Chris@16:       //std::cout << "New Root\n";
Chris@16:       std::vector<stack_element> stack;
Chris@16:       typename Node::iterator itr = node->begin();
Chris@16:       do {
Chris@16:         //std::cout << "LOOP\n";
Chris@16:         //std::cout << node->rect << std::endl;
Chris@16:         Interval rectIvl = rect.get(orient);
Chris@16:         Interval nodeIvl = node->rect.get(orient);
Chris@16:         bool iresult = intersect(rectIvl, nodeIvl, false);
Chris@16:         bool tresult = !node->tracedPath(rectIvl);
Chris@16:         //std::cout << (itr != node->end()) << " " << iresult << " " << tresult << std::endl;
Chris@16:         Rectangle nextRect1 = Rectangle(rectIvl, rectIvl);
Chris@16:         Unit low = rect.get(orient.get_perpendicular()).low();
Chris@16:         Unit high = node->rect.get(orient.get_perpendicular()).high();
Chris@16:         nextRect1.set(orient.get_perpendicular(), Interval(low, high));
Chris@16:         if(iresult && tresult) {
Chris@16:           node->addPath(rectIvl);
Chris@16:           bool writeOut = true;
Chris@16:           //check further visibility beyond this node
Chris@16:           for(typename Node::iterator itr2 = node->begin(); itr2 != node->end(); ++itr2) {
Chris@16:             Interval nodeIvl3 = (*itr2)->rect.get(orient);
Chris@16:             //if a child of this node can contain the interval then we can extend through
Chris@16:             if(contains(nodeIvl3, rectIvl, true)) writeOut = false;
Chris@16:             //std::cout << "child " << (*itr2)->rect << std::endl;
Chris@16:           }
Chris@16:           Rectangle nextRect2 = Rectangle(rectIvl, rectIvl);
Chris@16:           Unit low2 = rect.get(orient.get_perpendicular()).low();
Chris@16:           Unit high2 = node->rect.get(orient.get_perpendicular()).high();
Chris@16:           nextRect2.set(orient.get_perpendicular(), Interval(low2, high2));
Chris@16:           if(writeOut) {
Chris@16:             //std::cout << "write out " << nextRect << std::endl;
Chris@16:             outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect2));
Chris@16:           } else {
Chris@101:             //std::cout << "suppress " << nextRect << std::endl;
Chris@16:           }
Chris@16:         }
Chris@16:         if(itr != node->end() && iresult && tresult) {
Chris@16:           //std::cout << "recurse into child\n";
Chris@16:           stack.push_back(stack_element(node, rect, itr));
Chris@16:           rect = nextRect1;
Chris@16:           node = *itr;
Chris@16:           itr = node->begin();
Chris@16:         } else {
Chris@16:           if(!stack.empty()) {
Chris@16:             //std::cout << "recurse out of child\n";
Chris@16:             node = stack.back().node;
Chris@16:             rect = stack.back().rect;
Chris@16:             itr = stack.back().itr;
Chris@16:             stack.pop_back();
Chris@16:           } else {
Chris@16:             //std::cout << "empty stack\n";
Chris@16:             //if there were no children of the root node
Chris@16: //             Rectangle nextRect = Rectangle(rectIvl, rectIvl);
Chris@16: //             Unit low = rect.get(orient.get_perpendicular()).low();
Chris@16: //             Unit high = node->rect.get(orient.get_perpendicular()).high();
Chris@16: //             nextRect.set(orient.get_perpendicular(), Interval(low, high));
Chris@16: //             outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect));
Chris@16:           }
Chris@16:           //std::cout << "increment " << (itr != node->end()) << std::endl;
Chris@16:           if(itr != node->end()) {
Chris@16:             ++itr;
Chris@16:             if(itr != node->end()) {
Chris@16:               //std::cout << "recurse into next child.\n";
Chris@16:               stack.push_back(stack_element(node, rect, itr));
Chris@16:               Interval rectIvl2 = rect.get(orient);
Chris@16:               Interval nodeIvl2 = node->rect.get(orient);
Chris@16:               /*bool iresult =*/ intersect(rectIvl2, nodeIvl2, false);
Chris@16:               Rectangle nextRect2 = Rectangle(rectIvl2, rectIvl2);
Chris@16:               Unit low2 = rect.get(orient.get_perpendicular()).low();
Chris@16:               Unit high2 = node->rect.get(orient.get_perpendicular()).high();
Chris@16:               nextRect2.set(orient.get_perpendicular(), Interval(low2, high2));
Chris@16:               rect = nextRect2;
Chris@16:               //std::cout << "rect for next child" << rect << std::endl;
Chris@16:               node = *itr;
Chris@16:               itr = node->begin();
Chris@16:             }
Chris@16:           }
Chris@16:         }
Chris@16:       } while(!stack.empty() || itr != node->end());
Chris@16:     }
Chris@16: 
Chris@16:     /*  Function recursive version of getMaxCover
Chris@16:         Because the code is so much simpler than the loop algorithm I retain it for clarity
Chris@16: 
Chris@16:     template <class cT>
Chris@16:     static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient,
Chris@16:                                    const Rectangle& rect) {
Chris@16:       Interval rectIvl = rect.get(orient);
Chris@16:       Interval nodeIvl = node->rect.get(orient);
Chris@16:       if(!intersect(rectIvl, nodeIvl, false)) {
Chris@16:         return;
Chris@16:       }
Chris@16:       if(node->tracedPath(rectIvl)) {
Chris@16:         return;
Chris@16:       }
Chris@16:       node->addPath(rectIvl);
Chris@16:       Rectangle nextRect(rectIvl, rectIvl);
Chris@16:       Unit low = rect.get(orient.get_perpendicular()).low();
Chris@16:       Unit high = node->rect.get(orient.get_perpendicular()).high();
Chris@16:       nextRect.set(orient.get_perpendicular(), Interval(low, high));
Chris@16:       bool writeOut = true;
Chris@16:       rectIvl = nextRect.get(orient);
Chris@16:       for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
Chris@16:         nodeIvl = (*itr)->rect.get(orient);
Chris@16:         if(contains(nodeIvl, rectIvl, true)) writeOut = false;
Chris@16:       }
Chris@16:       if(writeOut) {
Chris@16:         outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect));
Chris@16:       }
Chris@16:       for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
Chris@16:         getMaxCover(outputContainer, *itr, orient, nextRect);
Chris@16:       }
Chris@16:     }
Chris@16:     */
Chris@16: 
Chris@16:     //iterator range is assummed to be in topological order meaning all node's trailing
Chris@16:     //edges are in sorted order
Chris@16:     template <class iT>
Chris@16:     static inline void computeDag(iT beginNode, iT endNode, orientation_2d orient,
Chris@16:                                   std::size_t size) {
Chris@16:       std::vector<EdgeAssociation> leadingEdges;
Chris@16:       leadingEdges.reserve(size);
Chris@16:       for(iT iter = beginNode; iter != endNode; ++iter) {
Chris@16:         Node* nodep = &(*iter);
Chris@16:         Unit leading = nodep->rect.get(orient.get_perpendicular()).low();
Chris@16:         Interval rectIvl = nodep->rect.get(orient);
Chris@16:         leadingEdges.push_back(EdgeAssociation(std::pair<Unit, Interval>(leading, rectIvl), nodep));
Chris@16:       }
Chris@16:       polygon_sort(leadingEdges.begin(), leadingEdges.end(), lessEdgeAssociation());
Chris@16:       typename std::vector<EdgeAssociation>::iterator leadingBegin = leadingEdges.begin();
Chris@16:       iT trailingBegin = beginNode;
Chris@16:       while(leadingBegin != leadingEdges.end()) {
Chris@16:         EdgeAssociation& leadingSegment = (*leadingBegin);
Chris@16:         Unit trailing = (*trailingBegin).rect.get(orient.get_perpendicular()).high();
Chris@16:         Interval ivl = (*trailingBegin).rect.get(orient);
Chris@16:         std::pair<Unit, Interval> trailingSegment(trailing, ivl);
Chris@16:         if(leadingSegment.first.first < trailingSegment.first) {
Chris@16:           ++leadingBegin;
Chris@16:           continue;
Chris@16:         }
Chris@16:         if(leadingSegment.first.first > trailingSegment.first) {
Chris@16:           ++trailingBegin;
Chris@16:           continue;
Chris@16:         }
Chris@16:         if(leadingSegment.first.second.high() <= trailingSegment.second.low()) {
Chris@16:           ++leadingBegin;
Chris@16:           continue;
Chris@16:         }
Chris@16:         if(trailingSegment.second.high() <= leadingSegment.first.second.low()) {
Chris@16:           ++trailingBegin;
Chris@16:           continue;
Chris@16:         }
Chris@16:         //leading segment intersects trailing segment
Chris@16:         (*trailingBegin).add((*leadingBegin).second);
Chris@16:         if(leadingSegment.first.second.high() > trailingSegment.second.high()) {
Chris@16:           ++trailingBegin;
Chris@16:           continue;
Chris@16:         }
Chris@16:         if(trailingSegment.second.high() > leadingSegment.first.second.high()) {
Chris@16:           ++leadingBegin;
Chris@16:           continue;
Chris@16:         }
Chris@16:         ++leadingBegin;
Chris@16:         ++trailingBegin;
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     template <class cT>
Chris@16:     static inline void getMaxCover(cT& outputContainer,
Chris@16:                                    const std::vector<Rectangle>& rects, orientation_2d orient) {
Chris@16:       if(rects.empty()) return;
Chris@16:       std::vector<Node> nodes;
Chris@16:       {
Chris@16:         if(rects.size() == 1) {
Chris@16:           outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(rects[0]));
Chris@16:           return;
Chris@16:         }
Chris@16:         nodes.reserve(rects.size());
Chris@16:         for(std::size_t i = 0; i < rects.size(); ++i) { nodes.push_back(Node(rects[i])); }
Chris@16:       }
Chris@16:       computeDag(nodes.begin(), nodes.end(), orient, nodes.size());
Chris@16:       for(std::size_t i = 0; i < nodes.size(); ++i) {
Chris@16:         getMaxCover(outputContainer, &(nodes[i]), orient);
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:   };
Chris@16: }
Chris@16: }
Chris@16: 
Chris@16: #endif