summaryrefslogtreecommitdiff
path: root/src/polygon.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/polygon.cpp')
-rw-r--r--src/polygon.cpp250
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
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-30 01:48:54 +0000