]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /* |
2 | Copyright 2008 Intel Corporation | |
3 | ||
4 | Use, modification and distribution are subject to the Boost Software License, | |
5 | Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
6 | http://www.boost.org/LICENSE_1_0.txt). | |
7 | */ | |
8 | #include<iostream> | |
9 | #include<cassert> | |
10 | #ifndef BOOST_POLYGON_POLYGON_FORMATION_HPP | |
11 | #define BOOST_POLYGON_POLYGON_FORMATION_HPP | |
12 | namespace boost { namespace polygon{ | |
13 | ||
14 | namespace polygon_formation { | |
15 | ||
16 | /* | |
17 | * End has two states, HEAD and TAIL as is represented by a bool | |
18 | */ | |
19 | typedef bool End; | |
20 | ||
21 | /* | |
22 | * HEAD End is represented as false because it is the lesser state | |
23 | */ | |
24 | const End HEAD = false; | |
25 | ||
26 | /* | |
27 | * TAIL End is represented by true because TAIL comes after head and 1 after 0 | |
28 | */ | |
29 | const End TAIL = true; | |
30 | ||
31 | /* | |
32 | * 2D turning direction, left and right sides (is a boolean value since it has two states.) | |
33 | */ | |
34 | typedef bool Side; | |
35 | ||
36 | /* | |
37 | * LEFT Side is 0 because we inuitively think left to right; left < right | |
38 | */ | |
39 | const Side LEFT = false; | |
40 | ||
41 | /* | |
42 | * RIGHT Side is 1 so that right > left | |
43 | */ | |
44 | const Side RIGHT = true; | |
45 | ||
46 | /* | |
47 | * The PolyLine class is data storage and services for building and representing partial polygons. | |
48 | * As the polyline is added to it extends its storage to accomodate the data. | |
49 | * PolyLines can be joined head-to-head/head-to-tail when it is determined that two polylines are | |
50 | * part of the same polygon. | |
51 | * PolyLines keep state information about what orientation their incomplete head and tail geometry have, | |
52 | * which side of the polyline is solid and whether the polyline is joined head-to-head and tail-to-head. | |
53 | * PolyLines have nothing whatsoever to do with holes. | |
54 | * It may be valuable to collect a histogram of PolyLine lengths used by an algorithm on its typical data | |
55 | * sets and tune the allocation of the initial vector of coordinate data to be greater than or equal to | |
56 | * the mean, median, mode, or mean plus some number of standard deviation, or just generally large enough | |
57 | * to prevent too much unnecesary reallocations, but not too big that it wastes a lot of memory and degrades cache | |
58 | * performance. | |
59 | */ | |
60 | template <typename Unit> | |
61 | class PolyLine { | |
62 | private: | |
63 | //data | |
64 | ||
65 | /* | |
66 | * ptdata_ a vector of coordiantes | |
67 | * if VERTICAL_HEAD, first coordiante is an X | |
68 | * else first coordinate is a Y | |
69 | */ | |
70 | std::vector<Unit> ptdata_; | |
71 | ||
72 | /* | |
73 | * head and tail points to other polylines before and after this in a chain | |
74 | */ | |
75 | PolyLine* headp_; | |
76 | PolyLine* tailp_; | |
77 | ||
78 | /* | |
79 | * state bitmask | |
80 | * bit zero is orientation, 0 H, 1 V | |
81 | * bit 1 is head connectivity, 0 for head, 1 for tail | |
82 | * bit 2 is tail connectivity, 0 for head, 1 for tail | |
83 | * bit 3 is solid to left of PolyLine when 1, right when 0 | |
84 | */ | |
85 | int state_; | |
86 | ||
87 | public: | |
88 | /* | |
89 | * default constructor (for preallocation) | |
90 | */ | |
91 | PolyLine(); | |
92 | ||
93 | /* | |
94 | * constructor that takes the orientation, coordiante and side to which there is solid | |
95 | */ | |
96 | PolyLine(orientation_2d orient, Unit coord, Side side); | |
97 | ||
98 | //copy constructor | |
99 | PolyLine(const PolyLine& pline); | |
100 | ||
101 | //destructor | |
102 | ~PolyLine(); | |
103 | ||
104 | //assignment operator | |
105 | PolyLine& operator=(const PolyLine& that); | |
106 | ||
107 | //equivalence operator | |
108 | bool operator==(const PolyLine& b) const; | |
109 | ||
110 | /* | |
111 | * valid PolyLine (only default constructed polylines are invalid.) | |
112 | */ | |
113 | bool isValid() const; | |
114 | ||
115 | /* | |
116 | * Orientation of Head | |
117 | */ | |
118 | orientation_2d headOrient() const; | |
119 | ||
120 | /* | |
121 | * returns true if first coordinate is an X value (first segment is vertical) | |
122 | */ | |
123 | bool verticalHead() const; | |
124 | ||
125 | /* | |
126 | * returns the orientation_2d fo the tail | |
127 | */ | |
128 | orientation_2d tailOrient() const; | |
129 | ||
130 | /* | |
131 | * returns true if last coordinate is an X value (last segment is vertical) | |
132 | */ | |
133 | bool verticalTail() const; | |
134 | ||
135 | /* | |
136 | * retrun true if PolyLine has odd number of coordiantes | |
137 | */ | |
138 | bool oddLength() const; | |
139 | ||
140 | /* | |
141 | * retrun the End of the other polyline that the specified end of this polyline is connected to | |
142 | */ | |
143 | End endConnectivity(End end) const; | |
144 | ||
145 | /* | |
146 | * retrun true if the head of this polyline is connect to the tail of a polyline | |
147 | */ | |
148 | bool headToTail() const; | |
149 | /* | |
150 | * retrun true if the head of this polyline is connect to the head of a polyline | |
151 | */ | |
152 | bool headToHead() const; | |
153 | ||
154 | /* | |
155 | * retrun true if the tail of this polyline is connect to the tail of a polyline | |
156 | */ | |
157 | bool tailToTail() const; | |
158 | /* | |
159 | * retrun true if the tail of this polyline is connect to the head of a polyline | |
160 | */ | |
161 | bool tailToHead() const; | |
162 | ||
163 | /* | |
164 | * retrun the side on which there is solid for this polyline | |
165 | */ | |
166 | Side solidSide() const; | |
167 | ||
168 | /* | |
169 | * retrun true if there is solid to the right of this polyline | |
170 | */ | |
171 | bool solidToRight() const; | |
172 | ||
173 | /* | |
174 | * returns true if the polyline tail is not connected | |
175 | */ | |
176 | bool active() const; | |
177 | ||
178 | /* | |
179 | * adds a coordinate value to the end of the polyline changing the tail orientation | |
180 | */ | |
181 | PolyLine& pushCoordinate(Unit coord); | |
182 | ||
183 | /* | |
184 | * removes a coordinate value at the end of the polyline changing the tail orientation | |
185 | */ | |
186 | PolyLine& popCoordinate(); | |
187 | ||
188 | /* | |
189 | * extends the tail of the polyline to include the point, changing orientation if needed | |
190 | */ | |
191 | PolyLine& pushPoint(const point_data<Unit>& point); | |
192 | ||
193 | /* | |
194 | * changes the last coordinate of the tail of the polyline by the amount of the delta | |
195 | */ | |
196 | PolyLine& extendTail(Unit delta); | |
197 | ||
198 | /* | |
199 | * join thisEnd of this polyline to that polyline's end | |
200 | */ | |
201 | PolyLine& joinTo(End thisEnd, PolyLine& that, End end); | |
202 | ||
203 | /* | |
204 | * join an end of this polyline to the tail of that polyline | |
205 | */ | |
206 | PolyLine& joinToTail(PolyLine& that, End end); | |
207 | ||
208 | /* | |
209 | * join an end of this polyline to the head of that polyline | |
210 | */ | |
211 | PolyLine& joinToHead(PolyLine& that, End end); | |
212 | ||
213 | /* | |
214 | * join the head of this polyline to the head of that polyline | |
215 | */ | |
216 | //join this to that in the given way | |
217 | PolyLine& joinHeadToHead(PolyLine& that); | |
218 | ||
219 | /* | |
220 | * join the head of this polyline to the tail of that polyline | |
221 | */ | |
222 | PolyLine& joinHeadToTail(PolyLine& that); | |
223 | ||
224 | /* | |
225 | * join the tail of this polyline to the head of that polyline | |
226 | */ | |
227 | PolyLine& joinTailToHead(PolyLine& that); | |
228 | ||
229 | /* | |
230 | * join the tail of this polyline to the tail of that polyline | |
231 | */ | |
232 | PolyLine& joinTailToTail(PolyLine& that); | |
233 | ||
234 | /* | |
235 | * dissconnect the tail at the end of the polygon | |
236 | */ | |
237 | PolyLine& disconnectTails(); | |
238 | ||
239 | /* | |
240 | * get the coordinate at one end of this polyline, by default the tail end | |
241 | */ | |
242 | Unit getEndCoord(End end = TAIL) const; | |
243 | ||
244 | /* | |
245 | * get the point on the polyline at the given index (polylines have the same number of coordinates as points | |
246 | */ | |
247 | point_data<Unit> getPoint(unsigned int index) const; | |
248 | ||
249 | /* | |
250 | * get the point on one end of the polyline, by default the tail | |
251 | */ | |
252 | point_data<Unit> getEndPoint(End end = TAIL) const; | |
253 | ||
254 | /* | |
255 | * get the orientation of a segment by index | |
256 | */ | |
257 | orientation_2d segmentOrient(unsigned int index = 0) const; | |
258 | ||
259 | /* | |
260 | * get a coordinate by index using the square bracket operator | |
261 | */ | |
262 | Unit operator[] (unsigned int index) const; | |
263 | ||
264 | /* | |
265 | * get the number of segments/points/coordinates in the polyline | |
266 | */ | |
267 | unsigned int numSegments() const; | |
268 | ||
269 | /* | |
270 | * get the pointer to the next polyline at one end of this | |
271 | */ | |
272 | PolyLine* next(End end) const; | |
273 | ||
274 | /* | |
275 | * write out coordinates of this and all attached polylines to a single vector | |
276 | */ | |
277 | PolyLine* writeOut(std::vector<Unit>& outVec, End startEnd = TAIL) const; | |
278 | ||
279 | private: | |
280 | //methods | |
281 | PolyLine& joinTo_(End thisEnd, PolyLine& that, End end); | |
282 | }; | |
283 | ||
284 | //forward declaration | |
285 | template<bool orientT, typename Unit> | |
286 | class PolyLinePolygonData; | |
287 | ||
288 | //forward declaration | |
289 | template<bool orientT, typename Unit> | |
290 | class PolyLinePolygonWithHolesData; | |
291 | ||
292 | /* | |
293 | * ActiveTail represents an edge of an incomplete polygon. | |
294 | * | |
295 | * An ActiveTail object is the active tail end of a polyline object, which may (should) be the attached to | |
296 | * a chain of polyline objects through a pointer. The ActiveTail class provides an abstraction between | |
297 | * and algorithm that builds polygons and the PolyLine data representation of incomplete polygons that are | |
298 | * being built. It does this by providing an iterface to access the information about the last edge at the | |
299 | * tail of the PolyLine it is associated with. To a polygon constructing algorithm, an ActiveTail is a floating | |
300 | * edge of an incomplete polygon and has an orientation and coordinate value, as well as knowing which side of | |
301 | * that edge is supposed to be solid or space. Any incomplete polygon will have two active tails. Active tails | |
302 | * may be joined together to merge two incomplete polygons into a larger incomplete polygon. If two active tails | |
303 | * that are to be merged are the oppositve ends of the same incomplete polygon that indicates that the polygon | |
304 | * has been closed and is complete. The active tail keeps a pointer to the other active tail of its incomplete | |
305 | * polygon so that it is easy to check this condition. These pointers are updated when active tails are joined. | |
306 | * The active tail also keeps a list of pointers to active tail objects that serve as handles to closed holes. In | |
307 | * this way a hole can be associated to another incomplete polygon, which will eventually be its enclosing shell, | |
308 | * or reassociate the hole to another incomplete polygon in the case that it become a hole itself. Alternately, | |
309 | * the active tail may add a filiment to stitch a hole into a shell and "fracture" the hole out of the interior | |
310 | * of a polygon. The active tail maintains a static output buffer to temporarily write polygon data to when | |
311 | * it outputs a figure so that outputting a polygon does not require the allocation of a temporary buffer. This | |
312 | * static buffer should be destroyed whenever the program determines that it won't need it anymore and would prefer to | |
313 | * release the memory it has allocated back to the system. | |
314 | */ | |
315 | template <typename Unit> | |
316 | class ActiveTail { | |
317 | private: | |
318 | //data | |
319 | PolyLine<Unit>* tailp_; | |
320 | ActiveTail *otherTailp_; | |
321 | std::list<ActiveTail*> holesList_; | |
322 | //Sum of all the polylines which constitute the active tail (including holes)// | |
323 | size_t polyLineSize_; | |
324 | public: | |
325 | ||
326 | inline size_t getPolyLineSize(){ | |
327 | return polyLineSize_; | |
328 | } | |
329 | ||
330 | inline void setPolyLineSize(int delta){ | |
331 | polyLineSize_ = delta; | |
332 | } | |
333 | ||
334 | inline void addPolyLineSize(int delta){ | |
335 | polyLineSize_ += delta; | |
336 | } | |
337 | ||
338 | /* | |
339 | * iterator over coordinates of the figure | |
340 | */ | |
341 | class iterator { | |
342 | private: | |
343 | const PolyLine<Unit>* pLine_; | |
344 | const PolyLine<Unit>* pLineEnd_; | |
345 | unsigned int index_; | |
346 | unsigned int indexEnd_; | |
347 | End startEnd_; | |
348 | public: | |
349 | inline iterator() : pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() {} | |
350 | inline iterator(const ActiveTail* at, bool isHole, orientation_2d orient) : | |
351 | pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() { | |
352 | //if it is a hole and orientation is vertical or it is not a hole and orientation is horizontal | |
353 | //we want to use this active tail, otherwise we want to use the other active tail | |
354 | startEnd_ = TAIL; | |
355 | if(!isHole ^ (orient == HORIZONTAL)) { | |
356 | //switch winding direction | |
357 | at = at->getOtherActiveTail(); | |
358 | } | |
359 | //now we have the right winding direction | |
360 | //if it is horizontal we need to skip the first element | |
361 | pLine_ = at->getTail(); | |
362 | ||
363 | if(at->getTail()->numSegments() > 0) | |
364 | index_ = at->getTail()->numSegments() - 1; | |
365 | ||
366 | if((at->getOrient() == HORIZONTAL) ^ (orient == HORIZONTAL)) { | |
367 | pLineEnd_ = at->getTail(); | |
368 | indexEnd_ = pLineEnd_->numSegments() - 1; | |
369 | if(index_ == 0) { | |
370 | pLine_ = at->getTail()->next(HEAD); | |
371 | if(at->getTail()->endConnectivity(HEAD) == TAIL) { | |
372 | index_ = pLine_->numSegments() -1; | |
373 | } else { | |
374 | startEnd_ = HEAD; | |
375 | index_ = 0; | |
376 | } | |
377 | } else { --index_; } | |
378 | } else { | |
379 | pLineEnd_ = at->getOtherActiveTail()->getTail(); | |
380 | if(pLineEnd_->numSegments() > 0) | |
381 | indexEnd_ = pLineEnd_->numSegments() - 1; | |
382 | } | |
383 | at->getTail()->joinTailToTail(*(at->getOtherActiveTail()->getTail())); | |
384 | } | |
385 | ||
386 | inline size_t size(void){ | |
387 | size_t count = 0; | |
388 | End dir = startEnd_; | |
389 | PolyLine<Unit> const * currLine = pLine_; | |
390 | size_t ops = 0; | |
391 | while(currLine != pLineEnd_){ | |
392 | ops++; | |
393 | count += currLine->numSegments(); | |
394 | currLine = currLine->next(dir == HEAD ? TAIL : HEAD); | |
395 | dir = currLine->endConnectivity(dir == HEAD ? TAIL : HEAD); | |
396 | } | |
397 | count += pLineEnd_->numSegments(); | |
398 | return count; //no. of vertices | |
399 | } | |
400 | ||
401 | //use bitwise copy and assign provided by the compiler | |
402 | inline iterator& operator++() { | |
403 | if(pLine_ == pLineEnd_ && index_ == indexEnd_) { | |
404 | pLine_ = 0; | |
405 | index_ = 0; | |
406 | return *this; | |
407 | } | |
408 | if(startEnd_ == HEAD) { | |
409 | ++index_; | |
410 | if(index_ == pLine_->numSegments()) { | |
411 | End end = pLine_->endConnectivity(TAIL); | |
412 | pLine_ = pLine_->next(TAIL); | |
413 | if(end == TAIL) { | |
414 | startEnd_ = TAIL; | |
415 | index_ = pLine_->numSegments() -1; | |
416 | } else { | |
417 | index_ = 0; | |
418 | } | |
419 | } | |
420 | } else { | |
421 | if(index_ == 0) { | |
422 | End end = pLine_->endConnectivity(HEAD); | |
423 | pLine_ = pLine_->next(HEAD); | |
424 | if(end == TAIL) { | |
425 | index_ = pLine_->numSegments() -1; | |
426 | } else { | |
427 | startEnd_ = HEAD; | |
428 | index_ = 0; | |
429 | } | |
430 | } else { | |
431 | --index_; | |
432 | } | |
433 | } | |
434 | return *this; | |
435 | } | |
436 | inline const iterator operator++(int) { | |
437 | iterator tmp(*this); | |
438 | ++(*this); | |
439 | return tmp; | |
440 | } | |
441 | inline bool operator==(const iterator& that) const { | |
442 | return pLine_ == that.pLine_ && index_ == that.index_; | |
443 | } | |
444 | inline bool operator!=(const iterator& that) const { | |
445 | return pLine_ != that.pLine_ || index_ != that.index_; | |
446 | } | |
447 | inline Unit operator*() { return (*pLine_)[index_]; } | |
448 | }; | |
449 | ||
450 | /* | |
451 | * iterator over holes contained within the figure | |
452 | */ | |
453 | typedef typename std::list<ActiveTail*>::const_iterator iteratorHoles; | |
454 | ||
455 | //default constructor | |
456 | ActiveTail(); | |
457 | ||
458 | //constructor | |
459 | ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp); | |
460 | ||
461 | //constructor | |
462 | ActiveTail(PolyLine<Unit>* active, ActiveTail* otherTailp); | |
463 | ||
464 | //copy constructor | |
465 | ActiveTail(const ActiveTail& that); | |
466 | ||
467 | //destructor | |
468 | ~ActiveTail(); | |
469 | ||
470 | //assignment operator | |
471 | ActiveTail& operator=(const ActiveTail& that); | |
472 | ||
473 | //equivalence operator | |
474 | bool operator==(const ActiveTail& b) const; | |
475 | ||
476 | /* | |
477 | * comparison operators, ActiveTail objects are sortable by geometry | |
478 | */ | |
479 | bool operator<(const ActiveTail& b) const; | |
480 | bool operator<=(const ActiveTail& b) const; | |
481 | bool operator>(const ActiveTail& b) const; | |
482 | bool operator>=(const ActiveTail& b) const; | |
483 | ||
484 | /* | |
485 | * get the pointer to the polyline that this is an active tail of | |
486 | */ | |
487 | PolyLine<Unit>* getTail() const; | |
488 | ||
489 | /* | |
490 | * get the pointer to the polyline at the other end of the chain | |
491 | */ | |
492 | PolyLine<Unit>* getOtherTail() const; | |
493 | ||
494 | /* | |
495 | * get the pointer to the activetail at the other end of the chain | |
496 | */ | |
497 | ActiveTail* getOtherActiveTail() const; | |
498 | ||
499 | /* | |
500 | * test if another active tail is the other end of the chain | |
501 | */ | |
502 | bool isOtherTail(const ActiveTail& b); | |
503 | ||
504 | /* | |
505 | * update this end of chain pointer to new polyline | |
506 | */ | |
507 | ActiveTail& updateTail(PolyLine<Unit>* newTail); | |
508 | ||
509 | /* | |
510 | * associate a hole to this active tail by the specified policy | |
511 | */ | |
512 | ActiveTail* addHole(ActiveTail* hole, bool fractureHoles); | |
513 | ||
514 | /* | |
515 | * get the list of holes | |
516 | */ | |
517 | const std::list<ActiveTail*>& getHoles() const; | |
518 | ||
519 | /* | |
520 | * copy holes from that to this | |
521 | */ | |
522 | void copyHoles(ActiveTail& that); | |
523 | ||
524 | /* | |
525 | * find out if solid to right | |
526 | */ | |
527 | bool solidToRight() const; | |
528 | ||
529 | /* | |
530 | * get coordinate (getCoord and getCoordinate are aliases for eachother) | |
531 | */ | |
532 | Unit getCoord() const; | |
533 | Unit getCoordinate() const; | |
534 | ||
535 | /* | |
536 | * get the tail orientation | |
537 | */ | |
538 | orientation_2d getOrient() const; | |
539 | ||
540 | /* | |
541 | * add a coordinate to the polygon at this active tail end, properly handle degenerate edges by removing redundant coordinate | |
542 | */ | |
543 | void pushCoordinate(Unit coord); | |
544 | ||
545 | /* | |
546 | * write the figure that this active tail points to out to the temp buffer | |
547 | */ | |
548 | void writeOutFigure(std::vector<Unit>& outVec, bool isHole = false) const; | |
549 | ||
550 | /* | |
551 | * write the figure that this active tail points to out through iterators | |
552 | */ | |
553 | void writeOutFigureItrs(iterator& beginOut, iterator& endOut, bool isHole = false, orientation_2d orient = VERTICAL) const; | |
554 | iterator begin(bool isHole, orientation_2d orient) const; | |
555 | iterator end() const; | |
556 | ||
557 | /* | |
558 | * write the holes that this active tail points to out through iterators | |
559 | */ | |
560 | void writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const; | |
561 | iteratorHoles beginHoles() const; | |
562 | iteratorHoles endHoles() const; | |
563 | ||
564 | /* | |
565 | * joins the two chains that the two active tail tails are ends of | |
566 | * checks for closure of figure and writes out polygons appropriately | |
567 | * returns a handle to a hole if one is closed | |
568 | */ | |
569 | static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, std::vector<Unit>& outBufferTmp); | |
570 | template <typename PolygonT> | |
571 | static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, typename std::vector<PolygonT>& outBufferTmp); | |
572 | ||
573 | /* | |
574 | * deallocate temp buffer | |
575 | */ | |
576 | static void destroyOutBuffer(); | |
577 | ||
578 | /* | |
579 | * deallocate all polygon data this active tail points to (deep delete, call only from one of a pair of active tails) | |
580 | */ | |
581 | void destroyContents(); | |
582 | }; | |
583 | ||
584 | /* allocate a polyline object */ | |
585 | template <typename Unit> | |
586 | PolyLine<Unit>* createPolyLine(orientation_2d orient, Unit coord, Side side); | |
587 | ||
588 | /* deallocate a polyline object */ | |
589 | template <typename Unit> | |
590 | void destroyPolyLine(PolyLine<Unit>* pLine); | |
591 | ||
592 | /* allocate an activetail object */ | |
593 | template <typename Unit> | |
594 | ActiveTail<Unit>* createActiveTail(); | |
595 | ||
596 | /* deallocate an activetail object */ | |
597 | template <typename Unit> | |
598 | void destroyActiveTail(ActiveTail<Unit>* aTail); | |
599 | ||
600 | template<bool orientT, typename Unit> | |
601 | class PolyLineHoleData { | |
602 | private: | |
603 | ActiveTail<Unit>* p_; | |
604 | public: | |
605 | typedef Unit coordinate_type; | |
606 | typedef typename ActiveTail<Unit>::iterator compact_iterator_type; | |
607 | typedef iterator_compact_to_points<compact_iterator_type, point_data<coordinate_type> > iterator_type; | |
608 | inline PolyLineHoleData() : p_(0) {} | |
609 | inline PolyLineHoleData(ActiveTail<Unit>* p) : p_(p) {} | |
610 | //use default copy and assign | |
611 | inline compact_iterator_type begin_compact() const { return p_->begin(true, (orientT ? VERTICAL : HORIZONTAL)); } | |
612 | inline compact_iterator_type end_compact() const { return p_->end(); } | |
613 | inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); } | |
614 | inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); } | |
615 | inline std::size_t size() const { | |
616 | return p_->getPolyLineSize(); | |
617 | } | |
618 | inline ActiveTail<Unit>* yield() { return p_; } | |
619 | }; | |
620 | ||
621 | template<bool orientT, typename Unit> | |
622 | class PolyLinePolygonWithHolesData { | |
623 | private: | |
624 | ActiveTail<Unit>* p_; | |
625 | public: | |
626 | typedef Unit coordinate_type; | |
627 | typedef typename ActiveTail<Unit>::iterator compact_iterator_type; | |
628 | typedef iterator_compact_to_points<compact_iterator_type, point_data<coordinate_type> > iterator_type; | |
629 | typedef PolyLineHoleData<orientT, Unit> hole_type; | |
630 | typedef typename coordinate_traits<Unit>::area_type area_type; | |
631 | class iteratorHoles { | |
632 | private: | |
633 | typename ActiveTail<Unit>::iteratorHoles itr_; | |
634 | public: | |
635 | inline iteratorHoles() : itr_() {} | |
636 | inline iteratorHoles(typename ActiveTail<Unit>::iteratorHoles itr) : itr_(itr) {} | |
637 | //use bitwise copy and assign provided by the compiler | |
638 | inline iteratorHoles& operator++() { | |
639 | ++itr_; | |
640 | return *this; | |
641 | } | |
642 | inline const iteratorHoles operator++(int) { | |
643 | iteratorHoles tmp(*this); | |
644 | ++(*this); | |
645 | return tmp; | |
646 | } | |
647 | inline bool operator==(const iteratorHoles& that) const { | |
648 | return itr_ == that.itr_; | |
649 | } | |
650 | inline bool operator!=(const iteratorHoles& that) const { | |
651 | return itr_ != that.itr_; | |
652 | } | |
653 | inline PolyLineHoleData<orientT, Unit> operator*() { return PolyLineHoleData<orientT, Unit>(*itr_);} | |
654 | }; | |
655 | typedef iteratorHoles iterator_holes_type; | |
656 | ||
657 | inline PolyLinePolygonWithHolesData() : p_(0) {} | |
658 | inline PolyLinePolygonWithHolesData(ActiveTail<Unit>* p) : p_(p) {} | |
659 | //use default copy and assign | |
660 | inline compact_iterator_type begin_compact() const { return p_->begin(false, (orientT ? VERTICAL : HORIZONTAL)); } | |
661 | inline compact_iterator_type end_compact() const { return p_->end(); } | |
662 | inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); } | |
663 | inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); } | |
664 | inline iteratorHoles begin_holes() const { return iteratorHoles(p_->beginHoles()); } | |
665 | inline iteratorHoles end_holes() const { return iteratorHoles(p_->endHoles()); } | |
666 | inline ActiveTail<Unit>* yield() { return p_; } | |
667 | //stub out these four required functions that will not be used but are needed for the interface | |
668 | inline std::size_t size_holes() const { return 0; } | |
669 | inline std::size_t size() const { return 0; } | |
670 | }; | |
671 | ||
672 | ||
673 | template <bool orientT, typename Unit, typename polygon_concept_type> | |
674 | struct PolyLineType { }; | |
675 | template <bool orientT, typename Unit> | |
676 | struct PolyLineType<orientT, Unit, polygon_90_with_holes_concept> { typedef PolyLinePolygonWithHolesData<orientT, Unit> type; }; | |
677 | template <bool orientT, typename Unit> | |
678 | struct PolyLineType<orientT, Unit, polygon_45_with_holes_concept> { typedef PolyLinePolygonWithHolesData<orientT, Unit> type; }; | |
679 | template <bool orientT, typename Unit> | |
680 | struct PolyLineType<orientT, Unit, polygon_with_holes_concept> { typedef PolyLinePolygonWithHolesData<orientT, Unit> type; }; | |
681 | template <bool orientT, typename Unit> | |
682 | struct PolyLineType<orientT, Unit, polygon_90_concept> { typedef PolyLineHoleData<orientT, Unit> type; }; | |
683 | template <bool orientT, typename Unit> | |
684 | struct PolyLineType<orientT, Unit, polygon_45_concept> { typedef PolyLineHoleData<orientT, Unit> type; }; | |
685 | template <bool orientT, typename Unit> | |
686 | struct PolyLineType<orientT, Unit, polygon_concept> { typedef PolyLineHoleData<orientT, Unit> type; }; | |
687 | ||
688 | template <bool orientT, typename Unit, typename polygon_concept_type> | |
689 | class ScanLineToPolygonItrs { | |
690 | private: | |
691 | std::map<Unit, ActiveTail<Unit>*> tailMap_; | |
692 | typedef typename PolyLineType<orientT, Unit, polygon_concept_type>::type PolyLinePolygonData; | |
693 | std::vector<PolyLinePolygonData> outputPolygons_; | |
694 | bool fractureHoles_; | |
695 | public: | |
696 | typedef typename std::vector<PolyLinePolygonData>::iterator iterator; | |
697 | inline ScanLineToPolygonItrs() : tailMap_(), outputPolygons_(), fractureHoles_(false) {} | |
698 | /* construct a scanline with the proper offsets, protocol and options */ | |
699 | inline ScanLineToPolygonItrs(bool fractureHoles) : tailMap_(), outputPolygons_(), fractureHoles_(fractureHoles) {} | |
700 | ||
701 | ~ScanLineToPolygonItrs() { clearOutput_(); } | |
702 | ||
703 | /* process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */ | |
704 | void processEdges(iterator& beginOutput, iterator& endOutput, | |
705 | Unit currentX, std::vector<interval_data<Unit> >& leftEdges, | |
706 | std::vector<interval_data<Unit> >& rightEdges, | |
707 | size_t vertexThreshold=(std::numeric_limits<size_t>::max)() ); | |
708 | ||
709 | /********************************************************************** | |
710 | *methods implementing new polygon formation code | |
711 | * | |
712 | **********************************************************************/ | |
713 | void updatePartialSimplePolygonsWithRightEdges(Unit currentX, | |
714 | const std::vector<interval_data<Unit> >& leftEdges, size_t threshold); | |
715 | ||
716 | void updatePartialSimplePolygonsWithLeftEdges(Unit currentX, | |
717 | const std::vector<interval_data<Unit> >& leftEdges, size_t threshold); | |
718 | ||
719 | void closePartialSimplePolygon(Unit, ActiveTail<Unit>*, ActiveTail<Unit>*); | |
720 | ||
721 | void maintainPartialSimplePolygonInvariant(iterator& ,iterator& ,Unit, | |
722 | const std::vector<interval_data<Unit> >&, | |
723 | const std::vector<interval_data<Unit> >&, | |
724 | size_t vertexThreshold=(std::numeric_limits<size_t>::max)()); | |
725 | ||
726 | void insertNewLeftEdgeIntoTailMap(Unit, Unit, Unit, | |
727 | typename std::map<Unit, ActiveTail<Unit>*>::iterator &); | |
728 | /**********************************************************************/ | |
729 | ||
730 | inline size_t getTailMapSize(){ | |
731 | typename std::map<Unit, ActiveTail<Unit>* >::const_iterator itr; | |
732 | size_t tsize = 0; | |
733 | for(itr=tailMap_.begin(); itr!=tailMap_.end(); ++itr){ | |
734 | tsize += (itr->second)->getPolyLineSize(); | |
735 | } | |
736 | return tsize; | |
737 | } | |
738 | /*print the active tails in this map:*/ | |
739 | inline void print(){ | |
740 | typename std::map<Unit, ActiveTail<Unit>* >::const_iterator itr; | |
741 | printf("=========TailMap[%lu]=========\n", tailMap_.size()); | |
742 | for(itr=tailMap_.begin(); itr!=tailMap_.end(); ++itr){ | |
743 | std::cout<< "[" << itr->first << "] : " << std::endl; | |
744 | //print active tail// | |
745 | ActiveTail<Unit> const *t = (itr->second); | |
746 | PolyLine<Unit> const *pBegin = t->getTail(); | |
747 | PolyLine<Unit> const *pEnd = t->getOtherActiveTail()->getTail(); | |
748 | std::string sorient = pBegin->solidToRight() ? "RIGHT" : "LEFT"; | |
749 | std::cout<< " ActiveTail.tailp_ (solid= " << sorient ; | |
750 | End dir = TAIL; | |
751 | while(pBegin!=pEnd){ | |
752 | std::cout << pBegin << "={ "; | |
753 | for(size_t i=0; i<pBegin->numSegments(); i++){ | |
754 | point_data<Unit> u = pBegin->getPoint(i); | |
755 | std::cout << "(" << u.x() << "," << u.y() << ") "; | |
756 | } | |
757 | std::cout << "} "; | |
758 | pBegin = pBegin->next(dir == HEAD ? TAIL : HEAD); | |
759 | dir = pBegin->endConnectivity(dir == HEAD ? TAIL : HEAD); | |
760 | } | |
761 | if(pEnd){ | |
762 | std::cout << pEnd << "={ "; | |
763 | for(size_t i=0; i<pEnd->numSegments(); i++){ | |
764 | point_data<Unit> u = pEnd->getPoint(i); | |
765 | std::cout << "(" << u.x() << "," << u.y() << ") "; | |
766 | } | |
767 | std::cout << "} "; | |
768 | } | |
769 | std::cout << " end= " << pEnd << std::endl; | |
770 | } | |
771 | } | |
772 | ||
773 | private: | |
774 | void clearOutput_(); | |
775 | }; | |
776 | ||
777 | /* | |
778 | * ScanLine does all the work of stitching together polygons from incoming vertical edges | |
779 | */ | |
780 | // template <typename Unit, typename polygon_concept_type> | |
781 | // class ScanLineToPolygons { | |
782 | // private: | |
783 | // ScanLineToPolygonItrs<true, Unit> scanline_; | |
784 | // public: | |
785 | // inline ScanLineToPolygons() : scanline_() {} | |
786 | // /* construct a scanline with the proper offsets, protocol and options */ | |
787 | // inline ScanLineToPolygons(bool fractureHoles) : scanline_(fractureHoles) {} | |
788 | ||
789 | // /* process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */ | |
790 | // inline void processEdges(std::vector<Unit>& outBufferTmp, Unit currentX, std::vector<interval_data<Unit> >& leftEdges, | |
791 | // std::vector<interval_data<Unit> >& rightEdges) { | |
792 | // typename ScanLineToPolygonItrs<true, Unit>::iterator itr, endItr; | |
793 | // scanline_.processEdges(itr, endItr, currentX, leftEdges, rightEdges); | |
794 | // //copy data into outBufferTmp | |
795 | // while(itr != endItr) { | |
796 | // typename PolyLinePolygonData<true, Unit>::iterator pditr; | |
797 | // outBufferTmp.push_back(0); | |
798 | // unsigned int sizeIndex = outBufferTmp.size() - 1; | |
799 | // int count = 0; | |
800 | // for(pditr = (*itr).begin(); pditr != (*itr).end(); ++pditr) { | |
801 | // outBufferTmp.push_back(*pditr); | |
802 | // ++count; | |
803 | // } | |
804 | // outBufferTmp[sizeIndex] = count; | |
805 | // typename PolyLinePolygonData<true, Unit>::iteratorHoles pdHoleItr; | |
806 | // for(pdHoleItr = (*itr).beginHoles(); pdHoleItr != (*itr).endHoles(); ++pdHoleItr) { | |
807 | // outBufferTmp.push_back(0); | |
808 | // unsigned int sizeIndex2 = outBufferTmp.size() - 1; | |
809 | // int count2 = 0; | |
810 | // for(pditr = (*pdHoleItr).begin(); pditr != (*pdHoleItr).end(); ++pditr) { | |
811 | // outBufferTmp.push_back(*pditr); | |
812 | // ++count2; | |
813 | // } | |
814 | // outBufferTmp[sizeIndex2] = -count; | |
815 | // } | |
816 | // ++itr; | |
817 | // } | |
818 | // } | |
819 | // }; | |
820 | ||
821 | const int VERTICAL_HEAD = 1, HEAD_TO_TAIL = 2, TAIL_TO_TAIL = 4, SOLID_TO_RIGHT = 8; | |
822 | ||
823 | //EVERY FUNCTION in this DEF file should be explicitly defined as inline | |
824 | ||
825 | //microsoft compiler improperly warns whenever you cast an integer to bool | |
826 | //call this function on an integer to convert it to bool without a warning | |
827 | template <class T> | |
828 | inline bool to_bool(const T& val) { return val != 0; } | |
829 | ||
830 | //default constructor (for preallocation) | |
831 | template <typename Unit> | |
832 | inline PolyLine<Unit>::PolyLine() : ptdata_() ,headp_(0), tailp_(0), state_(-1) {} | |
833 | ||
834 | //constructor | |
835 | template <typename Unit> | |
836 | inline PolyLine<Unit>::PolyLine(orientation_2d orient, Unit coord, Side side) : | |
837 | ptdata_(1, coord), | |
838 | headp_(0), | |
839 | tailp_(0), | |
840 | state_(orient.to_int() + | |
841 | (side << 3)){} | |
842 | ||
843 | //copy constructor | |
844 | template <typename Unit> | |
845 | inline PolyLine<Unit>::PolyLine(const PolyLine<Unit>& pline) : ptdata_(pline.ptdata_), | |
846 | headp_(pline.headp_), | |
847 | tailp_(pline.tailp_), | |
848 | state_(pline.state_) {} | |
849 | ||
850 | //destructor | |
851 | template <typename Unit> | |
852 | inline PolyLine<Unit>::~PolyLine() { | |
853 | //clear out data just in case it is read later | |
854 | headp_ = tailp_ = 0; | |
855 | state_ = 0; | |
856 | } | |
857 | ||
858 | template <typename Unit> | |
859 | inline PolyLine<Unit>& PolyLine<Unit>::operator=(const PolyLine<Unit>& that) { | |
860 | if(!(this == &that)) { | |
861 | headp_ = that.headp_; | |
862 | tailp_ = that.tailp_; | |
863 | ptdata_ = that.ptdata_; | |
864 | state_ = that.state_; | |
865 | } | |
866 | return *this; | |
867 | } | |
868 | ||
869 | template <typename Unit> | |
870 | inline bool PolyLine<Unit>::operator==(const PolyLine<Unit>& b) const { | |
871 | return this == &b || (state_ == b.state_ && | |
872 | headp_ == b.headp_ && | |
873 | tailp_ == b.tailp_); | |
874 | } | |
875 | ||
876 | //valid PolyLine | |
877 | template <typename Unit> | |
878 | inline bool PolyLine<Unit>::isValid() const { | |
879 | return state_ > -1; } | |
880 | ||
881 | //first coordinate is an X value | |
882 | //first segment is vertical | |
883 | template <typename Unit> | |
884 | inline bool PolyLine<Unit>::verticalHead() const { | |
885 | return state_ & VERTICAL_HEAD; | |
886 | } | |
887 | ||
888 | //retrun true is PolyLine has odd number of coordiantes | |
889 | template <typename Unit> | |
890 | inline bool PolyLine<Unit>::oddLength() const { | |
891 | return to_bool((ptdata_.size()-1) % 2); | |
892 | } | |
893 | ||
894 | //last coordiante is an X value | |
895 | //last segment is vertical | |
896 | template <typename Unit> | |
897 | inline bool PolyLine<Unit>::verticalTail() const { | |
898 | return to_bool(verticalHead() ^ oddLength()); | |
899 | } | |
900 | ||
901 | template <typename Unit> | |
902 | inline orientation_2d PolyLine<Unit>::tailOrient() const { | |
903 | return (verticalTail() ? VERTICAL : HORIZONTAL); | |
904 | } | |
905 | ||
906 | template <typename Unit> | |
907 | inline orientation_2d PolyLine<Unit>::headOrient() const { | |
908 | return (verticalHead() ? VERTICAL : HORIZONTAL); | |
909 | } | |
910 | ||
911 | template <typename Unit> | |
912 | inline End PolyLine<Unit>::endConnectivity(End end) const { | |
913 | //Tail should be defined as true | |
914 | if(end) { return tailToTail(); } | |
915 | return headToTail(); | |
916 | } | |
917 | ||
918 | template <typename Unit> | |
919 | inline bool PolyLine<Unit>::headToTail() const { | |
920 | return to_bool(state_ & HEAD_TO_TAIL); | |
921 | } | |
922 | ||
923 | template <typename Unit> | |
924 | inline bool PolyLine<Unit>::headToHead() const { | |
925 | return to_bool(!headToTail()); | |
926 | } | |
927 | ||
928 | template <typename Unit> | |
929 | inline bool PolyLine<Unit>::tailToHead() const { | |
930 | return to_bool(!tailToTail()); | |
931 | } | |
932 | ||
933 | template <typename Unit> | |
934 | inline bool PolyLine<Unit>::tailToTail() const { | |
935 | return to_bool(state_ & TAIL_TO_TAIL); | |
936 | } | |
937 | ||
938 | template <typename Unit> | |
939 | inline Side PolyLine<Unit>::solidSide() const { | |
940 | return solidToRight(); } | |
941 | ||
942 | template <typename Unit> | |
943 | inline bool PolyLine<Unit>::solidToRight() const { | |
944 | return to_bool(state_ & SOLID_TO_RIGHT) != 0; | |
945 | } | |
946 | ||
947 | template <typename Unit> | |
948 | inline bool PolyLine<Unit>::active() const { | |
949 | return !to_bool(tailp_); | |
950 | } | |
951 | ||
952 | template <typename Unit> | |
953 | inline PolyLine<Unit>& PolyLine<Unit>::pushCoordinate(Unit coord) { | |
954 | ptdata_.push_back(coord); | |
955 | return *this; | |
956 | } | |
957 | ||
958 | template <typename Unit> | |
959 | inline PolyLine<Unit>& PolyLine<Unit>::popCoordinate() { | |
960 | ptdata_.pop_back(); | |
961 | return *this; | |
962 | } | |
963 | ||
964 | template <typename Unit> | |
965 | inline PolyLine<Unit>& PolyLine<Unit>::pushPoint(const point_data<Unit>& point) { | |
966 | if(numSegments()){ | |
967 | point_data<Unit> endPt = getEndPoint(); | |
968 | //vertical is true, horizontal is false | |
969 | if((tailOrient().to_int() ? point.get(VERTICAL) == endPt.get(VERTICAL) : point.get(HORIZONTAL) == endPt.get(HORIZONTAL))) { | |
970 | //we were pushing a colinear segment | |
971 | return popCoordinate(); | |
972 | } | |
973 | } | |
974 | return pushCoordinate(tailOrient().to_int() ? point.get(VERTICAL) : point.get(HORIZONTAL)); | |
975 | } | |
976 | ||
977 | template <typename Unit> | |
978 | inline PolyLine<Unit>& PolyLine<Unit>::extendTail(Unit delta) { | |
979 | ptdata_.back() += delta; | |
980 | return *this; | |
981 | } | |
982 | ||
983 | //private member function that creates a link from this PolyLine to that | |
984 | template <typename Unit> | |
985 | inline PolyLine<Unit>& PolyLine<Unit>::joinTo_(End thisEnd, PolyLine<Unit>& that, End end) { | |
986 | if(thisEnd){ | |
987 | tailp_ = &that; | |
988 | state_ &= ~TAIL_TO_TAIL; //clear any previous state_ of bit (for safety) | |
989 | state_ |= (end << 2); //place bit into mask | |
990 | } else { | |
991 | headp_ = &that; | |
992 | state_ &= ~HEAD_TO_TAIL; //clear any previous state_ of bit (for safety) | |
993 | state_ |= (end << 1); //place bit into mask | |
994 | } | |
995 | return *this; | |
996 | } | |
997 | ||
998 | //join two PolyLines (both ways of the association) | |
999 | template <typename Unit> | |
1000 | inline PolyLine<Unit>& PolyLine<Unit>::joinTo(End thisEnd, PolyLine<Unit>& that, End end) { | |
1001 | joinTo_(thisEnd, that, end); | |
1002 | that.joinTo_(end, *this, thisEnd); | |
1003 | return *this; | |
1004 | } | |
1005 | ||
1006 | //convenience functions for joining PolyLines | |
1007 | template <typename Unit> | |
1008 | inline PolyLine<Unit>& PolyLine<Unit>::joinToTail(PolyLine<Unit>& that, End end) { | |
1009 | return joinTo(TAIL, that, end); | |
1010 | } | |
1011 | template <typename Unit> | |
1012 | inline PolyLine<Unit>& PolyLine<Unit>::joinToHead(PolyLine<Unit>& that, End end) { | |
1013 | return joinTo(HEAD, that, end); | |
1014 | } | |
1015 | template <typename Unit> | |
1016 | inline PolyLine<Unit>& PolyLine<Unit>::joinHeadToHead(PolyLine<Unit>& that) { | |
1017 | return joinToHead(that, HEAD); | |
1018 | } | |
1019 | template <typename Unit> | |
1020 | inline PolyLine<Unit>& PolyLine<Unit>::joinHeadToTail(PolyLine<Unit>& that) { | |
1021 | return joinToHead(that, TAIL); | |
1022 | } | |
1023 | template <typename Unit> | |
1024 | inline PolyLine<Unit>& PolyLine<Unit>::joinTailToHead(PolyLine<Unit>& that) { | |
1025 | return joinToTail(that, HEAD); | |
1026 | } | |
1027 | template <typename Unit> | |
1028 | inline PolyLine<Unit>& PolyLine<Unit>::joinTailToTail(PolyLine<Unit>& that) { | |
1029 | return joinToTail(that, TAIL); | |
1030 | } | |
1031 | ||
1032 | template <typename Unit> | |
1033 | inline PolyLine<Unit>& PolyLine<Unit>::disconnectTails() { | |
1034 | next(TAIL)->state_ &= !TAIL_TO_TAIL; | |
1035 | next(TAIL)->tailp_ = 0; | |
1036 | state_ &= !TAIL_TO_TAIL; | |
1037 | tailp_ = 0; | |
1038 | return *this; | |
1039 | } | |
1040 | ||
1041 | template <typename Unit> | |
1042 | inline Unit PolyLine<Unit>::getEndCoord(End end) const { | |
1043 | if(end) | |
1044 | return ptdata_.back(); | |
1045 | return ptdata_.front(); | |
1046 | } | |
1047 | ||
1048 | template <typename Unit> | |
1049 | inline orientation_2d PolyLine<Unit>::segmentOrient(unsigned int index) const { | |
1050 | return (to_bool((unsigned int)verticalHead() ^ (index % 2)) ? VERTICAL : HORIZONTAL); | |
1051 | } | |
1052 | ||
1053 | template <typename Unit> | |
1054 | inline point_data<Unit> PolyLine<Unit>::getPoint(unsigned int index) const { | |
1055 | //assert(isValid() && headp_->isValid()) ("PolyLine: headp_ must be valid"); | |
1056 | point_data<Unit> pt; | |
1057 | pt.set(HORIZONTAL, ptdata_[index]); | |
1058 | pt.set(VERTICAL, ptdata_[index]); | |
1059 | Unit prevCoord; | |
1060 | if(index == 0) { | |
1061 | prevCoord = headp_->getEndCoord(headToTail()); | |
1062 | } else { | |
1063 | prevCoord = ptdata_[index-1]; | |
1064 | } | |
1065 | pt.set(segmentOrient(index), prevCoord); | |
1066 | return pt; | |
1067 | } | |
1068 | ||
1069 | template <typename Unit> | |
1070 | inline point_data<Unit> PolyLine<Unit>::getEndPoint(End end) const { | |
1071 | return getPoint((end ? numSegments() - 1 : (unsigned int)0)); | |
1072 | } | |
1073 | ||
1074 | template <typename Unit> | |
1075 | inline Unit PolyLine<Unit>::operator[] (unsigned int index) const { | |
1076 | //assert(ptdata_.size() > index) ("PolyLine: out of bounds index"); | |
1077 | return ptdata_[index]; | |
1078 | } | |
1079 | ||
1080 | template <typename Unit> | |
1081 | inline unsigned int PolyLine<Unit>::numSegments() const { | |
1082 | return ptdata_.size(); | |
1083 | } | |
1084 | ||
1085 | template <typename Unit> | |
1086 | inline PolyLine<Unit>* PolyLine<Unit>::next(End end) const { | |
1087 | return (end ? tailp_ : headp_); | |
1088 | } | |
1089 | ||
1090 | template <typename Unit> | |
1091 | inline ActiveTail<Unit>::ActiveTail() : tailp_(0), otherTailp_(0), holesList_(), | |
1092 | polyLineSize_(0) {} | |
1093 | ||
1094 | template <typename Unit> | |
1095 | inline ActiveTail<Unit>::ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp) : | |
1096 | tailp_(0), otherTailp_(0), holesList_(), polyLineSize_(0) { | |
1097 | tailp_ = createPolyLine(orient, coord, solidToRight); | |
1098 | otherTailp_ = otherTailp; | |
1099 | polyLineSize_ = tailp_->numSegments(); | |
1100 | } | |
1101 | ||
1102 | template <typename Unit> | |
1103 | inline ActiveTail<Unit>::ActiveTail(PolyLine<Unit>* active, ActiveTail<Unit>* otherTailp) : | |
1104 | tailp_(active), otherTailp_(otherTailp), holesList_(), | |
1105 | polyLineSize_(0) {} | |
1106 | ||
1107 | //copy constructor | |
1108 | template <typename Unit> | |
1109 | inline ActiveTail<Unit>::ActiveTail(const ActiveTail<Unit>& that) : tailp_(that.tailp_), otherTailp_(that.otherTailp_), holesList_(), polyLineSize_(that.polyLineSize_) {} | |
1110 | ||
1111 | //destructor | |
1112 | template <typename Unit> | |
1113 | inline ActiveTail<Unit>::~ActiveTail() { | |
1114 | //clear them in case the memory is read later | |
1115 | tailp_ = 0; otherTailp_ = 0; | |
1116 | } | |
1117 | ||
1118 | template <typename Unit> | |
1119 | inline ActiveTail<Unit>& ActiveTail<Unit>::operator=(const ActiveTail<Unit>& that) { | |
1120 | //self assignment is safe in this case | |
1121 | tailp_ = that.tailp_; | |
1122 | otherTailp_ = that.otherTailp_; | |
1123 | polyLineSize_ = that.polyLineSize_; | |
1124 | return *this; | |
1125 | } | |
1126 | ||
1127 | template <typename Unit> | |
1128 | inline bool ActiveTail<Unit>::operator==(const ActiveTail<Unit>& b) const { | |
1129 | return tailp_ == b.tailp_ && otherTailp_ == b.otherTailp_; | |
1130 | } | |
1131 | ||
1132 | template <typename Unit> | |
1133 | inline bool ActiveTail<Unit>::operator<(const ActiveTail<Unit>& b) const { | |
1134 | return tailp_->getEndPoint().get(VERTICAL) < b.tailp_->getEndPoint().get(VERTICAL); | |
1135 | } | |
1136 | ||
1137 | template <typename Unit> | |
1138 | inline bool ActiveTail<Unit>::operator<=(const ActiveTail<Unit>& b) const { | |
1139 | return !(*this > b); } | |
1140 | ||
1141 | template <typename Unit> | |
1142 | inline bool ActiveTail<Unit>::operator>(const ActiveTail<Unit>& b) const { | |
1143 | return b < (*this); } | |
1144 | ||
1145 | template <typename Unit> | |
1146 | inline bool ActiveTail<Unit>::operator>=(const ActiveTail<Unit>& b) const { | |
1147 | return !(*this < b); } | |
1148 | ||
1149 | template <typename Unit> | |
1150 | inline PolyLine<Unit>* ActiveTail<Unit>::getTail() const { | |
1151 | return tailp_; } | |
1152 | ||
1153 | template <typename Unit> | |
1154 | inline PolyLine<Unit>* ActiveTail<Unit>::getOtherTail() const { | |
1155 | return otherTailp_->tailp_; } | |
1156 | ||
1157 | template <typename Unit> | |
1158 | inline ActiveTail<Unit>* ActiveTail<Unit>::getOtherActiveTail() const { | |
1159 | return otherTailp_; } | |
1160 | ||
1161 | template <typename Unit> | |
1162 | inline bool ActiveTail<Unit>::isOtherTail(const ActiveTail<Unit>& b) { | |
1163 | // assert( (tailp_ == b.getOtherTail() && getOtherTail() == b.tailp_) || | |
1164 | // (tailp_ != b.getOtherTail() && getOtherTail() != b.tailp_)) | |
1165 | // ("ActiveTail: Active tails out of sync"); | |
1166 | return otherTailp_ == &b; | |
1167 | } | |
1168 | ||
1169 | template <typename Unit> | |
1170 | inline ActiveTail<Unit>& ActiveTail<Unit>::updateTail(PolyLine<Unit>* newTail) { | |
1171 | //subtract the old size and add new size// | |
1172 | int delta = newTail->numSegments() - tailp_->numSegments(); | |
1173 | addPolyLineSize(delta); | |
1174 | otherTailp_->addPolyLineSize(delta); | |
1175 | tailp_ = newTail; | |
1176 | return *this; | |
1177 | } | |
1178 | ||
1179 | template <typename Unit> | |
1180 | inline ActiveTail<Unit>* ActiveTail<Unit>::addHole(ActiveTail<Unit>* hole, bool fractureHoles) { | |
1181 | ||
1182 | if(!fractureHoles){ | |
1183 | holesList_.push_back(hole); | |
1184 | copyHoles(*hole); | |
1185 | copyHoles(*(hole->getOtherActiveTail())); | |
1186 | return this; | |
1187 | } | |
1188 | ActiveTail<Unit>* h, *v; | |
1189 | ActiveTail<Unit>* other = hole->getOtherActiveTail(); | |
1190 | if(other->getOrient() == VERTICAL) { | |
1191 | //assert that hole.getOrient() == HORIZONTAL | |
1192 | //this case should never happen | |
1193 | h = hole; | |
1194 | v = other; | |
1195 | } else { | |
1196 | //assert that hole.getOrient() == VERTICAL | |
1197 | h = other; | |
1198 | v = hole; | |
1199 | } | |
1200 | h->pushCoordinate(v->getCoordinate()); | |
1201 | //assert that h->getOrient() == VERTICAL | |
1202 | //v->pushCoordinate(getCoordinate()); | |
1203 | //assert that v->getOrient() == VERTICAL | |
1204 | //I can't close a figure by adding a hole, so pass zero for xMin and yMin | |
1205 | std::vector<Unit> tmpVec; | |
1206 | ActiveTail<Unit>::joinChains(this, h, false, tmpVec); | |
1207 | return v; | |
1208 | } | |
1209 | ||
1210 | template <typename Unit> | |
1211 | inline const std::list<ActiveTail<Unit>*>& ActiveTail<Unit>::getHoles() const { | |
1212 | return holesList_; | |
1213 | } | |
1214 | ||
1215 | template <typename Unit> | |
1216 | inline void ActiveTail<Unit>::copyHoles(ActiveTail<Unit>& that) { | |
1217 | holesList_.splice(holesList_.end(), that.holesList_); //splice the two lists together | |
1218 | } | |
1219 | ||
1220 | template <typename Unit> | |
1221 | inline bool ActiveTail<Unit>::solidToRight() const { | |
1222 | return getTail()->solidToRight(); } | |
1223 | ||
1224 | template <typename Unit> | |
1225 | inline Unit ActiveTail<Unit>::getCoord() const { | |
1226 | return getTail()->getEndCoord(); } | |
1227 | ||
1228 | template <typename Unit> | |
1229 | inline Unit ActiveTail<Unit>::getCoordinate() const { | |
1230 | return getCoord(); } | |
1231 | ||
1232 | template <typename Unit> | |
1233 | inline orientation_2d ActiveTail<Unit>::getOrient() const { | |
1234 | return getTail()->tailOrient(); } | |
1235 | ||
1236 | template <typename Unit> | |
1237 | inline void ActiveTail<Unit>::pushCoordinate(Unit coord) { | |
1238 | //appropriately handle any co-linear polyline segments by calling push point internally | |
1239 | point_data<Unit> p; | |
1240 | p.set(HORIZONTAL, coord); | |
1241 | p.set(VERTICAL, coord); | |
1242 | //if we are vertical assign the last coordinate (an X) to p.x, else to p.y | |
1243 | p.set(getOrient().get_perpendicular(), getCoordinate()); | |
1244 | int oldSegments = tailp_->numSegments(); | |
1245 | tailp_->pushPoint(p); | |
1246 | int delta = tailp_->numSegments() - oldSegments; | |
1247 | addPolyLineSize(delta); | |
1248 | otherTailp_->addPolyLineSize(delta); | |
1249 | } | |
1250 | ||
1251 | ||
1252 | //global utility functions | |
1253 | template <typename Unit> | |
1254 | inline PolyLine<Unit>* createPolyLine(orientation_2d orient, Unit coord, Side side) { | |
1255 | return new PolyLine<Unit>(orient, coord, side); | |
1256 | } | |
1257 | ||
1258 | template <typename Unit> | |
1259 | inline void destroyPolyLine(PolyLine<Unit>* pLine) { | |
1260 | delete pLine; | |
1261 | } | |
1262 | ||
1263 | template <typename Unit> | |
1264 | inline ActiveTail<Unit>* createActiveTail() { | |
1265 | //consider replacing system allocator with ActiveTail memory pool | |
1266 | return new ActiveTail<Unit>(); | |
1267 | } | |
1268 | ||
1269 | template <typename Unit> | |
1270 | inline void destroyActiveTail(ActiveTail<Unit>* aTail) { | |
1271 | delete aTail; | |
1272 | } | |
1273 | ||
1274 | ||
1275 | //no recursion, to prevent max recursion depth errors | |
1276 | template <typename Unit> | |
1277 | inline void ActiveTail<Unit>::destroyContents() { | |
1278 | tailp_->disconnectTails(); | |
1279 | PolyLine<Unit>* nextPolyLinep = tailp_->next(HEAD); | |
1280 | End end = tailp_->endConnectivity(HEAD); | |
1281 | destroyPolyLine(tailp_); | |
1282 | while(nextPolyLinep) { | |
1283 | End nextEnd = nextPolyLinep->endConnectivity(!end); //get the direction of next polyLine | |
1284 | PolyLine<Unit>* nextNextPolyLinep = nextPolyLinep->next(!end); //get the next polyline | |
1285 | destroyPolyLine(nextPolyLinep); //destroy the current polyline | |
1286 | end = nextEnd; | |
1287 | nextPolyLinep = nextNextPolyLinep; | |
1288 | } | |
1289 | } | |
1290 | ||
1291 | template <typename Unit> | |
1292 | inline typename ActiveTail<Unit>::iterator ActiveTail<Unit>::begin(bool isHole, orientation_2d orient) const { | |
1293 | return iterator(this, isHole, orient); | |
1294 | } | |
1295 | ||
1296 | template <typename Unit> | |
1297 | inline typename ActiveTail<Unit>::iterator ActiveTail<Unit>::end() const { | |
1298 | return iterator(); | |
1299 | } | |
1300 | ||
1301 | template <typename Unit> | |
1302 | inline typename ActiveTail<Unit>::iteratorHoles ActiveTail<Unit>::beginHoles() const { | |
1303 | return holesList_.begin(); | |
1304 | } | |
1305 | ||
1306 | template <typename Unit> | |
1307 | inline typename ActiveTail<Unit>::iteratorHoles ActiveTail<Unit>::endHoles() const { | |
1308 | return holesList_.end(); | |
1309 | } | |
1310 | ||
1311 | template <typename Unit> | |
1312 | inline void ActiveTail<Unit>::writeOutFigureItrs(iterator& beginOut, iterator& endOut, bool isHole, orientation_2d orient) const { | |
1313 | beginOut = begin(isHole, orient); | |
1314 | endOut = end(); | |
1315 | } | |
1316 | ||
1317 | template <typename Unit> | |
1318 | inline void ActiveTail<Unit>::writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const { | |
1319 | beginOut = beginHoles(); | |
1320 | endOut = endHoles(); | |
1321 | } | |
1322 | ||
1323 | template <typename Unit> | |
1324 | inline void ActiveTail<Unit>::writeOutFigure(std::vector<Unit>& outVec, bool isHole) const { | |
1325 | //we start writing out the polyLine that this active tail points to at its tail | |
1326 | std::size_t size = outVec.size(); | |
1327 | outVec.push_back(0); //place holder for size | |
1328 | PolyLine<Unit>* nextPolyLinep = 0; | |
1329 | if(!isHole){ | |
1330 | nextPolyLinep = otherTailp_->tailp_->writeOut(outVec); | |
1331 | } else { | |
1332 | nextPolyLinep = tailp_->writeOut(outVec); | |
1333 | } | |
1334 | Unit firsty = outVec[size + 1]; | |
1335 | if((getOrient() == HORIZONTAL) ^ !isHole) { | |
1336 | //our first coordinate is a y value, so we need to rotate it to the end | |
1337 | typename std::vector<Unit>::iterator tmpItr = outVec.begin(); | |
1338 | tmpItr += size; | |
1339 | outVec.erase(++tmpItr); //erase the 2nd element | |
1340 | } | |
1341 | End startEnd = tailp_->endConnectivity(HEAD); | |
1342 | if(isHole) startEnd = otherTailp_->tailp_->endConnectivity(HEAD); | |
1343 | while(nextPolyLinep) { | |
1344 | bool nextStartEnd = nextPolyLinep->endConnectivity(!startEnd); | |
1345 | nextPolyLinep = nextPolyLinep->writeOut(outVec, startEnd); | |
1346 | startEnd = nextStartEnd; | |
1347 | } | |
1348 | if((getOrient() == HORIZONTAL) ^ !isHole) { | |
1349 | //we want to push the y value onto the end since we ought to have ended with an x | |
1350 | outVec.push_back(firsty); //should never be executed because we want first value to be an x | |
1351 | } | |
1352 | //the vector contains the coordinates of the linked list of PolyLines in the correct order | |
1353 | //first element is supposed to be the size | |
1354 | outVec[size] = outVec.size() - 1 - size; //number of coordinates in vector | |
1355 | //assert outVec[size] % 2 == 0 //it should be even | |
1356 | //make the size negative for holes | |
1357 | outVec[size] *= (isHole ? -1 : 1); | |
1358 | } | |
1359 | ||
1360 | //no recursion to prevent max recursion depth errors | |
1361 | template <typename Unit> | |
1362 | inline PolyLine<Unit>* PolyLine<Unit>::writeOut(std::vector<Unit>& outVec, End startEnd) const { | |
1363 | if(startEnd == HEAD){ | |
1364 | //forward order | |
1365 | outVec.insert(outVec.end(), ptdata_.begin(), ptdata_.end()); | |
1366 | return tailp_; | |
1367 | }else{ | |
1368 | //reverse order | |
1369 | //do not reserve because we expect outVec to be large enough already | |
1370 | for(int i = ptdata_.size() - 1; i >= 0; --i){ | |
1371 | outVec.push_back(ptdata_[i]); | |
1372 | } | |
1373 | //NT didn't know about this version of the API.... | |
1374 | //outVec.insert(outVec.end(), ptdata_.rbegin(), ptdata_.rend()); | |
1375 | return headp_; | |
1376 | } | |
1377 | } | |
1378 | ||
1379 | //solid indicates if it was joined by a solit or a space | |
1380 | template <typename Unit> | |
1381 | inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, std::vector<Unit>& outBufferTmp) | |
1382 | { | |
1383 | //checks to see if we closed a figure | |
1384 | if(at1->isOtherTail(*at2)){ | |
1385 | //value of solid tells us if we closed solid or hole | |
1386 | //and output the solid or handle the hole appropriately | |
1387 | //if the hole needs to fracture across horizontal partition boundary we need to notify | |
1388 | //the calling context to do so | |
1389 | if(solid) { | |
1390 | //the chains are being joined because there is solid to the right | |
1391 | //this means that if the figure is closed at this point it must be a hole | |
1392 | //because otherwise it would have to have another vertex to the right of this one | |
1393 | //and would not be closed at this point | |
1394 | return at1; | |
1395 | } else { | |
1396 | //assert pG != 0 | |
1397 | //the figure that was closed is a shell | |
1398 | at1->writeOutFigure(outBufferTmp); | |
1399 | //process holes of the polygon | |
1400 | at1->copyHoles(*at2); //there should not be holes on at2, but if there are, copy them over | |
1401 | const std::list<ActiveTail<Unit>*>& holes = at1->getHoles(); | |
1402 | for(typename std::list<ActiveTail<Unit>*>::const_iterator litr = holes.begin(); litr != holes.end(); ++litr) { | |
1403 | (*litr)->writeOutFigure(outBufferTmp, true); | |
1404 | //delete the hole | |
1405 | (*litr)->destroyContents(); | |
1406 | destroyActiveTail((*litr)->getOtherActiveTail()); | |
1407 | destroyActiveTail((*litr)); | |
1408 | } | |
1409 | //delete the polygon | |
1410 | at1->destroyContents(); | |
1411 | //at2 contents are the same as at1, so it should not destroy them | |
1412 | destroyActiveTail(at1); | |
1413 | destroyActiveTail(at2); | |
1414 | } | |
1415 | return 0; | |
1416 | } | |
1417 | //join the two partial polygons into one large partial polygon | |
1418 | at1->getTail()->joinTailToTail(*(at2->getTail())); | |
1419 | *(at1->getOtherActiveTail()) = ActiveTail(at1->getOtherTail(), at2->getOtherActiveTail()); | |
1420 | *(at2->getOtherActiveTail()) = ActiveTail(at2->getOtherTail(), at1->getOtherActiveTail()); | |
1421 | ||
1422 | int accumulate = at2->getPolyLineSize() + at1->getPolyLineSize(); | |
1423 | (at1->getOtherActiveTail())->setPolyLineSize(accumulate); | |
1424 | (at2->getOtherActiveTail())->setPolyLineSize(accumulate); | |
1425 | ||
1426 | at1->getOtherActiveTail()->copyHoles(*at1); | |
1427 | at1->getOtherActiveTail()->copyHoles(*at2); | |
1428 | destroyActiveTail(at1); | |
1429 | destroyActiveTail(at2); | |
1430 | return 0; | |
1431 | } | |
1432 | ||
1433 | //solid indicates if it was joined by a solit or a space | |
1434 | template <typename Unit> | |
1435 | template <typename PolygonT> | |
1436 | inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, | |
1437 | std::vector<PolygonT>& outBufferTmp) { | |
1438 | //checks to see if we closed a figure | |
1439 | if(at1->isOtherTail(*at2)){ | |
1440 | //value of solid tells us if we closed solid or hole | |
1441 | //and output the solid or handle the hole appropriately | |
1442 | //if the hole needs to fracture across horizontal partition boundary we need to notify | |
1443 | //the calling context to do so | |
1444 | if(solid) { | |
1445 | //the chains are being joined because there is solid to the right | |
1446 | //this means that if the figure is closed at this point it must be a hole | |
1447 | //because otherwise it would have to have another vertex to the right of this one | |
1448 | //and would not be closed at this point | |
1449 | return at1; | |
1450 | } else { | |
1451 | //assert pG != 0 | |
1452 | //the figure that was closed is a shell | |
1453 | outBufferTmp.push_back(at1); | |
1454 | at1->copyHoles(*at2); //there should not be holes on at2, but if there are, copy them over | |
1455 | } | |
1456 | return 0; | |
1457 | } | |
1458 | //join the two partial polygons into one large partial polygon | |
1459 | at1->getTail()->joinTailToTail(*(at2->getTail())); | |
1460 | *(at1->getOtherActiveTail()) = ActiveTail<Unit>(at1->getOtherTail(), at2->getOtherActiveTail()); | |
1461 | *(at2->getOtherActiveTail()) = ActiveTail<Unit>(at2->getOtherTail(), at1->getOtherActiveTail()); | |
1462 | ||
1463 | int accumulate = at2->getPolyLineSize() + at1->getPolyLineSize(); | |
1464 | (at1->getOtherActiveTail())->setPolyLineSize(accumulate); | |
1465 | (at2->getOtherActiveTail())->setPolyLineSize(accumulate); | |
1466 | ||
1467 | at1->getOtherActiveTail()->copyHoles(*at1); | |
1468 | at1->getOtherActiveTail()->copyHoles(*at2); | |
1469 | destroyActiveTail(at1); | |
1470 | destroyActiveTail(at2); | |
1471 | return 0; | |
1472 | } | |
1473 | ||
1474 | template <class TKey, class T> inline typename std::map<TKey, T>::iterator findAtNext(std::map<TKey, T>& theMap, | |
1475 | typename std::map<TKey, T>::iterator pos, const TKey& key) | |
1476 | { | |
1477 | if(pos == theMap.end()) return theMap.find(key); | |
1478 | //if they match the mapItr is pointing to the correct position | |
1479 | if(pos->first < key) { | |
1480 | return theMap.find(key); | |
1481 | } | |
1482 | if(pos->first > key) { | |
1483 | return theMap.end(); | |
1484 | } | |
1485 | //else they are equal and no need to do anything to the iterator | |
1486 | return pos; | |
1487 | } | |
1488 | ||
1489 | // createActiveTailsAsPair is called in these two end cases of geometry | |
1490 | // 1. lower left concave corner | |
1491 | // ###| | |
1492 | // ###| | |
1493 | // ###|### | |
1494 | // ###|### | |
1495 | // 2. lower left convex corner | |
1496 | // |### | |
1497 | // |### | |
1498 | // | | |
1499 | // | | |
1500 | // In case 1 there may be a hole propigated up from the bottom. If the fracture option is enabled | |
1501 | // the two active tails that form the filament fracture line edges can become the new active tail pair | |
1502 | // by pushing x and y onto them. Otherwise the hole simply needs to be associated to one of the new active tails | |
1503 | // with add hole | |
1504 | template <typename Unit> | |
1505 | inline std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> createActiveTailsAsPair(Unit x, Unit y, bool solid, ActiveTail<Unit>* phole, bool fractureHoles) { | |
1506 | ActiveTail<Unit>* at1 = 0; | |
1507 | ActiveTail<Unit>* at2 = 0; | |
1508 | if(!phole || !fractureHoles){ | |
1509 | at1 = createActiveTail<Unit>(); | |
1510 | at2 = createActiveTail<Unit>(); | |
1511 | (*at1) = ActiveTail<Unit>(VERTICAL, x, solid, at2); | |
1512 | (*at2) = ActiveTail<Unit>(HORIZONTAL, y, !solid, at1); | |
1513 | //provide a function through activeTail class to provide this | |
1514 | at1->getTail()->joinHeadToHead(*(at2->getTail())); | |
1515 | ||
1516 | at1->addPolyLineSize(1); | |
1517 | at2->addPolyLineSize(1); | |
1518 | ||
1519 | if(phole) | |
1520 | at1->addHole(phole, fractureHoles); //assert fractureHoles == false | |
1521 | return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2); | |
1522 | } | |
1523 | //assert phole is not null | |
1524 | //assert fractureHoles is true | |
1525 | if(phole->getOrient() == VERTICAL) { | |
1526 | at2 = phole; | |
1527 | } else { | |
1528 | at2 = phole->getOtherActiveTail(); //should never be executed since orientation is expected to be vertical | |
1529 | } | |
1530 | //assert solid == false, we should be creating a corner with solid below and to the left if there was a hole | |
1531 | at1 = at2->getOtherActiveTail(); | |
1532 | //assert at1 is horizontal | |
1533 | at1->pushCoordinate(x); | |
1534 | //assert at2 is vertical | |
1535 | at2->pushCoordinate(y); | |
1536 | ||
1537 | return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2); | |
1538 | } | |
1539 | ||
1540 | /* | |
1541 | * | | |
1542 | * | | |
1543 | * = | |
1544 | * |######## | |
1545 | * |######## (add a new ActiveTail in the tailMap_). | |
1546 | * |######## | |
1547 | * |######## | |
1548 | * |######## | |
1549 | * = | |
1550 | * | | |
1551 | * | | |
1552 | * | |
1553 | * NOTE: Call this only if you are sure that the $ledege$ is not in the tailMap_ | |
1554 | */ | |
1555 | template<bool orientT, typename Unit, typename polygon_concept_type> | |
1556 | inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: | |
1557 | insertNewLeftEdgeIntoTailMap(Unit currentX, Unit yBegin, Unit yEnd, | |
1558 | typename std::map<Unit, ActiveTail<Unit> *>::iterator &hint){ | |
1559 | ActiveTail<Unit> *currentTail = NULL; | |
1560 | std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = | |
1561 | createActiveTailsAsPair(currentX, yBegin, true, currentTail, | |
1562 | fractureHoles_); | |
1563 | currentTail = tailPair.first; | |
1564 | if(!tailMap_.empty()){ | |
1565 | ++hint; | |
1566 | } | |
1567 | hint = tailMap_.insert(hint, std::make_pair(yBegin, tailPair.second)); | |
1568 | currentTail->pushCoordinate(yEnd); ++hint; | |
1569 | hint = tailMap_.insert(hint, std::make_pair(yEnd, currentTail)); | |
1570 | } | |
1571 | ||
1572 | template<bool orientT, typename Unit, typename polygon_concept_type> | |
1573 | inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: | |
1574 | closePartialSimplePolygon(Unit currentX, ActiveTail<Unit>*pfig, | |
1575 | ActiveTail<Unit>*ppfig){ | |
1576 | pfig->pushCoordinate(currentX); | |
1577 | ActiveTail<Unit>::joinChains(pfig, ppfig, false, outputPolygons_); | |
1578 | } | |
1579 | /* | |
1580 | * If the invariant is maintained correctly then left edges can do the | |
1581 | * following. | |
1582 | * | |
1583 | * =### | |
1584 | * ####### | |
1585 | * ####### | |
1586 | * ####### | |
1587 | * ####### | |
1588 | * =### | |
1589 | * |### (input left edge) | |
1590 | * |### | |
1591 | * =### | |
1592 | * ####### | |
1593 | * ####### | |
1594 | * =### | |
1595 | */ | |
1596 | template<bool orientT, typename Unit, typename polygon_concept_type> | |
1597 | inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: | |
1598 | updatePartialSimplePolygonsWithLeftEdges(Unit currentX, | |
1599 | const std::vector<interval_data<Unit> > &leftEdges, size_t vertexThreshold){ | |
1600 | typename std::map<Unit, ActiveTail<Unit>* >::iterator succ, succ1; | |
1601 | typename std::map<Unit, ActiveTail<Unit>* >::iterator pred, pred1, hint; | |
1602 | Unit begin, end; | |
1603 | ActiveTail<Unit> *pfig, *ppfig; | |
1604 | std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair; | |
1605 | size_t pfig_size = 0; | |
1606 | ||
1607 | hint = tailMap_.begin(); | |
1608 | for(size_t i=0; i < leftEdges.size(); i++){ | |
1609 | begin = leftEdges[i].get(LOW); end = leftEdges[i].get(HIGH); | |
1610 | succ = findAtNext(tailMap_, hint, begin); | |
1611 | pred = findAtNext(tailMap_, hint, end); | |
1612 | ||
1613 | if(succ != tailMap_.end() && pred != tailMap_.end()){ //CASE-1// | |
1614 | //join the corresponding active tails// | |
1615 | pfig = succ->second; ppfig = pred->second; | |
1616 | pfig_size = pfig->getPolyLineSize() + ppfig->getPolyLineSize(); | |
1617 | ||
1618 | if(pfig_size >= vertexThreshold){ | |
1619 | size_t bsize = pfig->getPolyLineSize(); | |
1620 | size_t usize = ppfig->getPolyLineSize(); | |
1621 | ||
1622 | if(usize+2 < vertexThreshold){ | |
1623 | //cut-off the lower piece (succ1, succ) join (succ1, pred)// | |
1624 | succ1 = succ; --succ1; | |
1625 | assert((succ1 != tailMap_.end()) && | |
1626 | ((succ->second)->getOtherActiveTail() == succ1->second)); | |
1627 | closePartialSimplePolygon(currentX, succ1->second, succ->second); | |
1628 | tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first, | |
1629 | true, NULL, fractureHoles_); | |
1630 | ||
1631 | //just update the succ1 with new ActiveTail<Unit>*// | |
1632 | succ1->second = tailPair.second; | |
1633 | ActiveTail<Unit>::joinChains(tailPair.first, pred->second, true, | |
1634 | outputPolygons_); | |
1635 | }else if(bsize+2 < vertexThreshold){ | |
1636 | //cut-off the upper piece () join ()// | |
1637 | pred1 = pred; ++pred1; | |
1638 | assert(pred1 != tailMap_.end() && | |
1639 | ((pred1->second)->getOtherActiveTail() == pred->second)); | |
1640 | closePartialSimplePolygon(currentX, pred->second, pred1->second); | |
1641 | ||
1642 | //just update the pred1 with ActiveTail<Unit>* = pfig// | |
1643 | pred1->second = pfig; | |
1644 | pfig->pushCoordinate(currentX); | |
1645 | pfig->pushCoordinate(pred1->first); | |
1646 | }else{ | |
1647 | //cut both and create an left edge between (pred->first, succ1)// | |
1648 | succ1 = succ; --succ1; | |
1649 | pred1 = pred; ++pred1; | |
1650 | assert(pred1 != tailMap_.end() && succ1 != tailMap_.end()); | |
1651 | assert((pred1->second)->getOtherActiveTail() == pred->second); | |
1652 | assert((succ1->second)->getOtherActiveTail() == succ->second); | |
1653 | ||
1654 | closePartialSimplePolygon(currentX, succ1->second, succ->second); | |
1655 | closePartialSimplePolygon(currentX, pred->second, pred1->second); | |
1656 | ||
1657 | tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first, | |
1658 | true, NULL, fractureHoles_); | |
1659 | succ1->second = tailPair.second; | |
1660 | pred1->second = tailPair.first; | |
1661 | (tailPair.first)->pushCoordinate(pred1->first); | |
1662 | } | |
1663 | }else{ | |
1664 | //just join them with closing// | |
1665 | pfig->pushCoordinate(currentX); | |
1666 | ActiveTail<Unit>::joinChains(pfig, ppfig, true, outputPolygons_); | |
1667 | } | |
1668 | hint = pred; ++hint; | |
1669 | tailMap_.erase(succ); tailMap_.erase(pred); | |
1670 | }else if(succ == tailMap_.end() && pred != tailMap_.end()){ //CASE-2// | |
1671 | //succ is missing in the map, first insert it into the map// | |
1672 | tailPair = createActiveTailsAsPair<Unit>(currentX, begin, true, NULL, | |
1673 | fractureHoles_); | |
1674 | hint = pred; ++hint; | |
1675 | hint = tailMap_.insert(hint, std::make_pair(begin, tailPair.second)); | |
1676 | ||
1677 | pfig = pred->second; | |
1678 | pfig_size = pfig->getPolyLineSize() + 2; | |
1679 | if(pfig_size >= vertexThreshold){ | |
1680 | //cut-off piece from [pred, pred1] , add [begin, pred1]// | |
1681 | pred1 = pred; ++pred1; | |
1682 | assert((pred1 != tailMap_.end()) && | |
1683 | ((pred1->second)->getOtherActiveTail() == pred->second)); | |
1684 | closePartialSimplePolygon(currentX, pred->second, pred1->second); | |
1685 | ||
1686 | //update: we need left edge between (begin, pred1->first)// | |
1687 | pred1->second = tailPair.first; | |
1688 | (tailPair.first)->pushCoordinate(pred1->first); | |
1689 | }else{ | |
1690 | //just join// | |
1691 | ActiveTail<Unit>::joinChains(tailPair.first, pfig, | |
1692 | true, outputPolygons_); | |
1693 | } | |
1694 | tailMap_.erase(pred); | |
1695 | }else if(succ != tailMap_.end() && pred == tailMap_.end()){ //CASE-3// | |
1696 | //pred is missing in the map, first insert it into the map// | |
1697 | hint = succ; ++hint; | |
1698 | hint = tailMap_.insert(hint, std::make_pair(end, (ActiveTail<Unit> *) NULL)); | |
1699 | pfig = succ->second; | |
1700 | pfig_size = pfig->getPolyLineSize() + 2; | |
1701 | if(pfig_size >= vertexThreshold){ | |
1702 | //this figure needs cutting here// | |
1703 | succ1 = succ; --succ1; | |
1704 | assert((succ1 != tailMap_.end()) && | |
1705 | (succ1->second == pfig->getOtherActiveTail())); | |
1706 | ppfig = succ1->second; | |
1707 | closePartialSimplePolygon(currentX, ppfig, pfig); | |
1708 | ||
1709 | //update: we need a left edge between (succ1->first, end)// | |
1710 | tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first, | |
1711 | true, NULL, fractureHoles_); | |
1712 | succ1->second = tailPair.second; | |
1713 | hint->second = tailPair.first; | |
1714 | (tailPair.first)->pushCoordinate(end); | |
1715 | }else{ | |
1716 | //no cutting needed// | |
1717 | hint->second = pfig; | |
1718 | pfig->pushCoordinate(currentX); | |
1719 | pfig->pushCoordinate(end); | |
1720 | } | |
1721 | tailMap_.erase(succ); | |
1722 | }else{ | |
1723 | //insert both pred and succ// | |
1724 | insertNewLeftEdgeIntoTailMap(currentX, begin, end, hint); | |
1725 | } | |
1726 | } | |
1727 | } | |
1728 | ||
1729 | template<bool orientT, typename Unit, typename polygon_concept_type> | |
1730 | inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: | |
1731 | updatePartialSimplePolygonsWithRightEdges(Unit currentX, | |
1732 | const std::vector<interval_data<Unit> > &rightEdges, size_t vertexThreshold) | |
1733 | { | |
1734 | ||
1735 | typename std::map<Unit, ActiveTail<Unit>* >::iterator succ, pred, hint; | |
1736 | std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair; | |
1737 | Unit begin, end; | |
1738 | size_t i = 0; | |
1739 | //If rightEdges is non-empty Then tailMap_ is non-empty // | |
1740 | assert(rightEdges.empty() || !tailMap_.empty() ); | |
1741 | ||
1742 | while( i < rightEdges.size() ){ | |
1743 | //find the interval in the tailMap which contains this interval// | |
1744 | pred = tailMap_.lower_bound(rightEdges[i].get(HIGH)); | |
1745 | assert(pred != tailMap_.end()); | |
1746 | succ = pred; --succ; | |
1747 | assert(pred != succ); | |
1748 | end = pred->first; begin = succ->first; | |
1749 | ||
1750 | //we now have a [begin, end] // | |
1751 | bool found_solid_opening = false; | |
1752 | bool erase_succ = true, erase_pred = true; | |
1753 | Unit solid_opening_begin = 0; | |
1754 | Unit solid_opening_end = 0; | |
1755 | size_t j = i+1; | |
1756 | ActiveTail<Unit> *pfig = succ->second; | |
1757 | ActiveTail<Unit> *ppfig = pred->second; | |
1758 | size_t partial_fig_size = pfig->getPolyLineSize(); | |
1759 | //Invariant:// | |
1760 | assert(succ->second && (pfig)->getOtherActiveTail() == ppfig); | |
1761 | ||
1762 | hint = succ; | |
1763 | Unit key = rightEdges[i].get(LOW); | |
1764 | if(begin != key){ | |
1765 | found_solid_opening = true; | |
1766 | solid_opening_begin = begin; solid_opening_end = key; | |
1767 | } | |
1768 | ||
1769 | while(j < rightEdges.size() && rightEdges[j].get(HIGH) <= end){ | |
1770 | if(rightEdges[j-1].get(HIGH) != rightEdges[j].get(LOW)){ | |
1771 | if(!found_solid_opening){ | |
1772 | found_solid_opening = true; | |
1773 | solid_opening_begin = rightEdges[j-1].get(HIGH); | |
1774 | solid_opening_end = rightEdges[j].get(LOW); | |
1775 | }else{ | |
1776 | ++hint; | |
1777 | insertNewLeftEdgeIntoTailMap(currentX, | |
1778 | rightEdges[j-1].get(HIGH), rightEdges[j].get(LOW), hint); | |
1779 | } | |
1780 | } | |
1781 | j++; | |
1782 | } | |
1783 | ||
1784 | //trailing edge// | |
1785 | if(end != rightEdges[j-1].get(HIGH)){ | |
1786 | if(!found_solid_opening){ | |
1787 | found_solid_opening = true; | |
1788 | solid_opening_begin = rightEdges[j-1].get(HIGH); solid_opening_end = end; | |
1789 | }else{ | |
1790 | // a solid opening has been found already, we need to insert a new left | |
1791 | // between [rightEdges[j-1].get(HIGH), end] | |
1792 | Unit lbegin = rightEdges[j-1].get(HIGH); | |
1793 | tailPair = createActiveTailsAsPair<Unit>(currentX, lbegin, true, NULL, | |
1794 | fractureHoles_); | |
1795 | hint = tailMap_.insert(pred, std::make_pair(lbegin, tailPair.second)); | |
1796 | pred->second = tailPair.first; | |
1797 | (tailPair.first)->pushCoordinate(end); | |
1798 | erase_pred = false; | |
1799 | } | |
1800 | } | |
1801 | ||
1802 | size_t vertex_delta = ((begin != solid_opening_begin) && | |
1803 | (end != solid_opening_end)) ? 4 : 2; | |
1804 | ||
1805 | if(!found_solid_opening){ | |
1806 | //just close the figure, TODO: call closePartialPolygon// | |
1807 | pfig->pushCoordinate(currentX); | |
1808 | ActiveTail<Unit>::joinChains(pfig, ppfig, false, outputPolygons_); | |
1809 | hint = pred; ++hint; | |
1810 | }else if(partial_fig_size+vertex_delta >= vertexThreshold){ | |
1811 | //close the figure and add a pseudo left-edge// | |
1812 | closePartialSimplePolygon(currentX, pfig, ppfig); | |
1813 | assert(begin != solid_opening_begin || end != solid_opening_end); | |
1814 | ||
1815 | if(begin != solid_opening_begin && end != solid_opening_end){ | |
1816 | insertNewLeftEdgeIntoTailMap(currentX, solid_opening_begin, | |
1817 | solid_opening_end, hint); | |
1818 | }else if(begin == solid_opening_begin){ | |
1819 | //we just need to update the succ in the tailMap_// | |
1820 | tailPair = createActiveTailsAsPair<Unit>(currentX, solid_opening_begin, | |
1821 | true, NULL, fractureHoles_); | |
1822 | succ->second = tailPair.second; | |
1823 | hint = succ; ++hint; | |
1824 | hint = tailMap_.insert(pred, std::make_pair(solid_opening_end, | |
1825 | tailPair.first)); | |
1826 | (tailPair.first)->pushCoordinate(solid_opening_end); | |
1827 | erase_succ = false; | |
1828 | }else{ | |
1829 | //we just need to update the pred in the tailMap_// | |
1830 | tailPair = createActiveTailsAsPair<Unit>(currentX, solid_opening_begin, | |
1831 | true, NULL, fractureHoles_); | |
1832 | hint = tailMap_.insert(pred, std::make_pair(solid_opening_begin, | |
1833 | tailPair.second)); | |
1834 | pred->second = tailPair.first; | |
1835 | (tailPair.first)->pushCoordinate(solid_opening_end); | |
1836 | erase_pred = false; | |
1837 | } | |
1838 | }else{ | |
1839 | //continue the figure (by adding at-most two new vertices)// | |
1840 | if(begin != solid_opening_begin){ | |
1841 | pfig->pushCoordinate(currentX); | |
1842 | pfig->pushCoordinate(solid_opening_begin); | |
1843 | //insert solid_opening_begin// | |
1844 | hint = succ; ++hint; | |
1845 | hint = tailMap_.insert(hint, std::make_pair(solid_opening_begin, pfig)); | |
1846 | }else{ | |
1847 | erase_succ = false; | |
1848 | } | |
1849 | ||
1850 | if(end != solid_opening_end){ | |
1851 | std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = | |
1852 | createActiveTailsAsPair<Unit>(currentX, solid_opening_end, false, | |
1853 | NULL, fractureHoles_); | |
1854 | hint = pred; ++hint; | |
1855 | hint = tailMap_.insert(hint, std::make_pair(solid_opening_end, | |
1856 | tailPair.second)); | |
1857 | ActiveTail<Unit>::joinChains(tailPair.first, ppfig, false, | |
1858 | outputPolygons_); | |
1859 | }else{ | |
1860 | erase_pred = false; | |
1861 | } | |
1862 | } | |
1863 | ||
1864 | //Remove the pred and succ if necessary// | |
1865 | if(erase_succ){ | |
1866 | tailMap_.erase(succ); | |
1867 | } | |
1868 | if(erase_pred){ | |
1869 | tailMap_.erase(pred); | |
1870 | } | |
1871 | i = j; | |
1872 | } | |
1873 | } | |
1874 | ||
1875 | // Maintains the following invariant: | |
1876 | // a. All the partial polygons formed at any state can be closed | |
1877 | // by a single edge. | |
1878 | template<bool orientT, typename Unit, typename polygon_concept_type> | |
1879 | inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: | |
1880 | maintainPartialSimplePolygonInvariant(iterator& beginOutput, | |
1881 | iterator& endOutput, Unit currentX, const std::vector<interval_data<Unit> >& l, | |
1882 | const std::vector<interval_data<Unit> >& r, size_t vertexThreshold) { | |
1883 | ||
1884 | clearOutput_(); | |
1885 | if(!l.empty()){ | |
1886 | updatePartialSimplePolygonsWithLeftEdges(currentX, l, vertexThreshold); | |
1887 | } | |
1888 | ||
1889 | if(!r.empty()){ | |
1890 | updatePartialSimplePolygonsWithRightEdges(currentX, r, vertexThreshold); | |
1891 | } | |
1892 | beginOutput = outputPolygons_.begin(); | |
1893 | endOutput = outputPolygons_.end(); | |
1894 | ||
1895 | } | |
1896 | ||
1897 | //Process edges connects vertical input edges (right or left edges of figures) to horizontal edges stored as member | |
1898 | //data of the scanline object. It also creates now horizontal edges as needed to construct figures from edge data. | |
1899 | // | |
1900 | //There are only 12 geometric end cases where the scanline intersects a horizontal edge and even fewer unique | |
1901 | //actions to take: | |
1902 | // 1. Solid on both sides of the vertical partition after the current position and space on both sides before | |
1903 | // ###|### | |
1904 | // ###|### | |
1905 | // | | |
1906 | // | | |
1907 | // This case does not need to be handled because there is no vertical edge at the current x coordinate. | |
1908 | // | |
1909 | // 2. Solid on both sides of the vertical partition before the current position and space on both sides after | |
1910 | // | | |
1911 | // | | |
1912 | // ###|### | |
1913 | // ###|### | |
1914 | // This case does not need to be handled because there is no vertical edge at the current x coordinate. | |
1915 | // | |
1916 | // 3. Solid on the left of the vertical partition after the current position and space elsewhere | |
1917 | // ###| | |
1918 | // ###| | |
1919 | // | | |
1920 | // | | |
1921 | // The horizontal edge from the left is found and turns upward because of the vertical right edge to become | |
1922 | // the currently active vertical edge. | |
1923 | // | |
1924 | // 4. Solid on the left of the vertical partion before the current position and space elsewhere | |
1925 | // | | |
1926 | // | | |
1927 | // ###| | |
1928 | // ###| | |
1929 | // The horizontal edge from the left is found and joined to the currently active vertical edge. | |
1930 | // | |
1931 | // 5. Solid to the right above and below and solid to the left above current position. | |
1932 | // ###|### | |
1933 | // ###|### | |
1934 | // |### | |
1935 | // |### | |
1936 | // The horizontal edge from the left is found and joined to the currently active vertical edge, | |
1937 | // potentially closing a hole. | |
1938 | // | |
1939 | // 6. Solid on the left of the vertical partion before the current position and solid to the right above and below | |
1940 | // |### | |
1941 | // |### | |
1942 | // ###|### | |
1943 | // ###|### | |
1944 | // The horizontal edge from the left is found and turns upward because of the vertical right edge to become | |
1945 | // the currently active vertical edge. | |
1946 | // | |
1947 | // 7. Solid on the right of the vertical partition after the current position and space elsewhere | |
1948 | // |### | |
1949 | // |### | |
1950 | // | | |
1951 | // | | |
1952 | // Create two new ActiveTails, one is added to the horizontal edges and the other becomes the vertical currentTail | |
1953 | // | |
1954 | // 8. Solid on the right of the vertical partion before the current position and space elsewhere | |
1955 | // | | |
1956 | // | | |
1957 | // |### | |
1958 | // |### | |
1959 | // The currentTail vertical edge turns right and is added to the horizontal edges data | |
1960 | // | |
1961 | // 9. Solid to the right above and solid to the left above and below current position. | |
1962 | // ###|### | |
1963 | // ###|### | |
1964 | // ###| | |
1965 | // ###| | |
1966 | // The currentTail vertical edge turns right and is added to the horizontal edges data | |
1967 | // | |
1968 | // 10. Solid on the left of the vertical partion above and below the current position and solid to the right below | |
1969 | // ###| | |
1970 | // ###| | |
1971 | // ###|### | |
1972 | // ###|### | |
1973 | // Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail | |
1974 | // | |
1975 | // 11. Solid to the right above and solid to the left below current position. | |
1976 | // |### | |
1977 | // |### | |
1978 | // ###| | |
1979 | // ###| | |
1980 | // The currentTail vertical edge joins the horizontal edge from the left (may close a polygon) | |
1981 | // Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail | |
1982 | // | |
1983 | // 12. Solid on the left of the vertical partion above the current position and solid to the right below | |
1984 | // ###| | |
1985 | // ###| | |
1986 | // |### | |
1987 | // |### | |
1988 | // The currentTail vertical edge turns right and is added to the horizontal edges data. | |
1989 | // The horizontal edge from the left turns upward and becomes the currentTail vertical edge | |
1990 | // | |
1991 | template <bool orientT, typename Unit, typename polygon_concept_type> | |
1992 | inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: | |
1993 | processEdges(iterator& beginOutput, iterator& endOutput, | |
1994 | Unit currentX, std::vector<interval_data<Unit> >& leftEdges, | |
1995 | std::vector<interval_data<Unit> >& rightEdges, | |
1996 | size_t vertexThreshold) { | |
1997 | clearOutput_(); | |
1998 | typename std::map<Unit, ActiveTail<Unit>*>::iterator nextMapItr; | |
1999 | //foreach edge | |
2000 | unsigned int leftIndex = 0; | |
2001 | unsigned int rightIndex = 0; | |
2002 | bool bottomAlreadyProcessed = false; | |
2003 | ActiveTail<Unit>* currentTail = 0; | |
2004 | const Unit UnitMax = (std::numeric_limits<Unit>::max)(); | |
2005 | ||
2006 | if(vertexThreshold < (std::numeric_limits<size_t>::max)()){ | |
2007 | maintainPartialSimplePolygonInvariant(beginOutput, endOutput, currentX, | |
2008 | leftEdges, rightEdges, vertexThreshold); | |
2009 | return; | |
2010 | } | |
2011 | ||
2012 | nextMapItr = tailMap_.begin(); | |
2013 | while(leftIndex < leftEdges.size() || rightIndex < rightEdges.size()) { | |
2014 | interval_data<Unit> edges[2] = {interval_data<Unit> (UnitMax, UnitMax), | |
2015 | interval_data<Unit> (UnitMax, UnitMax)}; | |
2016 | bool haveNextEdge = true; | |
2017 | if(leftIndex < leftEdges.size()) | |
2018 | edges[0] = leftEdges[leftIndex]; | |
2019 | else | |
2020 | haveNextEdge = false; | |
2021 | if(rightIndex < rightEdges.size()) | |
2022 | edges[1] = rightEdges[rightIndex]; | |
2023 | else | |
2024 | haveNextEdge = false; | |
2025 | bool trailingEdge = edges[1].get(LOW) < edges[0].get(LOW); | |
2026 | interval_data<Unit> & edge = edges[trailingEdge]; | |
2027 | interval_data<Unit> & nextEdge = edges[!trailingEdge]; | |
2028 | //process this edge | |
2029 | if(!bottomAlreadyProcessed) { | |
2030 | //assert currentTail = 0 | |
2031 | ||
2032 | //process the bottom end of this edge | |
2033 | typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(LOW)); | |
2034 | if(thisMapItr != tailMap_.end()) { | |
2035 | //there is an edge in the map at the low end of this edge | |
2036 | //it needs to turn upward and become the current tail | |
2037 | ActiveTail<Unit>* tail = thisMapItr->second; | |
2038 | if(currentTail) { | |
2039 | //stitch currentTail into this tail | |
2040 | currentTail = tail->addHole(currentTail, fractureHoles_); | |
2041 | if(!fractureHoles_) | |
2042 | currentTail->pushCoordinate(currentX); | |
2043 | } else { | |
2044 | currentTail = tail; | |
2045 | currentTail->pushCoordinate(currentX); | |
2046 | } | |
2047 | //assert currentTail->getOrient() == VERTICAL | |
2048 | nextMapItr = thisMapItr; //set nextMapItr to the next position after this one | |
2049 | ++nextMapItr; | |
2050 | //remove thisMapItr from the map | |
2051 | tailMap_.erase(thisMapItr); | |
2052 | } else { | |
2053 | //there is no edge in the map at the low end of this edge | |
2054 | //we need to create one and another one to be the current vertical tail | |
2055 | //if this is a trailing edge then there is space to the right of the vertical edge | |
2056 | //so pass the inverse of trailingEdge to indicate solid to the right | |
2057 | std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = | |
2058 | createActiveTailsAsPair(currentX, edge.get(LOW), !trailingEdge, currentTail, fractureHoles_); | |
2059 | currentTail = tailPair.first; | |
2060 | tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(LOW), tailPair.second)); | |
2061 | // leave nextMapItr unchanged | |
2062 | } | |
2063 | ||
2064 | } | |
2065 | if(haveNextEdge && edge.get(HIGH) == nextEdge.get(LOW)) { | |
2066 | //the top of this edge is equal to the bottom of the next edge, process them both | |
2067 | bottomAlreadyProcessed = true; | |
2068 | typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(HIGH)); | |
2069 | if(thisMapItr == tailMap_.end()) //assert this should never happen | |
2070 | return; | |
2071 | if(trailingEdge) { | |
2072 | //geometry at this position | |
2073 | // |## | |
2074 | // |## | |
2075 | // ----- | |
2076 | // ##| | |
2077 | // ##| | |
2078 | //current tail should join thisMapItr tail | |
2079 | ActiveTail<Unit>* tail = thisMapItr->second; | |
2080 | //pass false because they are being joined because space is to the right and it will close a solid figure | |
2081 | ActiveTail<Unit>::joinChains(currentTail, tail, false, outputPolygons_); | |
2082 | //two new tails are created, the vertical becomes current tail, the horizontal becomes thisMapItr tail | |
2083 | //pass true becuase they are created at the lower left corner of some solid | |
2084 | //pass null because there is no hole pointer possible | |
2085 | std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = | |
2086 | createActiveTailsAsPair<Unit>(currentX, edge.get(HIGH), true, 0, fractureHoles_); | |
2087 | currentTail = tailPair.first; | |
2088 | thisMapItr->second = tailPair.second; | |
2089 | } else { | |
2090 | //geometry at this position | |
2091 | // ##| | |
2092 | // ##| | |
2093 | // ----- | |
2094 | // |## | |
2095 | // |## | |
2096 | //current tail should turn right | |
2097 | currentTail->pushCoordinate(edge.get(HIGH)); | |
2098 | //thisMapItr tail should turn up | |
2099 | thisMapItr->second->pushCoordinate(currentX); | |
2100 | //thisMapItr tail becomes current tail and current tail becomes thisMapItr tail | |
2101 | std::swap(currentTail, thisMapItr->second); | |
2102 | } | |
2103 | nextMapItr = thisMapItr; //set nextMapItr to the next position after this one | |
2104 | ++nextMapItr; | |
2105 | } else { | |
2106 | //there is a gap between the top of this edge and the bottom of the next, process the top of this edge | |
2107 | bottomAlreadyProcessed = false; | |
2108 | //process the top of this edge | |
2109 | typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(HIGH)); | |
2110 | if(thisMapItr != tailMap_.end()) { | |
2111 | //thisMapItr is pointing to a horizontal edge in the map at the top of this vertical edge | |
2112 | //we need to join them and potentially close a figure | |
2113 | //assert currentTail != 0 | |
2114 | ActiveTail<Unit>* tail = thisMapItr->second; | |
2115 | //pass the opositve of trailing edge to mean that they are joined because of solid to the right | |
2116 | currentTail = ActiveTail<Unit>::joinChains(currentTail, tail, !trailingEdge, outputPolygons_); | |
2117 | nextMapItr = thisMapItr; //set nextMapItr to the next position after this one | |
2118 | ++nextMapItr; | |
2119 | if(currentTail) { //figure is not closed// | |
2120 | Unit nextItrY = UnitMax; | |
2121 | if(nextMapItr != tailMap_.end()) { | |
2122 | nextItrY = nextMapItr->first; | |
2123 | } | |
2124 | //for it to be a hole this must have been a left edge | |
2125 | Unit leftY = UnitMax; | |
2126 | if(leftIndex + 1 < leftEdges.size()) | |
2127 | leftY = leftEdges[leftIndex+1].get(LOW); | |
2128 | Unit rightY = nextEdge.get(LOW); | |
2129 | if(!haveNextEdge || (nextItrY < leftY && nextItrY < rightY)) { | |
2130 | //we need to add it to the next edge above it in the map | |
2131 | tail = nextMapItr->second; | |
2132 | tail = tail->addHole(currentTail, fractureHoles_); | |
2133 | if(fractureHoles_) { | |
2134 | //some small additional work stitching in the filament | |
2135 | tail->pushCoordinate(nextItrY); | |
2136 | nextMapItr->second = tail; | |
2137 | } | |
2138 | //set current tail to null | |
2139 | currentTail = 0; | |
2140 | } | |
2141 | } | |
2142 | //delete thisMapItr from the map | |
2143 | tailMap_.erase(thisMapItr); | |
2144 | } else { | |
2145 | //currentTail must turn right and be added into the map | |
2146 | currentTail->pushCoordinate(edge.get(HIGH)); | |
2147 | //assert currentTail->getOrient() == HORIZONTAL | |
2148 | tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(HIGH), currentTail)); | |
2149 | //set currentTail to null | |
2150 | currentTail = 0; | |
2151 | //leave nextMapItr unchanged, it is still next | |
2152 | } | |
2153 | } | |
2154 | ||
2155 | //increment index | |
2156 | leftIndex += !trailingEdge; | |
2157 | rightIndex += trailingEdge; | |
2158 | } //end while | |
2159 | beginOutput = outputPolygons_.begin(); | |
2160 | endOutput = outputPolygons_.end(); | |
2161 | } //end function | |
2162 | ||
2163 | template<bool orientT, typename Unit, typename polygon_concept_type> | |
2164 | inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::clearOutput_() { | |
2165 | for(std::size_t i = 0; i < outputPolygons_.size(); ++i) { | |
2166 | ActiveTail<Unit>* at1 = outputPolygons_[i].yield(); | |
2167 | const std::list<ActiveTail<Unit>*>& holes = at1->getHoles(); | |
2168 | for(typename std::list<ActiveTail<Unit>*>::const_iterator litr = holes.begin(); litr != holes.end(); ++litr) { | |
2169 | //delete the hole | |
2170 | (*litr)->destroyContents(); | |
2171 | destroyActiveTail((*litr)->getOtherActiveTail()); | |
2172 | destroyActiveTail((*litr)); | |
2173 | } | |
2174 | //delete the polygon | |
2175 | at1->destroyContents(); | |
2176 | //at2 contents are the same as at1, so it should not destroy them | |
2177 | destroyActiveTail((at1)->getOtherActiveTail()); | |
2178 | destroyActiveTail(at1); | |
2179 | } | |
2180 | outputPolygons_.clear(); | |
2181 | } | |
2182 | ||
2183 | } //polygon_formation namespace | |
2184 | ||
2185 | template <bool orientT, typename Unit> | |
2186 | struct geometry_concept<polygon_formation::PolyLinePolygonWithHolesData<orientT, Unit> > { | |
2187 | typedef polygon_90_with_holes_concept type; | |
2188 | }; | |
2189 | ||
2190 | template <bool orientT, typename Unit> | |
2191 | struct geometry_concept<polygon_formation::PolyLineHoleData<orientT, Unit> > { | |
2192 | typedef polygon_90_concept type; | |
2193 | }; | |
2194 | ||
2195 | //public API to access polygon formation algorithm | |
2196 | template <typename output_container, typename iterator_type, typename concept_type> | |
2197 | unsigned int get_polygons(output_container& container, | |
2198 | iterator_type begin, iterator_type end, orientation_2d orient, | |
2199 | bool fracture_holes, concept_type, | |
2200 | size_t sliceThreshold = (std::numeric_limits<size_t>::max)() ) { | |
2201 | typedef typename output_container::value_type polygon_type; | |
2202 | typedef typename std::iterator_traits<iterator_type>::value_type::first_type coordinate_type; | |
2203 | polygon_type poly; | |
2204 | unsigned int countPolygons = 0; | |
2205 | typedef typename geometry_concept<polygon_type>::type polygon_concept_type; | |
2206 | polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type> scanlineToPolygonItrsV(fracture_holes); | |
2207 | polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type> scanlineToPolygonItrsH(fracture_holes); | |
2208 | std::vector<interval_data<coordinate_type> > leftEdges; | |
2209 | std::vector<interval_data<coordinate_type> > rightEdges; | |
2210 | coordinate_type prevPos = (std::numeric_limits<coordinate_type>::max)(); | |
2211 | coordinate_type prevY = (std::numeric_limits<coordinate_type>::max)(); | |
2212 | int count = 0; | |
2213 | for(iterator_type itr = begin; | |
2214 | itr != end; ++ itr) { | |
2215 | coordinate_type pos = (*itr).first; | |
2216 | if(pos != prevPos) { | |
2217 | if(orient == VERTICAL) { | |
2218 | typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; | |
2219 | scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, | |
2220 | leftEdges, rightEdges, sliceThreshold); | |
2221 | for( ; itrPoly != itrPolyEnd; ++ itrPoly) { | |
2222 | ++countPolygons; | |
2223 | assign(poly, *itrPoly); | |
2224 | container.insert(container.end(), poly); | |
2225 | } | |
2226 | } else { | |
2227 | typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; | |
2228 | scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, | |
2229 | leftEdges, rightEdges, sliceThreshold); | |
2230 | for( ; itrPoly != itrPolyEnd; ++ itrPoly) { | |
2231 | ++countPolygons; | |
2232 | assign(poly, *itrPoly); | |
2233 | container.insert(container.end(), poly); | |
2234 | } | |
2235 | } | |
2236 | leftEdges.clear(); | |
2237 | rightEdges.clear(); | |
2238 | prevPos = pos; | |
2239 | prevY = (*itr).second.first; | |
2240 | count = (*itr).second.second; | |
2241 | continue; | |
2242 | } | |
2243 | coordinate_type y = (*itr).second.first; | |
2244 | if(count != 0 && y != prevY) { | |
2245 | std::pair<interval_data<coordinate_type>, int> element(interval_data<coordinate_type>(prevY, y), count); | |
2246 | if(element.second == 1) { | |
2247 | if(leftEdges.size() && leftEdges.back().high() == element.first.low()) { | |
2248 | encompass(leftEdges.back(), element.first); | |
2249 | } else { | |
2250 | leftEdges.push_back(element.first); | |
2251 | } | |
2252 | } else { | |
2253 | if(rightEdges.size() && rightEdges.back().high() == element.first.low()) { | |
2254 | encompass(rightEdges.back(), element.first); | |
2255 | } else { | |
2256 | rightEdges.push_back(element.first); | |
2257 | } | |
2258 | } | |
2259 | ||
2260 | } | |
2261 | prevY = y; | |
2262 | count += (*itr).second.second; | |
2263 | } | |
2264 | if(orient == VERTICAL) { | |
2265 | typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; | |
2266 | scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges, sliceThreshold); | |
2267 | for( ; itrPoly != itrPolyEnd; ++ itrPoly) { | |
2268 | ++countPolygons; | |
2269 | assign(poly, *itrPoly); | |
2270 | container.insert(container.end(), poly); | |
2271 | } | |
2272 | } else { | |
2273 | typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; | |
2274 | scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges, sliceThreshold); | |
2275 | ||
2276 | for( ; itrPoly != itrPolyEnd; ++ itrPoly) { | |
2277 | ++countPolygons; | |
2278 | assign(poly, *itrPoly); | |
2279 | container.insert(container.end(), poly); | |
2280 | } | |
2281 | } | |
2282 | return countPolygons; | |
2283 | } | |
2284 | ||
2285 | } | |
2286 | } | |
2287 | #endif |