diff options
author | Rafael Laboissière <rafael@debian.org> | 2020-02-09 05:51:46 -0300 |
---|---|---|
committer | Rafael Laboissière <rafael@debian.org> | 2020-02-09 05:51:46 -0300 |
commit | a45e15f167ef0a7cba3e9ed572209f3522658320 (patch) | |
tree | 481982ed20977db86d2e3309ee5e709da54e2b79 /src/polygon.cpp | |
parent | 87f1c69f10eb490ae5bdfbd551ba386b58e199e3 (diff) |
New upstream version 4.0.0
Diffstat (limited to 'src/polygon.cpp')
-rw-r--r-- | src/polygon.cpp | 250 |
1 files changed, 250 insertions, 0 deletions
diff --git a/src/polygon.cpp b/src/polygon.cpp new file mode 100644 index 0000000..63628c5 --- /dev/null +++ b/src/polygon.cpp @@ -0,0 +1,250 @@ +/*************************************************************************** + * Developer: Francisco Martínez del Río (2011) * + * fmartin@ujaen.es * + * Version: 1.4.1 * + * * + * This is a public domain program * + ***************************************************************************/ + +#include "polygon.h" +#include "utilities.h" +#include <limits> +#include <set> +#include <cstdlib> +#include <algorithm> + +void Contour::boundingbox (Point& min, Point& max) +{ + min.x = min.y = numeric_limits<double>::max (); + max.x = max.y = -numeric_limits<double>::max (); + Contour::iterator i = begin(); + while (i != end()) { + if (i->x < min.x) + min.x = i->x; + if (i->x > max.x) + max.x = i->x; + if (i->y < min.y) + min.y = i->y; + if (i->y > max.y) + max.y = i->y; + ++i; + } +} + +bool Contour::counterclockwise () +{ + if (_precomputedCC) + return _CC; + _precomputedCC = true; + double area = 0.0; + for (unsigned int c = 0; c < nvertices () - 1; c++) + area += vertex (c).x * vertex (c+1).y - vertex (c+1).x * vertex (c).y; + area += vertex (nvertices ()-1).x * vertex (0).y - vertex (0).x * vertex (nvertices ()-1).y; + return _CC = area >= 0.0; +} + +void Contour::move (double x, double y) +{ + for (unsigned int i = 0; i < points.size (); i++) { + points[i].x += x; + points[i].y += y; + } +} + + +unsigned Polygon::nvertices () const +{ + unsigned int nv = 0; + for (unsigned int i = 0; i < ncontours (); i++) + nv += contours[i].nvertices (); + return nv; +} + +void Polygon::boundingbox (Point& min, Point& max) +{ + min.x = min.y = numeric_limits<double>::max (); + max.x = max.y = -numeric_limits<double>::max (); + Point mintmp; + Point maxtmp; + for (unsigned int i = 0; i < ncontours (); i++) { + contours[i].boundingbox (mintmp, maxtmp); + if (mintmp.x < min.x) + min.x = mintmp.x; + if (maxtmp.x > max.x) + max.x = maxtmp.x; + if (mintmp.y < min.y) + min.y = mintmp.y; + if (maxtmp.y > max.y) + max.y = maxtmp.y; + } +} + +void Polygon::move (double x, double y) +{ + for (unsigned int i = 0; i < contours.size (); i++) + contours[i].move (x, y); +} + + +/* + * The following code is necessary for implementing the computeHoles member function + * + */ + +namespace { // start of anonymous namespace + struct SweepEvent; + struct SegmentComp : public binary_function<SweepEvent*, SweepEvent*, bool> { + bool operator() (SweepEvent* e1, SweepEvent* e2); + }; + + struct SweepEvent { + Point p; // point associated with the event + bool left; // is the point the left endpoint of the segment (p, other->p)? + int pl; // Polygon to which the associated segment belongs to + SweepEvent* other; // Event associated to the other endpoint of the segment + /** Does the segment (p, other->p) represent an inside-outside transition in the polygon for a vertical ray from (p.x, -infinite) that crosses the segment? */ + bool inOut; + set<SweepEvent*, SegmentComp>::iterator poss; // Only used in "left" events. Position of the event (segment) in S + + /** Class constructor */ + SweepEvent (const Point& pp, bool b, int apl) : p (pp), left (b), pl (apl) {} + /** Return the segment associated to the SweepEvent */ + Segment segment () { return Segment (p, other->p); } + /** Is the segment (p, other->p) below point x */ + bool below (const Point& x) const { return (left) ? signedArea (p, other->p, x) > 0 : signedArea (other->p, p, x) > 0; } + /** Is the segment (p, other->p) above point x */ + bool above (const Point& x) const { return !below (x); } + }; + + struct SweepEventComp : public binary_function<SweepEvent*, SweepEvent*, bool> { + bool operator() (SweepEvent* e1, SweepEvent* e2) { + if (e1->p.x < e2->p.x) // Different x coordinate + return true; + if (e2->p.x < e1->p.x) // Different x coordinate + return false; + if (e1->p != e2->p) // Different points, but same x coordinate. The event with lower y coordinate is processed first + return e1->p.y < e2->p.y; + if (e1->left != e2->left) // Same point, but one is a left endpoint and the other a right endpoint. The right endpoint is processed first + return !e1->left; + // Same point, both events are left endpoints or both are right endpoints. The event associate to the bottom segment is processed first + return e1->below (e2->other->p); + } +}; + +} // end of anonymous namespace + +bool SegmentComp::operator() (SweepEvent* e1, SweepEvent* e2) { + if (e1 == e2) + return false; + if (signedArea (e1->p, e1->other->p, e2->p) != 0 || signedArea (e1->p, e1->other->p, e2->other->p) != 0) { + // Segments are not collinear + // If they share their left endpoint use the right endpoint to sort + if (e1->p == e2->p) + return e1->below (e2->other->p); + // Different points + SweepEventComp comp; + if (comp (e1, e2)) // has the segment associated to e1 been sorted in evp before the segment associated to e2? + return e1->below (e2->p); + // The segment associated to e2 has been sorted in evp before the segment associated to e1 + return e2->above (e1->p); + } + // Segments are collinear. Just a consistent criterion is used + if (e1->p == e2->p) + return e1 < e2; + SweepEventComp comp; + return comp (e1, e2); +} + +//#define _DEBUG_ +void Polygon::computeHoles () +{ + if (ncontours () < 2) { + if (ncontours () == 1 && contour (0).clockwise ()) + contour (0).changeOrientation (); + return; + } + vector<SweepEvent> ev; + vector<SweepEvent*> evp; + ev.reserve (nvertices ()*2); + evp.reserve (nvertices ()*2); + for (unsigned i = 0; i < ncontours (); i++) { +// cout << contour (i); + contour (i).setCounterClockwise (); +// cout << contour (i); + for (unsigned j = 0; j < contour (i).nedges (); j++) { + Segment s = contour(i).segment (j); + if (s.begin ().x == s.end ().x) // vertical segments are not processed + continue; + ev.push_back (SweepEvent (s.begin (), true, i)); + ev.push_back (SweepEvent (s.end (), true, i)); + SweepEvent* se1 = &ev[ev.size ()-2]; + SweepEvent* se2 = &ev[ev.size ()-1]; + se1->other = se2; + se2->other = se1; + if (se1->p.x < se2->p.x) { + se2->left = false; + se1->inOut = false; + } else { + se1->left = false; + se2->inOut = true; + } + evp.push_back (se1); + evp.push_back (se2); + } + } + sort (evp.begin (), evp.end (), SweepEventComp ()); + + set<SweepEvent*, SegmentComp> S; // Status line + vector<bool> processed (ncontours (), false); + vector<int> holeOf (ncontours (), -1); + int nprocessed = 0; + for (unsigned i = 0; i < evp.size () && nprocessed < ncontours (); i++) { + SweepEvent* e = evp[i]; + #ifdef _DEBUG_ + cout << "Process event: " << *e << endl; + #endif + + if (e->left) { // the segment must be inserted into S + e->poss = S.insert(e).first; + if (!processed[e->pl]) { + processed[e->pl] = true; + nprocessed++; + set<SweepEvent*, SegmentComp>::iterator prev = e->poss; + if (prev == S.begin()) { + contour (e->pl).setCounterClockwise (); + } else { + prev--; + if (!(*prev)->inOut) { + holeOf[e->pl] = (*prev)->pl; + contour (e->pl).setExternal (false); + contour ((*prev)->pl).addHole (e->pl); + if (contour((*prev)->pl).counterclockwise ()) + contour (e->pl).setClockwise (); + else + contour (e->pl).setCounterClockwise (); + } else if (holeOf[(*prev)->pl] != -1) { + holeOf[e->pl] = holeOf[(*prev)->pl]; + contour (e->pl).setExternal (false); + contour (holeOf[e->pl]).addHole (e->pl); + if (contour(holeOf[e->pl]).counterclockwise ()) + contour (e->pl).setClockwise (); + else + contour (e->pl).setCounterClockwise (); + } else { + contour (e->pl).setCounterClockwise (); + } + } + } + } else { // the segment must be removed from S + S.erase (e->other->poss); + } + #ifdef _DEBUG_ + cout << "Tras ajuste: " << endl; + for (set<SweepEvent*, SegmentComp>::const_iterator it2 = S.begin(); it2 != S.end(); it2++) + cout << **it2 << endl; + cout << endl; + string st; + getline (cin, st); + #endif + } +} |