|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r86009 - in branches/release: boost/polygon boost/polygon/detail libs/polygon/benchmark libs/polygon/doc libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2013-09-29 14:44:36
Author: asydorchuk
Date: 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013)
New Revision: 86009
URL: http://svn.boost.org/trac/boost/changeset/86009
Log:
Polygon: Merging trunk into the release branch.
Text files modified:
branches/release/boost/polygon/detail/polygon_45_touch.hpp | 4
branches/release/boost/polygon/detail/polygon_formation.hpp | 791 ++++++++++++++++++++++++++++++++-------
branches/release/boost/polygon/detail/voronoi_predicates.hpp | 350 ++++++++--------
branches/release/boost/polygon/detail/voronoi_structures.hpp | 45 -
branches/release/boost/polygon/polygon_90_set_data.hpp | 28 +
branches/release/boost/polygon/voronoi_builder.hpp | 2
branches/release/libs/polygon/benchmark/Jamfile.v2 | 19
branches/release/libs/polygon/benchmark/voronoi_benchmark_points.cpp | 78 ++-
branches/release/libs/polygon/benchmark/voronoi_benchmark_segments.cpp | 97 +++-
branches/release/libs/polygon/doc/gtl_polygon_90_set_concept.htm | 86 +--
branches/release/libs/polygon/test/Jamfile.v2 | 5
branches/release/libs/polygon/test/gtl_boost_unit_test.cpp | 248 ++++++++++++
branches/release/libs/polygon/test/voronoi_predicates_test.cpp | 171 +++++--
branches/release/libs/polygon/test/voronoi_structures_test.cpp | 70 +-
14 files changed, 1424 insertions(+), 570 deletions(-)
Modified: branches/release/boost/polygon/detail/polygon_45_touch.hpp
==============================================================================
--- branches/release/boost/polygon/detail/polygon_45_touch.hpp Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/boost/polygon/detail/polygon_45_touch.hpp 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -65,8 +65,8 @@
inline CountTouch& operator=(const CountTouch& count) { counts = count.counts; return *this; }
inline int& operator[](int index) {
std::vector<std::pair<int, int> >::iterator itr =
- std::lower_bound(counts.begin(), counts.end(),
- std::make_pair(index, int(0)));
+ std::lower_bound(counts.begin(), counts.end(),
+ std::make_pair(index, int(0)));
if(itr != counts.end() && itr->first == index) {
return itr->second;
}
Modified: branches/release/boost/polygon/detail/polygon_formation.hpp
==============================================================================
--- branches/release/boost/polygon/detail/polygon_formation.hpp Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/boost/polygon/detail/polygon_formation.hpp 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -1,10 +1,12 @@
/*
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<iostream>
+#include<cassert>
#ifndef BOOST_POLYGON_POLYGON_FORMATION_HPP
#define BOOST_POLYGON_POLYGON_FORMATION_HPP
namespace boost { namespace polygon{
@@ -25,24 +27,24 @@
* 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.
+ * 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.
@@ -59,14 +61,14 @@
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<Unit> ptdata_;
-
+
/*
* head and tail points to other polylines before and after this in a chain
*/
@@ -87,18 +89,18 @@
* 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);
@@ -118,18 +120,18 @@
/*
* returns true if first coordinate is an X value (first segment is vertical)
*/
- bool verticalHead() const;
+ 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
*/
@@ -157,7 +159,7 @@
* 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
*/
@@ -177,12 +179,12 @@
* 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
*/
@@ -299,7 +301,7 @@
* 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
+ * 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,
@@ -314,11 +316,25 @@
class ActiveTail {
private:
//data
- PolyLine<Unit>* tailp_;
+ PolyLine<Unit>* tailp_;
ActiveTail *otherTailp_;
std::list<ActiveTail*> 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
*/
@@ -331,7 +347,7 @@
End startEnd_;
public:
inline iterator() : pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() {}
- inline iterator(const ActiveTail* at, bool isHole, orientation_2d orient) :
+ 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
@@ -343,7 +359,10 @@
//now we have the right winding direction
//if it is horizontal we need to skip the first element
pLine_ = at->getTail();
- index_ = at->getTail()->numSegments() - 1;
+
+ if(at->getTail()->numSegments() > 0)
+ index_ = at->getTail()->numSegments() - 1;
+
if((at->getOrient() == HORIZONTAL) ^ (orient == HORIZONTAL)) {
pLineEnd_ = at->getTail();
indexEnd_ = pLineEnd_->numSegments() - 1;
@@ -358,10 +377,27 @@
} 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<Unit> 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_) {
@@ -560,7 +596,7 @@
/* deallocate an activetail object */
template <typename Unit>
void destroyActiveTail(ActiveTail<Unit>* aTail);
-
+
template<bool orientT, typename Unit>
class PolyLineHoleData {
private:
@@ -576,7 +612,9 @@
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 0; }
+ inline std::size_t size() const {
+ return p_->getPolyLineSize();
+ }
inline ActiveTail<Unit>* yield() { return p_; }
template<class iT>
inline PolyLineHoleData& set(iT inputBegin, iT inputEnd) {
@@ -586,7 +624,7 @@
inline PolyLineHoleData& set_compact(iT inputBegin, iT inputEnd) {
return *this;
}
-
+
};
template<bool orientT, typename Unit>
@@ -646,7 +684,7 @@
inline PolyLinePolygonWithHolesData& set_compact(iT inputBegin, iT inputEnd) {
return *this;
}
-
+
// initialize a polygon from x,y values, it is assumed that the first is an x
// and that the input is a well behaved polygon
template<class iT>
@@ -679,18 +717,83 @@
std::vector<PolyLinePolygonData> outputPolygons_;
bool fractureHoles_;
public:
- typedef typename std::vector<PolyLinePolygonData>::iterator iterator;
+ typedef typename std::vector<PolyLinePolygonData>::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<interval_data<Unit> >& leftEdges,
- std::vector<interval_data<Unit> >& rightEdges);
-
+ void processEdges(iterator& beginOutput, iterator& endOutput,
+ Unit currentX, std::vector<interval_data<Unit> >& leftEdges,
+ std::vector<interval_data<Unit> >& rightEdges,
+ size_t vertexThreshold=(std::numeric_limits<size_t>::max)() );
+
+ /**********************************************************************
+ *methods implementing new polygon formation code
+ *
+ **********************************************************************/
+ void updatePartialSimplePolygonsWithRightEdges(Unit currentX,
+ const std::vector<interval_data<Unit> >& leftEdges, size_t threshold);
+
+ void updatePartialSimplePolygonsWithLeftEdges(Unit currentX,
+ const std::vector<interval_data<Unit> >& leftEdges, size_t threshold);
+
+ void closePartialSimplePolygon(Unit, ActiveTail<Unit>*, ActiveTail<Unit>*);
+
+ void maintainPartialSimplePolygonInvariant(iterator& ,iterator& ,Unit,
+ const std::vector<interval_data<Unit> >&,
+ const std::vector<interval_data<Unit> >&,
+ size_t vertexThreshold=(std::numeric_limits<size_t>::max)());
+
+ void insertNewLeftEdgeIntoTailMap(Unit, Unit, Unit,
+ typename std::map<Unit, ActiveTail<Unit>*>::iterator &);
+ /**********************************************************************/
+
+ inline size_t getTailMapSize(){
+ typename std::map<Unit, ActiveTail<Unit>* >::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<Unit, ActiveTail<Unit>* >::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<Unit> const *t = (itr->second);
+ PolyLine<Unit> const *pBegin = t->getTail();
+ PolyLine<Unit> 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; i<pBegin->numSegments(); i++){
+ point_data<Unit> 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; i<pEnd->numSegments(); i++){
+ point_data<Unit> u = pEnd->getPoint(i);
+ std::cout << "(" << u.x() << "," << u.y() << ") ";
+ }
+ std::cout << "} ";
+ }
+ std::cout << " end= " << pEnd << std::endl;
+ }
+ }
+
private:
void clearOutput_();
};
@@ -706,9 +809,9 @@
// 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<Unit>& outBufferTmp, Unit currentX, std::vector<interval_data<Unit> >& leftEdges,
+// inline void processEdges(std::vector<Unit>& outBufferTmp, Unit currentX, std::vector<interval_data<Unit> >& leftEdges,
// std::vector<interval_data<Unit> >& rightEdges) {
// typename ScanLineToPolygonItrs<true, Unit>::iterator itr, endItr;
// scanline_.processEdges(itr, endItr, currentX, leftEdges, rightEdges);
@@ -754,12 +857,12 @@
//constructor
template <typename Unit>
- inline PolyLine<Unit>::PolyLine(orientation_2d orient, Unit coord, Side side) :
+ inline PolyLine<Unit>::PolyLine(orientation_2d orient, Unit coord, Side side) :
ptdata_(1, coord),
headp_(0),
tailp_(0),
state_(orient.to_int() +
- (side << 3)) {}
+ (side << 3)){}
//copy constructor
template <typename Unit>
@@ -796,7 +899,7 @@
//valid PolyLine
template <typename Unit>
- inline bool PolyLine<Unit>::isValid() const {
+ inline bool PolyLine<Unit>::isValid() const {
return state_ > -1; }
//first coordinate is an X value
@@ -818,7 +921,7 @@
inline bool PolyLine<Unit>::verticalTail() const {
return to_bool(verticalHead() ^ oddLength());
}
-
+
template <typename Unit>
inline orientation_2d PolyLine<Unit>::tailOrient() const {
return (verticalTail() ? VERTICAL : HORIZONTAL);
@@ -850,16 +953,16 @@
inline bool PolyLine<Unit>::tailToHead() const {
return to_bool(!tailToTail());
}
-
+
template <typename Unit>
inline bool PolyLine<Unit>::tailToTail() const {
return to_bool(state_ & TAIL_TO_TAIL);
}
template <typename Unit>
- inline Side PolyLine<Unit>::solidSide() const {
+ inline Side PolyLine<Unit>::solidSide() const {
return solidToRight(); }
-
+
template <typename Unit>
inline bool PolyLine<Unit>::solidToRight() const {
return to_bool(state_ & SOLID_TO_RIGHT) != 0;
@@ -884,12 +987,14 @@
template <typename Unit>
inline PolyLine<Unit>& PolyLine<Unit>::pushPoint(const point_data<Unit>& point) {
- point_data<Unit> 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();
- }
+ if(numSegments()){
+ point_data<Unit> 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));
}
@@ -1007,28 +1112,31 @@
}
template <typename Unit>
- inline ActiveTail<Unit>::ActiveTail() : tailp_(0), otherTailp_(0), holesList_() {}
+ inline ActiveTail<Unit>::ActiveTail() : tailp_(0), otherTailp_(0), holesList_(),
+ polyLineSize_(0) {}
template <typename Unit>
- inline ActiveTail<Unit>::ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp) :
- tailp_(0), otherTailp_(0), holesList_() {
+ inline ActiveTail<Unit>::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 <typename Unit>
- inline ActiveTail<Unit>::ActiveTail(PolyLine<Unit>* active, ActiveTail<Unit>* otherTailp) :
- tailp_(active), otherTailp_(otherTailp), holesList_() {}
+ inline ActiveTail<Unit>::ActiveTail(PolyLine<Unit>* active, ActiveTail<Unit>* otherTailp) :
+ tailp_(active), otherTailp_(otherTailp), holesList_(),
+ polyLineSize_(0) {}
//copy constructor
template <typename Unit>
- inline ActiveTail<Unit>::ActiveTail(const ActiveTail<Unit>& that) : tailp_(that.tailp_), otherTailp_(that.otherTailp_), holesList_() {}
+ inline ActiveTail<Unit>::ActiveTail(const ActiveTail<Unit>& that) : tailp_(that.tailp_), otherTailp_(that.otherTailp_), holesList_(), polyLineSize_(that.polyLineSize_) {}
//destructor
template <typename Unit>
- inline ActiveTail<Unit>::~ActiveTail() {
+ inline ActiveTail<Unit>::~ActiveTail() {
//clear them in case the memory is read later
- tailp_ = 0; otherTailp_ = 0;
+ tailp_ = 0; otherTailp_ = 0;
}
template <typename Unit>
@@ -1036,6 +1144,7 @@
//self assignment is safe in this case
tailp_ = that.tailp_;
otherTailp_ = that.otherTailp_;
+ polyLineSize_ = that.polyLineSize_;
return *this;
}
@@ -1050,45 +1159,50 @@
}
template <typename Unit>
- inline bool ActiveTail<Unit>::operator<=(const ActiveTail<Unit>& b) const {
+ inline bool ActiveTail<Unit>::operator<=(const ActiveTail<Unit>& b) const {
return !(*this > b); }
-
+
template <typename Unit>
- inline bool ActiveTail<Unit>::operator>(const ActiveTail<Unit>& b) const {
+ inline bool ActiveTail<Unit>::operator>(const ActiveTail<Unit>& b) const {
return b < (*this); }
-
+
template <typename Unit>
- inline bool ActiveTail<Unit>::operator>=(const ActiveTail<Unit>& b) const {
+ inline bool ActiveTail<Unit>::operator>=(const ActiveTail<Unit>& b) const {
return !(*this < b); }
template <typename Unit>
- inline PolyLine<Unit>* ActiveTail<Unit>::getTail() const {
+ inline PolyLine<Unit>* ActiveTail<Unit>::getTail() const {
return tailp_; }
template <typename Unit>
- inline PolyLine<Unit>* ActiveTail<Unit>::getOtherTail() const {
+ inline PolyLine<Unit>* ActiveTail<Unit>::getOtherTail() const {
return otherTailp_->tailp_; }
template <typename Unit>
- inline ActiveTail<Unit>* ActiveTail<Unit>::getOtherActiveTail() const {
+ inline ActiveTail<Unit>* ActiveTail<Unit>::getOtherActiveTail() const {
return otherTailp_; }
template <typename Unit>
inline bool ActiveTail<Unit>::isOtherTail(const ActiveTail<Unit>& b) {
// assert( (tailp_ == b.getOtherTail() && getOtherTail() == b.tailp_) ||
- // (tailp_ != b.getOtherTail() && getOtherTail() != b.tailp_))
+ // (tailp_ != b.getOtherTail() && getOtherTail() != b.tailp_))
// ("ActiveTail: Active tails out of sync");
return otherTailp_ == &b;
}
template <typename Unit>
inline ActiveTail<Unit>& ActiveTail<Unit>::updateTail(PolyLine<Unit>* newTail) {
+ //subtract the old size and add new size//
+ int delta = newTail->numSegments() - tailp_->numSegments();
+ addPolyLineSize(delta);
+ otherTailp_->addPolyLineSize(delta);
tailp_ = newTail;
return *this;
}
template <typename Unit>
inline ActiveTail<Unit>* ActiveTail<Unit>::addHole(ActiveTail<Unit>* hole, bool fractureHoles) {
+
if(!fractureHoles){
holesList_.push_back(hole);
copyHoles(*hole);
@@ -1100,7 +1214,7 @@
if(other->getOrient() == VERTICAL) {
//assert that hole.getOrient() == HORIZONTAL
//this case should never happen
- h = hole;
+ h = hole;
v = other;
} else {
//assert that hole.getOrient() == VERTICAL
@@ -1128,30 +1242,34 @@
}
template <typename Unit>
- inline bool ActiveTail<Unit>::solidToRight() const {
+ inline bool ActiveTail<Unit>::solidToRight() const {
return getTail()->solidToRight(); }
template <typename Unit>
- inline Unit ActiveTail<Unit>::getCoord() const {
+ inline Unit ActiveTail<Unit>::getCoord() const {
return getTail()->getEndCoord(); }
-
+
template <typename Unit>
- inline Unit ActiveTail<Unit>::getCoordinate() const {
- return getCoord(); }
+ inline Unit ActiveTail<Unit>::getCoordinate() const {
+ return getCoord(); }
template <typename Unit>
- inline orientation_2d ActiveTail<Unit>::getOrient() const {
+ inline orientation_2d ActiveTail<Unit>::getOrient() const {
return getTail()->tailOrient(); }
template <typename Unit>
- inline void ActiveTail<Unit>::pushCoordinate(Unit coord) {
+ inline void ActiveTail<Unit>::pushCoordinate(Unit coord) {
//appropriately handle any co-linear polyline segments by calling push point internally
point_data<Unit> p;
p.set(HORIZONTAL, coord);
p.set(VERTICAL, coord);
//if we are vertical assign the last coordinate (an X) to p.x, else to p.y
p.set(getOrient().get_perpendicular(), getCoordinate());
+ int oldSegments = tailp_->numSegments();
tailp_->pushPoint(p);
+ int delta = tailp_->numSegments() - oldSegments;
+ addPolyLineSize(delta);
+ otherTailp_->addPolyLineSize(delta);
}
@@ -1241,16 +1359,16 @@
if((getOrient() == HORIZONTAL) ^ !isHole) {
//our first coordinate is a y value, so we need to rotate it to the end
typename std::vector<Unit>::iterator tmpItr = outVec.begin();
- tmpItr += size;
+ tmpItr += size;
outVec.erase(++tmpItr); //erase the 2nd element
}
End startEnd = tailp_->endConnectivity(HEAD);
if(isHole) startEnd = otherTailp_->tailp_->endConnectivity(HEAD);
while(nextPolyLinep) {
bool nextStartEnd = nextPolyLinep->endConnectivity(!startEnd);
- nextPolyLinep = nextPolyLinep->writeOut(outVec, startEnd);
+ nextPolyLinep = nextPolyLinep->writeOut(outVec, startEnd);
startEnd = nextStartEnd;
- }
+ }
if((getOrient() == HORIZONTAL) ^ !isHole) {
//we want to push the y value onto the end since we ought to have ended with an x
outVec.push_back(firsty); //should never be executed because we want first value to be an x
@@ -1284,7 +1402,7 @@
//solid indicates if it was joined by a solit or a space
template <typename Unit>
- inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, std::vector<Unit>& outBufferTmp)
+ inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, std::vector<Unit>& outBufferTmp)
{
//checks to see if we closed a figure
if(at1->isOtherTail(*at2)){
@@ -1324,6 +1442,11 @@
at1->getTail()->joinTailToTail(*(at2->getTail()));
*(at1->getOtherActiveTail()) = ActiveTail(at1->getOtherTail(), at2->getOtherActiveTail());
*(at2->getOtherActiveTail()) = ActiveTail(at2->getOtherTail(), at1->getOtherActiveTail());
+
+ int accumulate = at2->getPolyLineSize() + at1->getPolyLineSize();
+ (at1->getOtherActiveTail())->setPolyLineSize(accumulate);
+ (at2->getOtherActiveTail())->setPolyLineSize(accumulate);
+
at1->getOtherActiveTail()->copyHoles(*at1);
at1->getOtherActiveTail()->copyHoles(*at2);
destroyActiveTail(at1);
@@ -1334,7 +1457,7 @@
//solid indicates if it was joined by a solit or a space
template <typename Unit>
template <typename PolygonT>
- inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid,
+ inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid,
std::vector<PolygonT>& outBufferTmp) {
//checks to see if we closed a figure
if(at1->isOtherTail(*at2)){
@@ -1348,7 +1471,7 @@
//because otherwise it would have to have another vertex to the right of this one
//and would not be closed at this point
return at1;
- } else {
+ } else {
//assert pG != 0
//the figure that was closed is a shell
outBufferTmp.push_back(at1);
@@ -1360,6 +1483,11 @@
at1->getTail()->joinTailToTail(*(at2->getTail()));
*(at1->getOtherActiveTail()) = ActiveTail<Unit>(at1->getOtherTail(), at2->getOtherActiveTail());
*(at2->getOtherActiveTail()) = ActiveTail<Unit>(at2->getOtherTail(), at1->getOtherActiveTail());
+
+ int accumulate = at2->getPolyLineSize() + at1->getPolyLineSize();
+ (at1->getOtherActiveTail())->setPolyLineSize(accumulate);
+ (at2->getOtherActiveTail())->setPolyLineSize(accumulate);
+
at1->getOtherActiveTail()->copyHoles(*at1);
at1->getOtherActiveTail()->copyHoles(*at2);
destroyActiveTail(at1);
@@ -1367,8 +1495,8 @@
return 0;
}
- template <class TKey, class T> inline typename std::map<TKey, T>::iterator findAtNext(std::map<TKey, T>& theMap,
- typename std::map<TKey, T>::iterator pos, const TKey& key)
+ template <class TKey, class T> inline typename std::map<TKey, T>::iterator findAtNext(std::map<TKey, T>& theMap,
+ typename std::map<TKey, T>::iterator pos, const TKey& key)
{
if(pos == theMap.end()) return theMap.find(key);
//if they match the mapItr is pointing to the correct position
@@ -1377,22 +1505,22 @@
}
if(pos->first > key) {
return theMap.end();
- }
+ }
//else they are equal and no need to do anything to the iterator
return pos;
}
// createActiveTailsAsPair is called in these two end cases of geometry
// 1. lower left concave corner
+ // ###|
// ###|
- // ###|
- // ###|###
+ // ###|###
// ###|###
// 2. lower left convex corner
- // |###
- // |###
- // |
- // |
+ // |###
+ // |###
+ // |
+ // |
// In case 1 there may be a hole propigated up from the bottom. If the fracture option is enabled
// the two active tails that form the filament fracture line edges can become the new active tail pair
// by pushing x and y onto them. Otherwise the hole simply needs to be associated to one of the new active tails
@@ -1408,7 +1536,11 @@
(*at2) = ActiveTail<Unit>(HORIZONTAL, y, !solid, at1);
//provide a function through activeTail class to provide this
at1->getTail()->joinHeadToHead(*(at2->getTail()));
- if(phole)
+
+ at1->addPolyLineSize(1);
+ at2->addPolyLineSize(1);
+
+ if(phole)
at1->addHole(phole, fractureHoles); //assert fractureHoles == false
return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2);
}
@@ -1425,118 +1557,486 @@
at1->pushCoordinate(x);
//assert at2 is vertical
at2->pushCoordinate(y);
+
return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2);
}
+ /*
+ * |
+ * |
+ * =
+ * |########
+ * |######## (add a new ActiveTail in the tailMap_).
+ * |########
+ * |########
+ * |########
+ * =
+ * |
+ * |
+ *
+ * NOTE: Call this only if you are sure that the $ledege$ is not in the tailMap_
+ */
+ template<bool orientT, typename Unit, typename polygon_concept_type>
+ inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
+ insertNewLeftEdgeIntoTailMap(Unit currentX, Unit yBegin, Unit yEnd,
+ typename std::map<Unit, ActiveTail<Unit> *>::iterator &hint){
+ ActiveTail<Unit> *currentTail = NULL;
+ std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair =
+ createActiveTailsAsPair(currentX, yBegin, true, currentTail,
+ fractureHoles_);
+ currentTail = tailPair.first;
+ if(!tailMap_.empty()){
+ ++hint;
+ }
+ hint = tailMap_.insert(hint, std::make_pair(yBegin, tailPair.second));
+ currentTail->pushCoordinate(yEnd); ++hint;
+ hint = tailMap_.insert(hint, std::make_pair(yEnd, currentTail));
+ }
+
+ template<bool orientT, typename Unit, typename polygon_concept_type>
+ inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
+ closePartialSimplePolygon(Unit currentX, ActiveTail<Unit>*pfig,
+ ActiveTail<Unit>*ppfig){
+ pfig->pushCoordinate(currentX);
+ ActiveTail<Unit>::joinChains(pfig, ppfig, false, outputPolygons_);
+ }
+ /*
+ * If the invariant is maintained correctly then left edges can do the
+ * following.
+ *
+ * =###
+ * #######
+ * #######
+ * #######
+ * #######
+ * =###
+ * |### (input left edge)
+ * |###
+ * =###
+ * #######
+ * #######
+ * =###
+ */
+ template<bool orientT, typename Unit, typename polygon_concept_type>
+ inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
+ updatePartialSimplePolygonsWithLeftEdges(Unit currentX,
+ const std::vector<interval_data<Unit> > &leftEdges, size_t vertexThreshold){
+ typename std::map<Unit, ActiveTail<Unit>* >::iterator succ, succ1;
+ typename std::map<Unit, ActiveTail<Unit>* >::iterator pred, pred1, hint;
+ Unit begin, end;
+ ActiveTail<Unit> *pfig, *ppfig;
+ std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair;
+ size_t pfig_size = 0;
+
+ hint = tailMap_.begin();
+ for(size_t i=0; i < leftEdges.size(); i++){
+ begin = leftEdges[i].get(LOW); end = leftEdges[i].get(HIGH);
+ succ = findAtNext(tailMap_, hint, begin);
+ pred = findAtNext(tailMap_, hint, end);
+
+ if(succ != tailMap_.end() && pred != tailMap_.end()){ //CASE-1//
+ //join the corresponding active tails//
+ pfig = succ->second; ppfig = pred->second;
+ pfig_size = pfig->getPolyLineSize() + ppfig->getPolyLineSize();
+
+ if(pfig_size >= vertexThreshold){
+ size_t bsize = pfig->getPolyLineSize();
+ size_t usize = ppfig->getPolyLineSize();
+
+ if(usize+2 < vertexThreshold){
+ //cut-off the lower piece (succ1, succ) join (succ1, pred)//
+ succ1 = succ; --succ1;
+ assert((succ1 != tailMap_.end()) &&
+ ((succ->second)->getOtherActiveTail() == succ1->second));
+ closePartialSimplePolygon(currentX, succ1->second, succ->second);
+ tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first,
+ true, NULL, fractureHoles_);
+
+ //just update the succ1 with new ActiveTail<Unit>*//
+ succ1->second = tailPair.second;
+ ActiveTail<Unit>::joinChains(tailPair.first, pred->second, true,
+ outputPolygons_);
+ }else if(bsize+2 < vertexThreshold){
+ //cut-off the upper piece () join ()//
+ pred1 = pred; ++pred1;
+ assert(pred1 != tailMap_.end() &&
+ ((pred1->second)->getOtherActiveTail() == pred->second));
+ closePartialSimplePolygon(currentX, pred->second, pred1->second);
+
+ //just update the pred1 with ActiveTail<Unit>* = pfig//
+ pred1->second = pfig;
+ pfig->pushCoordinate(currentX);
+ pfig->pushCoordinate(pred1->first);
+ }else{
+ //cut both and create an left edge between (pred->first, succ1)//
+ succ1 = succ; --succ1;
+ pred1 = pred; ++pred1;
+ assert(pred1 != tailMap_.end() && succ1 != tailMap_.end());
+ assert((pred1->second)->getOtherActiveTail() == pred->second);
+ assert((succ1->second)->getOtherActiveTail() == succ->second);
+
+ closePartialSimplePolygon(currentX, succ1->second, succ->second);
+ closePartialSimplePolygon(currentX, pred->second, pred1->second);
+
+ tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first,
+ true, NULL, fractureHoles_);
+ succ1->second = tailPair.second;
+ pred1->second = tailPair.first;
+ (tailPair.first)->pushCoordinate(pred1->first);
+ }
+ }else{
+ //just join them with closing//
+ pfig->pushCoordinate(currentX);
+ ActiveTail<Unit>::joinChains(pfig, ppfig, true, outputPolygons_);
+ }
+ hint = pred; ++hint;
+ tailMap_.erase(succ); tailMap_.erase(pred);
+ }else if(succ == tailMap_.end() && pred != tailMap_.end()){ //CASE-2//
+ //succ is missing in the map, first insert it into the map//
+ tailPair = createActiveTailsAsPair<Unit>(currentX, begin, true, NULL,
+ fractureHoles_);
+ hint = pred; ++hint;
+ hint = tailMap_.insert(hint, std::make_pair(begin, tailPair.second));
+
+ pfig = pred->second;
+ pfig_size = pfig->getPolyLineSize() + 2;
+ if(pfig_size >= vertexThreshold){
+ //cut-off piece from [pred, pred1] , add [begin, pred1]//
+ pred1 = pred; ++pred1;
+ assert((pred1 != tailMap_.end()) &&
+ ((pred1->second)->getOtherActiveTail() == pred->second));
+ closePartialSimplePolygon(currentX, pred->second, pred1->second);
+
+ //update: we need left edge between (begin, pred1->first)//
+ pred1->second = tailPair.first;
+ (tailPair.first)->pushCoordinate(pred1->first);
+ }else{
+ //just join//
+ ActiveTail<Unit>::joinChains(tailPair.first, pfig,
+ true, outputPolygons_);
+ }
+ tailMap_.erase(pred);
+ }else if(succ != tailMap_.end() && pred == tailMap_.end()){ //CASE-3//
+ //pred is missing in the map, first insert it into the map//
+ hint = succ; ++hint;
+ hint = tailMap_.insert(hint, std::make_pair(end, (ActiveTail<Unit> *) NULL));
+ pfig = succ->second;
+ pfig_size = pfig->getPolyLineSize() + 2;
+ if(pfig_size >= vertexThreshold){
+ //this figure needs cutting here//
+ succ1 = succ; --succ1;
+ assert((succ1 != tailMap_.end()) &&
+ (succ1->second == pfig->getOtherActiveTail()));
+ ppfig = succ1->second;
+ closePartialSimplePolygon(currentX, ppfig, pfig);
+
+ //update: we need a left edge between (succ1->first, end)//
+ tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first,
+ true, NULL, fractureHoles_);
+ succ1->second = tailPair.second;
+ hint->second = tailPair.first;
+ (tailPair.first)->pushCoordinate(end);
+ }else{
+ //no cutting needed//
+ hint->second = pfig;
+ pfig->pushCoordinate(currentX);
+ pfig->pushCoordinate(end);
+ }
+ tailMap_.erase(succ);
+ }else{
+ //insert both pred and succ//
+ insertNewLeftEdgeIntoTailMap(currentX, begin, end, hint);
+ }
+ }
+ }
+
+ template<bool orientT, typename Unit, typename polygon_concept_type>
+ inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
+ updatePartialSimplePolygonsWithRightEdges(Unit currentX,
+ const std::vector<interval_data<Unit> > &rightEdges, size_t vertexThreshold)
+ {
+
+ typename std::map<Unit, ActiveTail<Unit>* >::iterator succ, pred, hint;
+ std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair;
+ Unit begin, end;
+ size_t i = 0;
+ //If rightEdges is non-empty Then tailMap_ is non-empty //
+ assert(rightEdges.empty() || !tailMap_.empty() );
+
+ while( i < rightEdges.size() ){
+ //find the interval in the tailMap which contains this interval//
+ pred = tailMap_.lower_bound(rightEdges[i].get(HIGH));
+ assert(pred != tailMap_.end());
+ succ = pred; --succ;
+ assert(pred != succ);
+ end = pred->first; begin = succ->first;
+
+ //we now have a [begin, end] //
+ bool found_solid_opening = false;
+ bool erase_succ = true, erase_pred = true;
+ Unit solid_opening_begin = 0;
+ Unit solid_opening_end = 0;
+ size_t j = i+1;
+ ActiveTail<Unit> *pfig = succ->second;
+ ActiveTail<Unit> *ppfig = pred->second;
+ size_t partial_fig_size = pfig->getPolyLineSize();
+ //Invariant://
+ assert(succ->second && (pfig)->getOtherActiveTail() == ppfig);
+
+ hint = succ;
+ Unit key = rightEdges[i].get(LOW);
+ if(begin != key){
+ found_solid_opening = true;
+ solid_opening_begin = begin; solid_opening_end = key;
+ }
+
+ while(j < rightEdges.size() && rightEdges[j].get(HIGH) <= end){
+ if(rightEdges[j-1].get(HIGH) != rightEdges[j].get(LOW)){
+ if(!found_solid_opening){
+ found_solid_opening = true;
+ solid_opening_begin = rightEdges[j-1].get(HIGH);
+ solid_opening_end = rightEdges[j].get(LOW);
+ }else{
+ ++hint;
+ insertNewLeftEdgeIntoTailMap(currentX,
+ rightEdges[j-1].get(HIGH), rightEdges[j].get(LOW), hint);
+ }
+ }
+ j++;
+ }
+
+ //trailing edge//
+ if(end != rightEdges[j-1].get(HIGH)){
+ if(!found_solid_opening){
+ found_solid_opening = true;
+ solid_opening_begin = rightEdges[j-1].get(HIGH); solid_opening_end = end;
+ }else{
+ // a solid opening has been found already, we need to insert a new left
+ // between [rightEdges[j-1].get(HIGH), end]
+ Unit lbegin = rightEdges[j-1].get(HIGH);
+ tailPair = createActiveTailsAsPair<Unit>(currentX, lbegin, true, NULL,
+ fractureHoles_);
+ hint = tailMap_.insert(pred, std::make_pair(lbegin, tailPair.second));
+ pred->second = tailPair.first;
+ (tailPair.first)->pushCoordinate(end);
+ erase_pred = false;
+ }
+ }
+
+ size_t vertex_delta = ((begin != solid_opening_begin) &&
+ (end != solid_opening_end)) ? 4 : 2;
+
+ if(!found_solid_opening){
+ //just close the figure, TODO: call closePartialPolygon//
+ pfig->pushCoordinate(currentX);
+ ActiveTail<Unit>::joinChains(pfig, ppfig, false, outputPolygons_);
+ hint = pred; ++hint;
+ }else if(partial_fig_size+vertex_delta >= vertexThreshold){
+ //close the figure and add a pseudo left-edge//
+ closePartialSimplePolygon(currentX, pfig, ppfig);
+ assert(begin != solid_opening_begin || end != solid_opening_end);
+
+ if(begin != solid_opening_begin && end != solid_opening_end){
+ insertNewLeftEdgeIntoTailMap(currentX, solid_opening_begin,
+ solid_opening_end, hint);
+ }else if(begin == solid_opening_begin){
+ //we just need to update the succ in the tailMap_//
+ tailPair = createActiveTailsAsPair<Unit>(currentX, solid_opening_begin,
+ true, NULL, fractureHoles_);
+ succ->second = tailPair.second;
+ hint = succ; ++hint;
+ hint = tailMap_.insert(pred, std::make_pair(solid_opening_end,
+ tailPair.first));
+ (tailPair.first)->pushCoordinate(solid_opening_end);
+ erase_succ = false;
+ }else{
+ //we just need to update the pred in the tailMap_//
+ tailPair = createActiveTailsAsPair<Unit>(currentX, solid_opening_begin,
+ true, NULL, fractureHoles_);
+ hint = tailMap_.insert(pred, std::make_pair(solid_opening_begin,
+ tailPair.second));
+ pred->second = tailPair.first;
+ (tailPair.first)->pushCoordinate(solid_opening_end);
+ erase_pred = false;
+ }
+ }else{
+ //continue the figure (by adding at-most two new vertices)//
+ if(begin != solid_opening_begin){
+ pfig->pushCoordinate(currentX);
+ pfig->pushCoordinate(solid_opening_begin);
+ //insert solid_opening_begin//
+ hint = succ; ++hint;
+ hint = tailMap_.insert(hint, std::make_pair(solid_opening_begin, pfig));
+ }else{
+ erase_succ = false;
+ }
+
+ if(end != solid_opening_end){
+ std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair =
+ createActiveTailsAsPair<Unit>(currentX, solid_opening_end, false,
+ NULL, fractureHoles_);
+ hint = pred; ++hint;
+ hint = tailMap_.insert(hint, std::make_pair(solid_opening_end,
+ tailPair.second));
+ ActiveTail<Unit>::joinChains(tailPair.first, ppfig, false,
+ outputPolygons_);
+ }else{
+ erase_pred = false;
+ }
+ }
+
+ //Remove the pred and succ if necessary//
+ if(erase_succ){
+ tailMap_.erase(succ);
+ }
+ if(erase_pred){
+ tailMap_.erase(pred);
+ }
+ i = j;
+ }
+ }
+
+ // Maintains the following invariant:
+ // a. All the partial polygons formed at any state can be closed
+ // by a single edge.
+ template<bool orientT, typename Unit, typename polygon_concept_type>
+ inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
+ maintainPartialSimplePolygonInvariant(iterator& beginOutput,
+ iterator& endOutput, Unit currentX, const std::vector<interval_data<Unit> >& l,
+ const std::vector<interval_data<Unit> >& r, size_t vertexThreshold) {
+
+ clearOutput_();
+ if(!l.empty()){
+ updatePartialSimplePolygonsWithLeftEdges(currentX, l, vertexThreshold);
+ }
+
+ if(!r.empty()){
+ updatePartialSimplePolygonsWithRightEdges(currentX, r, vertexThreshold);
+ }
+ beginOutput = outputPolygons_.begin();
+ endOutput = outputPolygons_.end();
+
+ }
+
//Process edges connects vertical input edges (right or left edges of figures) to horizontal edges stored as member
//data of the scanline object. It also creates now horizontal edges as needed to construct figures from edge data.
//
- //There are only 12 geometric end cases where the scanline intersects a horizontal edge and even fewer unique
+ //There are only 12 geometric end cases where the scanline intersects a horizontal edge and even fewer unique
//actions to take:
// 1. Solid on both sides of the vertical partition after the current position and space on both sides before
- // ###|###
- // ###|###
- // |
- // |
+ // ###|###
+ // ###|###
+ // |
+ // |
// This case does not need to be handled because there is no vertical edge at the current x coordinate.
//
// 2. Solid on both sides of the vertical partition before the current position and space on both sides after
- // |
- // |
- // ###|###
- // ###|###
+ // |
+ // |
+ // ###|###
+ // ###|###
// This case does not need to be handled because there is no vertical edge at the current x coordinate.
//
// 3. Solid on the left of the vertical partition after the current position and space elsewhere
- // ###|
- // ###|
- // |
- // |
+ // ###|
+ // ###|
+ // |
+ // |
// The horizontal edge from the left is found and turns upward because of the vertical right edge to become
// the currently active vertical edge.
//
// 4. Solid on the left of the vertical partion before the current position and space elsewhere
- // |
- // |
- // ###|
+ // |
+ // |
+ // ###|
// ###|
// The horizontal edge from the left is found and joined to the currently active vertical edge.
//
// 5. Solid to the right above and below and solid to the left above current position.
- // ###|###
- // ###|###
- // |###
- // |###
+ // ###|###
+ // ###|###
+ // |###
+ // |###
// The horizontal edge from the left is found and joined to the currently active vertical edge,
// potentially closing a hole.
//
// 6. Solid on the left of the vertical partion before the current position and solid to the right above and below
// |###
- // |###
- // ###|###
+ // |###
+ // ###|###
// ###|###
// The horizontal edge from the left is found and turns upward because of the vertical right edge to become
// the currently active vertical edge.
//
// 7. Solid on the right of the vertical partition after the current position and space elsewhere
- // |###
- // |###
- // |
- // |
+ // |###
+ // |###
+ // |
+ // |
// Create two new ActiveTails, one is added to the horizontal edges and the other becomes the vertical currentTail
//
// 8. Solid on the right of the vertical partion before the current position and space elsewhere
- // |
- // |
- // |###
+ // |
+ // |
+ // |###
// |###
// The currentTail vertical edge turns right and is added to the horizontal edges data
//
// 9. Solid to the right above and solid to the left above and below current position.
- // ###|###
- // ###|###
- // ###|
+ // ###|###
+ // ###|###
+ // ###|
// ###|
// The currentTail vertical edge turns right and is added to the horizontal edges data
//
// 10. Solid on the left of the vertical partion above and below the current position and solid to the right below
+ // ###|
// ###|
- // ###|
- // ###|###
+ // ###|###
// ###|###
// Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail
//
// 11. Solid to the right above and solid to the left below current position.
+ // |###
// |###
- // |###
- // ###|
+ // ###|
// ###|
// The currentTail vertical edge joins the horizontal edge from the left (may close a polygon)
// Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail
//
// 12. Solid on the left of the vertical partion above the current position and solid to the right below
+ // ###|
// ###|
- // ###|
- // |###
+ // |###
// |###
// The currentTail vertical edge turns right and is added to the horizontal edges data.
// The horizontal edge from the left turns upward and becomes the currentTail vertical edge
//
template <bool orientT, typename Unit, typename polygon_concept_type>
inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
- processEdges(iterator& beginOutput, iterator& endOutput,
- Unit currentX, std::vector<interval_data<Unit> >& leftEdges,
- std::vector<interval_data<Unit> >& rightEdges) {
+ processEdges(iterator& beginOutput, iterator& endOutput,
+ Unit currentX, std::vector<interval_data<Unit> >& leftEdges,
+ std::vector<interval_data<Unit> >& rightEdges,
+ size_t vertexThreshold) {
clearOutput_();
- typename std::map<Unit, ActiveTail<Unit>*>::iterator nextMapItr = tailMap_.begin();
+ typename std::map<Unit, ActiveTail<Unit>*>::iterator nextMapItr;
//foreach edge
unsigned int leftIndex = 0;
unsigned int rightIndex = 0;
bool bottomAlreadyProcessed = false;
ActiveTail<Unit>* currentTail = 0;
const Unit UnitMax = (std::numeric_limits<Unit>::max)();
+
+ if(vertexThreshold < (std::numeric_limits<size_t>::max)()){
+ maintainPartialSimplePolygonInvariant(beginOutput, endOutput, currentX,
+ leftEdges, rightEdges, vertexThreshold);
+ return;
+ }
+
+ nextMapItr = tailMap_.begin();
while(leftIndex < leftEdges.size() || rightIndex < rightEdges.size()) {
- interval_data<Unit> edges[2] = {interval_data<Unit> (UnitMax, UnitMax), interval_data<Unit> (UnitMax, UnitMax)};
+ interval_data<Unit> edges[2] = {interval_data<Unit> (UnitMax, UnitMax),
+ interval_data<Unit> (UnitMax, UnitMax)};
bool haveNextEdge = true;
if(leftIndex < leftEdges.size())
edges[0] = leftEdges[leftIndex];
@@ -1551,7 +2051,7 @@
interval_data<Unit> & nextEdge = edges[!trailingEdge];
//process this edge
if(!bottomAlreadyProcessed) {
- //assert currentTail = 0
+ //assert currentTail = 0
//process the bottom end of this edge
typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(LOW));
@@ -1578,7 +2078,7 @@
//we need to create one and another one to be the current vertical tail
//if this is a trailing edge then there is space to the right of the vertical edge
//so pass the inverse of trailingEdge to indicate solid to the right
- std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair =
+ std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair =
createActiveTailsAsPair(currentX, edge.get(LOW), !trailingEdge, currentTail, fractureHoles_);
currentTail = tailPair.first;
tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(LOW), tailPair.second));
@@ -1606,7 +2106,7 @@
//two new tails are created, the vertical becomes current tail, the horizontal becomes thisMapItr tail
//pass true becuase they are created at the lower left corner of some solid
//pass null because there is no hole pointer possible
- std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair =
+ std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair =
createActiveTailsAsPair<Unit>(currentX, edge.get(HIGH), true, 0, fractureHoles_);
currentTail = tailPair.first;
thisMapItr->second = tailPair.second;
@@ -1640,7 +2140,7 @@
currentTail = ActiveTail<Unit>::joinChains(currentTail, tail, !trailingEdge, outputPolygons_);
nextMapItr = thisMapItr; //set nextMapItr to the next position after this one
++nextMapItr;
- if(currentTail) {
+ if(currentTail) { //figure is not closed//
Unit nextItrY = UnitMax;
if(nextMapItr != tailMap_.end()) {
nextItrY = nextMapItr->first;
@@ -1662,7 +2162,7 @@
//set current tail to null
currentTail = 0;
}
- }
+ }
//delete thisMapItr from the map
tailMap_.erase(thisMapItr);
} else {
@@ -1675,7 +2175,7 @@
//leave nextMapItr unchanged, it is still next
}
}
-
+
//increment index
leftIndex += !trailingEdge;
rightIndex += trailingEdge;
@@ -1718,8 +2218,10 @@
//public API to access polygon formation algorithm
template <typename output_container, typename iterator_type, typename concept_type>
- unsigned int get_polygons(output_container& container, iterator_type begin, iterator_type end,
- orientation_2d orient, bool fracture_holes, concept_type ) {
+ unsigned int get_polygons(output_container& container,
+ iterator_type begin, iterator_type end, orientation_2d orient,
+ bool fracture_holes, concept_type,
+ size_t sliceThreshold = (std::numeric_limits<size_t>::max)() ) {
typedef typename output_container::value_type polygon_type;
typedef typename std::iterator_traits<iterator_type>::value_type::first_type coordinate_type;
polygon_type poly;
@@ -1738,7 +2240,8 @@
if(pos != prevPos) {
if(orient == VERTICAL) {
typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd;
- scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges);
+ scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos,
+ leftEdges, rightEdges, sliceThreshold);
for( ; itrPoly != itrPolyEnd; ++ itrPoly) {
++countPolygons;
assign(poly, *itrPoly);
@@ -1746,7 +2249,8 @@
}
} else {
typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd;
- scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges);
+ scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos,
+ leftEdges, rightEdges, sliceThreshold);
for( ; itrPoly != itrPolyEnd; ++ itrPoly) {
++countPolygons;
assign(poly, *itrPoly);
@@ -1783,7 +2287,7 @@
}
if(orient == VERTICAL) {
typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd;
- scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges);
+ scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges, sliceThreshold);
for( ; itrPoly != itrPolyEnd; ++ itrPoly) {
++countPolygons;
assign(poly, *itrPoly);
@@ -1791,7 +2295,8 @@
}
} else {
typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd;
- scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges);
+ scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges, sliceThreshold);
+
for( ; itrPoly != itrPolyEnd; ++ itrPoly) {
++countPolygons;
assign(poly, *itrPoly);
Modified: branches/release/boost/polygon/detail/voronoi_predicates.hpp
==============================================================================
--- branches/release/boost/polygon/detail/voronoi_predicates.hpp Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/boost/polygon/detail/voronoi_predicates.hpp 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -161,21 +161,21 @@
bool operator()(const site_type& lhs, const circle_type& rhs) const {
typename ulp_cmp_type::Result xCmp =
- ulp_cmp(to_fpt(lhs.x()), to_fpt(rhs.lower_x()), ULPSx5);
+ ulp_cmp(to_fpt(lhs.x0()), to_fpt(rhs.lower_x()), ULPSx5);
if (xCmp != ulp_cmp_type::EQUAL)
return xCmp == ulp_cmp_type::LESS;
typename ulp_cmp_type::Result yCmp =
- ulp_cmp(to_fpt(lhs.y()), to_fpt(rhs.lower_y()), ULPSx5);
+ ulp_cmp(to_fpt(lhs.y0()), to_fpt(rhs.lower_y()), ULPSx5);
return yCmp == ulp_cmp_type::LESS;
}
bool operator()(const circle_type& lhs, const site_type& rhs) const {
typename ulp_cmp_type::Result xCmp =
- ulp_cmp(to_fpt(lhs.lower_x()), to_fpt(rhs.x()), ULPSx5);
+ ulp_cmp(to_fpt(lhs.lower_x()), to_fpt(rhs.x0()), ULPSx5);
if (xCmp != ulp_cmp_type::EQUAL)
return xCmp == ulp_cmp_type::LESS;
typename ulp_cmp_type::Result yCmp =
- ulp_cmp(to_fpt(lhs.lower_y()), to_fpt(rhs.y()), ULPSx5);
+ ulp_cmp(to_fpt(lhs.lower_y()), to_fpt(rhs.y0()), ULPSx5);
return yCmp == ulp_cmp_type::LESS;
}
@@ -198,24 +198,25 @@
class distance_predicate {
public:
typedef Site site_type;
+ typedef typename site_type::point_type point_type;
// Returns true if a horizontal line going through a new site intersects
// right arc at first, else returns false. If horizontal line goes
// through intersection point of the given two arcs returns false also.
bool operator()(const site_type& left_site,
const site_type& right_site,
- const site_type& new_site) const {
+ const point_type& new_point) const {
if (!left_site.is_segment()) {
if (!right_site.is_segment()) {
- return pp(left_site, right_site, new_site);
+ return pp(left_site, right_site, new_point);
} else {
- return ps(left_site, right_site, new_site, false);
+ return ps(left_site, right_site, new_point, false);
}
} else {
if (!right_site.is_segment()) {
- return ps(right_site, left_site, new_site, true);
+ return ps(right_site, left_site, new_point, true);
} else {
- return ss(left_site, right_site, new_site);
+ return ss(left_site, right_site, new_point);
}
}
}
@@ -229,18 +230,15 @@
MORE = 1
};
- typedef typename Site::point_type point_type;
-
// Robust predicate, avoids using high-precision libraries.
// Returns true if a horizontal line going through the new point site
// intersects right arc at first, else returns false. If horizontal line
// goes through intersection point of the given two arcs returns false.
bool pp(const site_type& left_site,
const site_type& right_site,
- const site_type& new_site) const {
+ const point_type& new_point) const {
const point_type& left_point = left_site.point0();
const point_type& right_point = right_site.point0();
- const point_type& new_point = new_site.point0();
if (left_point.x() > right_point.x()) {
if (new_point.y() <= left_point.y())
return false;
@@ -261,16 +259,15 @@
}
bool ps(const site_type& left_site, const site_type& right_site,
- const site_type& new_site, bool reverse_order) const {
+ const point_type& new_point, bool reverse_order) const {
kPredicateResult fast_res = fast_ps(
- left_site, right_site, new_site, reverse_order);
- if (fast_res != UNDEFINED)
- return (fast_res == LESS);
-
- fpt_type dist1 = find_distance_to_point_arc(
- left_site, new_site.point0());
- fpt_type dist2 = find_distance_to_segment_arc(
- right_site, new_site.point0());
+ left_site, right_site, new_point, reverse_order);
+ if (fast_res != UNDEFINED) {
+ return fast_res == LESS;
+ }
+
+ fpt_type dist1 = find_distance_to_point_arc(left_site, new_point);
+ fpt_type dist2 = find_distance_to_segment_arc(right_site, new_point);
// The undefined ulp range is equal to 3EPS + 7EPS <= 10ULP.
return reverse_order ^ (dist1 < dist2);
@@ -278,19 +275,15 @@
bool ss(const site_type& left_site,
const site_type& right_site,
- const site_type& new_site) const {
+ const point_type& new_point) const {
// Handle temporary segment sites.
- if (left_site.point0() == right_site.point0() &&
- left_site.point1() == right_site.point1()) {
- return ot::eval(left_site.point0(),
- left_site.point1(),
- new_site.point0()) == ot::LEFT;
+ if (left_site.sorted_index() == right_site.sorted_index()) {
+ return ot::eval(
+ left_site.point0(), left_site.point1(), new_point) == ot::LEFT;
}
- fpt_type dist1 = find_distance_to_segment_arc(
- left_site, new_site.point0());
- fpt_type dist2 = find_distance_to_segment_arc(
- right_site, new_site.point0());
+ fpt_type dist1 = find_distance_to_segment_arc(left_site, new_point);
+ fpt_type dist2 = find_distance_to_segment_arc(right_site, new_point);
// The undefined ulp range is equal to 7EPS + 7EPS <= 14ULP.
return dist1 < dist2;
@@ -309,8 +302,8 @@
if (is_vertical(site)) {
return (to_fpt(site.x()) - to_fpt(point.x())) * to_fpt(0.5);
} else {
- const point_type& segment0 = site.point0(true);
- const point_type& segment1 = site.point1(true);
+ const point_type& segment0 = site.point0();
+ const point_type& segment1 = site.point1();
fpt_type a1 = to_fpt(segment1.x()) - to_fpt(segment0.x());
fpt_type b1 = to_fpt(segment1.y()) - to_fpt(segment0.y());
fpt_type k = get_sqrt(a1 * a1 + b1 * b1);
@@ -335,11 +328,10 @@
kPredicateResult fast_ps(
const site_type& left_site, const site_type& right_site,
- const site_type& new_site, bool reverse_order) const {
+ const point_type& new_point, bool reverse_order) const {
const point_type& site_point = left_site.point0();
- const point_type& segment_start = right_site.point0(true);
- const point_type& segment_end = right_site.point1(true);
- const point_type& new_point = new_site.point0();
+ const point_type& segment_start = right_site.point0();
+ const point_type& segment_end = right_site.point1();
if (ot::eval(segment_start, segment_end, new_point) != ot::RIGHT)
return (!right_site.is_inverse()) ? LESS : MORE;
@@ -394,7 +386,9 @@
public:
typedef Node node_type;
typedef typename Node::site_type site_type;
- typedef typename site_type::coordinate_type coordinate_type;
+ typedef typename site_type::point_type point_type;
+ typedef typename point_type::coordinate_type coordinate_type;
+ typedef point_comparison_predicate<point_type> point_comparison_type;
typedef distance_predicate<site_type> distance_predicate_type;
// Compares nodes in the balanced binary search tree. Nodes are
@@ -408,13 +402,17 @@
// Get x coordinate of the rightmost site from both nodes.
const site_type& site1 = get_comparison_site(node1);
const site_type& site2 = get_comparison_site(node2);
+ const point_type& point1 = get_comparison_point(site1);
+ const point_type& point2 = get_comparison_point(site2);
- if (site1.x() < site2.x()) {
+ if (point1.x() < point2.x()) {
// The second node contains a new site.
- return predicate_(node1.left_site(), node1.right_site(), site2);
- } else if (site1.x() > site2.x()) {
+ return distance_predicate_(
+ node1.left_site(), node1.right_site(), point2);
+ } else if (point1.x() > point2.x()) {
// The first node contains a new site.
- return !predicate_(node2.left_site(), node2.right_site(), site1);
+ return !distance_predicate_(
+ node2.left_site(), node2.right_site(), point1);
} else {
// This checks were evaluated experimentally.
if (site1.sorted_index() == site2.sorted_index()) {
@@ -443,25 +441,31 @@
return node.right_site();
}
+ const point_type& get_comparison_point(const site_type& site) const {
+ return point_comparison_(site.point0(), site.point1()) ?
+ site.point0() : site.point1();
+ }
+
// Get comparison pair: y coordinate and direction of the newer site.
std::pair<coordinate_type, int> get_comparison_y(
const node_type& node, bool is_new_node = true) const {
if (node.left_site().sorted_index() ==
node.right_site().sorted_index()) {
- return std::make_pair(node.left_site().y(), 0);
+ return std::make_pair(node.left_site().y0(), 0);
}
if (node.left_site().sorted_index() > node.right_site().sorted_index()) {
if (!is_new_node &&
node.left_site().is_segment() &&
is_vertical(node.left_site())) {
- return std::make_pair(node.left_site().y1(), 1);
+ return std::make_pair(node.left_site().y0(), 1);
}
- return std::make_pair(node.left_site().y(), 1);
+ return std::make_pair(node.left_site().y1(), 1);
}
- return std::make_pair(node.right_site().y(), -1);
+ return std::make_pair(node.right_site().y0(), -1);
}
- distance_predicate_type predicate_;
+ point_comparison_type point_comparison_;
+ distance_predicate_type distance_predicate_;
};
template <typename Site>
@@ -473,8 +477,9 @@
bool ppp(const site_type& site1,
const site_type& site2,
const site_type& site3) const {
- return ot::eval(site1.point0(), site2.point0(), site3.point0()) ==
- ot::RIGHT;
+ return ot::eval(site1.point0(),
+ site2.point0(),
+ site3.point0()) == ot::RIGHT;
}
bool pps(const site_type& site1,
@@ -482,10 +487,10 @@
const site_type& site3,
int segment_index) const {
if (segment_index != 2) {
- typename ot::Orientation orient1 = ot::eval(site1.point0(),
- site2.point0(), site3.point0(true));
- typename ot::Orientation orient2 = ot::eval(site1.point0(),
- site2.point0(), site3.point1(true));
+ typename ot::Orientation orient1 = ot::eval(
+ site1.point0(), site2.point0(), site3.point0());
+ typename ot::Orientation orient2 = ot::eval(
+ site1.point0(), site2.point0(), site3.point1());
if (segment_index == 1 && site1.x0() >= site2.x0()) {
if (orient1 != ot::RIGHT)
return false;
@@ -496,9 +501,8 @@
return false;
}
} else {
- if (site3.point0(true) == site1.point0() &&
- site3.point1(true) == site2.point0())
- return false;
+ return (site3.point0() != site1.point0()) ||
+ (site3.point1() != site2.point0());
}
return true;
}
@@ -507,17 +511,16 @@
const site_type& site2,
const site_type& site3,
int point_index) const {
- if (site2.point0() == site3.point0() &&
- site2.point1() == site3.point1()) {
+ if (site2.sorted_index() == site3.sorted_index()) {
return false;
}
if (point_index == 2) {
if (!site2.is_inverse() && site3.is_inverse())
return false;
if (site2.is_inverse() == site3.is_inverse() &&
- ot::eval(site2.point0(true),
+ ot::eval(site2.point0(),
site1.point0(),
- site3.point1(true)) != ot::RIGHT)
+ site3.point1()) != ot::RIGHT)
return false;
}
return true;
@@ -526,11 +529,8 @@
bool sss(const site_type& site1,
const site_type& site2,
const site_type& site3) const {
- if (site1.point0() == site2.point0() && site1.point1() == site2.point1())
- return false;
- if (site2.point0() == site3.point0() && site2.point1() == site3.point1())
- return false;
- return true;
+ return (site1.sorted_index() != site2.sorted_index()) &&
+ (site2.sorted_index() != site3.sorted_index());
}
};
@@ -620,10 +620,10 @@
bool recompute_c_y = true,
bool recompute_lower_x = true) {
big_int_type cA[4], cB[4];
- big_int_type line_a = static_cast<int_x2_type>(site3.point1(true).y()) -
- static_cast<int_x2_type>(site3.point0(true).y());
- big_int_type line_b = static_cast<int_x2_type>(site3.point0(true).x()) -
- static_cast<int_x2_type>(site3.point1(true).x());
+ big_int_type line_a = static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0());
+ big_int_type line_b = static_cast<int_x2_type>(site3.x0()) -
+ static_cast<int_x2_type>(site3.x1());
big_int_type segm_len = line_a * line_a + line_b * line_b;
big_int_type vec_x = static_cast<int_x2_type>(site2.y()) -
static_cast<int_x2_type>(site1.y());
@@ -636,15 +636,15 @@
big_int_type teta = line_a * vec_x + line_b * vec_y;
big_int_type denom = vec_x * line_b - vec_y * line_a;
- big_int_type dif0 = static_cast<int_x2_type>(site3.point1().y()) -
+ big_int_type dif0 = static_cast<int_x2_type>(site3.y1()) -
static_cast<int_x2_type>(site1.y());
big_int_type dif1 = static_cast<int_x2_type>(site1.x()) -
- static_cast<int_x2_type>(site3.point1().x());
+ static_cast<int_x2_type>(site3.x1());
big_int_type A = line_a * dif1 - line_b * dif0;
- dif0 = static_cast<int_x2_type>(site3.point1().y()) -
+ dif0 = static_cast<int_x2_type>(site3.y1()) -
static_cast<int_x2_type>(site2.y());
dif1 = static_cast<int_x2_type>(site2.x()) -
- static_cast<int_x2_type>(site3.point1().x());
+ static_cast<int_x2_type>(site3.x1());
big_int_type B = line_a * dif1 - line_b * dif0;
big_int_type sum_AB = A + B;
@@ -716,10 +716,10 @@
bool recompute_c_y = true,
bool recompute_lower_x = true) {
big_int_type a[2], b[2], c[2], cA[4], cB[4];
- const point_type& segm_start1 = site2.point1(true);
- const point_type& segm_end1 = site2.point0(true);
- const point_type& segm_start2 = site3.point0(true);
- const point_type& segm_end2 = site3.point1(true);
+ const point_type& segm_start1 = site2.point1();
+ const point_type& segm_end1 = site2.point0();
+ const point_type& segm_start2 = site3.point0();
+ const point_type& segm_end2 = site3.point1();
a[0] = static_cast<int_x2_type>(segm_end1.x()) -
static_cast<int_x2_type>(segm_start1.x());
b[0] = static_cast<int_x2_type>(segm_end1.y()) -
@@ -850,32 +850,32 @@
big_int_type a[3], b[3], c[3], cA[4], cB[4];
// cA - corresponds to the cross product.
// cB - corresponds to the squared length.
- a[0] = static_cast<int_x2_type>(site1.x1(true)) -
- static_cast<int_x2_type>(site1.x0(true));
- a[1] = static_cast<int_x2_type>(site2.x1(true)) -
- static_cast<int_x2_type>(site2.x0(true));
- a[2] = static_cast<int_x2_type>(site3.x1(true)) -
- static_cast<int_x2_type>(site3.x0(true));
-
- b[0] = static_cast<int_x2_type>(site1.y1(true)) -
- static_cast<int_x2_type>(site1.y0(true));
- b[1] = static_cast<int_x2_type>(site2.y1(true)) -
- static_cast<int_x2_type>(site2.y0(true));
- b[2] = static_cast<int_x2_type>(site3.y1(true)) -
- static_cast<int_x2_type>(site3.y0(true));
-
- c[0] = static_cast<int_x2_type>(site1.x0(true)) *
- static_cast<int_x2_type>(site1.y1(true)) -
- static_cast<int_x2_type>(site1.y0(true)) *
- static_cast<int_x2_type>(site1.x1(true));
- c[1] = static_cast<int_x2_type>(site2.x0(true)) *
- static_cast<int_x2_type>(site2.y1(true)) -
- static_cast<int_x2_type>(site2.y0(true)) *
- static_cast<int_x2_type>(site2.x1(true));
- c[2] = static_cast<int_x2_type>(site3.x0(true)) *
- static_cast<int_x2_type>(site3.y1(true)) -
- static_cast<int_x2_type>(site3.y0(true)) *
- static_cast<int_x2_type>(site3.x1(true));
+ a[0] = static_cast<int_x2_type>(site1.x1()) -
+ static_cast<int_x2_type>(site1.x0());
+ a[1] = static_cast<int_x2_type>(site2.x1()) -
+ static_cast<int_x2_type>(site2.x0());
+ a[2] = static_cast<int_x2_type>(site3.x1()) -
+ static_cast<int_x2_type>(site3.x0());
+
+ b[0] = static_cast<int_x2_type>(site1.y1()) -
+ static_cast<int_x2_type>(site1.y0());
+ b[1] = static_cast<int_x2_type>(site2.y1()) -
+ static_cast<int_x2_type>(site2.y0());
+ b[2] = static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0());
+
+ c[0] = static_cast<int_x2_type>(site1.x0()) *
+ static_cast<int_x2_type>(site1.y1()) -
+ static_cast<int_x2_type>(site1.y0()) *
+ static_cast<int_x2_type>(site1.x1());
+ c[1] = static_cast<int_x2_type>(site2.x0()) *
+ static_cast<int_x2_type>(site2.y1()) -
+ static_cast<int_x2_type>(site2.y0()) *
+ static_cast<int_x2_type>(site2.x1());
+ c[2] = static_cast<int_x2_type>(site3.x0()) *
+ static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0()) *
+ static_cast<int_x2_type>(site3.x1());
for (int i = 0; i < 3; ++i)
cB[i] = a[i] * a[i] + b[i] * b[i];
@@ -1060,48 +1060,46 @@
const site_type& site3,
int segment_index,
circle_type& c_event) {
- fpt_type line_a = to_fpt(site3.point1(true).y()) -
- to_fpt(site3.point0(true).y());
- fpt_type line_b = to_fpt(site3.point0(true).x()) -
- to_fpt(site3.point1(true).x());
+ fpt_type line_a = to_fpt(site3.y1()) - to_fpt(site3.y0());
+ fpt_type line_b = to_fpt(site3.x0()) - to_fpt(site3.x1());
fpt_type vec_x = to_fpt(site2.y()) - to_fpt(site1.y());
fpt_type vec_y = to_fpt(site1.x()) - to_fpt(site2.x());
robust_fpt_type teta(robust_cross_product(
- static_cast<int_x2_type>(site3.point1(true).y()) -
- static_cast<int_x2_type>(site3.point0(true).y()),
- static_cast<int_x2_type>(site3.point0(true).x()) -
- static_cast<int_x2_type>(site3.point1(true).x()),
+ static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0()),
+ static_cast<int_x2_type>(site3.x0()) -
+ static_cast<int_x2_type>(site3.x1()),
static_cast<int_x2_type>(site2.x()) -
static_cast<int_x2_type>(site1.x()),
static_cast<int_x2_type>(site2.y()) -
static_cast<int_x2_type>(site1.y())), to_fpt(1.0));
robust_fpt_type A(robust_cross_product(
- static_cast<int_x2_type>(site3.point1(true).y()) -
- static_cast<int_x2_type>(site3.point0(true).y()),
- static_cast<int_x2_type>(site3.point0(true).x()) -
- static_cast<int_x2_type>(site3.point1(true).x()),
- static_cast<int_x2_type>(site3.point1().y()) -
+ static_cast<int_x2_type>(site3.y0()) -
+ static_cast<int_x2_type>(site3.y1()),
+ static_cast<int_x2_type>(site3.x0()) -
+ static_cast<int_x2_type>(site3.x1()),
+ static_cast<int_x2_type>(site3.y1()) -
static_cast<int_x2_type>(site1.y()),
- static_cast<int_x2_type>(site1.x()) -
- static_cast<int_x2_type>(site3.point1().x())), to_fpt(1.0));
+ static_cast<int_x2_type>(site3.x1()) -
+ static_cast<int_x2_type>(site1.x())), to_fpt(1.0));
robust_fpt_type B(robust_cross_product(
- static_cast<int_x2_type>(site3.point1(true).y()) -
- static_cast<int_x2_type>(site3.point0(true).y()),
- static_cast<int_x2_type>(site3.point0(true).x()) -
- static_cast<int_x2_type>(site3.point1(true).x()),
- static_cast<int_x2_type>(site3.point1().y()) -
+ static_cast<int_x2_type>(site3.y0()) -
+ static_cast<int_x2_type>(site3.y1()),
+ static_cast<int_x2_type>(site3.x0()) -
+ static_cast<int_x2_type>(site3.x1()),
+ static_cast<int_x2_type>(site3.y1()) -
static_cast<int_x2_type>(site2.y()),
- static_cast<int_x2_type>(site2.x()) -
- static_cast<int_x2_type>(site3.point1().x())), to_fpt(1.0));
+ static_cast<int_x2_type>(site3.x1()) -
+ static_cast<int_x2_type>(site2.x())), to_fpt(1.0));
robust_fpt_type denom(robust_cross_product(
- static_cast<int_x2_type>(site2.y()) -
- static_cast<int_x2_type>(site1.y()),
+ static_cast<int_x2_type>(site1.y()) -
+ static_cast<int_x2_type>(site2.y()),
static_cast<int_x2_type>(site1.x()) -
static_cast<int_x2_type>(site2.x()),
- static_cast<int_x2_type>(site3.point1(true).y()) -
- static_cast<int_x2_type>(site3.point0(true).y()),
- static_cast<int_x2_type>(site3.point0(true).x()) -
- static_cast<int_x2_type>(site3.point1(true).x())), to_fpt(1.0));
+ static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0()),
+ static_cast<int_x2_type>(site3.x1()) -
+ static_cast<int_x2_type>(site3.x0())), to_fpt(1.0));
robust_fpt_type inv_segm_len(to_fpt(1.0) /
get_sqrt(line_a * line_a + line_b * line_b), to_fpt(3.0));
robust_dif_type t;
@@ -1118,11 +1116,11 @@
t += teta * (A + B) / (robust_fpt_type(to_fpt(2.0)) * denom * denom);
}
robust_dif_type c_x, c_y;
- c_x += robust_fpt_type(to_fpt(0.5) * (to_fpt(site1.x()) +
- to_fpt(site2.x())));
+ c_x += robust_fpt_type(to_fpt(0.5) *
+ (to_fpt(site1.x()) + to_fpt(site2.x())));
c_x += robust_fpt_type(vec_x) * t;
- c_y += robust_fpt_type(to_fpt(0.5) * (to_fpt(site1.y()) +
- to_fpt(site2.y())));
+ c_y += robust_fpt_type(to_fpt(0.5) *
+ (to_fpt(site1.y()) + to_fpt(site2.y())));
c_y += robust_fpt_type(vec_y) * t;
robust_dif_type r, lower_x(c_x);
r -= robust_fpt_type(line_a) * robust_fpt_type(site3.x0());
@@ -1149,10 +1147,10 @@
const site_type& site3,
int point_index,
circle_type& c_event) {
- const point_type& segm_start1 = site2.point1(true);
- const point_type& segm_end1 = site2.point0(true);
- const point_type& segm_start2 = site3.point0(true);
- const point_type& segm_end2 = site3.point1(true);
+ const point_type& segm_start1 = site2.point1();
+ const point_type& segm_end1 = site2.point0();
+ const point_type& segm_start2 = site3.point0();
+ const point_type& segm_end2 = site3.point1();
fpt_type a1 = to_fpt(segm_end1.x()) - to_fpt(segm_start1.x());
fpt_type b1 = to_fpt(segm_end1.y()) - to_fpt(segm_start1.y());
fpt_type a2 = to_fpt(segm_end2.x()) - to_fpt(segm_start2.x());
@@ -1343,54 +1341,54 @@
const site_type& site2,
const site_type& site3,
circle_type& c_event) {
- robust_fpt_type a1(to_fpt(site1.x1(true)) - to_fpt(site1.x0(true)));
- robust_fpt_type b1(to_fpt(site1.y1(true)) - to_fpt(site1.y0(true)));
+ robust_fpt_type a1(to_fpt(site1.x1()) - to_fpt(site1.x0()));
+ robust_fpt_type b1(to_fpt(site1.y1()) - to_fpt(site1.y0()));
robust_fpt_type c1(robust_cross_product(
- site1.x0(true), site1.y0(true),
- site1.x1(true), site1.y1(true)), to_fpt(1.0));
+ site1.x0(), site1.y0(),
+ site1.x1(), site1.y1()), to_fpt(1.0));
- robust_fpt_type a2(to_fpt(site2.x1(true)) - to_fpt(site2.x0(true)));
- robust_fpt_type b2(to_fpt(site2.y1(true)) - to_fpt(site2.y0(true)));
+ robust_fpt_type a2(to_fpt(site2.x1()) - to_fpt(site2.x0()));
+ robust_fpt_type b2(to_fpt(site2.y1()) - to_fpt(site2.y0()));
robust_fpt_type c2(robust_cross_product(
- site2.x0(true), site2.y0(true),
- site2.x1(true), site2.y1(true)), to_fpt(1.0));
+ site2.x0(), site2.y0(),
+ site2.x1(), site2.y1()), to_fpt(1.0));
- robust_fpt_type a3(to_fpt(site3.x1(true)) - to_fpt(site3.x0(true)));
- robust_fpt_type b3(to_fpt(site3.y1(true)) - to_fpt(site3.y0(true)));
+ robust_fpt_type a3(to_fpt(site3.x1()) - to_fpt(site3.x0()));
+ robust_fpt_type b3(to_fpt(site3.y1()) - to_fpt(site3.y0()));
robust_fpt_type c3(robust_cross_product(
- site3.x0(true), site3.y0(true),
- site3.x1(true), site3.y1(true)), to_fpt(1.0));
+ site3.x0(), site3.y0(),
+ site3.x1(), site3.y1()), to_fpt(1.0));
robust_fpt_type len1 = (a1 * a1 + b1 * b1).sqrt();
robust_fpt_type len2 = (a2 * a2 + b2 * b2).sqrt();
robust_fpt_type len3 = (a3 * a3 + b3 * b3).sqrt();
robust_fpt_type cross_12(robust_cross_product(
- static_cast<int_x2_type>(site1.x1(true)) -
- static_cast<int_x2_type>(site1.x0(true)),
- static_cast<int_x2_type>(site1.y1(true)) -
- static_cast<int_x2_type>(site1.y0(true)),
- static_cast<int_x2_type>(site2.x1(true)) -
- static_cast<int_x2_type>(site2.x0(true)),
- static_cast<int_x2_type>(site2.y1(true)) -
- static_cast<int_x2_type>(site2.y0(true))), to_fpt(1.0));
+ static_cast<int_x2_type>(site1.x1()) -
+ static_cast<int_x2_type>(site1.x0()),
+ static_cast<int_x2_type>(site1.y1()) -
+ static_cast<int_x2_type>(site1.y0()),
+ static_cast<int_x2_type>(site2.x1()) -
+ static_cast<int_x2_type>(site2.x0()),
+ static_cast<int_x2_type>(site2.y1()) -
+ static_cast<int_x2_type>(site2.y0())), to_fpt(1.0));
robust_fpt_type cross_23(robust_cross_product(
- static_cast<int_x2_type>(site2.x1(true)) -
- static_cast<int_x2_type>(site2.x0(true)),
- static_cast<int_x2_type>(site2.y1(true)) -
- static_cast<int_x2_type>(site2.y0(true)),
- static_cast<int_x2_type>(site3.x1(true)) -
- static_cast<int_x2_type>(site3.x0(true)),
- static_cast<int_x2_type>(site3.y1(true)) -
- static_cast<int_x2_type>(site3.y0(true))), to_fpt(1.0));
+ static_cast<int_x2_type>(site2.x1()) -
+ static_cast<int_x2_type>(site2.x0()),
+ static_cast<int_x2_type>(site2.y1()) -
+ static_cast<int_x2_type>(site2.y0()),
+ static_cast<int_x2_type>(site3.x1()) -
+ static_cast<int_x2_type>(site3.x0()),
+ static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0())), to_fpt(1.0));
robust_fpt_type cross_31(robust_cross_product(
- static_cast<int_x2_type>(site3.x1(true)) -
- static_cast<int_x2_type>(site3.x0(true)),
- static_cast<int_x2_type>(site3.y1(true)) -
- static_cast<int_x2_type>(site3.y0(true)),
- static_cast<int_x2_type>(site1.x1(true)) -
- static_cast<int_x2_type>(site1.x0(true)),
- static_cast<int_x2_type>(site1.y1(true)) -
- static_cast<int_x2_type>(site1.y0(true))), to_fpt(1.0));
+ static_cast<int_x2_type>(site3.x1()) -
+ static_cast<int_x2_type>(site3.x0()),
+ static_cast<int_x2_type>(site3.y1()) -
+ static_cast<int_x2_type>(site3.y0()),
+ static_cast<int_x2_type>(site1.x1()) -
+ static_cast<int_x2_type>(site1.x0()),
+ static_cast<int_x2_type>(site1.y1()) -
+ static_cast<int_x2_type>(site1.y0())), to_fpt(1.0));
// denom = cross_12 * len3 + cross_23 * len1 + cross_31 * len2.
robust_dif_type denom;
Modified: branches/release/boost/polygon/detail/voronoi_structures.hpp
==============================================================================
--- branches/release/boost/polygon/detail/voronoi_structures.hpp Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/boost/polygon/detail/voronoi_structures.hpp 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -130,48 +130,36 @@
(this->point1_ != that.point1_);
}
- coordinate_type x(bool oriented = false) const {
- return x0(oriented);
+ coordinate_type x() const {
+ return point0_.x();
}
- coordinate_type y(bool oriented = false) const {
- return y0(oriented);
+ coordinate_type y() const {
+ return point0_.y();
}
- coordinate_type x0(bool oriented = false) const {
- if (!oriented)
- return point0_.x();
- return is_inverse() ? point1_.x() : point0_.x();
+ coordinate_type x0() const {
+ return point0_.x();
}
- coordinate_type y0(bool oriented = false) const {
- if (!oriented)
- return point0_.y();
- return is_inverse() ? point1_.y() : point0_.y();
+ coordinate_type y0() const {
+ return point0_.y();
}
- coordinate_type x1(bool oriented = false) const {
- if (!oriented)
- return point1_.x();
- return is_inverse() ? point0_.x() : point1_.x();
+ coordinate_type x1() const {
+ return point1_.x();
}
- coordinate_type y1(bool oriented = false) const {
- if (!oriented)
- return point1_.y();
- return is_inverse() ? point0_.y() : point1_.y();
+ coordinate_type y1() const {
+ return point1_.y();
}
- const point_type& point0(bool oriented = false) const {
- if (!oriented)
- return point0_;
- return is_inverse() ? point1_ : point0_;
+ const point_type& point0() const {
+ return point0_;
}
- const point_type& point1(bool oriented = false) const {
- if (!oriented)
- return point1_;
- return is_inverse() ? point0_ : point1_;
+ const point_type& point1() const {
+ return point1_;
}
std::size_t sorted_index() const {
@@ -197,6 +185,7 @@
}
site_event& inverse() {
+ std::swap(point0_, point1_);
flags_ ^= IS_INVERSE;
return *this;
}
Modified: branches/release/boost/polygon/polygon_90_set_data.hpp
==============================================================================
--- branches/release/boost/polygon/polygon_90_set_data.hpp Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/boost/polygon/polygon_90_set_data.hpp 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -164,6 +164,12 @@
}
template <typename output_container>
+ inline void get(output_container& output, size_t vthreshold) const {
+ get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type(), vthreshold);
+ }
+
+
+ template <typename output_container>
inline void get_polygons(output_container& output) const {
get_dispatch(output, polygon_90_concept());
}
@@ -829,10 +835,25 @@
void get_dispatch(output_container& output, polygon_90_concept tag) const {
get_fracture(output, true, tag);
}
+
+ template <typename output_container>
+ void get_dispatch(output_container& output, polygon_90_concept tag,
+ size_t vthreshold) const {
+ get_fracture(output, true, tag, vthreshold);
+ }
+
template <typename output_container>
void get_dispatch(output_container& output, polygon_90_with_holes_concept tag) const {
get_fracture(output, false, tag);
}
+
+ template <typename output_container>
+ void get_dispatch(output_container& output, polygon_90_with_holes_concept tag,
+ size_t vthreshold) const {
+ get_fracture(output, false, tag, vthreshold);
+ }
+
+
template <typename output_container>
void get_dispatch(output_container& output, polygon_45_concept tag) const {
get_fracture(output, true, tag);
@@ -854,6 +875,13 @@
clean();
::boost::polygon::get_polygons(container, data_.begin(), data_.end(), orient_, fracture_holes, tag);
}
+
+ template <typename output_container, typename concept_type>
+ void get_fracture(output_container& container, bool fracture_holes, concept_type tag,
+ size_t vthreshold) const {
+ clean();
+ ::boost::polygon::get_polygons(container, data_.begin(), data_.end(), orient_, fracture_holes, tag, vthreshold);
+ }
};
template <typename coordinate_type>
Modified: branches/release/boost/polygon/voronoi_builder.hpp
==============================================================================
--- branches/release/boost/polygon/voronoi_builder.hpp Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/boost/polygon/voronoi_builder.hpp 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -388,7 +388,7 @@
site_event_type site1 = it_first->first.left_site();
if (!site1.is_segment() && site3.is_segment() &&
- site3.point1(true) == site1.point0()) {
+ site3.point1() == site1.point0()) {
site3.inverse();
}
Modified: branches/release/libs/polygon/benchmark/Jamfile.v2
==============================================================================
--- branches/release/libs/polygon/benchmark/Jamfile.v2 Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/libs/polygon/benchmark/Jamfile.v2 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -5,21 +5,24 @@
import testing ;
+# Path constants required by the benchmarks.
+path-constant GMP_ROOT : /home/slevin/Workspace/Libraries/gmp ;
+path-constant MPFR_ROOT : /home/slevin/Workspace/Libraries/mpfr ;
+path-constant CGAL_ROOT : /home/slevin/Workspace/Libraries/cgal ;
+path-constant SHULL_ROOT : /home/slevin/Workspace/Libraries/s_hull ;
+
project voronoi-benchmark
:
requirements
<include>$(CGAL_ROOT)/include
- <include>$(SHULL_ROOT)
- <toolset>msvc:<include>$(CGAL_ROOT)/auxiliary/gmp/include
- <toolset>msvc:<library>$(CGAL_ROOT)/lib/libCGAL-vc90-mt-4.0.lib
- <toolset>msvc:<library>$(CGAL_ROOT)/lib/libCGAL_Core-vc90-mt-4.0.lib
- <toolset>msvc:<library>$(CGAL_ROOT)/auxiliary/gmp/lib/libgmp-10.lib
- <toolset>msvc:<library>$(CGAL_ROOT)/auxiliary/gmp/lib/libmpfr-4.lib
- <toolset>msvc:<library>$(BOOST_ROOT)/libs/thread/build//boost_thread
- <toolset>msvc:<library>$(BOOST_ROOT)/libs/test/build//boost_unit_test_framework
+ <include>$(SHULL_ROOT)/include
+ <toolset>gcc:<library>$(GMP_ROOT)/lib/libgmp.so
+ <toolset>gcc:<library>$(MPFR_ROOT)/lib/libmpfr.so
<toolset>gcc:<library>$(CGAL_ROOT)/lib/libCGAL.so
<toolset>gcc:<library>$(CGAL_ROOT)/lib/libCGAL_Core.so
<toolset>gcc:<library>$(SHULL_ROOT)/s_hull.so
+ <toolset>gcc:<library>$(BOOST_ROOT)/libs/timer/build//boost_timer
+ <toolset>gcc:<library>$(BOOST_ROOT)/libs/thread/build//boost_thread
<toolset>gcc:<library>$(BOOST_ROOT)/libs/test/build//boost_unit_test_framework
;
Modified: branches/release/libs/polygon/benchmark/voronoi_benchmark_points.cpp
==============================================================================
--- branches/release/libs/polygon/benchmark/voronoi_benchmark_points.cpp Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/libs/polygon/benchmark/voronoi_benchmark_points.cpp 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -16,9 +16,11 @@
#include <utility>
#include <boost/random/mersenne_twister.hpp>
-#include <boost/timer.hpp>
+#include <boost/timer/timer.hpp>
typedef boost::int32_t int32;
+using boost::timer::cpu_times;
+using boost::timer::nanosecond_type;
// Include for the Boost.Polygon Voronoi library.
#include <boost/polygon/voronoi.hpp>
@@ -26,18 +28,11 @@
typedef boost::polygon::voronoi_diagram<double> VD_BOOST;
// Includes for the CGAL library.
-#include <CGAL/Quotient.h>
-#include <CGAL/MP_Float.h>
-#include <CGAL/Simple_cartesian.h>
-#include <CGAL/Segment_Delaunay_graph_filtered_traits_2.h>
-#include <CGAL/Segment_Delaunay_graph_2.h>
-typedef CGAL::Quotient<CGAL::MP_Float> ENT;
-typedef CGAL::Simple_cartesian<double> CK;
-typedef CGAL::Simple_cartesian<ENT> EK;
-typedef CGAL::Segment_Delaunay_graph_filtered_traits_2<
- CK, CGAL::Field_with_sqrt_tag, EK, CGAL::Field_tag> Gt;
-typedef CGAL::Segment_Delaunay_graph_2<Gt> SDT_CGAL;
-typedef SDT_CGAL::Point_2 Point_CGAL;
+#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
+#include <CGAL/Delaunay_triangulation_2.h>
+typedef CGAL::Exact_predicates_inexact_constructions_kernel CGAL_KERNEL;
+typedef CGAL::Delaunay_triangulation_2<CGAL_KERNEL> DT_CGAL;
+typedef CGAL_KERNEL::Point_2 POINT_CGAL;
// Includes for the S-Hull library.
#include <s_hull.h>
@@ -48,7 +43,7 @@
const int NUM_RUNS[] = {100000, 10000, 1000, 100, 10, 1};
std::ofstream bf("benchmark_points.txt",
std::ios_base::out | std::ios_base::app);
-boost::timer timer;
+boost::timer::cpu_timer timer;
void format_line(int num_points, int num_tests, double time_per_test) {
bf << "| " << std::setw(16) << num_points << " ";
@@ -57,50 +52,65 @@
bf << "|" << std::endl;
}
-void run_boost_test() {
+double get_elapsed_secs() {
+ cpu_times elapsed_times(timer.elapsed());
+ return 1E-9 * static_cast<double>(
+ elapsed_times.system + elapsed_times.user);
+}
+
+void run_boost_voronoi_test() {
boost::mt19937 gen(RANDOM_SEED);
- bf << "Boost.Polygon Voronoi of Points:\n";
+ bf << "Boost.Polygon Voronoi Diagram of Points:\n";
for (int i = 0; i < NUM_TESTS; ++i) {
- timer.restart();
+ timer.start();
for (int j = 0; j < NUM_RUNS[i]; ++j) {
VB_BOOST vb;
VD_BOOST vd;
- for (int k = 0; k < NUM_POINTS[i]; ++k)
- vb.insert_point(static_cast<int32>(gen()), static_cast<int32>(gen()));
+ for (int k = 0; k < NUM_POINTS[i]; ++k) {
+ int32 x = static_cast<int32>(gen());
+ int32 y = static_cast<int32>(gen());
+ vb.insert_point(x, y);
+ }
vb.construct(&vd);
}
- double time_per_test = timer.elapsed() / NUM_RUNS[i];
+ double time_per_test = get_elapsed_secs() / NUM_RUNS[i];
format_line(NUM_POINTS[i], NUM_RUNS[i], time_per_test);
}
bf << "\n";
}
-void run_cgal_test() {
+void run_cgal_delaunay_test() {
boost::mt19937 gen(RANDOM_SEED);
- bf << "CGAL Triangulation of Points:\n";
+ bf << "CGAL Delaunay Triangulation of Points:\n";
for (int i = 0; i < NUM_TESTS; ++i) {
- timer.restart();
+ timer.start();
for (int j = 0; j < NUM_RUNS[i]; ++j) {
- SDT_CGAL dt;
+ DT_CGAL dt;
+ std::vector<POINT_CGAL> points;
for (int k = 0; k < NUM_POINTS[i]; ++k) {
- dt.insert(Point_CGAL(
- static_cast<int32>(gen()), static_cast<int32>(gen())));
+ int32 x = static_cast<int32>(gen());
+ int32 y = static_cast<int32>(gen());
+ points.push_back(POINT_CGAL(x, y));
}
+ // CGAL's implementation sorts points along
+ // the Hilbert curve implicitly to improve
+ // spatial ordering of the input geometries.
+ dt.insert(points.begin(), points.end());
}
- double time_per_test = timer.elapsed() / NUM_RUNS[i];
+ double time_per_test = get_elapsed_secs() / NUM_RUNS[i];
format_line(NUM_POINTS[i], NUM_RUNS[i], time_per_test);
}
bf << "\n";
}
-void run_shull_test() {
+void run_shull_delaunay_test() {
boost::mt19937 gen(RANDOM_SEED);
- bf << "S-Hull Triangulation of Points:\n";
+ bf << "S-Hull Delaunay Triangulation of Points:\n";
// This value is required by S-Hull as it doesn't seem to support properly
// coordinates with the absolute value higher than 100.
float koef = 100.0 / (1 << 16) / (1 << 15);
for (int i = 0; i < NUM_TESTS; ++i) {
- timer.restart();
+ timer.start();
for (int j = 0; j < NUM_RUNS[i]; ++j) {
// S-Hull doesn't deal properly with duplicates so we need
// to eliminate them before running the algorithm.
@@ -124,7 +134,7 @@
}
s_hull_del_ray2(pts, triads);
}
- double time_per_test = timer.elapsed() / NUM_RUNS[i];
+ double time_per_test = get_elapsed_secs() / NUM_RUNS[i];
format_line(NUM_POINTS[i], NUM_RUNS[i], time_per_test);
}
bf << "\n";
@@ -133,9 +143,9 @@
int main() {
bf << std::setiosflags(std::ios::right | std::ios::fixed)
<< std::setprecision(6);
- run_boost_test();
- run_cgal_test();
- run_shull_test();
+ run_boost_voronoi_test();
+ run_cgal_delaunay_test();
+ run_shull_delaunay_test();
bf.close();
return 0;
}
Modified: branches/release/libs/polygon/benchmark/voronoi_benchmark_segments.cpp
==============================================================================
--- branches/release/libs/polygon/benchmark/voronoi_benchmark_segments.cpp Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/libs/polygon/benchmark/voronoi_benchmark_segments.cpp 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -16,26 +16,24 @@
#include <utility>
#include <boost/random/mersenne_twister.hpp>
-#include <boost/timer.hpp>
+#include <boost/timer/timer.hpp>
typedef boost::int32_t int32;
+using boost::timer::cpu_times;
+using boost::timer::nanosecond_type;
// Include for the Boost.Polygon Voronoi library.
#include <boost/polygon/voronoi.hpp>
typedef boost::polygon::voronoi_diagram<double> VD_BOOST;
// Includes for the CGAL library.
-#include <CGAL/Quotient.h>
-#include <CGAL/MP_Float.h>
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Segment_Delaunay_graph_filtered_traits_2.h>
#include <CGAL/Segment_Delaunay_graph_2.h>
-typedef CGAL::Quotient<CGAL::MP_Float> ENT;
-typedef CGAL::Simple_cartesian<double> CK;
-typedef CGAL::Simple_cartesian<ENT> EK;
-typedef CGAL::Segment_Delaunay_graph_filtered_traits_2<
- CK, CGAL::Field_with_sqrt_tag, EK, CGAL::Field_tag> Gt;
-typedef CGAL::Segment_Delaunay_graph_2<Gt> SDT_CGAL;
+
+typedef CGAL::Simple_cartesian<double> K;
+typedef CGAL::Segment_Delaunay_graph_filtered_traits_without_intersections_2<K> GT;
+typedef CGAL::Segment_Delaunay_graph_2<GT> SDT_CGAL;
typedef SDT_CGAL::Point_2 Point_CGAL;
typedef SDT_CGAL::Site_2 Site_CGAL;
@@ -51,7 +49,7 @@
const int NUM_RUNS[] = {100000, 10000, 1000, 100, 10, 1};
std::ofstream bf("benchmark_segments.txt",
std::ios_base::out | std::ios_base::app);
-boost::timer timer;
+boost::timer::cpu_timer timer;
void format_line(int num_points, int num_tests, double time_per_test) {
bf << "| " << std::setw(16) << num_points << " ";
@@ -60,7 +58,13 @@
bf << "|" << std::endl;
}
-void clean_segment_set(std::vector<SEGMENT_POLYGON> &data) {
+double get_elapsed_secs() {
+ cpu_times elapsed_times(timer.elapsed());
+ return 1E-9 * static_cast<double>(
+ elapsed_times.system + elapsed_times.user);
+}
+
+void clean_segment_set(std::vector<SEGMENT_POLYGON>* data) {
typedef int32 Unit;
typedef boost::polygon::scanline_base<Unit>::Point Point;
typedef boost::polygon::scanline_base<Unit>::half_edge half_edge;
@@ -68,9 +72,9 @@
std::vector<std::pair<half_edge, segment_id> > half_edges;
std::vector<std::pair<half_edge, segment_id> > half_edges_out;
segment_id id = 0;
- half_edges.reserve(data.size());
- for (std::vector<SEGMENT_POLYGON>::iterator it = data.begin();
- it != data.end(); ++it) {
+ half_edges.reserve(data->size());
+ for (std::vector<SEGMENT_POLYGON>::iterator it = data->begin();
+ it != data->end(); ++it) {
POINT_POLYGON l = it->low();
POINT_POLYGON h = it->high();
half_edges.push_back(std::make_pair(half_edge(l, h), id++));
@@ -85,19 +89,19 @@
id = half_edges_out[i].second;
POINT_POLYGON l = half_edges_out[i].first.first;
POINT_POLYGON h = half_edges_out[i].first.second;
- SEGMENT_POLYGON orig_seg = data[id];
+ SEGMENT_POLYGON orig_seg = data->at(id);
if (orig_seg.high() < orig_seg.low())
std::swap(l, h);
result.push_back(SEGMENT_POLYGON(l, h));
}
- std::swap(result, data);
+ std::swap(result, *data);
}
std::vector<double> get_intersection_runtime() {
std::vector<double> running_times;
boost::mt19937 gen(RANDOM_SEED);
for (int i = 0; i < NUM_TESTS; ++i) {
- timer.restart();
+ timer.start();
for (int j = 0; j < NUM_RUNS[i]; ++j) {
SSD_POLYGON ssd;
for (int k = 0; k < NUM_SEGMENTS[i]; ++k) {
@@ -108,18 +112,18 @@
ssd.push_back(SEGMENT_POLYGON(
POINT_POLYGON(x1, y1), POINT_POLYGON(x1 + dx, y1 + dy)));
}
- clean_segment_set(ssd);
+ clean_segment_set(&ssd);
}
- running_times.push_back(timer.elapsed());
+ running_times.push_back(get_elapsed_secs());
}
return running_times;
}
-void run_voronoi_test(const std::vector<double> &running_times) {
+void run_boost_voronoi_test(const std::vector<double> &running_times) {
boost::mt19937 gen(RANDOM_SEED);
bf << "Boost.Polygon Voronoi of Segments:\n";
for (int i = 0; i < NUM_TESTS; ++i) {
- timer.restart();
+ timer.start();
for (int j = 0; j < NUM_RUNS[i]; ++j) {
SSD_POLYGON ssd;
VD_BOOST vd;
@@ -129,22 +133,24 @@
int32 dx = (gen() & 1023) + 1;
int32 dy = (gen() & 1023) + 1;
ssd.push_back(SEGMENT_POLYGON(
- POINT_POLYGON(x1, y1), POINT_POLYGON(x1 + dx, y1 + dy)));
+ POINT_POLYGON(x1, y1),
+ POINT_POLYGON(x1 + dx, y1 + dy)));
}
- clean_segment_set(ssd);
+ clean_segment_set(&ssd);
boost::polygon::construct_voronoi(ssd.begin(), ssd.end(), &vd);
}
- double time_per_test = (timer.elapsed() - running_times[i]) / NUM_RUNS[i];
+ double time_per_test =
+ (get_elapsed_secs() - running_times[i]) / NUM_RUNS[i];
format_line(NUM_SEGMENTS[i], NUM_RUNS[i], time_per_test);
}
bf << "\n";
}
-void run_cgal_test(const std::vector<double> &running_times) {
+void run_cgal_delaunay_test(const std::vector<double> &running_times) {
boost::mt19937 gen(RANDOM_SEED);
bf << "CGAL Triangulation of Segments:\n";
for (int i = 0; i < NUM_TESTS; ++i) {
- timer.restart();
+ timer.start();
for (int j = 0; j < NUM_RUNS[i]; ++j) {
SSD_POLYGON ssd;
for (int k = 0; k < NUM_SEGMENTS[i]; ++k) {
@@ -152,18 +158,37 @@
int32 y1 = gen();
int32 dx = (gen() & 1023) + 1;
int32 dy = (gen() & 1023) + 1;
- ssd.push_back(SEGMENT_POLYGON(POINT_POLYGON(x1, y1),
- POINT_POLYGON(x1 + dx, y1 + dy)));
+ ssd.push_back(SEGMENT_POLYGON(
+ POINT_POLYGON(x1, y1),
+ POINT_POLYGON(x1 + dx, y1 + dy)));
}
- clean_segment_set(ssd);
- SDT_CGAL dt;
+ clean_segment_set(&ssd);
+
+ typedef std::vector<Point_CGAL> Points_container;
+ typedef std::vector<Points_container>::size_type Index_type;
+ typedef std::vector< std::pair<Index_type, Index_type> > Constraints_container;
+ Points_container points;
+ Constraints_container constraints;
+ points.reserve(ssd.size() * 2);
+ constraints.reserve(ssd.size());
for (SSD_POLYGON::iterator it = ssd.begin(); it != ssd.end(); ++it) {
- dt.insert(Site_CGAL::construct_site_2(
- Point_CGAL(it->low().x(), it->low().y()),
- Point_CGAL(it->high().x(), it->high().y())));
+ points.push_back(Point_CGAL(
+ boost::polygon::x(it->low()),
+ boost::polygon::y(it->low())));
+ points.push_back(Point_CGAL(
+ boost::polygon::x(it->high()),
+ boost::polygon::y(it->high())));
+ constraints.push_back(
+ std::make_pair(points.size() - 2, points.size() - 1));
}
+
+ SDT_CGAL sdg;
+ sdg.insert_segments(
+ points.begin(), points.end(),
+ constraints.begin(), constraints.end());
}
- double time_per_test = (timer.elapsed() - running_times[i]) / NUM_RUNS[i];
+ double time_per_test =
+ (get_elapsed_secs() - running_times[i]) / NUM_RUNS[i];
format_line(NUM_SEGMENTS[i], NUM_RUNS[i], time_per_test);
}
bf << "\n";
@@ -173,8 +198,8 @@
bf << std::setiosflags(std::ios::right | std::ios::fixed)
<< std::setprecision(6);
std::vector<double> running_times = get_intersection_runtime();
- run_voronoi_test(running_times);
- run_cgal_test(running_times);
+ run_boost_voronoi_test(running_times);
+ run_cgal_delaunay_test(running_times);
bf.close();
return 0;
}
Modified: branches/release/libs/polygon/doc/gtl_polygon_90_set_concept.htm
Modified: branches/release/libs/polygon/test/Jamfile.v2
Modified: branches/release/libs/polygon/test/gtl_boost_unit_test.cpp
Modified: branches/release/libs/polygon/test/voronoi_predicates_test.cpp
Modified: branches/release/libs/polygon/test/voronoi_structures_test.cpp
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk
==============================================================================
--- branches/release/libs/polygon/doc/gtl_polygon_90_set_concept.htm Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/libs/polygon/doc/gtl_polygon_90_set_concept.htm 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -1,28 +1,18 @@
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
-<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"
- xmlns:v="urn:schemas-microsoft-com:vml"
- xmlns:o="urn:schemas-microsoft-com:office:office"
- xmlns:(null)1="http://www.w3.org/TR/REC-html40" lang="en">
-<head>
-<!--
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:(null)1="http://www.w3.org/TR/REC-html40" lang="en"><head><!--
Copyright 2009-2010 Intel Corporation
license banner
--->
- <title>Boost Polygon Library: Polygon 90 Set Concept</title>
- <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" />
-<!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> -->
-</head>
-<body>
-<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0"
- cellpadding="0" cellspacing="0">
+--><title>Boost Polygon Library: Polygon 90 Set Concept</title>
+
+
+
+
+ <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" /><!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> --></head><body>
+<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
<tbody>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1"
- valign="top">
- <div style="padding: 5px;" align="center"> <img
- src="images/boost.png" border="0" height="86" width="277" /><a
- title="www.boost.org home page" href="http://www.boost.org/"
- tabindex="2" style="border: medium none ;"> </a> </div>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277" /><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;"> </a> </div>
<div style="margin: 5px;">
<h3 class="navbar">Contents</h3>
<ul>
@@ -77,14 +67,9 @@
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
- <div style="padding: 5px;" align="center"> <img
- src="images/intlogo.gif" border="0" height="51" width="127" /><a
- title="www.adobe.com home page" href="http://www.adobe.com/"
- tabindex="2" style="border: medium none ;"> </a> </div>
+ <div style="padding: 5px;" align="center"> <img src="images/intlogo.gif" border="0" height="51" width="127" /><a title="www.adobe.com home page" href="http://www.adobe.com/" tabindex="2" style="border: medium none ;"> </a> </div>
</td>
- <td
- style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
- valign="top" width="100%">
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
<!-- End Header --><br />
<p>
</p>
@@ -110,16 +95,13 @@
polygon_90_with_holes_concept or rectangle_concept are automatically
models of polygon_90_set_concept.</p>
<h2>Operators</h2>
- <p>The return type of some operators is the <font
- face="Courier New">polygon_90_set_view</font> operator template
+ <p>The return type of some operators is the <font face="Courier New">polygon_90_set_view</font> operator template
type. This type is itself a model of the polygon_90_set concept,
-but furthermore can be used as an argument to the <font
- face="Courier New">polygon_90_set_data</font> constructor and
+but furthermore can be used as an argument to the <font face="Courier New">polygon_90_set_data</font> constructor and
assignment operator. The operator template exists to eliminate
temp copies of intermediate results when Boolean operators are chained
together.</p>
- <p>Operators are declared inside the namespace <font
- face="Courier New">boost::polygon::operators</font>.</p>
+ <p>Operators are declared inside the namespace <font face="Courier New">boost::polygon::operators</font>.</p>
<table id="table3" border="1" width="100%">
<tbody>
<tr>
@@ -773,6 +755,22 @@
complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
+ <td style="vertical-align: top;"><font face="Courier New">template
+<typename output_container><br />
+void <b>get</b>(output_container& output, size_t k) const</font></td>
+ <td style="vertical-align: top;">Expects a standard
+container of geometry objects. Will scan and eliminate
+overlaps. Converts polygon set geometry to objects of that type
+and appends them to the container. The resulting polygons will
+have at most k vertices. For Manhattan data k should be at least 4 .
+Polygons will be output with counterclockwise winding, hole polygons
+will be output with clockwise winding. The last vertex of an
+output polygon is not the duplicate of the first, and the number of
+points is equal to the number of edges. O( n log n) runtime
+complexity and O(n) memory wrt vertices + intersections.<br />
+ </td>
+ </tr>
+<tr>
<td width="586"><font face="Courier New">template
<typename output_container><br />
void <b>get_polygons</b>(output_container& output) const</font></td>
@@ -915,8 +913,7 @@
</tr>
<tr>
<td width="586"><font face="Courier New">polygon_90_set_data&
- <b>move</b>(coordinate_type x_delta, <br />
-
+ <b>move</b>(coordinate_type x_delta, <br />
coordinate_type y_delta) </font> </td>
<td>Add x_delta to x values and y_delta to y values of
vertices stored within the polygon set. Linear wrt. vertices.</td>
@@ -985,14 +982,10 @@
</td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1"
- valign="top"> </td>
- <td
- style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
- valign="top" width="100%">
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
<table class="docinfo" id="table4" frame="void" rules="none">
- <colgroup> <col class="docinfo-name" /><col
- class="docinfo-content" /> </colgroup> <tbody valign="top">
+ <colgroup> <col class="docinfo-name" /><col class="docinfo-content" /> </colgroup> <tbody valign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
<td>Copyright © Intel Corporation 2008-2010.</td>
@@ -1000,10 +993,7 @@
<tr class="field">
<th class="docinfo-name">License:</th>
<td class="field-body">Distributed under the Boost Software
-License, Version 1.0. (See accompanying file <tt class="literal"> <span
- class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
- class="reference" target="_top"
- href="http://www.boost.org/LICENSE_1_0.txt">
+License, Version 1.0. (See accompanying file <tt class="literal"> <span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
http://www.boost.org/LICENSE_1_0.txt>)</td>
</tr>
</tbody>
@@ -1012,5 +1002,5 @@
</tr>
</tbody>
</table>
-</body>
-</html>
+
+</body></html>
\ No newline at end of file
==============================================================================
--- branches/release/libs/polygon/test/Jamfile.v2 Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/libs/polygon/test/Jamfile.v2 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -24,6 +24,11 @@
[ run gtl_boost_unit_test.cpp ]
;
+test-suite skeleton-unit
+ :
+ [ run skeleton_predicates_test.cpp ]
+ ;
+
test-suite voronoi-unit
:
[ run voronoi_builder_test.cpp ]
==============================================================================
--- branches/release/libs/polygon/test/gtl_boost_unit_test.cpp Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/libs/polygon/test/gtl_boost_unit_test.cpp 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -6,7 +6,7 @@
http://www.boost.org/LICENSE_1_0.txt).
*/
#include <iostream>
-//#define BOOST_POLYGON_NO_DEPS
+#define BOOST_POLYGON_NO_DEPS
#include <boost/polygon/polygon.hpp>
namespace gtl = boost::polygon;
@@ -2221,6 +2221,239 @@
return gtl::equivalence(rect, rect2);
}
+/*************New Polygon Formation Tests********************/
+/*
+ *
+ * Test Input:
+ * +--------------------+
+ * | +-------+ |
+ * | | | |
+ * | | | |
+ * +-----+ | | |
+ * | | | |
+ * | | | |
+ * +-----+ | | |
+ * | | | |
+ * | | | |
+ * | +-------+ |
+ * +--------+ |
+ * | |
+ * | |
+ * +--------+ |
+ * | |
+ * | |
+ * +--------+ |
+ * | |
+ * | |
+ * +--------+ |
+ * | |
+ * | |
+ * +--------------------+
+ *
+ * Test Plan:
+ * a. call 'get(out, param)' , param >=4
+ * b. check if each polygon in the container is <= param
+ * c. check the area of all the pieces sum up to original piece
+ */
+typedef int intDC;
+typedef boost::polygon::polygon_90_with_holes_data<intDC> GTLPolygon;
+typedef boost::polygon::polygon_90_set_data<intDC> GTLPolygonSet;
+typedef boost::polygon::polygon_90_concept GTLPolygonConcept;
+typedef boost::polygon::point_data<intDC> GTLPoint;
+inline void PrintPolygon(const GTLPolygon&);
+inline GTLPolygon CreateGTLPolygon(const int*, size_t);
+int test_new_polygon_formation(int argc, char** argv){
+ // //
+ // Sub-Test-1: do a Boolean and call the new get //
+ // //
+ int coordinates[] = {0,0, 10,0, 10,10, 0,10};
+ int coordinates1[] = {9,1, 20,1, 20,10, 9,10};
+ std::vector<GTLPoint> pts;
+ size_t count = sizeof(coordinates)/(2*sizeof(intDC));
+ size_t count1 = sizeof(coordinates1)/(2*sizeof(intDC));
+ GTLPolygon poly, poly1;
+ GTLPolygonSet polySet;
+
+ poly = CreateGTLPolygon(coordinates, count);
+ poly1 = CreateGTLPolygon(coordinates1, count1);
+
+ polySet.insert(poly);
+ polySet.insert(poly1);
+
+ std::vector<GTLPolygon> result;
+ polySet.get(result, 100);
+
+ if(result.size() > 1){
+ std::cerr << "FAILED: expecting only one polygon because the"
+ " threshold is 100" << std::endl;
+ return 1;
+ }
+
+ if(result[0].size() != 6){
+ std::cerr << "FAILED: expecting only 6 vertices" << std::endl;
+ return 1;
+ }
+
+ if(area(result[0]) != 190){
+ std::cerr <<"FAILED: expecting only 6 vertices" << std::endl;
+ return 1;
+ }
+
+ //expect no more than 1 polygon
+ std::cout << "Found " << result.size() << "polygons after union"
+ << std::endl;
+ for(size_t i=0; i<result.size(); i++){
+ PrintPolygon(result[i]);
+ }
+
+ intDC shell_coords[] = {0,0, 10,0, 10,21, 0,21, 0,15, 3,15, 3,13,
+ 0,13, 0,10, 5,10, 5,8, 0,8, 0,5, 5,5, 5,3, 0,3};
+ intDC hole_coords[] = {4,11, 7,11, 7,19, 4,19};
+ GTLPolygon slice_polygon, slice_hole;
+ count = sizeof(shell_coords)/(2*sizeof(intDC));
+ count1 = sizeof(hole_coords)/(2*sizeof(intDC));
+
+ slice_polygon = CreateGTLPolygon(shell_coords, count);
+ slice_hole = CreateGTLPolygon(hole_coords, count1);
+
+ result.clear();
+ polySet.clear();
+ polySet.insert(slice_polygon);
+ polySet.insert(slice_hole, true);
+
+ polySet.get(result);
+ double gold_area = 0;
+ std::cout << "Found " << result.size() << " slices" << std::endl;
+ for(size_t i=0; i<result.size(); i++){
+ PrintPolygon(result[i]);
+ gold_area += area(result[i]);
+ }
+
+ result.clear();
+ polySet.get(result, 6);
+ double platinum_area = 0;
+ std::cout << "Found " << result.size() << " slices" << std::endl;
+ for(size_t i=0; i<result.size(); i++){
+ PrintPolygon(result[i]);
+ platinum_area += area(result[i]);
+ if(result[i].size() > 6){
+ std::cerr << "FAILED: expecting size to be less than 6" << std::endl;
+ return 1;
+ }
+ }
+
+ std::cout << "platinum_area = " << platinum_area << " , gold_area="
+ << gold_area << std::endl;
+ if( platinum_area != gold_area){
+ std::cerr << "FAILED: Area mismatch" << std::endl;
+ return 1;
+ }
+ std::cout << "[SUB-TEST-1] PASSED\n";
+
+ result.clear();
+ polySet.get(result, 4);
+ platinum_area = 0;
+ std::cout << "Found " << result.size() << " slices" << std::endl;
+ for(size_t i=0; i<result.size(); i++){
+ PrintPolygon(result[i]);
+ platinum_area += area(result[i]);
+ if(result[i].size() > 4){
+ std::cerr << "FAILED: expecting size to be < 4" << std::endl;
+ return 1;
+ }
+ }
+
+ std::cout << "platinum_area=" << platinum_area << ", gold_area="
+ << gold_area << std::endl;
+
+ if( platinum_area != gold_area){
+ std::cerr << "FAILED: Area mismatch" << std::endl;
+ return 1;
+ }
+
+ std::cout << "[SUB-TEST-1] PASSED" << std::endl;
+ return 0;
+}
+
+/*
+ * INPUT:
+ * +--------+
+ * | |
+ * | |
+ * | +---+
+ * | |
+ * | +---+
+ * | |
+ * +--------+
+ * X
+ *
+ * TEST PLAN: as the sweepline moves and reaches
+ * X the number of vertices in the solid jumps by 4
+ * instead of 2. So make sure we don't get a 6 vertex
+ * polygon when the threshold is 4 and 6.
+ */
+int test_new_polygon_formation_marginal_threshold(int argc, char**){
+ std::vector<GTLPoint> pts;
+ GTLPolygon polygon;
+ GTLPolygonSet pset;
+ std::vector<GTLPolygon> result;
+ intDC coords[] = {0,0, 15,0, 15,10, 10,10, 10,15, 5,15, 5,10, 0,10};
+ size_t count = sizeof(coords)/(2*sizeof(intDC));
+
+ polygon = CreateGTLPolygon(coords, count);
+ pset.insert(polygon);
+
+ for(size_t i=0; i<1; i++){
+ pset.get(result, i ? 4 : 6);
+ double gold_area = 175, plat_area = 0;
+ for(size_t i=0; i<result.size(); i++){
+ if(result[i].size() > (i ? 4 : 6) ){
+ size_t expected = i ? 4 : 6;
+ std::cerr << "FAILED: Expecting no more than " <<
+ expected << " vertices" << std::endl;
+ return 1;
+ }
+ PrintPolygon(result[i]);
+ plat_area += area(result[i]);
+ }
+
+ if(plat_area != gold_area){
+ std::cerr << "FAILED area mismatch gold=" << gold_area <<
+ " plat=" << plat_area << std::endl;
+ return 1;
+ }
+ }
+ std::cout << "Test Passed" << std::endl;
+ return 0;
+}
+
+inline void PrintPolygon(const GTLPolygon& p){
+ //get an iterator of the point_data<int>
+ boost::polygon::point_data<int> pt;
+ boost::polygon::polygon_90_data<int>::iterator_type itr;
+
+ size_t vertex_id = 0;
+ for(itr = p.begin(); itr != p.end(); ++itr){
+ pt = *itr;
+ std::cout << "Vertex-" << ++vertex_id << "(" << pt.x() <<
+ "," << pt.y() << ")" << std::endl;
+ }
+}
+
+// size: is the number of vertices //
+inline GTLPolygon CreateGTLPolygon(const int *coords, size_t size){
+ GTLPolygon r;
+ std::vector<GTLPoint> pts;
+
+ for(size_t i=0; i<size; i++){
+ pts.push_back( GTLPoint(coords[2*i], coords[2*i+1]) );
+ }
+ boost::polygon::set_points(r, pts.begin(), pts.end());
+ return r;
+}
+
+/************************************************************/
+
int main() {
test_view_as();
//this test fails and I'd like to get it to pass
@@ -3615,6 +3848,19 @@
assert_s(segs.size() == 4, "intersection3");
}
+
+ /*New polygon_formation tests*/
+ if(test_new_polygon_formation(0,NULL)){
+ std::cerr << "[test_new_polygon_formation] failed" << std::endl;
+ return 1;
+ }
+
+ if(test_new_polygon_formation_marginal_threshold(0,NULL)){
+ std::cerr << "[test_new_polygon_formation_marginal_threshold] failed"
+ << std::endl;
+ return 1;
+ }
+
std::cout << "ALL TESTS COMPLETE\n";
return 0;
}
==============================================================================
--- branches/release/libs/polygon/test/voronoi_predicates_test.cpp Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/libs/polygon/test/voronoi_predicates_test.cpp 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -55,8 +55,8 @@
BOOST_CHECK_EQUAL(event_comparison(A, B), R1); \
BOOST_CHECK_EQUAL(event_comparison(B, A), R2)
-#define CHECK_DISTANCE_PREDICATE(S1, S2, S3, RES) \
- BOOST_CHECK_EQUAL(distance_predicate(S1, S2, S3), RES)
+#define CHECK_DISTANCE_PREDICATE(S1, S2, P3, RES) \
+ BOOST_CHECK_EQUAL(distance_predicate(S1, S2, P3), RES)
#define CHECK_NODE_COMPARISON(node, nodes, res, sz) \
for (int i = 0; i < sz; ++i) { \
@@ -140,102 +140,119 @@
BOOST_AUTO_TEST_CASE(distance_predicate_test1) {
site_type site1(-5, 0);
+ site1.sorted_index(1);
site_type site2(-8, 9);
+ site2.sorted_index(0);
site_type site3(-2, 1);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 5), false);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 5), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 4), false);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 4), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 6), true);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 6), true);
+ site3.sorted_index(2);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 5), false);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, 5), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 4), false);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, 4), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 6), true);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, 6), true);
}
BOOST_AUTO_TEST_CASE(distance_predicate_test2) {
site_type site1(-4, 0, -4, 20);
+ site1.sorted_index(0);
site_type site2(-2, 10);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 11), false);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 9), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 11), true);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 9), true);
+ site2.sorted_index(1);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 11), false);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 9), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 11), true);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 9), true);
}
BOOST_AUTO_TEST_CASE(disntace_predicate_test3) {
site_type site1(-5, 5, 2, -2);
+ site1.sorted_index(0);
site1.inverse();
site_type site2(-2, 4);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -1), false);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -1), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 1), false);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 1), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 4), true);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 4), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 5), true);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 5), false);
+ site2.sorted_index(1);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, -1), false);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, -1), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 1), false);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 1), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 4), true);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 4), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 5), true);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 5), false);
}
BOOST_AUTO_TEST_CASE(distance_predicate_test4) {
site_type site1(-5, 5, 2, -2);
+ site1.sorted_index(0);
site_type site2(-2, -4);
+ site2.sorted_index(2);
site_type site3(-4, 1);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, 1), true);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, 1), true);
- CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, 1), true);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, 1), true);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -2), true);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -2), false);
- CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, -2), true);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, -2), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -8), true);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -8), false);
- CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, -8), true);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, -8), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(0, -9), true);
- CHECK_DISTANCE_PREDICATE(site2, site1, site_type(0, -9), false);
- CHECK_DISTANCE_PREDICATE(site1, site3, site_type(0, -9), true);
- CHECK_DISTANCE_PREDICATE(site3, site1, site_type(0, -9), false);
+ site3.sorted_index(1);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, 1), true);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, 1), true);
+ CHECK_DISTANCE_PREDICATE(site1, site3, point_type(0, 1), true);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, 1), true);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, -2), true);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, -2), false);
+ CHECK_DISTANCE_PREDICATE(site1, site3, point_type(0, -2), true);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, -2), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, -8), true);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, -8), false);
+ CHECK_DISTANCE_PREDICATE(site1, site3, point_type(0, -8), true);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, -8), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(0, -9), true);
+ CHECK_DISTANCE_PREDICATE(site2, site1, point_type(0, -9), false);
+ CHECK_DISTANCE_PREDICATE(site1, site3, point_type(0, -9), true);
+ CHECK_DISTANCE_PREDICATE(site3, site1, point_type(0, -9), false);
}
BOOST_AUTO_TEST_CASE(disntace_predicate_test5) {
site_type site1(-5, 5, 2, -2);
+ site1.sorted_index(0);
site_type site2 = site1;
site2.inverse();
site_type site3(-2, 4);
+ site3.sorted_index(3);
site_type site4(-2, -4);
+ site4.sorted_index(2);
site_type site5(-4, 1);
- CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 1), false);
- CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 4), false);
- CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 5), false);
- CHECK_DISTANCE_PREDICATE(site3, site2, site_type(0, 7), true);
- CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -2), false);
- CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -2), false);
- CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -8), false);
- CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -8), false);
- CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -9), false);
- CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -9), false);
- CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -18), false);
- CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -18), false);
- CHECK_DISTANCE_PREDICATE(site4, site1, site_type(0, -1), true);
- CHECK_DISTANCE_PREDICATE(site5, site1, site_type(0, -1), true);
+ site5.sorted_index(1);
+ CHECK_DISTANCE_PREDICATE(site3, site2, point_type(0, 1), false);
+ CHECK_DISTANCE_PREDICATE(site3, site2, point_type(0, 4), false);
+ CHECK_DISTANCE_PREDICATE(site3, site2, point_type(0, 5), false);
+ CHECK_DISTANCE_PREDICATE(site3, site2, point_type(0, 7), true);
+ CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -2), false);
+ CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -2), false);
+ CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -8), false);
+ CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -8), false);
+ CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -9), false);
+ CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -9), false);
+ CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -18), false);
+ CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -18), false);
+ CHECK_DISTANCE_PREDICATE(site4, site1, point_type(0, -1), true);
+ CHECK_DISTANCE_PREDICATE(site5, site1, point_type(0, -1), true);
}
BOOST_AUTO_TEST_CASE(distance_predicate_test6) {
site_type site1(-5, 0, 2, 7);
site_type site2 = site1;
site2.inverse();
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(2, 7), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(1, 5), false);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(-1, 5), true);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(2, 7), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(1, 5), false);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(-1, 5), true);
}
BOOST_AUTO_TEST_CASE(distance_predicate_test7) {
site_type site1(-5, 5, 2, -2);
+ site1.sorted_index(1);
site1.inverse();
site_type site2(-5, 5, 0, 6);
+ site2.sorted_index(0);
site_type site3(-2, 4, 0, 4);
- site_type site4(0, 2);
- site_type site5(0, 5);
- site_type site6(0, 6);
- site_type site7(0, 8);
+ site3.sorted_index(2);
+ point_type site4(0, 2);
+ point_type site5(0, 5);
+ point_type site6(0, 6);
+ point_type site7(0, 8);
CHECK_DISTANCE_PREDICATE(site1, site2, site4, false);
CHECK_DISTANCE_PREDICATE(site1, site2, site5, true);
CHECK_DISTANCE_PREDICATE(site1, site2, site6, true);
@@ -251,11 +268,13 @@
CHECK_DISTANCE_PREDICATE(site3, site1, site7, true);
}
-BOOST_AUTO_TEST_CASE(distatnce_predicate_test8) {
+BOOST_AUTO_TEST_CASE(distance_predicate_test8) {
site_type site1(-5, 3, -2, 2);
+ site1.sorted_index(0);
site1.inverse();
site_type site2(-5, 5, -2, 2);
- CHECK_DISTANCE_PREDICATE(site1, site2, site_type(-4, 2), false);
+ site2.sorted_index(1);
+ CHECK_DISTANCE_PREDICATE(site1, site2, point_type(-4, 2), false);
}
BOOST_AUTO_TEST_CASE(node_comparison_test1) {
@@ -377,8 +396,11 @@
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test1) {
site_type site1(0, 0);
+ site1.sorted_index(1);
site_type site2(-8, 0);
+ site2.sorted_index(0);
site_type site3(0, 6);
+ site3.sorted_index(2);
CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, -4.0, 3.0, 1.0);
}
@@ -386,78 +408,109 @@
int min_int = (std::numeric_limits<int>::min)();
int max_int = (std::numeric_limits<int>::max)();
site_type site1(min_int, min_int);
+ site1.sorted_index(0);
site_type site2(min_int, max_int);
+ site2.sorted_index(1);
site_type site3(max_int-1, max_int-1);
+ site3.sorted_index(2);
site_type site4(max_int, max_int);
+ site4.sorted_index(3);
CHECK_CIRCLE_EXISTENCE(site1, site2, site4, true);
CHECK_CIRCLE_EXISTENCE(site1, site3, site4, false);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test3) {
site_type site1(-4, 0);
+ site1.sorted_index(0);
site_type site2(0, 4);
+ site2.sorted_index(4);
site_type site3(site1.point0(), site2.point0());
+ site3.sorted_index(1);
CHECK_CIRCLE_EXISTENCE(site1, site3, site2, false);
site_type site4(-2, 0);
+ site4.sorted_index(2);
site_type site5(0, 2);
+ site5.sorted_index(3);
CHECK_CIRCLE_EXISTENCE(site3, site4, site5, false);
CHECK_CIRCLE_EXISTENCE(site4, site5, site3, false);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test4) {
site_type site1(-4, 0, -4, 20);
+ site1.sorted_index(0);
site_type site2(-2, 10);
+ site2.sorted_index(1);
site_type site3(4, 10);
+ site3.sorted_index(2);
CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 1.0, 6.0, 6.0);
CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 14.0, 6.0);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test5) {
site_type site1(1, 0, 7, 0);
+ site1.sorted_index(2);
site1.inverse();
site_type site2(-2, 4, 10, 4);
+ site2.sorted_index(0);
site_type site3(6, 2);
+ site3.sorted_index(3);
site_type site4(1, 0);
+ site4.sorted_index(1);
CHECK_CIRCLE_FORMATION_PREDICATE(site3, site1, site2, 4.0, 2.0, 6.0);
CHECK_CIRCLE_FORMATION_PREDICATE(site4, site2, site1, 1.0, 2.0, 3.0);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test6) {
site_type site1(-1, 2, 8, -10);
+ site1.sorted_index(1);
site1.inverse();
site_type site2(-1, 0, 8, 12);
+ site2.sorted_index(0);
site_type site3(1, 1);
+ site3.sorted_index(2);
CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 6.0, 1.0, 11.0);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test7) {
site_type site1(1, 0, 6, 0);
+ site1.sorted_index(2);
site1.inverse();
site_type site2(-6, 4, 0, 12);
+ site2.sorted_index(0);
site_type site3(1, 0);
+ site3.sorted_index(1);
CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 5.0, 6.0);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test8) {
site_type site1(1, 0, 5, 0);
+ site1.sorted_index(2);
site1.inverse();
site_type site2(0, 12, 8, 6);
+ site2.sorted_index(0);
site_type site3(1, 0);
+ site3.sorted_index(1);
CHECK_CIRCLE_FORMATION_PREDICATE(site3, site2, site1, 1.0, 5.0, 6.0);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test9) {
site_type site1(0, 0, 4, 0);
+ site1.sorted_index(1);
site_type site2(0, 0, 0, 4);
+ site2.sorted_index(0);
site_type site3(0, 4, 4, 4);
+ site3.sorted_index(2);
site1.inverse();
CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 2.0, 2.0, 4.0);
}
BOOST_AUTO_TEST_CASE(circle_formation_predicate_test10) {
site_type site1(1, 0, 41, 30);
+ site1.sorted_index(1);
site_type site2(-39, 30, 1, 60);
+ site2.sorted_index(0);
site_type site3(1, 60, 41, 30);
+ site3.sorted_index(2);
site1.inverse();
CHECK_CIRCLE_FORMATION_PREDICATE(site1, site2, site3, 1.0, 30.0, 25.0);
}
==============================================================================
--- branches/release/libs/polygon/test/voronoi_structures_test.cpp Sun Sep 29 14:11:30 2013 (r86008)
+++ branches/release/libs/polygon/test/voronoi_structures_test.cpp 2013-09-29 14:44:35 EDT (Sun, 29 Sep 2013) (r86009)
@@ -27,12 +27,12 @@
BOOST_AUTO_TEST_CASE(point_2d_test1) {
point_type p(1, 2);
- BOOST_CHECK_EQUAL(p.x(), 1);
- BOOST_CHECK_EQUAL(p.y(), 2);
+ BOOST_CHECK_EQUAL(1, p.x());
+ BOOST_CHECK_EQUAL(2, p.y());
p.x(3);
- BOOST_CHECK_EQUAL(p.x(), 3);
+ BOOST_CHECK_EQUAL(3, p.x());
p.y(4);
- BOOST_CHECK_EQUAL(p.y(), 4);
+ BOOST_CHECK_EQUAL(4, p.y());
}
BOOST_AUTO_TEST_CASE(site_event_test1) {
@@ -40,14 +40,16 @@
s.sorted_index(1);
s.initial_index(2);
s.source_category(SOURCE_CATEGORY_SEGMENT_START_POINT);
- BOOST_CHECK(s.x0() == 1 && s.x1() == 1);
- BOOST_CHECK(s.y0() == 2 && s.y1() == 2);
+ BOOST_CHECK_EQUAL(1, s.x0());
+ BOOST_CHECK_EQUAL(1, s.x1());
+ BOOST_CHECK_EQUAL(2, s.y0());
+ BOOST_CHECK_EQUAL(2, s.y1());
BOOST_CHECK(s.is_point());
BOOST_CHECK(!s.is_segment());
BOOST_CHECK(!s.is_inverse());
- BOOST_CHECK(s.sorted_index() == 1);
- BOOST_CHECK(s.initial_index() == 2);
- BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_SEGMENT_START_POINT);
+ BOOST_CHECK_EQUAL(1, s.sorted_index());
+ BOOST_CHECK_EQUAL(2, s.initial_index());
+ BOOST_CHECK_EQUAL(SOURCE_CATEGORY_SEGMENT_START_POINT, s.source_category());
}
BOOST_AUTO_TEST_CASE(site_event_test2) {
@@ -55,38 +57,38 @@
s.sorted_index(1);
s.initial_index(2);
s.source_category(SOURCE_CATEGORY_INITIAL_SEGMENT);
- BOOST_CHECK(s.x0(true) == 1 && s.x0() == 1);
- BOOST_CHECK(s.y0(true) == 2 && s.y0() == 2);
- BOOST_CHECK(s.x1(true) == 3 && s.x1() == 3);
- BOOST_CHECK(s.y1(true) == 4 && s.y1() == 4);
+ BOOST_CHECK_EQUAL(1, s.x0());
+ BOOST_CHECK_EQUAL(2, s.y0());
+ BOOST_CHECK_EQUAL(3, s.x1());
+ BOOST_CHECK_EQUAL(4, s.y1());
BOOST_CHECK(!s.is_point());
BOOST_CHECK(s.is_segment());
BOOST_CHECK(!s.is_inverse());
- BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_INITIAL_SEGMENT);
+ BOOST_CHECK_EQUAL(SOURCE_CATEGORY_INITIAL_SEGMENT, s.source_category());
s.inverse();
- BOOST_CHECK(s.x1(true) == 1 && s.x0() == 1);
- BOOST_CHECK(s.y1(true) == 2 && s.y0() == 2);
- BOOST_CHECK(s.x0(true) == 3 && s.x1() == 3);
- BOOST_CHECK(s.y0(true) == 4 && s.y1() == 4);
+ BOOST_CHECK_EQUAL(3, s.x0());
+ BOOST_CHECK_EQUAL(4, s.y0());
+ BOOST_CHECK_EQUAL(1, s.x1());
+ BOOST_CHECK_EQUAL(2, s.y1());
BOOST_CHECK(s.is_inverse());
- BOOST_CHECK(s.source_category() == SOURCE_CATEGORY_INITIAL_SEGMENT);
+ BOOST_CHECK_EQUAL(SOURCE_CATEGORY_INITIAL_SEGMENT, s.source_category());
}
BOOST_AUTO_TEST_CASE(circle_event_test) {
circle_type c(0, 1, 2);
- BOOST_CHECK_EQUAL(c.x(), 0);
- BOOST_CHECK_EQUAL(c.y(), 1);
- BOOST_CHECK_EQUAL(c.lower_x(), 2);
- BOOST_CHECK_EQUAL(c.lower_y(), 1);
+ BOOST_CHECK_EQUAL(0, c.x());
+ BOOST_CHECK_EQUAL(1, c.y());
+ BOOST_CHECK_EQUAL(2, c.lower_x());
+ BOOST_CHECK_EQUAL(1, c.lower_y());
BOOST_CHECK(c.is_active());
c.x(3);
c.y(4);
c.lower_x(5);
- BOOST_CHECK_EQUAL(c.x(), 3);
- BOOST_CHECK_EQUAL(c.y(), 4);
- BOOST_CHECK_EQUAL(c.lower_x(), 5);
- BOOST_CHECK_EQUAL(c.lower_y(), 4);
+ BOOST_CHECK_EQUAL(3, c.x());
+ BOOST_CHECK_EQUAL(4, c.y());
+ BOOST_CHECK_EQUAL(5, c.lower_x());
+ BOOST_CHECK_EQUAL(4, c.lower_y());
c.deactivate();
BOOST_CHECK(!c.is_active());
}
@@ -101,20 +103,20 @@
*vi[i] <<= 1;
BOOST_CHECK(!q.empty());
for (int i = 0; i < 20; ++i, q.pop())
- BOOST_CHECK_EQUAL(q.top(), i << 1);
+ BOOST_CHECK_EQUAL(i << 1, q.top());
BOOST_CHECK(q.empty());
}
BOOST_AUTO_TEST_CASE(beach_line_node_key_test) {
node_key_type key(1);
- BOOST_CHECK_EQUAL(key.left_site(), 1);
- BOOST_CHECK_EQUAL(key.right_site(), 1);
+ BOOST_CHECK_EQUAL(1, key.left_site());
+ BOOST_CHECK_EQUAL(1, key.right_site());
key.left_site(2);
- BOOST_CHECK_EQUAL(key.left_site(), 2);
- BOOST_CHECK_EQUAL(key.right_site(), 1);
+ BOOST_CHECK_EQUAL(2, key.left_site());
+ BOOST_CHECK_EQUAL(1, key.right_site());
key.right_site(3);
- BOOST_CHECK_EQUAL(key.left_site(), 2);
- BOOST_CHECK_EQUAL(key.right_site(), 3);
+ BOOST_CHECK_EQUAL(2, key.left_site());
+ BOOST_CHECK_EQUAL(3, key.right_site());
}
BOOST_AUTO_TEST_CASE(beach_line_node_data_test) {