third_party/boost/include/boost/polygon/detail/max_cover.hpp - webm/webmlive - Git at Google

 /*
   Copyright 2008 Intel Corporation

   Use, modification and distribution are subject to the Boost Software License,
   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt).
 */
 #ifndef BOOST_POLYGON_MAX_COVER_HPP
 #define BOOST_POLYGON_MAX_COVER_HPP
 namespace boost { namespace polygon{

   template <typename Unit>
   struct MaxCover {
     typedef interval_data<Unit> Interval;
     typedef rectangle_data<Unit> Rectangle;

     class Node {
     private:
       std::vector<Node*> children_;
       std::set<Interval> tracedPaths_;
     public:
       Rectangle rect;
       Node() : children_(), tracedPaths_(), rect() {}
       Node(const Rectangle rectIn) : children_(), tracedPaths_(), rect(rectIn) {}
       typedef typename std::vector<Node*>::iterator iterator;
       inline iterator begin() { return children_.begin(); }
       inline iterator end() { return children_.end(); }
       inline void add(Node* child) { children_.push_back(child); }
       inline bool tracedPath(const Interval& ivl) const {
         return tracedPaths_.find(ivl) != tracedPaths_.end();
       }
       inline void addPath(const Interval& ivl) {
         tracedPaths_.insert(tracedPaths_.end(), ivl);
       }
     };

     typedef std::pair<std::pair<Unit, Interval>, Node* > EdgeAssociation;

     class lessEdgeAssociation : public std::binary_function<const EdgeAssociation&, const EdgeAssociation&, bool> {
     public:
       inline lessEdgeAssociation() {}
       inline bool operator () (const EdgeAssociation& elem1, const EdgeAssociation& elem2) const {
         if(elem1.first.first < elem2.first.first) return true;
         if(elem1.first.first > elem2.first.first) return false;
         return elem1.first.second < elem2.first.second;
       }
     };

     template <class cT>
     static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient) {
       Interval rectIvl = node->rect.get(orient);
       if(node->tracedPath(rectIvl)) {
         return;
       }
       node->addPath(rectIvl);
       if(node->begin() == node->end()) {
         //std::cout << "WRITE OUT 3: " << node->rect << std::endl;
         outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(node->rect));
         return;
       }
       bool writeOut = true;
       for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
         getMaxCover(outputContainer, *itr, orient, node->rect); //get rectangles down path
         Interval nodeIvl = (*itr)->rect.get(orient);
         if(contains(nodeIvl, rectIvl, true)) writeOut = false;
       }
       if(writeOut) {
         //std::cout << "WRITE OUT 2: " << node->rect << std::endl;
         outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(node->rect));
       }
     }

     struct stack_element {
       inline stack_element() :
         node(), rect(), itr() {}
       inline stack_element(Node* n,
                            const Rectangle& r,
                            typename Node::iterator i) :
         node(n), rect(r), itr(i) {}
       Node* node;
       Rectangle rect;
       typename Node::iterator itr;
     };

     template <class cT>
     static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient,
                                    Rectangle rect) {
       //std::cout << "New Root\n";
       std::vector<stack_element> stack;
       typename Node::iterator itr = node->begin();
       do {
         //std::cout << "LOOP\n";
         //std::cout << node->rect << std::endl;
         Interval rectIvl = rect.get(orient);
         Interval nodeIvl = node->rect.get(orient);
         bool iresult = intersect(rectIvl, nodeIvl, false);
         bool tresult = !node->tracedPath(rectIvl);
         //std::cout << (itr != node->end()) << " " << iresult << " " << tresult << std::endl;
         Rectangle nextRect1 = Rectangle(rectIvl, rectIvl);
         Unit low = rect.get(orient.get_perpendicular()).low();
         Unit high = node->rect.get(orient.get_perpendicular()).high();
         nextRect1.set(orient.get_perpendicular(), Interval(low, high));
         if(iresult && tresult) {
           node->addPath(rectIvl);
           bool writeOut = true;
           //check further visibility beyond this node
           for(typename Node::iterator itr2 = node->begin(); itr2 != node->end(); ++itr2) {
             Interval nodeIvl3 = (*itr2)->rect.get(orient);
             //if a child of this node can contain the interval then we can extend through
             if(contains(nodeIvl3, rectIvl, true)) writeOut = false;
             //std::cout << "child " << (*itr2)->rect << std::endl;
           }
           Rectangle nextRect2 = Rectangle(rectIvl, rectIvl);
           Unit low2 = rect.get(orient.get_perpendicular()).low();
           Unit high2 = node->rect.get(orient.get_perpendicular()).high();
           nextRect2.set(orient.get_perpendicular(), Interval(low2, high2));
           if(writeOut) {
             //std::cout << "write out " << nextRect << std::endl;
             outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect2));
           } else {
             //std::cout << "supress " << nextRect << std::endl;
           }
         }
         if(itr != node->end() && iresult && tresult) {
           //std::cout << "recurse into child\n";
           stack.push_back(stack_element(node, rect, itr));
           rect = nextRect1;
           node = *itr;
           itr = node->begin();
         } else {
           if(!stack.empty()) {
             //std::cout << "recurse out of child\n";
             node = stack.back().node;
             rect = stack.back().rect;
             itr = stack.back().itr;
             stack.pop_back();
           } else {
             //std::cout << "empty stack\n";
             //if there were no children of the root node
 //             Rectangle nextRect = Rectangle(rectIvl, rectIvl);
 //             Unit low = rect.get(orient.get_perpendicular()).low();
 //             Unit high = node->rect.get(orient.get_perpendicular()).high();
 //             nextRect.set(orient.get_perpendicular(), Interval(low, high));
 //             outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect));
           }
           //std::cout << "increment " << (itr != node->end()) << std::endl;
           if(itr != node->end()) {
             ++itr;
             if(itr != node->end()) {
               //std::cout << "recurse into next child.\n";
               stack.push_back(stack_element(node, rect, itr));
               Interval rectIvl2 = rect.get(orient);
               Interval nodeIvl2 = node->rect.get(orient);
               /*bool iresult =*/ intersect(rectIvl2, nodeIvl2, false);
               Rectangle nextRect2 = Rectangle(rectIvl2, rectIvl2);
               Unit low2 = rect.get(orient.get_perpendicular()).low();
               Unit high2 = node->rect.get(orient.get_perpendicular()).high();
               nextRect2.set(orient.get_perpendicular(), Interval(low2, high2));
               rect = nextRect2;
               //std::cout << "rect for next child" << rect << std::endl;
               node = *itr;
               itr = node->begin();
             }
           }
         }
       } while(!stack.empty() || itr != node->end());
     }

     /*  Function recursive version of getMaxCover
         Because the code is so much simpler than the loop algorithm I retain it for clarity

     template <class cT>
     static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient,
                                    const Rectangle& rect) {
       Interval rectIvl = rect.get(orient);
       Interval nodeIvl = node->rect.get(orient);
       if(!intersect(rectIvl, nodeIvl, false)) {
         return;
       }
       if(node->tracedPath(rectIvl)) {
         return;
       }
       node->addPath(rectIvl);
       Rectangle nextRect(rectIvl, rectIvl);
       Unit low = rect.get(orient.get_perpendicular()).low();
       Unit high = node->rect.get(orient.get_perpendicular()).high();
       nextRect.set(orient.get_perpendicular(), Interval(low, high));
       bool writeOut = true;
       rectIvl = nextRect.get(orient);
       for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
         nodeIvl = (*itr)->rect.get(orient);
         if(contains(nodeIvl, rectIvl, true)) writeOut = false;
       }
       if(writeOut) {
         outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect));
       }
       for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
         getMaxCover(outputContainer, *itr, orient, nextRect);
       }
     }
     */

     //iterator range is assummed to be in topological order meaning all node's trailing
     //edges are in sorted order
     template <class iT>
     static inline void computeDag(iT beginNode, iT endNode, orientation_2d orient,
                                   std::size_t size) {
       std::vector<EdgeAssociation> leadingEdges;
       leadingEdges.reserve(size);
       for(iT iter = beginNode; iter != endNode; ++iter) {
         Node* nodep = &(*iter);
         Unit leading = nodep->rect.get(orient.get_perpendicular()).low();
         Interval rectIvl = nodep->rect.get(orient);
         leadingEdges.push_back(EdgeAssociation(std::pair<Unit, Interval>(leading, rectIvl), nodep));
       }
       gtlsort(leadingEdges.begin(), leadingEdges.end(), lessEdgeAssociation());
       typename std::vector<EdgeAssociation>::iterator leadingBegin = leadingEdges.begin();
       iT trailingBegin = beginNode;
       while(leadingBegin != leadingEdges.end()) {
         EdgeAssociation& leadingSegment = (*leadingBegin);
         Unit trailing = (*trailingBegin).rect.get(orient.get_perpendicular()).high();
         Interval ivl = (*trailingBegin).rect.get(orient);
         std::pair<Unit, Interval> trailingSegment(trailing, ivl);
         if(leadingSegment.first.first < trailingSegment.first) {
           ++leadingBegin;
           continue;
         }
         if(leadingSegment.first.first > trailingSegment.first) {
           ++trailingBegin;
           continue;
         }
         if(leadingSegment.first.second.high() <= trailingSegment.second.low()) {
           ++leadingBegin;
           continue;
         }
         if(trailingSegment.second.high() <= leadingSegment.first.second.low()) {
           ++trailingBegin;
           continue;
         }
         //leading segment intersects trailing segment
         (*trailingBegin).add((*leadingBegin).second);
         if(leadingSegment.first.second.high() > trailingSegment.second.high()) {
           ++trailingBegin;
           continue;
         }
         if(trailingSegment.second.high() > leadingSegment.first.second.high()) {
           ++leadingBegin;
           continue;
         }
         ++leadingBegin;
         ++trailingBegin;
       }
     }

     template <class cT>
     static inline void getMaxCover(cT& outputContainer,
                                    const std::vector<Rectangle>& rects, orientation_2d orient) {
       if(rects.empty()) return;
       std::vector<Node> nodes;
       {
         if(rects.size() == 1) {
           outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(rects[0]));
           return;
         }
         nodes.reserve(rects.size());
         for(std::size_t i = 0; i < rects.size(); ++i) { nodes.push_back(Node(rects[i])); }
       }
       computeDag(nodes.begin(), nodes.end(), orient, nodes.size());
       for(std::size_t i = 0; i < nodes.size(); ++i) {
         getMaxCover(outputContainer, &(nodes[i]), orient);
       }
     }

   };
 }
 }

 #endif
	/*
	Copyright 2008 Intel Corporation

	Use, modification and distribution are subject to the Boost Software License,
	Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	http://www.boost.org/LICENSE_1_0.txt).
	*/
	#ifndef BOOST_POLYGON_MAX_COVER_HPP
	#define BOOST_POLYGON_MAX_COVER_HPP
	namespace boost { namespace polygon{

	template <typename Unit>
	struct MaxCover {
	typedef interval_data<Unit> Interval;
	typedef rectangle_data<Unit> Rectangle;

	class Node {
	private:
	std::vector<Node*> children_;
	std::set<Interval> tracedPaths_;
	public:
	Rectangle rect;
	Node() : children_(), tracedPaths_(), rect() {}
	Node(const Rectangle rectIn) : children_(), tracedPaths_(), rect(rectIn) {}
	typedef typename std::vector<Node*>::iterator iterator;
	inline iterator begin() { return children_.begin(); }
	inline iterator end() { return children_.end(); }
	inline void add(Node* child) { children_.push_back(child); }
	inline bool tracedPath(const Interval& ivl) const {
	return tracedPaths_.find(ivl) != tracedPaths_.end();
	}
	inline void addPath(const Interval& ivl) {
	tracedPaths_.insert(tracedPaths_.end(), ivl);
	}
	};

	typedef std::pair<std::pair<Unit, Interval>, Node* > EdgeAssociation;

	class lessEdgeAssociation : public std::binary_function<const EdgeAssociation&, const EdgeAssociation&, bool> {
	public:
	inline lessEdgeAssociation() {}
	inline bool operator () (const EdgeAssociation& elem1, const EdgeAssociation& elem2) const {
	if(elem1.first.first < elem2.first.first) return true;
	if(elem1.first.first > elem2.first.first) return false;
	return elem1.first.second < elem2.first.second;
	}
	};

	template <class cT>
	static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient) {
	Interval rectIvl = node->rect.get(orient);
	if(node->tracedPath(rectIvl)) {
	return;
	}
	node->addPath(rectIvl);
	if(node->begin() == node->end()) {
	//std::cout << "WRITE OUT 3: " << node->rect << std::endl;
	outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(node->rect));
	return;
	}
	bool writeOut = true;
	for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
	getMaxCover(outputContainer, *itr, orient, node->rect); //get rectangles down path
	Interval nodeIvl = (*itr)->rect.get(orient);
	if(contains(nodeIvl, rectIvl, true)) writeOut = false;
	}
	if(writeOut) {
	//std::cout << "WRITE OUT 2: " << node->rect << std::endl;
	outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(node->rect));
	}
	}

	struct stack_element {
	inline stack_element() :
	node(), rect(), itr() {}
	inline stack_element(Node* n,
	const Rectangle& r,
	typename Node::iterator i) :
	node(n), rect(r), itr(i) {}
	Node* node;
	Rectangle rect;
	typename Node::iterator itr;
	};

	template <class cT>
	static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient,
	Rectangle rect) {
	//std::cout << "New Root\n";
	std::vector<stack_element> stack;
	typename Node::iterator itr = node->begin();
	do {
	//std::cout << "LOOP\n";
	//std::cout << node->rect << std::endl;
	Interval rectIvl = rect.get(orient);
	Interval nodeIvl = node->rect.get(orient);
	bool iresult = intersect(rectIvl, nodeIvl, false);
	bool tresult = !node->tracedPath(rectIvl);
	//std::cout << (itr != node->end()) << " " << iresult << " " << tresult << std::endl;
	Rectangle nextRect1 = Rectangle(rectIvl, rectIvl);
	Unit low = rect.get(orient.get_perpendicular()).low();
	Unit high = node->rect.get(orient.get_perpendicular()).high();
	nextRect1.set(orient.get_perpendicular(), Interval(low, high));
	if(iresult && tresult) {
	node->addPath(rectIvl);
	bool writeOut = true;
	//check further visibility beyond this node
	for(typename Node::iterator itr2 = node->begin(); itr2 != node->end(); ++itr2) {
	Interval nodeIvl3 = (*itr2)->rect.get(orient);
	//if a child of this node can contain the interval then we can extend through
	if(contains(nodeIvl3, rectIvl, true)) writeOut = false;
	//std::cout << "child " << (*itr2)->rect << std::endl;
	}
	Rectangle nextRect2 = Rectangle(rectIvl, rectIvl);
	Unit low2 = rect.get(orient.get_perpendicular()).low();
	Unit high2 = node->rect.get(orient.get_perpendicular()).high();
	nextRect2.set(orient.get_perpendicular(), Interval(low2, high2));
	if(writeOut) {
	//std::cout << "write out " << nextRect << std::endl;
	outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect2));
	} else {
	//std::cout << "supress " << nextRect << std::endl;
	}
	}
	if(itr != node->end() && iresult && tresult) {
	//std::cout << "recurse into child\n";
	stack.push_back(stack_element(node, rect, itr));
	rect = nextRect1;
	node = *itr;
	itr = node->begin();
	} else {
	if(!stack.empty()) {
	//std::cout << "recurse out of child\n";
	node = stack.back().node;
	rect = stack.back().rect;
	itr = stack.back().itr;
	stack.pop_back();
	} else {
	//std::cout << "empty stack\n";
	//if there were no children of the root node
	// Rectangle nextRect = Rectangle(rectIvl, rectIvl);
	// Unit low = rect.get(orient.get_perpendicular()).low();
	// Unit high = node->rect.get(orient.get_perpendicular()).high();
	// nextRect.set(orient.get_perpendicular(), Interval(low, high));
	// outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect));
	}
	//std::cout << "increment " << (itr != node->end()) << std::endl;
	if(itr != node->end()) {
	++itr;
	if(itr != node->end()) {
	//std::cout << "recurse into next child.\n";
	stack.push_back(stack_element(node, rect, itr));
	Interval rectIvl2 = rect.get(orient);
	Interval nodeIvl2 = node->rect.get(orient);
	/bool iresult =/ intersect(rectIvl2, nodeIvl2, false);
	Rectangle nextRect2 = Rectangle(rectIvl2, rectIvl2);
	Unit low2 = rect.get(orient.get_perpendicular()).low();
	Unit high2 = node->rect.get(orient.get_perpendicular()).high();
	nextRect2.set(orient.get_perpendicular(), Interval(low2, high2));
	rect = nextRect2;
	//std::cout << "rect for next child" << rect << std::endl;
	node = *itr;
	itr = node->begin();
	}
	}
	}
	} while(!stack.empty() \|\| itr != node->end());
	}

	/* Function recursive version of getMaxCover
	Because the code is so much simpler than the loop algorithm I retain it for clarity

	template <class cT>
	static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient,
	const Rectangle& rect) {
	Interval rectIvl = rect.get(orient);
	Interval nodeIvl = node->rect.get(orient);
	if(!intersect(rectIvl, nodeIvl, false)) {
	return;
	}
	if(node->tracedPath(rectIvl)) {
	return;
	}
	node->addPath(rectIvl);
	Rectangle nextRect(rectIvl, rectIvl);
	Unit low = rect.get(orient.get_perpendicular()).low();
	Unit high = node->rect.get(orient.get_perpendicular()).high();
	nextRect.set(orient.get_perpendicular(), Interval(low, high));
	bool writeOut = true;
	rectIvl = nextRect.get(orient);
	for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
	nodeIvl = (*itr)->rect.get(orient);
	if(contains(nodeIvl, rectIvl, true)) writeOut = false;
	}
	if(writeOut) {
	outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect));
	}
	for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
	getMaxCover(outputContainer, *itr, orient, nextRect);
	}
	}
	*/

	//iterator range is assummed to be in topological order meaning all node's trailing
	//edges are in sorted order
	template <class iT>
	static inline void computeDag(iT beginNode, iT endNode, orientation_2d orient,
	std::size_t size) {
	std::vector<EdgeAssociation> leadingEdges;
	leadingEdges.reserve(size);
	for(iT iter = beginNode; iter != endNode; ++iter) {
	Node* nodep = &(*iter);
	Unit leading = nodep->rect.get(orient.get_perpendicular()).low();
	Interval rectIvl = nodep->rect.get(orient);
	leadingEdges.push_back(EdgeAssociation(std::pair<Unit, Interval>(leading, rectIvl), nodep));
	}
	gtlsort(leadingEdges.begin(), leadingEdges.end(), lessEdgeAssociation());
	typename std::vector<EdgeAssociation>::iterator leadingBegin = leadingEdges.begin();
	iT trailingBegin = beginNode;
	while(leadingBegin != leadingEdges.end()) {
	EdgeAssociation& leadingSegment = (*leadingBegin);
	Unit trailing = (*trailingBegin).rect.get(orient.get_perpendicular()).high();
	Interval ivl = (*trailingBegin).rect.get(orient);
	std::pair<Unit, Interval> trailingSegment(trailing, ivl);
	if(leadingSegment.first.first < trailingSegment.first) {
	++leadingBegin;
	continue;
	}
	if(leadingSegment.first.first > trailingSegment.first) {
	++trailingBegin;
	continue;
	}
	if(leadingSegment.first.second.high() <= trailingSegment.second.low()) {
	++leadingBegin;
	continue;
	}
	if(trailingSegment.second.high() <= leadingSegment.first.second.low()) {
	++trailingBegin;
	continue;
	}
	//leading segment intersects trailing segment
	(trailingBegin).add((leadingBegin).second);
	if(leadingSegment.first.second.high() > trailingSegment.second.high()) {
	++trailingBegin;
	continue;
	}
	if(trailingSegment.second.high() > leadingSegment.first.second.high()) {
	++leadingBegin;
	continue;
	}
	++leadingBegin;
	++trailingBegin;
	}
	}

	template <class cT>
	static inline void getMaxCover(cT& outputContainer,
	const std::vector<Rectangle>& rects, orientation_2d orient) {
	if(rects.empty()) return;
	std::vector<Node> nodes;
	{
	if(rects.size() == 1) {
	outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(rects[0]));
	return;
	}
	nodes.reserve(rects.size());
	for(std::size_t i = 0; i < rects.size(); ++i) { nodes.push_back(Node(rects[i])); }
	}
	computeDag(nodes.begin(), nodes.end(), orient, nodes.size());
	for(std::size_t i = 0; i < nodes.size(); ++i) {
	getMaxCover(outputContainer, &(nodes[i]), orient);
	}
	}

	};
	}
	}

	#endif