1 /***************************************************************************
2 * Developer: Francisco Martínez del Río (2011) *
3 * fmartin@ujaen.es *
4 * Version: 1.4.1 *
5 * *
6 * This is a public domain program *
7 ***************************************************************************/
8
9 #include "polygon.h"
10 #include "utilities.h"
11 #include <limits>
12 #include <set>
13 #include <cstdlib>
14 #include <algorithm>
15
boundingbox(Point & min,Point & max)16 void Contour::boundingbox (Point& min, Point& max)
17 {
18 min.x = min.y = numeric_limits<double>::max ();
19 max.x = max.y = -numeric_limits<double>::max ();
20 Contour::iterator i = begin();
21 while (i != end()) {
22 if (i->x < min.x)
23 min.x = i->x;
24 if (i->x > max.x)
25 max.x = i->x;
26 if (i->y < min.y)
27 min.y = i->y;
28 if (i->y > max.y)
29 max.y = i->y;
30 ++i;
31 }
32 }
33
counterclockwise()34 bool Contour::counterclockwise ()
35 {
36 if (_precomputedCC)
37 return _CC;
38 _precomputedCC = true;
39 double area = 0.0;
40 for (unsigned int c = 0; c < nvertices () - 1; c++)
41 area += vertex (c).x * vertex (c+1).y - vertex (c+1).x * vertex (c).y;
42 area += vertex (nvertices ()-1).x * vertex (0).y - vertex (0).x * vertex (nvertices ()-1).y;
43 return _CC = area >= 0.0;
44 }
45
move(double x,double y)46 void Contour::move (double x, double y)
47 {
48 for (unsigned int i = 0; i < points.size (); i++) {
49 points[i].x += x;
50 points[i].y += y;
51 }
52 }
53
54
nvertices() const55 unsigned Polygon::nvertices () const
56 {
57 unsigned int nv = 0;
58 for (unsigned int i = 0; i < ncontours (); i++)
59 nv += contours[i].nvertices ();
60 return nv;
61 }
62
boundingbox(Point & min,Point & max)63 void Polygon::boundingbox (Point& min, Point& max)
64 {
65 min.x = min.y = numeric_limits<double>::max ();
66 max.x = max.y = -numeric_limits<double>::max ();
67 Point mintmp;
68 Point maxtmp;
69 for (unsigned int i = 0; i < ncontours (); i++) {
70 contours[i].boundingbox (mintmp, maxtmp);
71 if (mintmp.x < min.x)
72 min.x = mintmp.x;
73 if (maxtmp.x > max.x)
74 max.x = maxtmp.x;
75 if (mintmp.y < min.y)
76 min.y = mintmp.y;
77 if (maxtmp.y > max.y)
78 max.y = maxtmp.y;
79 }
80 }
81
move(double x,double y)82 void Polygon::move (double x, double y)
83 {
84 for (unsigned int i = 0; i < contours.size (); i++)
85 contours[i].move (x, y);
86 }
87
88
89 /*
90 * The following code is necessary for implementing the computeHoles member function
91 *
92 */
93
94 namespace { // start of anonymous namespace
95 struct SweepEvent;
96 struct SegmentComp : public binary_function<SweepEvent*, SweepEvent*, bool> {
97 bool operator() (SweepEvent* e1, SweepEvent* e2);
98 };
99
100 struct SweepEvent {
101 Point p; // point associated with the event
102 bool left; // is the point the left endpoint of the segment (p, other->p)?
103 int pl; // Polygon to which the associated segment belongs to
104 SweepEvent* other; // Event associated to the other endpoint of the segment
105 /** 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? */
106 bool inOut;
107 set<SweepEvent*, SegmentComp>::iterator poss; // Only used in "left" events. Position of the event (segment) in S
108
109 /** Class constructor */
SweepEvent__anon50fb85950111::SweepEvent110 SweepEvent (const Point& pp, bool b, int apl) : p (pp), left (b), pl (apl) {}
111 /** Return the segment associated to the SweepEvent */
segment__anon50fb85950111::SweepEvent112 Segment segment () { return Segment (p, other->p); }
113 /** Is the segment (p, other->p) below point x */
below__anon50fb85950111::SweepEvent114 bool below (const Point& x) const { return (left) ? signedArea (p, other->p, x) > 0 : signedArea (other->p, p, x) > 0; }
115 /** Is the segment (p, other->p) above point x */
above__anon50fb85950111::SweepEvent116 bool above (const Point& x) const { return !below (x); }
117 };
118
119 struct SweepEventComp : public binary_function<SweepEvent*, SweepEvent*, bool> {
operator ()__anon50fb85950111::SweepEventComp120 bool operator() (SweepEvent* e1, SweepEvent* e2) {
121 if (e1->p.x < e2->p.x) // Different x coordinate
122 return true;
123 if (e2->p.x < e1->p.x) // Different x coordinate
124 return false;
125 if (e1->p != e2->p) // Different points, but same x coordinate. The event with lower y coordinate is processed first
126 return e1->p.y < e2->p.y;
127 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
128 return !e1->left;
129 // Same point, both events are left endpoints or both are right endpoints. The event associate to the bottom segment is processed first
130 return e1->below (e2->other->p);
131 }
132 };
133
134 } // end of anonymous namespace
135
operator ()(SweepEvent * e1,SweepEvent * e2)136 bool SegmentComp::operator() (SweepEvent* e1, SweepEvent* e2) {
137 if (e1 == e2)
138 return false;
139 if (signedArea (e1->p, e1->other->p, e2->p) != 0 || signedArea (e1->p, e1->other->p, e2->other->p) != 0) {
140 // Segments are not collinear
141 // If they share their left endpoint use the right endpoint to sort
142 if (e1->p == e2->p)
143 return e1->below (e2->other->p);
144 // Different points
145 SweepEventComp comp;
146 if (comp (e1, e2)) // has the segment associated to e1 been sorted in evp before the segment associated to e2?
147 return e1->below (e2->p);
148 // The segment associated to e2 has been sorted in evp before the segment associated to e1
149 return e2->above (e1->p);
150 }
151 // Segments are collinear. Just a consistent criterion is used
152 if (e1->p == e2->p)
153 return e1 < e2;
154 SweepEventComp comp;
155 return comp (e1, e2);
156 }
157
158 //#define _DEBUG_
computeHoles()159 void Polygon::computeHoles ()
160 {
161 if (ncontours () < 2) {
162 if (ncontours () == 1 && contour (0).clockwise ())
163 contour (0).changeOrientation ();
164 return;
165 }
166 vector<SweepEvent> ev;
167 vector<SweepEvent*> evp;
168 ev.reserve (nvertices ()*2);
169 evp.reserve (nvertices ()*2);
170 for (unsigned i = 0; i < ncontours (); i++) {
171 // cout << contour (i);
172 contour (i).setCounterClockwise ();
173 // cout << contour (i);
174 for (unsigned j = 0; j < contour (i).nedges (); j++) {
175 Segment s = contour(i).segment (j);
176 if (s.begin ().x == s.end ().x) // vertical segments are not processed
177 continue;
178 ev.push_back (SweepEvent (s.begin (), true, i));
179 ev.push_back (SweepEvent (s.end (), true, i));
180 SweepEvent* se1 = &ev[ev.size ()-2];
181 SweepEvent* se2 = &ev[ev.size ()-1];
182 se1->other = se2;
183 se2->other = se1;
184 if (se1->p.x < se2->p.x) {
185 se2->left = false;
186 se1->inOut = false;
187 } else {
188 se1->left = false;
189 se2->inOut = true;
190 }
191 evp.push_back (se1);
192 evp.push_back (se2);
193 }
194 }
195 sort (evp.begin (), evp.end (), SweepEventComp ());
196
197 set<SweepEvent*, SegmentComp> S; // Status line
198 vector<bool> processed (ncontours (), false);
199 vector<int> holeOf (ncontours (), -1);
200 int nprocessed = 0;
201 for (unsigned i = 0; i < evp.size () && nprocessed < ncontours (); i++) {
202 SweepEvent* e = evp[i];
203 #ifdef _DEBUG_
204 cout << "Process event: " << *e << endl;
205 #endif
206
207 if (e->left) { // the segment must be inserted into S
208 e->poss = S.insert(e).first;
209 if (!processed[e->pl]) {
210 processed[e->pl] = true;
211 nprocessed++;
212 set<SweepEvent*, SegmentComp>::iterator prev = e->poss;
213 if (prev == S.begin()) {
214 contour (e->pl).setCounterClockwise ();
215 } else {
216 prev--;
217 if (!(*prev)->inOut) {
218 holeOf[e->pl] = (*prev)->pl;
219 contour (e->pl).setExternal (false);
220 contour ((*prev)->pl).addHole (e->pl);
221 if (contour((*prev)->pl).counterclockwise ())
222 contour (e->pl).setClockwise ();
223 else
224 contour (e->pl).setCounterClockwise ();
225 } else if (holeOf[(*prev)->pl] != -1) {
226 holeOf[e->pl] = holeOf[(*prev)->pl];
227 contour (e->pl).setExternal (false);
228 contour (holeOf[e->pl]).addHole (e->pl);
229 if (contour(holeOf[e->pl]).counterclockwise ())
230 contour (e->pl).setClockwise ();
231 else
232 contour (e->pl).setCounterClockwise ();
233 } else {
234 contour (e->pl).setCounterClockwise ();
235 }
236 }
237 }
238 } else { // the segment must be removed from S
239 S.erase (e->other->poss);
240 }
241 #ifdef _DEBUG_
242 cout << "Tras ajuste: " << endl;
243 for (set<SweepEvent*, SegmentComp>::const_iterator it2 = S.begin(); it2 != S.end(); it2++)
244 cout << **it2 << endl;
245 cout << endl;
246 string st;
247 getline (cin, st);
248 #endif
249 }
250 }
251