/* | |
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_PROPERTY_MERGE_HPP | |
#define BOOST_POLYGON_PROPERTY_MERGE_HPP | |
namespace boost { namespace polygon{ | |
template <typename coordinate_type> | |
class property_merge_point { | |
private: | |
coordinate_type x_, y_; | |
public: | |
inline property_merge_point() : x_(), y_() {} | |
inline property_merge_point(coordinate_type x, coordinate_type y) : x_(x), y_(y) {} | |
//use builtin assign and copy | |
inline bool operator==(const property_merge_point& that) const { return x_ == that.x_ && y_ == that.y_; } | |
inline bool operator!=(const property_merge_point& that) const { return !((*this) == that); } | |
inline bool operator<(const property_merge_point& that) const { | |
if(x_ < that.x_) return true; | |
if(x_ > that.x_) return false; | |
return y_ < that.y_; | |
} | |
inline coordinate_type x() const { return x_; } | |
inline coordinate_type y() const { return y_; } | |
inline void x(coordinate_type value) { x_ = value; } | |
inline void y(coordinate_type value) { y_ = value; } | |
}; | |
template <typename coordinate_type> | |
class property_merge_interval { | |
private: | |
coordinate_type low_, high_; | |
public: | |
inline property_merge_interval() : low_(), high_() {} | |
inline property_merge_interval(coordinate_type low, coordinate_type high) : low_(low), high_(high) {} | |
//use builtin assign and copy | |
inline bool operator==(const property_merge_interval& that) const { return low_ == that.low_ && high_ == that.high_; } | |
inline bool operator!=(const property_merge_interval& that) const { return !((*this) == that); } | |
inline bool operator<(const property_merge_interval& that) const { | |
if(low_ < that.low_) return true; | |
if(low_ > that.low_) return false; | |
return high_ < that.high_; | |
} | |
inline coordinate_type low() const { return low_; } | |
inline coordinate_type high() const { return high_; } | |
inline void low(coordinate_type value) { low_ = value; } | |
inline void high(coordinate_type value) { high_ = value; } | |
}; | |
template <typename coordinate_type, typename property_type, typename polygon_set_type, typename keytype = std::set<property_type> > | |
class merge_scanline { | |
public: | |
//definitions | |
typedef keytype property_set; | |
typedef std::vector<std::pair<property_type, int> > property_map; | |
typedef std::pair<property_merge_point<coordinate_type>, std::pair<property_type, int> > vertex_property; | |
typedef std::pair<property_merge_point<coordinate_type>, property_map> vertex_data; | |
typedef std::vector<vertex_property> property_merge_data; | |
//typedef std::map<property_set, polygon_set_type> Result; | |
typedef std::map<coordinate_type, property_map> scanline_type; | |
typedef typename scanline_type::iterator scanline_iterator; | |
typedef std::pair<property_merge_interval<coordinate_type>, std::pair<property_set, property_set> > edge_property; | |
typedef std::vector<edge_property> edge_property_vector; | |
//static public member functions | |
template <typename iT, typename orientation_2d_type> | |
static inline void | |
populate_property_merge_data(property_merge_data& pmd, iT input_begin, iT input_end, | |
const property_type& property, orientation_2d_type orient) { | |
for( ; input_begin != input_end; ++input_begin) { | |
std::pair<property_merge_point<coordinate_type>, std::pair<property_type, int> > element; | |
if(orient == HORIZONTAL) | |
element.first = property_merge_point<coordinate_type>((*input_begin).second.first, (*input_begin).first); | |
else | |
element.first = property_merge_point<coordinate_type>((*input_begin).first, (*input_begin).second.first); | |
element.second.first = property; | |
element.second.second = (*input_begin).second.second; | |
pmd.push_back(element); | |
} | |
} | |
//public member functions | |
merge_scanline() : output(), scanline(), currentVertex(), tmpVector(), previousY(), countFromBelow(), scanlinePosition() {} | |
merge_scanline(const merge_scanline& that) : | |
output(that.output), | |
scanline(that.scanline), | |
currentVertex(that.currentVertex), | |
tmpVector(that.tmpVector), | |
previousY(that.previousY), | |
countFromBelow(that.countFromBelow), | |
scanlinePosition(that.scanlinePosition) | |
{} | |
merge_scanline& operator=(const merge_scanline& that) { | |
output = that.output; | |
scanline = that.scanline; | |
currentVertex = that.currentVertex; | |
tmpVector = that.tmpVector; | |
previousY = that.previousY; | |
countFromBelow = that.countFromBelow; | |
scanlinePosition = that.scanlinePosition; | |
return *this; | |
} | |
template <typename result_type> | |
inline void perform_merge(result_type& result, property_merge_data& data) { | |
if(data.empty()) return; | |
//sort | |
gtlsort(data.begin(), data.end(), less_vertex_data<vertex_property>()); | |
//scanline | |
bool firstIteration = true; | |
scanlinePosition = scanline.end(); | |
for(std::size_t i = 0; i < data.size(); ++i) { | |
if(firstIteration) { | |
mergeProperty(currentVertex.second, data[i].second); | |
currentVertex.first = data[i].first; | |
firstIteration = false; | |
} else { | |
if(data[i].first != currentVertex.first) { | |
if(data[i].first.x() != currentVertex.first.x()) { | |
processVertex(output); | |
//std::cout << scanline.size() << " "; | |
countFromBelow.clear(); //should already be clear | |
writeOutput(currentVertex.first.x(), result, output); | |
currentVertex.second.clear(); | |
mergeProperty(currentVertex.second, data[i].second); | |
currentVertex.first = data[i].first; | |
//std::cout << assertRedundant(scanline) << "/" << scanline.size() << " "; | |
} else { | |
processVertex(output); | |
currentVertex.second.clear(); | |
mergeProperty(currentVertex.second, data[i].second); | |
currentVertex.first = data[i].first; | |
} | |
} else { | |
mergeProperty(currentVertex.second, data[i].second); | |
} | |
} | |
} | |
processVertex(output); | |
writeOutput(currentVertex.first.x(), result, output); | |
//std::cout << assertRedundant(scanline) << "/" << scanline.size() << "\n"; | |
//std::cout << scanline.size() << "\n"; | |
} | |
private: | |
//private supporting types | |
template <class T> | |
class less_vertex_data { | |
public: | |
less_vertex_data() {} | |
bool operator()(const T& lvalue, const T& rvalue) const { | |
if(lvalue.first.x() < rvalue.first.x()) return true; | |
if(lvalue.first.x() > rvalue.first.x()) return false; | |
if(lvalue.first.y() < rvalue.first.y()) return true; | |
return false; | |
} | |
}; | |
template <typename T> | |
struct lessPropertyCount { | |
lessPropertyCount() {} | |
bool operator()(const T& a, const T& b) { | |
return a.first < b.first; | |
} | |
}; | |
//private static member functions | |
static inline void mergeProperty(property_map& lvalue, std::pair<property_type, int>& rvalue) { | |
typename property_map::iterator itr = std::lower_bound(lvalue.begin(), lvalue.end(), rvalue, | |
lessPropertyCount<std::pair<property_type, int> >()); | |
if(itr == lvalue.end() || | |
(*itr).first != rvalue.first) { | |
lvalue.insert(itr, rvalue); | |
} else { | |
(*itr).second += rvalue.second; | |
if((*itr).second == 0) | |
lvalue.erase(itr); | |
} | |
// if(assertSorted(lvalue)) { | |
// std::cout << "in mergeProperty\n"; | |
// exit(0); | |
// } | |
} | |
// static inline bool assertSorted(property_map& pset) { | |
// bool result = false; | |
// for(std::size_t i = 1; i < pset.size(); ++i) { | |
// if(pset[i] < pset[i-1]) { | |
// std::cout << "Out of Order Error "; | |
// result = true; | |
// } | |
// if(pset[i].first == pset[i-1].first) { | |
// std::cout << "Duplicate Property Error "; | |
// result = true; | |
// } | |
// if(pset[0].second == 0 || pset[1].second == 0) { | |
// std::cout << "Empty Property Error "; | |
// result = true; | |
// } | |
// } | |
// return result; | |
// } | |
static inline void setProperty(property_set& pset, property_map& pmap) { | |
for(typename property_map::iterator itr = pmap.begin(); itr != pmap.end(); ++itr) { | |
if((*itr).second > 0) { | |
pset.insert(pset.end(), (*itr).first); | |
} | |
} | |
} | |
//private data members | |
edge_property_vector output; | |
scanline_type scanline; | |
vertex_data currentVertex; | |
property_map tmpVector; | |
coordinate_type previousY; | |
property_map countFromBelow; | |
scanline_iterator scanlinePosition; | |
//private member functions | |
inline void mergeCount(property_map& lvalue, property_map& rvalue) { | |
typename property_map::iterator litr = lvalue.begin(); | |
typename property_map::iterator ritr = rvalue.begin(); | |
tmpVector.clear(); | |
while(litr != lvalue.end() && ritr != rvalue.end()) { | |
if((*litr).first <= (*ritr).first) { | |
if(!tmpVector.empty() && | |
(*litr).first == tmpVector.back().first) { | |
tmpVector.back().second += (*litr).second; | |
} else { | |
tmpVector.push_back(*litr); | |
} | |
++litr; | |
} else if((*ritr).first <= (*litr).first) { | |
if(!tmpVector.empty() && | |
(*ritr).first == tmpVector.back().first) { | |
tmpVector.back().second += (*ritr).second; | |
} else { | |
tmpVector.push_back(*ritr); | |
} | |
++ritr; | |
} | |
} | |
while(litr != lvalue.end()) { | |
if(!tmpVector.empty() && | |
(*litr).first == tmpVector.back().first) { | |
tmpVector.back().second += (*litr).second; | |
} else { | |
tmpVector.push_back(*litr); | |
} | |
++litr; | |
} | |
while(ritr != rvalue.end()) { | |
if(!tmpVector.empty() && | |
(*ritr).first == tmpVector.back().first) { | |
tmpVector.back().second += (*ritr).second; | |
} else { | |
tmpVector.push_back(*ritr); | |
} | |
++ritr; | |
} | |
lvalue.clear(); | |
for(std::size_t i = 0; i < tmpVector.size(); ++i) { | |
if(tmpVector[i].second != 0) { | |
lvalue.push_back(tmpVector[i]); | |
} | |
} | |
// if(assertSorted(lvalue)) { | |
// std::cout << "in mergeCount\n"; | |
// exit(0); | |
// } | |
} | |
inline void processVertex(edge_property_vector& output) { | |
if(!countFromBelow.empty()) { | |
//we are processing an interval of change in scanline state between | |
//previous vertex position and current vertex position where | |
//count from below represents the change on the interval | |
//foreach scanline element from previous to current we | |
//write the interval on the scanline that is changing | |
//the old value and the new value to output | |
property_merge_interval<coordinate_type> currentInterval(previousY, currentVertex.first.y()); | |
coordinate_type currentY = currentInterval.low(); | |
if(scanlinePosition == scanline.end() || | |
(*scanlinePosition).first != previousY) { | |
scanlinePosition = scanline.lower_bound(previousY); | |
} | |
scanline_iterator previousScanlinePosition = scanlinePosition; | |
++scanlinePosition; | |
while(scanlinePosition != scanline.end()) { | |
coordinate_type elementY = (*scanlinePosition).first; | |
if(elementY <= currentInterval.high()) { | |
property_map& countOnLeft = (*previousScanlinePosition).second; | |
edge_property element; | |
output.push_back(element); | |
output.back().first = property_merge_interval<coordinate_type>((*previousScanlinePosition).first, elementY); | |
setProperty(output.back().second.first, countOnLeft); | |
mergeCount(countOnLeft, countFromBelow); | |
setProperty(output.back().second.second, countOnLeft); | |
if(output.back().second.first == output.back().second.second) { | |
output.pop_back(); //it was an internal vertical edge, not to be output | |
} | |
else if(output.size() > 1) { | |
edge_property& secondToLast = output[output.size()-2]; | |
if(secondToLast.first.high() == output.back().first.low() && | |
secondToLast.second.first == output.back().second.first && | |
secondToLast.second.second == output.back().second.second) { | |
//merge output onto previous output because properties are | |
//identical on both sides implying an internal horizontal edge | |
secondToLast.first.high(output.back().first.high()); | |
output.pop_back(); | |
} | |
} | |
if(previousScanlinePosition == scanline.begin()) { | |
if(countOnLeft.empty()) { | |
scanline.erase(previousScanlinePosition); | |
} | |
} else { | |
scanline_iterator tmpitr = previousScanlinePosition; | |
--tmpitr; | |
if((*tmpitr).second == (*previousScanlinePosition).second) | |
scanline.erase(previousScanlinePosition); | |
} | |
} else if(currentY < currentInterval.high()){ | |
//elementY > currentInterval.high() | |
//split the interval between previous and current scanline elements | |
std::pair<coordinate_type, property_map> elementScan; | |
elementScan.first = currentInterval.high(); | |
elementScan.second = (*previousScanlinePosition).second; | |
scanlinePosition = scanline.insert(scanlinePosition, elementScan); | |
continue; | |
} else { | |
break; | |
} | |
previousScanlinePosition = scanlinePosition; | |
currentY = previousY = elementY; | |
++scanlinePosition; | |
if(scanlinePosition == scanline.end() && | |
currentY < currentInterval.high()) { | |
//insert a new element for top of range | |
std::pair<coordinate_type, property_map> elementScan; | |
elementScan.first = currentInterval.high(); | |
scanlinePosition = scanline.insert(scanline.end(), elementScan); | |
} | |
} | |
if(scanlinePosition == scanline.end() && | |
currentY < currentInterval.high()) { | |
//handle case where we iterated to end of the scanline | |
//we need to insert an element into the scanline at currentY | |
//with property value coming from below | |
//and another one at currentInterval.high() with empty property value | |
mergeCount(scanline[currentY], countFromBelow); | |
std::pair<coordinate_type, property_map> elementScan; | |
elementScan.first = currentInterval.high(); | |
scanline.insert(scanline.end(), elementScan); | |
edge_property element; | |
output.push_back(element); | |
output.back().first = property_merge_interval<coordinate_type>(currentY, currentInterval.high()); | |
setProperty(output.back().second.second, countFromBelow); | |
mergeCount(countFromBelow, currentVertex.second); | |
} else { | |
mergeCount(countFromBelow, currentVertex.second); | |
if(countFromBelow.empty()) { | |
if(previousScanlinePosition == scanline.begin()) { | |
if((*previousScanlinePosition).second.empty()) { | |
scanline.erase(previousScanlinePosition); | |
//previousScanlinePosition = scanline.end(); | |
//std::cout << "ERASE_A "; | |
} | |
} else { | |
scanline_iterator tmpitr = previousScanlinePosition; | |
--tmpitr; | |
if((*tmpitr).second == (*previousScanlinePosition).second) { | |
scanline.erase(previousScanlinePosition); | |
//previousScanlinePosition = scanline.end(); | |
//std::cout << "ERASE_B "; | |
} | |
} | |
} | |
} | |
} else { | |
//count from below is empty, we are starting a new interval of change | |
countFromBelow = currentVertex.second; | |
scanlinePosition = scanline.lower_bound(currentVertex.first.y()); | |
if(scanlinePosition != scanline.end()) { | |
if((*scanlinePosition).first != currentVertex.first.y()) { | |
if(scanlinePosition != scanline.begin()) { | |
//decrement to get the lower position of the first interval this vertex intersects | |
--scanlinePosition; | |
//insert a new element into the scanline for the incoming vertex | |
property_map& countOnLeft = (*scanlinePosition).second; | |
std::pair<coordinate_type, property_map> element(currentVertex.first.y(), countOnLeft); | |
scanlinePosition = scanline.insert(scanlinePosition, element); | |
} else { | |
property_map countOnLeft; | |
std::pair<coordinate_type, property_map> element(currentVertex.first.y(), countOnLeft); | |
scanlinePosition = scanline.insert(scanlinePosition, element); | |
} | |
} | |
} else { | |
property_map countOnLeft; | |
std::pair<coordinate_type, property_map> element(currentVertex.first.y(), countOnLeft); | |
scanlinePosition = scanline.insert(scanlinePosition, element); | |
} | |
} | |
previousY = currentVertex.first.y(); | |
} | |
template <typename T> | |
inline int assertRedundant(T& t) { | |
if(t.empty()) return 0; | |
int count = 0; | |
typename T::iterator itr = t.begin(); | |
if((*itr).second.empty()) | |
++count; | |
typename T::iterator itr2 = itr; | |
++itr2; | |
while(itr2 != t.end()) { | |
if((*itr).second == (*itr2).second) | |
++count; | |
itr = itr2; | |
++itr2; | |
} | |
return count; | |
} | |
template <typename T> | |
inline void performExtract(T& result, property_merge_data& data) { | |
if(data.empty()) return; | |
//sort | |
gtlsort(data.begin(), data.end(), less_vertex_data<vertex_property>()); | |
//scanline | |
bool firstIteration = true; | |
scanlinePosition = scanline.end(); | |
for(std::size_t i = 0; i < data.size(); ++i) { | |
if(firstIteration) { | |
mergeProperty(currentVertex.second, data[i].second); | |
currentVertex.first = data[i].first; | |
firstIteration = false; | |
} else { | |
if(data[i].first != currentVertex.first) { | |
if(data[i].first.x() != currentVertex.first.x()) { | |
processVertex(output); | |
//std::cout << scanline.size() << " "; | |
countFromBelow.clear(); //should already be clear | |
writeGraph(currentVertex.first.x(), result, output, scanline); | |
currentVertex.second.clear(); | |
mergeProperty(currentVertex.second, data[i].second); | |
currentVertex.first = data[i].first; | |
} else { | |
processVertex(output); | |
currentVertex.second.clear(); | |
mergeProperty(currentVertex.second, data[i].second); | |
currentVertex.first = data[i].first; | |
} | |
} else { | |
mergeProperty(currentVertex.second, data[i].second); | |
} | |
} | |
} | |
processVertex(output); | |
writeGraph(currentVertex.first.x(), result, output, scanline); | |
//std::cout << scanline.size() << "\n"; | |
} | |
template <typename T> | |
inline void insertEdges(T& graph, property_set& p1, property_set& p2) { | |
for(typename property_set::iterator itr = p1.begin(); itr != p1.end(); ++itr) { | |
for(typename property_set::iterator itr2 = p2.begin(); itr2 != p2.end(); ++itr2) { | |
if(*itr != *itr2) { | |
graph[*itr].insert(*itr2); | |
graph[*itr2].insert(*itr); | |
} | |
} | |
} | |
} | |
template <typename T> | |
inline void propertySetAbove(coordinate_type y, property_set& ps, T& scanline) { | |
ps.clear(); | |
typename T::iterator itr = scanline.find(y); | |
if(itr != scanline.end()) | |
setProperty(ps, (*itr).second); | |
} | |
template <typename T> | |
inline void propertySetBelow(coordinate_type y, property_set& ps, T& scanline) { | |
ps.clear(); | |
typename T::iterator itr = scanline.find(y); | |
if(itr != scanline.begin()) { | |
--itr; | |
setProperty(ps, (*itr).second); | |
} | |
} | |
template <typename T, typename T2> | |
inline void writeGraph(coordinate_type x, T& graph, edge_property_vector& output, T2& scanline) { | |
if(output.empty()) return; | |
edge_property* previousEdgeP = &(output[0]); | |
bool firstIteration = true; | |
property_set ps; | |
for(std::size_t i = 0; i < output.size(); ++i) { | |
edge_property& previousEdge = *previousEdgeP; | |
edge_property& edge = output[i]; | |
if(previousEdge.first.high() == edge.first.low()) { | |
//horizontal edge | |
insertEdges(graph, edge.second.first, previousEdge.second.first); | |
//corner 1 | |
insertEdges(graph, edge.second.first, previousEdge.second.second); | |
//other horizontal edge | |
insertEdges(graph, edge.second.second, previousEdge.second.second); | |
//corner 2 | |
insertEdges(graph, edge.second.second, previousEdge.second.first); | |
} else { | |
if(!firstIteration){ | |
//look up regions above previous edge | |
propertySetAbove(previousEdge.first.high(), ps, scanline); | |
insertEdges(graph, ps, previousEdge.second.first); | |
insertEdges(graph, ps, previousEdge.second.second); | |
} | |
//look up regions below current edge in the scanline | |
propertySetBelow(edge.first.high(), ps, scanline); | |
insertEdges(graph, ps, edge.second.first); | |
insertEdges(graph, ps, edge.second.second); | |
} | |
firstIteration = false; | |
//vertical edge | |
insertEdges(graph, edge.second.second, edge.second.first); | |
//shared region to left | |
insertEdges(graph, edge.second.second, edge.second.second); | |
//shared region to right | |
insertEdges(graph, edge.second.first, edge.second.first); | |
previousEdgeP = &(output[i]); | |
} | |
edge_property& previousEdge = *previousEdgeP; | |
propertySetAbove(previousEdge.first.high(), ps, scanline); | |
insertEdges(graph, ps, previousEdge.second.first); | |
insertEdges(graph, ps, previousEdge.second.second); | |
output.clear(); | |
} | |
template <typename Result> | |
inline void writeOutput(coordinate_type x, Result& result, edge_property_vector& output) { | |
for(std::size_t i = 0; i < output.size(); ++i) { | |
edge_property& edge = output[i]; | |
//edge.second.first is the property set on the left of the edge | |
if(!edge.second.first.empty()) { | |
typename Result::iterator itr = result.find(edge.second.first); | |
if(itr == result.end()) { | |
std::pair<property_set, polygon_set_type> element(edge.second.first, polygon_set_type(VERTICAL)); | |
itr = result.insert(result.end(), element); | |
} | |
std::pair<interval_data<coordinate_type>, int> element2(interval_data<coordinate_type>(edge.first.low(), edge.first.high()), -1); //right edge of figure | |
(*itr).second.insert(x, element2); | |
} | |
if(!edge.second.second.empty()) { | |
//edge.second.second is the property set on the right of the edge | |
typename Result::iterator itr = result.find(edge.second.second); | |
if(itr == result.end()) { | |
std::pair<property_set, polygon_set_type> element(edge.second.second, polygon_set_type(VERTICAL)); | |
itr = result.insert(result.end(), element); | |
} | |
std::pair<interval_data<coordinate_type>, int> element3(interval_data<coordinate_type>(edge.first.low(), edge.first.high()), 1); //left edge of figure | |
(*itr).second.insert(x, element3); | |
} | |
} | |
output.clear(); | |
} | |
}; | |
} | |
} | |
#endif |