/* | |
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_RECTANGLE_FORMATION_HPP | |
#define BOOST_POLYGON_RECTANGLE_FORMATION_HPP | |
namespace boost { namespace polygon{ | |
namespace rectangle_formation { | |
template <class T> | |
class ScanLineToRects { | |
public: | |
typedef T rectangle_type; | |
typedef typename rectangle_traits<T>::coordinate_type coordinate_type; | |
typedef rectangle_data<coordinate_type> scan_rect_type; | |
private: | |
typedef std::set<scan_rect_type, less_rectangle_concept<scan_rect_type, scan_rect_type> > ScanData; | |
ScanData scanData_; | |
bool haveCurrentRect_; | |
scan_rect_type currentRect_; | |
orientation_2d orient_; | |
typename rectangle_traits<T>::coordinate_type currentCoordinate_; | |
public: | |
inline ScanLineToRects() : scanData_(), haveCurrentRect_(), currentRect_(), orient_(), currentCoordinate_() {} | |
inline ScanLineToRects(orientation_2d orient, rectangle_type model) : | |
scanData_(orientation_2d(orient.to_int() ? VERTICAL : HORIZONTAL)), | |
haveCurrentRect_(false), currentRect_(), orient_(orient), currentCoordinate_() { | |
assign(currentRect_, model); | |
currentCoordinate_ = (std::numeric_limits<coordinate_type>::max)(); | |
} | |
template <typename CT> | |
inline ScanLineToRects& processEdge(CT& rectangles, const interval_data<coordinate_type>& edge); | |
inline ScanLineToRects& nextMajorCoordinate(coordinate_type currentCoordinate) { | |
if(haveCurrentRect_) { | |
scanData_.insert(scanData_.end(), currentRect_); | |
haveCurrentRect_ = false; | |
} | |
currentCoordinate_ = currentCoordinate; | |
return *this; | |
} | |
}; | |
template <class CT, class ST, class rectangle_type, typename interval_type, typename coordinate_type> inline CT& | |
processEdge_(CT& rectangles, ST& scanData, const interval_type& edge, | |
bool& haveCurrentRect, rectangle_type& currentRect, coordinate_type currentCoordinate, orientation_2d orient) | |
{ | |
typedef typename CT::value_type result_type; | |
bool edgeProcessed = false; | |
if(!scanData.empty()) { | |
//process all rectangles in the scanData that touch the edge | |
typename ST::iterator dataIter = scanData.lower_bound(rectangle_type(edge, edge)); | |
//decrement beginIter until its low is less than edge's low | |
while((dataIter == scanData.end() || (*dataIter).get(orient).get(LOW) > edge.get(LOW)) && | |
dataIter != scanData.begin()) | |
{ | |
--dataIter; | |
} | |
//process each rectangle until the low end of the rectangle | |
//is greater than the high end of the edge | |
while(dataIter != scanData.end() && | |
(*dataIter).get(orient).get(LOW) <= edge.get(HIGH)) | |
{ | |
const rectangle_type& rect = *dataIter; | |
//if the rectangle data intersects the edge at all | |
if(rect.get(orient).get(HIGH) >= edge.get(LOW)) { | |
if(contains(rect.get(orient), edge, true)) { | |
//this is a closing edge | |
//we need to write out the intersecting rectangle and | |
//insert between 0 and 2 rectangles into the scanData | |
//write out rectangle | |
rectangle_type tmpRect = rect; | |
if(rect.get(orient.get_perpendicular()).get(LOW) < currentCoordinate) { | |
//set the high coordinate perpedicular to slicing orientation | |
//to the current coordinate of the scan event | |
tmpRect.set(orient.get_perpendicular().get_direction(HIGH), | |
currentCoordinate); | |
result_type result; | |
assign(result, tmpRect); | |
rectangles.insert(rectangles.end(), result); | |
} | |
//erase the rectangle from the scan data | |
typename ST::iterator nextIter = dataIter; | |
++nextIter; | |
scanData.erase(dataIter); | |
if(tmpRect.get(orient).get(LOW) < edge.get(LOW)) { | |
//insert a rectangle for the overhang of the bottom | |
//of the rectangle back into scan data | |
rectangle_type lowRect(tmpRect); | |
lowRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate, | |
currentCoordinate)); | |
lowRect.set(orient.get_direction(HIGH), edge.get(LOW)); | |
scanData.insert(nextIter, lowRect); | |
} | |
if(tmpRect.get(orient).get(HIGH) > edge.get(HIGH)) { | |
//insert a rectangle for the overhang of the top | |
//of the rectangle back into scan data | |
rectangle_type highRect(tmpRect); | |
highRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate, | |
currentCoordinate)); | |
highRect.set(orient.get_direction(LOW), edge.get(HIGH)); | |
scanData.insert(nextIter, highRect); | |
} | |
//we are done with this edge | |
edgeProcessed = true; | |
break; | |
} else { | |
//it must be an opening edge | |
//assert that rect does not overlap the edge but only touches | |
//write out rectangle | |
rectangle_type tmpRect = rect; | |
//set the high coordinate perpedicular to slicing orientation | |
//to the current coordinate of the scan event | |
if(tmpRect.get(orient.get_perpendicular().get_direction(LOW)) < currentCoordinate) { | |
tmpRect.set(orient.get_perpendicular().get_direction(HIGH), | |
currentCoordinate); | |
result_type result; | |
assign(result, tmpRect); | |
rectangles.insert(rectangles.end(), result); | |
} | |
//erase the rectangle from the scan data | |
typename ST::iterator nextIter = dataIter; | |
++nextIter; | |
scanData.erase(dataIter); | |
dataIter = nextIter; | |
if(haveCurrentRect) { | |
if(currentRect.get(orient).get(HIGH) >= edge.get(LOW)){ | |
if(!edgeProcessed && currentRect.get(orient.get_direction(HIGH)) > edge.get(LOW)){ | |
rectangle_type tmpRect2(currentRect); | |
tmpRect2.set(orient.get_direction(HIGH), edge.get(LOW)); | |
scanData.insert(nextIter, tmpRect2); | |
if(currentRect.get(orient.get_direction(HIGH)) > edge.get(HIGH)) { | |
currentRect.set(orient, interval_data<coordinate_type>(edge.get(HIGH), currentRect.get(orient.get_direction(HIGH)))); | |
} else { | |
haveCurrentRect = false; | |
} | |
} else { | |
//extend the top of current rect | |
currentRect.set(orient.get_direction(HIGH), | |
(std::max)(edge.get(HIGH), | |
tmpRect.get(orient.get_direction(HIGH)))); | |
} | |
} else { | |
//insert current rect into the scanData | |
scanData.insert(nextIter, currentRect); | |
//create a new current rect | |
currentRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate, | |
currentCoordinate)); | |
currentRect.set(orient, interval_data<coordinate_type>((std::min)(tmpRect.get(orient).get(LOW), | |
edge.get(LOW)), | |
(std::max)(tmpRect.get(orient).get(HIGH), | |
edge.get(HIGH)))); | |
} | |
} else { | |
haveCurrentRect = true; | |
currentRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate, | |
currentCoordinate)); | |
currentRect.set(orient, interval_data<coordinate_type>((std::min)(tmpRect.get(orient).get(LOW), | |
edge.get(LOW)), | |
(std::max)(tmpRect.get(orient).get(HIGH), | |
edge.get(HIGH)))); | |
} | |
//skip to nextIter position | |
edgeProcessed = true; | |
continue; | |
} | |
//edgeProcessed = true; | |
} | |
++dataIter; | |
} //end while edge intersects rectangle data | |
} | |
if(!edgeProcessed) { | |
if(haveCurrentRect) { | |
if(currentRect.get(orient.get_perpendicular().get_direction(HIGH)) | |
== currentCoordinate && | |
currentRect.get(orient.get_direction(HIGH)) >= edge.get(LOW)) | |
{ | |
if(currentRect.get(orient.get_direction(HIGH)) > edge.get(LOW)){ | |
rectangle_type tmpRect(currentRect); | |
tmpRect.set(orient.get_direction(HIGH), edge.get(LOW)); | |
scanData.insert(scanData.end(), tmpRect); | |
if(currentRect.get(orient.get_direction(HIGH)) > edge.get(HIGH)) { | |
currentRect.set(orient, | |
interval_data<coordinate_type>(edge.get(HIGH), | |
currentRect.get(orient.get_direction(HIGH)))); | |
return rectangles; | |
} else { | |
haveCurrentRect = false; | |
return rectangles; | |
} | |
} | |
//extend current rect | |
currentRect.set(orient.get_direction(HIGH), edge.get(HIGH)); | |
return rectangles; | |
} | |
scanData.insert(scanData.end(), currentRect); | |
haveCurrentRect = false; | |
} | |
rectangle_type tmpRect(currentRect); | |
tmpRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate, | |
currentCoordinate)); | |
tmpRect.set(orient, edge); | |
scanData.insert(tmpRect); | |
return rectangles; | |
} | |
return rectangles; | |
} | |
template <class T> | |
template <class CT> | |
inline | |
ScanLineToRects<T>& ScanLineToRects<T>::processEdge(CT& rectangles, const interval_data<coordinate_type>& edge) | |
{ | |
processEdge_(rectangles, scanData_, edge, haveCurrentRect_, currentRect_, currentCoordinate_, orient_); | |
return *this; | |
} | |
} //namespace rectangle_formation | |
template <typename T, typename T2> | |
struct get_coordinate_type_for_rectangles { | |
typedef typename polygon_traits<T>::coordinate_type type; | |
}; | |
template <typename T> | |
struct get_coordinate_type_for_rectangles<T, rectangle_concept> { | |
typedef typename rectangle_traits<T>::coordinate_type type; | |
}; | |
template <typename output_container, typename iterator_type, typename rectangle_concept> | |
void form_rectangles(output_container& output, iterator_type begin, iterator_type end, | |
orientation_2d orient, rectangle_concept ) { | |
typedef typename output_container::value_type rectangle_type; | |
typedef typename get_coordinate_type_for_rectangles<rectangle_type, typename geometry_concept<rectangle_type>::type>::type Unit; | |
rectangle_data<Unit> model; | |
Unit prevPos = (std::numeric_limits<Unit>::max)(); | |
rectangle_formation::ScanLineToRects<rectangle_data<Unit> > scanlineToRects(orient, model); | |
for(iterator_type itr = begin; | |
itr != end; ++ itr) { | |
Unit pos = (*itr).first; | |
if(pos != prevPos) { | |
scanlineToRects.nextMajorCoordinate(pos); | |
prevPos = pos; | |
} | |
Unit lowy = (*itr).second.first; | |
iterator_type tmp_itr = itr; | |
++itr; | |
Unit highy = (*itr).second.first; | |
scanlineToRects.processEdge(output, interval_data<Unit>(lowy, highy)); | |
if(abs((*itr).second.second) > 1) itr = tmp_itr; //next edge begins from this vertex | |
} | |
} | |
} | |
} | |
#endif | |