/usr/include/boost/polygon/detail
Edit: /usr/include/boost/polygon/detail/polygon_formation.hpp (87952B)
/*
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).
*/
#include
#include
#ifndef BOOST_POLYGON_POLYGON_FORMATION_HPP
#define BOOST_POLYGON_POLYGON_FORMATION_HPP
namespace boost { namespace polygon{
namespace polygon_formation {
/*
* End has two states, HEAD and TAIL as is represented by a bool
*/
typedef bool End;
/*
* HEAD End is represented as false because it is the lesser state
*/
const End HEAD = false;
/*
* TAIL End is represented by true because TAIL comes after head and 1 after 0
*/
const End TAIL = true;
/*
* 2D turning direction, left and right sides (is a boolean value since it has two states.)
*/
typedef bool Side;
/*
* LEFT Side is 0 because we inuitively think left to right; left < right
*/
const Side LEFT = false;
/*
* RIGHT Side is 1 so that right > left
*/
const Side RIGHT = true;
/*
* The PolyLine class is data storage and services for building and representing partial polygons.
* As the polyline is added to it extends its storage to accomodate the data.
* PolyLines can be joined head-to-head/head-to-tail when it is determined that two polylines are
* part of the same polygon.
* PolyLines keep state information about what orientation their incomplete head and tail geometry have,
* which side of the polyline is solid and whether the polyline is joined head-to-head and tail-to-head.
* PolyLines have nothing whatsoever to do with holes.
* It may be valuable to collect a histogram of PolyLine lengths used by an algorithm on its typical data
* sets and tune the allocation of the initial vector of coordinate data to be greater than or equal to
* the mean, median, mode, or mean plus some number of standard deviation, or just generally large enough
* to prevent too much unnecesary reallocations, but not too big that it wastes a lot of memory and degrades cache
* performance.
*/
template
class PolyLine {
private:
//data
/*
* ptdata_ a vector of coordiantes
* if VERTICAL_HEAD, first coordiante is an X
* else first coordinate is a Y
*/
std::vector ptdata_;
/*
* head and tail points to other polylines before and after this in a chain
*/
PolyLine* headp_;
PolyLine* tailp_;
/*
* state bitmask
* bit zero is orientation, 0 H, 1 V
* bit 1 is head connectivity, 0 for head, 1 for tail
* bit 2 is tail connectivity, 0 for head, 1 for tail
* bit 3 is solid to left of PolyLine when 1, right when 0
*/
int state_;
public:
/*
* default constructor (for preallocation)
*/
PolyLine();
/*
* constructor that takes the orientation, coordiante and side to which there is solid
*/
PolyLine(orientation_2d orient, Unit coord, Side side);
//copy constructor
PolyLine(const PolyLine& pline);
//destructor
~PolyLine();
//assignment operator
PolyLine& operator=(const PolyLine& that);
//equivalence operator
bool operator==(const PolyLine& b) const;
/*
* valid PolyLine (only default constructed polylines are invalid.)
*/
bool isValid() const;
/*
* Orientation of Head
*/
orientation_2d headOrient() const;
/*
* returns true if first coordinate is an X value (first segment is vertical)
*/
bool verticalHead() const;
/*
* returns the orientation_2d fo the tail
*/
orientation_2d tailOrient() const;
/*
* returns true if last coordinate is an X value (last segment is vertical)
*/
bool verticalTail() const;
/*
* retrun true if PolyLine has odd number of coordiantes
*/
bool oddLength() const;
/*
* retrun the End of the other polyline that the specified end of this polyline is connected to
*/
End endConnectivity(End end) const;
/*
* retrun true if the head of this polyline is connect to the tail of a polyline
*/
bool headToTail() const;
/*
* retrun true if the head of this polyline is connect to the head of a polyline
*/
bool headToHead() const;
/*
* retrun true if the tail of this polyline is connect to the tail of a polyline
*/
bool tailToTail() const;
/*
* retrun true if the tail of this polyline is connect to the head of a polyline
*/
bool tailToHead() const;
/*
* retrun the side on which there is solid for this polyline
*/
Side solidSide() const;
/*
* retrun true if there is solid to the right of this polyline
*/
bool solidToRight() const;
/*
* returns true if the polyline tail is not connected
*/
bool active() const;
/*
* adds a coordinate value to the end of the polyline changing the tail orientation
*/
PolyLine& pushCoordinate(Unit coord);
/*
* removes a coordinate value at the end of the polyline changing the tail orientation
*/
PolyLine& popCoordinate();
/*
* extends the tail of the polyline to include the point, changing orientation if needed
*/
PolyLine& pushPoint(const point_data& point);
/*
* changes the last coordinate of the tail of the polyline by the amount of the delta
*/
PolyLine& extendTail(Unit delta);
/*
* join thisEnd of this polyline to that polyline's end
*/
PolyLine& joinTo(End thisEnd, PolyLine& that, End end);
/*
* join an end of this polyline to the tail of that polyline
*/
PolyLine& joinToTail(PolyLine& that, End end);
/*
* join an end of this polyline to the head of that polyline
*/
PolyLine& joinToHead(PolyLine& that, End end);
/*
* join the head of this polyline to the head of that polyline
*/
//join this to that in the given way
PolyLine& joinHeadToHead(PolyLine& that);
/*
* join the head of this polyline to the tail of that polyline
*/
PolyLine& joinHeadToTail(PolyLine& that);
/*
* join the tail of this polyline to the head of that polyline
*/
PolyLine& joinTailToHead(PolyLine& that);
/*
* join the tail of this polyline to the tail of that polyline
*/
PolyLine& joinTailToTail(PolyLine& that);
/*
* dissconnect the tail at the end of the polygon
*/
PolyLine& disconnectTails();
/*
* get the coordinate at one end of this polyline, by default the tail end
*/
Unit getEndCoord(End end = TAIL) const;
/*
* get the point on the polyline at the given index (polylines have the same number of coordinates as points
*/
point_data getPoint(unsigned int index) const;
/*
* get the point on one end of the polyline, by default the tail
*/
point_data getEndPoint(End end = TAIL) const;
/*
* get the orientation of a segment by index
*/
orientation_2d segmentOrient(unsigned int index = 0) const;
/*
* get a coordinate by index using the square bracket operator
*/
Unit operator[] (unsigned int index) const;
/*
* get the number of segments/points/coordinates in the polyline
*/
unsigned int numSegments() const;
/*
* get the pointer to the next polyline at one end of this
*/
PolyLine* next(End end) const;
/*
* write out coordinates of this and all attached polylines to a single vector
*/
PolyLine* writeOut(std::vector& outVec, End startEnd = TAIL) const;
private:
//methods
PolyLine& joinTo_(End thisEnd, PolyLine& that, End end);
};
//forward declaration
template
class PolyLinePolygonData;
//forward declaration
template
class PolyLinePolygonWithHolesData;
/*
* ActiveTail represents an edge of an incomplete polygon.
*
* An ActiveTail object is the active tail end of a polyline object, which may (should) be the attached to
* a chain of polyline objects through a pointer. The ActiveTail class provides an abstraction between
* and algorithm that builds polygons and the PolyLine data representation of incomplete polygons that are
* being built. It does this by providing an iterface to access the information about the last edge at the
* tail of the PolyLine it is associated with. To a polygon constructing algorithm, an ActiveTail is a floating
* edge of an incomplete polygon and has an orientation and coordinate value, as well as knowing which side of
* that edge is supposed to be solid or space. Any incomplete polygon will have two active tails. Active tails
* may be joined together to merge two incomplete polygons into a larger incomplete polygon. If two active tails
* that are to be merged are the oppositve ends of the same incomplete polygon that indicates that the polygon
* has been closed and is complete. The active tail keeps a pointer to the other active tail of its incomplete
* polygon so that it is easy to check this condition. These pointers are updated when active tails are joined.
* The active tail also keeps a list of pointers to active tail objects that serve as handles to closed holes. In
* this way a hole can be associated to another incomplete polygon, which will eventually be its enclosing shell,
* or reassociate the hole to another incomplete polygon in the case that it become a hole itself. Alternately,
* the active tail may add a filiment to stitch a hole into a shell and "fracture" the hole out of the interior
* of a polygon. The active tail maintains a static output buffer to temporarily write polygon data to when
* it outputs a figure so that outputting a polygon does not require the allocation of a temporary buffer. This
* static buffer should be destroyed whenever the program determines that it won't need it anymore and would prefer to
* release the memory it has allocated back to the system.
*/
template
class ActiveTail {
private:
//data
PolyLine* tailp_;
ActiveTail *otherTailp_;
std::list holesList_;
//Sum of all the polylines which constitute the active tail (including holes)//
size_t polyLineSize_;
public:
inline size_t getPolyLineSize(){
return polyLineSize_;
}
inline void setPolyLineSize(int delta){
polyLineSize_ = delta;
}
inline void addPolyLineSize(int delta){
polyLineSize_ += delta;
}
/*
* iterator over coordinates of the figure
*/
class iterator {
private:
const PolyLine* pLine_;
const PolyLine* pLineEnd_;
unsigned int index_;
unsigned int indexEnd_;
End startEnd_;
public:
inline iterator() : pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() {}
inline iterator(const ActiveTail* at, bool isHole, orientation_2d orient) :
pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() {
//if it is a hole and orientation is vertical or it is not a hole and orientation is horizontal
//we want to use this active tail, otherwise we want to use the other active tail
startEnd_ = TAIL;
if(!isHole ^ (orient == HORIZONTAL)) {
//switch winding direction
at = at->getOtherActiveTail();
}
//now we have the right winding direction
//if it is horizontal we need to skip the first element
pLine_ = at->getTail();
if(at->getTail()->numSegments() > 0)
index_ = at->getTail()->numSegments() - 1;
if((at->getOrient() == HORIZONTAL) ^ (orient == HORIZONTAL)) {
pLineEnd_ = at->getTail();
indexEnd_ = pLineEnd_->numSegments() - 1;
if(index_ == 0) {
pLine_ = at->getTail()->next(HEAD);
if(at->getTail()->endConnectivity(HEAD) == TAIL) {
index_ = pLine_->numSegments() -1;
} else {
startEnd_ = HEAD;
index_ = 0;
}
} else { --index_; }
} else {
pLineEnd_ = at->getOtherActiveTail()->getTail();
if(pLineEnd_->numSegments() > 0)
indexEnd_ = pLineEnd_->numSegments() - 1;
}
at->getTail()->joinTailToTail(*(at->getOtherActiveTail()->getTail()));
}
inline size_t size(void){
size_t count = 0;
End dir = startEnd_;
PolyLine const * currLine = pLine_;
size_t ops = 0;
while(currLine != pLineEnd_){
ops++;
count += currLine->numSegments();
currLine = currLine->next(dir == HEAD ? TAIL : HEAD);
dir = currLine->endConnectivity(dir == HEAD ? TAIL : HEAD);
}
count += pLineEnd_->numSegments();
return count; //no. of vertices
}
//use bitwise copy and assign provided by the compiler
inline iterator& operator++() {
if(pLine_ == pLineEnd_ && index_ == indexEnd_) {
pLine_ = 0;
index_ = 0;
return *this;
}
if(startEnd_ == HEAD) {
++index_;
if(index_ == pLine_->numSegments()) {
End end = pLine_->endConnectivity(TAIL);
pLine_ = pLine_->next(TAIL);
if(end == TAIL) {
startEnd_ = TAIL;
index_ = pLine_->numSegments() -1;
} else {
index_ = 0;
}
}
} else {
if(index_ == 0) {
End end = pLine_->endConnectivity(HEAD);
pLine_ = pLine_->next(HEAD);
if(end == TAIL) {
index_ = pLine_->numSegments() -1;
} else {
startEnd_ = HEAD;
index_ = 0;
}
} else {
--index_;
}
}
return *this;
}
inline const iterator operator++(int) {
iterator tmp(*this);
++(*this);
return tmp;
}
inline bool operator==(const iterator& that) const {
return pLine_ == that.pLine_ && index_ == that.index_;
}
inline bool operator!=(const iterator& that) const {
return pLine_ != that.pLine_ || index_ != that.index_;
}
inline Unit operator*() { return (*pLine_)[index_]; }
};
/*
* iterator over holes contained within the figure
*/
typedef typename std::list::const_iterator iteratorHoles;
//default constructor
ActiveTail();
//constructor
ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp);
//constructor
ActiveTail(PolyLine* active, ActiveTail* otherTailp);
//copy constructor
ActiveTail(const ActiveTail& that);
//destructor
~ActiveTail();
//assignment operator
ActiveTail& operator=(const ActiveTail& that);
//equivalence operator
bool operator==(const ActiveTail& b) const;
/*
* comparison operators, ActiveTail objects are sortable by geometry
*/
bool operator<(const ActiveTail& b) const;
bool operator<=(const ActiveTail& b) const;
bool operator>(const ActiveTail& b) const;
bool operator>=(const ActiveTail& b) const;
/*
* get the pointer to the polyline that this is an active tail of
*/
PolyLine* getTail() const;
/*
* get the pointer to the polyline at the other end of the chain
*/
PolyLine* getOtherTail() const;
/*
* get the pointer to the activetail at the other end of the chain
*/
ActiveTail* getOtherActiveTail() const;
/*
* test if another active tail is the other end of the chain
*/
bool isOtherTail(const ActiveTail& b);
/*
* update this end of chain pointer to new polyline
*/
ActiveTail& updateTail(PolyLine* newTail);
/*
* associate a hole to this active tail by the specified policy
*/
ActiveTail* addHole(ActiveTail* hole, bool fractureHoles);
/*
* get the list of holes
*/
const std::list& getHoles() const;
/*
* copy holes from that to this
*/
void copyHoles(ActiveTail& that);
/*
* find out if solid to right
*/
bool solidToRight() const;
/*
* get coordinate (getCoord and getCoordinate are aliases for eachother)
*/
Unit getCoord() const;
Unit getCoordinate() const;
/*
* get the tail orientation
*/
orientation_2d getOrient() const;
/*
* add a coordinate to the polygon at this active tail end, properly handle degenerate edges by removing redundant coordinate
*/
void pushCoordinate(Unit coord);
/*
* write the figure that this active tail points to out to the temp buffer
*/
void writeOutFigure(std::vector& outVec, bool isHole = false) const;
/*
* write the figure that this active tail points to out through iterators
*/
void writeOutFigureItrs(iterator& beginOut, iterator& endOut, bool isHole = false, orientation_2d orient = VERTICAL) const;
iterator begin(bool isHole, orientation_2d orient) const;
iterator end() const;
/*
* write the holes that this active tail points to out through iterators
*/
void writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const;
iteratorHoles beginHoles() const;
iteratorHoles endHoles() const;
/*
* joins the two chains that the two active tail tails are ends of
* checks for closure of figure and writes out polygons appropriately
* returns a handle to a hole if one is closed
*/
static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, std::vector& outBufferTmp);
template
static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, typename std::vector& outBufferTmp);
/*
* deallocate temp buffer
*/
static void destroyOutBuffer();
/*
* deallocate all polygon data this active tail points to (deep delete, call only from one of a pair of active tails)
*/
void destroyContents();
};
/* allocate a polyline object */
template
PolyLine* createPolyLine(orientation_2d orient, Unit coord, Side side);
/* deallocate a polyline object */
template
void destroyPolyLine(PolyLine* pLine);
/* allocate an activetail object */
template
ActiveTail* createActiveTail();
/* deallocate an activetail object */
template
void destroyActiveTail(ActiveTail* aTail);
template
class PolyLineHoleData {
private:
ActiveTail* p_;
public:
typedef Unit coordinate_type;
typedef typename ActiveTail::iterator compact_iterator_type;
typedef iterator_compact_to_points > iterator_type;
inline PolyLineHoleData() : p_(0) {}
inline PolyLineHoleData(ActiveTail* p) : p_(p) {}
//use default copy and assign
inline compact_iterator_type begin_compact() const { return p_->begin(true, (orientT ? VERTICAL : HORIZONTAL)); }
inline compact_iterator_type end_compact() const { return p_->end(); }
inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); }
inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); }
inline std::size_t size() const {
return p_->getPolyLineSize();
}
inline ActiveTail* yield() { return p_; }
};
template
class PolyLinePolygonWithHolesData {
private:
ActiveTail* p_;
public:
typedef Unit coordinate_type;
typedef typename ActiveTail::iterator compact_iterator_type;
typedef iterator_compact_to_points > iterator_type;
typedef PolyLineHoleData hole_type;
typedef typename coordinate_traits::area_type area_type;
class iteratorHoles {
private:
typename ActiveTail::iteratorHoles itr_;
public:
inline iteratorHoles() : itr_() {}
inline iteratorHoles(typename ActiveTail::iteratorHoles itr) : itr_(itr) {}
//use bitwise copy and assign provided by the compiler
inline iteratorHoles& operator++() {
++itr_;
return *this;
}
inline const iteratorHoles operator++(int) {
iteratorHoles tmp(*this);
++(*this);
return tmp;
}
inline bool operator==(const iteratorHoles& that) const {
return itr_ == that.itr_;
}
inline bool operator!=(const iteratorHoles& that) const {
return itr_ != that.itr_;
}
inline PolyLineHoleData operator*() { return PolyLineHoleData(*itr_);}
};
typedef iteratorHoles iterator_holes_type;
inline PolyLinePolygonWithHolesData() : p_(0) {}
inline PolyLinePolygonWithHolesData(ActiveTail* p) : p_(p) {}
//use default copy and assign
inline compact_iterator_type begin_compact() const { return p_->begin(false, (orientT ? VERTICAL : HORIZONTAL)); }
inline compact_iterator_type end_compact() const { return p_->end(); }
inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); }
inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); }
inline iteratorHoles begin_holes() const { return iteratorHoles(p_->beginHoles()); }
inline iteratorHoles end_holes() const { return iteratorHoles(p_->endHoles()); }
inline ActiveTail* yield() { return p_; }
//stub out these four required functions that will not be used but are needed for the interface
inline std::size_t size_holes() const { return 0; }
inline std::size_t size() const { return 0; }
};
template
struct PolyLineType { };
template
struct PolyLineType { typedef PolyLinePolygonWithHolesData type; };
template
struct PolyLineType { typedef PolyLinePolygonWithHolesData type; };
template
struct PolyLineType { typedef PolyLinePolygonWithHolesData type; };
template
struct PolyLineType { typedef PolyLineHoleData type; };
template
struct PolyLineType { typedef PolyLineHoleData type; };
template
struct PolyLineType { typedef PolyLineHoleData type; };
template
class ScanLineToPolygonItrs {
private:
std::map*> tailMap_;
typedef typename PolyLineType::type PolyLinePolygonData;
std::vector outputPolygons_;
bool fractureHoles_;
public:
typedef typename std::vector::iterator iterator;
inline ScanLineToPolygonItrs() : tailMap_(), outputPolygons_(), fractureHoles_(false) {}
/* construct a scanline with the proper offsets, protocol and options */
inline ScanLineToPolygonItrs(bool fractureHoles) : tailMap_(), outputPolygons_(), fractureHoles_(fractureHoles) {}
~ScanLineToPolygonItrs() { clearOutput_(); }
/* process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */
void processEdges(iterator& beginOutput, iterator& endOutput,
Unit currentX, std::vector >& leftEdges,
std::vector >& rightEdges,
size_t vertexThreshold=(std::numeric_limits::max)() );
/**********************************************************************
*methods implementing new polygon formation code
*
**********************************************************************/
void updatePartialSimplePolygonsWithRightEdges(Unit currentX,
const std::vector >& leftEdges, size_t threshold);
void updatePartialSimplePolygonsWithLeftEdges(Unit currentX,
const std::vector >& leftEdges, size_t threshold);
void closePartialSimplePolygon(Unit, ActiveTail*, ActiveTail*);
void maintainPartialSimplePolygonInvariant(iterator& ,iterator& ,Unit,
const std::vector >&,
const std::vector >&,
size_t vertexThreshold=(std::numeric_limits::max)());
void insertNewLeftEdgeIntoTailMap(Unit, Unit, Unit,
typename std::map*>::iterator &);
/**********************************************************************/
inline size_t getTailMapSize(){
typename std::map* >::const_iterator itr;
size_t tsize = 0;
for(itr=tailMap_.begin(); itr!=tailMap_.end(); ++itr){
tsize += (itr->second)->getPolyLineSize();
}
return tsize;
}
/*print the active tails in this map:*/
inline void print(){
typename std::map* >::const_iterator itr;
printf("=========TailMap[%lu]=========\n", tailMap_.size());
for(itr=tailMap_.begin(); itr!=tailMap_.end(); ++itr){
std::cout<< "[" << itr->first << "] : " << std::endl;
//print active tail//
ActiveTail const *t = (itr->second);
PolyLine const *pBegin = t->getTail();
PolyLine const *pEnd = t->getOtherActiveTail()->getTail();
std::string sorient = pBegin->solidToRight() ? "RIGHT" : "LEFT";
std::cout<< " ActiveTail.tailp_ (solid= " << sorient ;
End dir = TAIL;
while(pBegin!=pEnd){
std::cout << pBegin << "={ ";
for(size_t i=0; inumSegments(); i++){
point_data u = pBegin->getPoint(i);
std::cout << "(" << u.x() << "," << u.y() << ") ";
}
std::cout << "} ";
pBegin = pBegin->next(dir == HEAD ? TAIL : HEAD);
dir = pBegin->endConnectivity(dir == HEAD ? TAIL : HEAD);
}
if(pEnd){
std::cout << pEnd << "={ ";
for(size_t i=0; inumSegments(); i++){
point_data u = pEnd->getPoint(i);
std::cout << "(" << u.x() << "," << u.y() << ") ";
}
std::cout << "} ";
}
std::cout << " end= " << pEnd << std::endl;
}
}
private:
void clearOutput_();
};
/*
* ScanLine does all the work of stitching together polygons from incoming vertical edges
*/
// template
// class ScanLineToPolygons {
// private:
// ScanLineToPolygonItrs scanline_;
// public:
// inline ScanLineToPolygons() : scanline_() {}
// /* construct a scanline with the proper offsets, protocol and options */
// inline ScanLineToPolygons(bool fractureHoles) : scanline_(fractureHoles) {}
// /* process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */
// inline void processEdges(std::vector& outBufferTmp, Unit currentX, std::vector >& leftEdges,
// std::vector >& rightEdges) {
// typename ScanLineToPolygonItrs::iterator itr, endItr;
// scanline_.processEdges(itr, endItr, currentX, leftEdges, rightEdges);
// //copy data into outBufferTmp
// while(itr != endItr) {
// typename PolyLinePolygonData::iterator pditr;
// outBufferTmp.push_back(0);
// unsigned int sizeIndex = outBufferTmp.size() - 1;
// int count = 0;
// for(pditr = (*itr).begin(); pditr != (*itr).end(); ++pditr) {
// outBufferTmp.push_back(*pditr);
// ++count;
// }
// outBufferTmp[sizeIndex] = count;
// typename PolyLinePolygonData::iteratorHoles pdHoleItr;
// for(pdHoleItr = (*itr).beginHoles(); pdHoleItr != (*itr).endHoles(); ++pdHoleItr) {
// outBufferTmp.push_back(0);
// unsigned int sizeIndex2 = outBufferTmp.size() - 1;
// int count2 = 0;
// for(pditr = (*pdHoleItr).begin(); pditr != (*pdHoleItr).end(); ++pditr) {
// outBufferTmp.push_back(*pditr);
// ++count2;
// }
// outBufferTmp[sizeIndex2] = -count;
// }
// ++itr;
// }
// }
// };
const int VERTICAL_HEAD = 1, HEAD_TO_TAIL = 2, TAIL_TO_TAIL = 4, SOLID_TO_RIGHT = 8;
//EVERY FUNCTION in this DEF file should be explicitly defined as inline
//microsoft compiler improperly warns whenever you cast an integer to bool
//call this function on an integer to convert it to bool without a warning
template
inline bool to_bool(const T& val) { return val != 0; }
//default constructor (for preallocation)
template
inline PolyLine::PolyLine() : ptdata_() ,headp_(0), tailp_(0), state_(-1) {}
//constructor
template
inline PolyLine::PolyLine(orientation_2d orient, Unit coord, Side side) :
ptdata_(1, coord),
headp_(0),
tailp_(0),
state_(orient.to_int() +
(side << 3)){}
//copy constructor
template
inline PolyLine::PolyLine(const PolyLine& pline) : ptdata_(pline.ptdata_),
headp_(pline.headp_),
tailp_(pline.tailp_),
state_(pline.state_) {}
//destructor
template
inline PolyLine::~PolyLine() {
//clear out data just in case it is read later
headp_ = tailp_ = 0;
state_ = 0;
}
template
inline PolyLine& PolyLine::operator=(const PolyLine& that) {
if(!(this == &that)) {
headp_ = that.headp_;
tailp_ = that.tailp_;
ptdata_ = that.ptdata_;
state_ = that.state_;
}
return *this;
}
template
inline bool PolyLine::operator==(const PolyLine& b) const {
return this == &b || (state_ == b.state_ &&
headp_ == b.headp_ &&
tailp_ == b.tailp_);
}
//valid PolyLine
template
inline bool PolyLine::isValid() const {
return state_ > -1; }
//first coordinate is an X value
//first segment is vertical
template
inline bool PolyLine::verticalHead() const {
return state_ & VERTICAL_HEAD;
}
//retrun true is PolyLine has odd number of coordiantes
template
inline bool PolyLine::oddLength() const {
return to_bool((ptdata_.size()-1) % 2);
}
//last coordiante is an X value
//last segment is vertical
template
inline bool PolyLine::verticalTail() const {
return to_bool(verticalHead() ^ oddLength());
}
template
inline orientation_2d PolyLine::tailOrient() const {
return (verticalTail() ? VERTICAL : HORIZONTAL);
}
template
inline orientation_2d PolyLine::headOrient() const {
return (verticalHead() ? VERTICAL : HORIZONTAL);
}
template
inline End PolyLine::endConnectivity(End end) const {
//Tail should be defined as true
if(end) { return tailToTail(); }
return headToTail();
}
template
inline bool PolyLine::headToTail() const {
return to_bool(state_ & HEAD_TO_TAIL);
}
template
inline bool PolyLine::headToHead() const {
return to_bool(!headToTail());
}
template
inline bool PolyLine::tailToHead() const {
return to_bool(!tailToTail());
}
template
inline bool PolyLine::tailToTail() const {
return to_bool(state_ & TAIL_TO_TAIL);
}
template
inline Side PolyLine::solidSide() const {
return solidToRight(); }
template
inline bool PolyLine::solidToRight() const {
return to_bool(state_ & SOLID_TO_RIGHT) != 0;
}
template
inline bool PolyLine::active() const {
return !to_bool(tailp_);
}
template
inline PolyLine& PolyLine::pushCoordinate(Unit coord) {
ptdata_.push_back(coord);
return *this;
}
template
inline PolyLine& PolyLine::popCoordinate() {
ptdata_.pop_back();
return *this;
}
template
inline PolyLine& PolyLine::pushPoint(const point_data& point) {
if(numSegments()){
point_data endPt = getEndPoint();
//vertical is true, horizontal is false
if((tailOrient().to_int() ? point.get(VERTICAL) == endPt.get(VERTICAL) : point.get(HORIZONTAL) == endPt.get(HORIZONTAL))) {
//we were pushing a colinear segment
return popCoordinate();
}
}
return pushCoordinate(tailOrient().to_int() ? point.get(VERTICAL) : point.get(HORIZONTAL));
}
template
inline PolyLine& PolyLine::extendTail(Unit delta) {
ptdata_.back() += delta;
return *this;
}
//private member function that creates a link from this PolyLine to that
template
inline PolyLine& PolyLine::joinTo_(End thisEnd, PolyLine& that, End end) {
if(thisEnd){
tailp_ = &that;
state_ &= ~TAIL_TO_TAIL; //clear any previous state_ of bit (for safety)
state_ |= (end << 2); //place bit into mask
} else {
headp_ = &that;
state_ &= ~HEAD_TO_TAIL; //clear any previous state_ of bit (for safety)
state_ |= (end << 1); //place bit into mask
}
return *this;
}
//join two PolyLines (both ways of the association)
template
inline PolyLine& PolyLine::joinTo(End thisEnd, PolyLine& that, End end) {
joinTo_(thisEnd, that, end);
that.joinTo_(end, *this, thisEnd);
return *this;
}
//convenience functions for joining PolyLines
template
inline PolyLine& PolyLine::joinToTail(PolyLine& that, End end) {
return joinTo(TAIL, that, end);
}
template
inline PolyLine& PolyLine::joinToHead(PolyLine& that, End end) {
return joinTo(HEAD, that, end);
}
template
inline PolyLine& PolyLine::joinHeadToHead(PolyLine& that) {
return joinToHead(that, HEAD);
}
template
inline PolyLine& PolyLine::joinHeadToTail(PolyLine& that) {
return joinToHead(that, TAIL);
}
template
inline PolyLine& PolyLine::joinTailToHead(PolyLine& that) {
return joinToTail(that, HEAD);
}
template
inline PolyLine& PolyLine::joinTailToTail(PolyLine& that) {
return joinToTail(that, TAIL);
}
template
inline PolyLine& PolyLine::disconnectTails() {
next(TAIL)->state_ &= !TAIL_TO_TAIL;
next(TAIL)->tailp_ = 0;
state_ &= !TAIL_TO_TAIL;
tailp_ = 0;
return *this;
}
template
inline Unit PolyLine::getEndCoord(End end) const {
if(end)
return ptdata_.back();
return ptdata_.front();
}
template
inline orientation_2d PolyLine::segmentOrient(unsigned int index) const {
return (to_bool((unsigned int)verticalHead() ^ (index % 2)) ? VERTICAL : HORIZONTAL);
}
template
inline point_data PolyLine::getPoint(unsigned int index) const {
//assert(isValid() && headp_->isValid()) ("PolyLine: headp_ must be valid");
point_data pt;
pt.set(HORIZONTAL, ptdata_[index]);
pt.set(VERTICAL, ptdata_[index]);
Unit prevCoord;
if(index == 0) {
prevCoord = headp_->getEndCoord(headToTail());
} else {
prevCoord = ptdata_[index-1];
}
pt.set(segmentOrient(index), prevCoord);
return pt;
}
template
inline point_data PolyLine::getEndPoint(End end) const {
return getPoint((end ? numSegments() - 1 : (unsigned int)0));
}
template
inline Unit PolyLine::operator[] (unsigned int index) const {
//assert(ptdata_.size() > index) ("PolyLine: out of bounds index");
return ptdata_[index];
}
template
inline unsigned int PolyLine::numSegments() const {
return ptdata_.size();
}
template
inline PolyLine* PolyLine::next(End end) const {
return (end ? tailp_ : headp_);
}
template
inline ActiveTail::ActiveTail() : tailp_(0), otherTailp_(0), holesList_(),
polyLineSize_(0) {}
template
inline ActiveTail::ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp) :
tailp_(0), otherTailp_(0), holesList_(), polyLineSize_(0) {
tailp_ = createPolyLine(orient, coord, solidToRight);
otherTailp_ = otherTailp;
polyLineSize_ = tailp_->numSegments();
}
template
inline ActiveTail::ActiveTail(PolyLine* active, ActiveTail* otherTailp) :
tailp_(active), otherTailp_(otherTailp), holesList_(),
polyLineSize_(0) {}
//copy constructor
template
inline ActiveTail::ActiveTail(const ActiveTail& that) : tailp_(that.tailp_), otherTailp_(that.otherTailp_), holesList_(), polyLineSize_(that.polyLineSize_) {}
//destructor
template
inline ActiveTail::~ActiveTail() {
//clear them in case the memory is read later
tailp_ = 0; otherTailp_ = 0;
}
template
inline ActiveTail& ActiveTail::operator=(const ActiveTail& that) {
//self assignment is safe in this case
tailp_ = that.tailp_;
otherTailp_ = that.otherTailp_;
polyLineSize_ = that.polyLineSize_;
return *this;
}
template
inline bool ActiveTail::operator==(const ActiveTail& b) const {
return tailp_ == b.tailp_ && otherTailp_ == b.otherTailp_;
}
template
inline bool ActiveTail::operator<(const ActiveTail& b) const {
return tailp_->getEndPoint().get(VERTICAL) < b.tailp_->getEndPoint().get(VERTICAL);
}
template
inline bool ActiveTail::operator<=(const ActiveTail& b) const {
return !(*this > b); }
template
inline bool ActiveTail::operator>(const ActiveTail& b) const {
return b < (*this); }
template
inline bool ActiveTail::operator>=(const ActiveTail& b) const {
return !(*this < b); }
template
inline PolyLine* ActiveTail::getTail() const {
return tailp_; }
template
inline PolyLine