1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 * Copyright (C) 2004-2006 Michael Wybrow <mjwybrow@users.sourceforge.net>
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 *
21 */
23 #include <stdio.h>
24 #include <cstdlib>
25 #include <algorithm>
26 #include <cassert>
27 #include <cmath>
29 #include "libavoid/shape.h"
30 #include "libavoid/region.h"
33 namespace Avoid {
35 Region *centerRegion = NULL;
37 static const BBox screenBBox =
38 {Point(-INFINITY, -INFINITY), Point(INFINITY, INFINITY)};
41 Region::Region()
42 : _bbox(screenBBox)
43 , _left(NULL), _right(NULL), _up(NULL), _down(NULL)
44 {
45 _blocks.clear();
46 }
49 Region::Region(double x1, double y1, double x2, double y2)
50 : _left(NULL), _right(NULL), _up(NULL), _down(NULL)
51 {
52 _bbox.a.x = x1;
53 _bbox.a.y = y1;
54 _bbox.b.x = x2;
55 _bbox.b.y = y2;
57 _blocks.clear();
58 }
61 static const unsigned int R_INSIDE = 0;
62 static const unsigned int R_LEFT = 1;
63 static const unsigned int R_LEDGE = 2;
64 static const unsigned int R_RIGHT = 4;
65 static const unsigned int R_REDGE = 8;
66 static const unsigned int R_ABOVE = 16;
67 static const unsigned int R_TEDGE = 32;
68 static const unsigned int R_BELOW = 64;
69 static const unsigned int R_BEDGE = 128;
71 static const unsigned int R_NONE = R_INSIDE;
72 static const unsigned int R_UP = R_ABOVE;
73 static const unsigned int R_DOWN = R_BELOW;
74 static const unsigned int R_HORI = R_LEFT | R_RIGHT;
75 static const unsigned int R_VERT = R_UP | R_DOWN;
78 static void printBBox(const char *label, const BBox &bbox)
79 {
80 if (label)
81 {
82 printf("%s: ", label);
83 }
84 printf("(%.2f, %.2f)-(%.2f, %.2f)\n", bbox.a.x, bbox.a.y,
85 bbox.b.x, bbox.b.y);
86 }
89 bool Region::overlapCheck(BBox& bbox, unsigned int& p)
90 {
91 p = R_INSIDE;
92 Point& a = bbox.a;
93 Point& b = bbox.b;
94 Point& r = _bbox.a;
95 Point& s = _bbox.b;
97 if (s.x <= a.x)
98 {
99 // Wholly right.
100 p = R_RIGHT;
101 return false;
102 }
103 else if (r.x >= b.x)
104 {
105 // Wholly left.
106 p = R_LEFT;
107 return false;
108 }
110 if (s.y <= a.y)
111 {
112 // Wholly below.
113 p = R_BELOW;
114 return false;
115 }
116 else if (r.y >= b.y)
117 {
118 // Wholly above.
119 p = R_ABOVE;
120 return false;
121 }
123 if (a.y == r.y)
124 {
125 // Shared top edge.
126 p |= R_TEDGE;
127 }
128 else if (a.y < r.y)
129 {
130 // Need to split above.
131 p |= R_ABOVE;
132 }
134 if (b.y == s.y)
135 {
136 // Shared bottom edge.
137 p |= R_BEDGE;
138 }
139 else if (b.y > s.y)
140 {
141 // Need to split below.
142 p |= R_BELOW;
143 }
145 if (a.x == r.x)
146 {
147 // Shared left edge.
148 p |= R_LEDGE;
149 }
150 else if (a.x < r.x)
151 {
152 // Need to split left.
153 p |= R_LEFT;
154 }
156 if (b.x == s.x)
157 {
158 // Shared right edge.
159 p |= R_REDGE;
160 }
161 else if (b.x > s.x)
162 {
163 // Need to split right.
164 p |= R_RIGHT;
165 }
167 return true;
168 }
171 void Region::getBBox(BBox& bb)
172 {
173 bb.a = _bbox.a;
174 bb.b = _bbox.b;
175 }
178 Region *Region::up(void)
179 {
180 return _up;
181 }
184 Region *Region::down(void)
185 {
186 return _down;
187 }
190 Region *Region::left(void)
191 {
192 return _left;
193 }
196 Region *Region::right(void)
197 {
198 return _right;
199 }
202 bool Region::isBlock(void)
203 {
204 return !(_blocks.empty());
205 }
208 void Region::initialSplit(BBox& bbox, unsigned int pos, unsigned int& shapeId)
209 {
210 Point& n1 = bbox.a;
211 Point& n2 = bbox.b;
212 Region *newR = this;
213 Region *left, *right, *top, *bottom;
215 if (pos == R_INSIDE)
216 {
217 split(n2.y, R_HORI);
218 split(n2.x, R_VERT);
219 newR = split(n1.y, R_HORI);
220 newR = newR->split(n1.x, R_VERT);
222 printf("%p - list %d add %d\n", newR,
223 (int) newR->_blocks.size(), shapeId);
224 newR->_blocks.push_back((int) shapeId);
225 newR->_blocks.sort();
226 newR->_blocks.unique();
227 }
228 else
229 {
230 Region *tar = NULL;
231 tar = newR->findRegion(n1.x, R_VERT);
232 if (pos & R_LEFT)
233 {
234 if (n1.x == tar->_bbox.a.x)
235 {
236 newR = tar->_right;
237 }
238 else if (n1.x == tar->_bbox.b.x)
239 {
240 newR = tar;
241 }
242 else
243 {
244 newR = tar->split(n1.x, R_VERT);
245 }
246 }
247 else if (!(pos & R_LEDGE))
248 {
249 newR = tar->split(n1.x, R_VERT);
250 }
251 left = newR;
253 tar = left->findRegion(n1.y, R_HORI);
254 if (pos & R_ABOVE)
255 {
256 if (n1.y == tar->_bbox.a.y)
257 {
258 newR = tar->_down;
259 }
260 else if (n1.y == tar->_bbox.b.y)
261 {
262 newR = tar;
263 }
264 else
265 {
266 newR = tar->split(n1.y, R_HORI);
267 }
268 }
269 else if (!(pos & R_TEDGE))
270 {
271 newR = tar->split(n1.y, R_HORI);
272 }
273 top = newR;
275 right = newR;
276 tar = newR->findRegion(n2.x, R_VERT);
277 if (pos & R_RIGHT)
278 {
280 if (n2.x == tar->_bbox.a.x)
281 {
282 right = tar->_left;
283 }
284 else if (n2.x == tar->_bbox.b.x)
285 {
286 right = tar;
287 }
288 else
289 {
290 tar->split(n2.x, R_VERT);
291 right = tar;
292 }
293 }
294 else if (!(pos & R_REDGE))
295 {
296 tar->split(n2.x, R_VERT);
297 right = tar;
298 }
300 bottom = right;
301 tar = right->findRegion(n2.y, R_HORI);
302 if (pos & R_BELOW)
303 {
304 if (n2.y == tar->_bbox.a.y)
305 {
306 bottom = tar->_up;
307 }
308 else if (n2.y == tar->_bbox.b.y)
309 {
310 bottom = tar;
311 }
312 else
313 {
314 tar->split(n2.y, R_HORI);
315 bottom = tar;
316 }
317 }
318 else if (!(pos & R_BEDGE))
319 {
320 tar->split(n2.y, R_HORI);
321 bottom = tar;
322 }
324 // top is actually top-left, and bottom is bottom-right.
325 Region *curr = top, *cptr = NULL;
326 while (curr->_bbox.b.y <= bottom->_bbox.b.y)
327 {
328 cptr = curr;
329 while (cptr->_bbox.b.x <= bottom->_bbox.b.x)
330 {
331 printf("%p - list %d add %d\n", cptr,
332 (int) cptr->_blocks.size(), shapeId);
333 cptr->_blocks.push_back((int) shapeId);
334 cptr->_blocks.sort();
335 cptr->_blocks.unique();
337 cptr = cptr->_right;
338 }
340 curr = curr->_down;
341 }
342 }
343 }
346 // Returns the region containing the value 'pos' in the direction 'dir'.
347 // Thus, if looking for the x value 55, you would pass R_VERT as 'dir'.
348 // 'forMerge' specifies that the left or top block of a pair of regions
349 // with the split value of 'pos' should be returned.
350 Region *Region::findRegion(double pos, unsigned int dir, const bool forMerge)
351 {
352 Region *curr = this;
354 if (dir & R_VERT)
355 {
356 while (pos > curr->_bbox.b.x)
357 {
358 curr = curr->_right;
359 }
360 while (pos < curr->_bbox.a.x)
361 {
362 curr = curr->_left;
363 }
364 if (forMerge)
365 {
366 if (pos == curr->_bbox.a.x)
367 {
368 curr = curr->_left;
369 }
370 if (pos != curr->_bbox.b.x)
371 {
372 // 'pos' is not on the boundary.
373 return NULL;
374 }
375 }
376 }
377 else if (dir & R_HORI)
378 {
379 while (pos > curr->_bbox.b.y)
380 {
381 curr = curr->_down;
382 }
383 while (pos < curr->_bbox.a.y)
384 {
385 curr = curr->_up;
386 }
387 if (forMerge)
388 {
389 if (pos == curr->_bbox.a.y)
390 {
391 curr = curr->_up;
392 }
393 if (pos != curr->_bbox.b.y)
394 {
395 // 'pos' is not on the boundary.
396 return NULL;
397 }
398 }
399 }
400 return curr;
401 }
404 Region *Region::split(double pos, unsigned int dir)
405 {
406 Region *newR = NULL;
407 bool first = true;
409 if (dir & R_VERT)
410 {
411 newR = splitDir(pos, R_UP, first);
412 if (_down) _down->splitDir(pos, R_DOWN);
413 }
414 else if (dir & R_HORI)
415 {
416 newR = splitDir(pos, R_RIGHT, first);
417 if (_left) _left->splitDir(pos, R_LEFT);
418 }
419 return newR;
420 }
423 void Region::merge(unsigned int dir)
424 {
425 bool first = true;
427 if (dir & R_VERT)
428 {
429 mergeDir(R_UP, first);
430 if (_down) _down->mergeDir(R_DOWN);
431 }
432 else if (dir & R_HORI)
433 {
434 mergeDir(R_RIGHT, first);
435 if (_left) _left->mergeDir(R_LEFT);
436 }
437 }
440 void Region::mergeRegion(Region *src)
441 {
442 assert(src != NULL);
444 if (src == _left)
445 {
446 pairHor(src->_left, this);
447 _bbox.a.x = src->_bbox.a.x;
448 }
449 else if (src == _right)
450 {
451 pairHor(this, src->_right);
452 _bbox.b.x = src->_bbox.b.x;
453 }
454 else if (src == _up)
455 {
456 pairVer(src->_up, this);
457 _bbox.a.y = src->_bbox.a.y;
458 }
459 else if (src == _down)
460 {
461 pairVer(this, src->_down);
462 _bbox.b.y = src->_bbox.b.y;
463 }
464 else
465 {
466 fprintf(stderr, "Error: Avoid::Region::merge(): "
467 "Argument not adjoining region.\n");
468 abort();
469 }
470 mergeAttributes(src);
471 printf("DEL %p\n", src);
472 delete src;
473 }
476 Region *Region::splitDir(double pos, unsigned int dir, bool first)
477 {
478 Point& o1 = _bbox.a;
479 Point& o2 = _bbox.b;
481 Region *newR = NULL;
483 if (dir & R_VERT)
484 {
485 assert(pos > _bbox.a.x);
486 assert(pos < _bbox.b.x);
488 // Vertical recursion:
490 // Create new block.
491 Region *r = new Region(pos, o1.y, o2.x, o2.y);
492 printf("NEW %p\n", r);
493 r->copyAttributes(this);
495 Region *o_up = _up;
496 Region *o_down = _down;
498 // Resize old block.
499 o2.x = pos;
501 pairHor(r, _right);
502 pairHor(this, r);
504 if (dir & R_UP)
505 {
506 if (!first) pairVer(r, _down->_right);
508 if (o_up) o_up->splitDir(pos, R_UP);
509 }
510 else if (dir & R_DOWN)
511 {
512 if (!first) pairVer(_up->_right, r);
514 if (o_down) o_down->splitDir(pos, R_DOWN);
515 }
516 newR = r;
517 }
518 else if (dir & R_HORI)
519 {
520 // Vertical recursion:
522 // Create new block.
523 Region *b = new Region(o1.x, pos, o2.x, o2.y);
524 printf("NEW %p\n", b);
525 b->copyAttributes(this);
527 Region *o_left = _left;
528 Region *o_right = _right;
530 // Resize old block.
531 o2.y = pos;
533 pairVer(b, _down);
534 pairVer(this, b);
536 if (dir & R_LEFT)
537 {
538 if (!first) pairHor(b, _right->_down);
540 if (o_left) o_left->splitDir(pos, R_LEFT);
541 }
542 else if (dir & R_RIGHT)
543 {
544 if (!first) pairHor(_left->_down, b);
546 if (o_right) o_right->splitDir(pos, R_RIGHT);
547 }
548 newR = b;
549 }
550 return newR;
551 }
554 void Region::mergeDir(unsigned int dir, bool first)
555 {
556 if (dir & R_VERT)
557 {
558 assert(_right != NULL);
560 mergeRegion(_right);
562 if (dir & R_UP)
563 {
564 if (_up) _up->mergeDir(dir, R_UP);
565 }
566 else if (dir & R_DOWN)
567 {
568 if (_down) _down->mergeDir(dir, R_DOWN);
569 }
570 }
571 else if (dir & R_HORI)
572 {
573 assert(_down != NULL);
575 mergeRegion(_down);
577 if (dir & R_LEFT)
578 {
579 if (_left) _left->mergeDir(dir, R_LEFT);
580 }
581 else if (dir & R_RIGHT)
582 {
583 if (_right) _right->mergeDir(dir, R_RIGHT);
584 }
585 }
586 }
589 void Region::copyAttributes(Region *src)
590 {
591 _blocks = src->_blocks;
592 }
595 void Region::mergeAttributes(Region *src)
596 {
597 _blocks.merge(src->_blocks);
598 _blocks.sort();
599 _blocks.unique();
600 }
603 //---------------------------
604 // Static member functions:
607 void Region::pairHor(Region *l, Region *r)
608 {
609 if (l) l->_right = r;
610 if (r) r->_left = l;
611 }
614 void Region::pairVer(Region *a, Region *b)
615 {
616 if (a) a->_down = b;
617 if (b) b->_up = a;
618 }
621 void Region::addShape(ShapeRef *shape)
622 {
623 if (!centerRegion)
624 {
625 // Add new default region.
626 centerRegion = new Region();
627 printf("NEW %p\n", centerRegion);
628 }
629 BBox bbox;
630 // Get bounding box for added shape.
631 shape->boundingBox(bbox);
632 printBBox("Add", bbox);
634 unsigned int shapeId = shape->id();
636 // Find starting point for overlap
637 Region *curr = centerRegion;
638 unsigned int pos = R_INSIDE;
639 while (!(curr->overlapCheck(bbox, pos)))
640 {
641 if (pos & R_LEFT)
642 {
643 curr = curr->_left;
644 }
645 else if (pos & R_RIGHT)
646 {
647 curr = curr->_right;
648 }
649 else if (pos & R_ABOVE)
650 {
651 curr = curr->_up;
652 }
653 else if (pos & R_BELOW)
654 {
655 curr = curr->_down;
656 }
657 }
659 curr->initialSplit(bbox, pos, shapeId);
660 centerRegion = curr;
661 }
664 void Region::removeShape(ShapeRef *shape)
665 {
666 const bool forMerge = true;
668 BBox bbox;
669 // Get bounding box for added shape.
670 shape->boundingBox(bbox);
671 printBBox("Remove", bbox);
673 unsigned int shapeId = shape->id();
675 Region *aboveTop = centerRegion->findRegion(bbox.a.y, R_HORI, forMerge);
676 Region *aboveBottom = aboveTop->findRegion(bbox.b.y, R_HORI, forMerge);
677 Region *leftOfLeft = aboveBottom->findRegion(bbox.a.x, R_VERT, forMerge);
678 Region *leftOfRight = leftOfLeft->findRegion(bbox.b.x, R_VERT, forMerge);
680 assert(aboveTop != NULL);
681 assert(aboveBottom != NULL);
682 assert(leftOfLeft != NULL);
683 assert(leftOfRight != NULL);
685 // Find Top Left.
686 Region *topLeft = leftOfLeft->_right;
687 while (topLeft->_bbox.a.y != aboveTop->_bbox.b.y)
688 {
689 topLeft = topLeft->_up;
690 }
692 // Find Bottom Right.
693 Region *botRight = leftOfRight;
694 while (botRight->_bbox.b.y != aboveBottom->_bbox.b.y)
695 {
696 botRight = botRight->_down;
697 }
699 // Clear blocking flag.
700 Region *curr = topLeft, *cptr = NULL;
701 while (curr->_bbox.b.y <= botRight->_bbox.b.y)
702 {
703 cptr = curr;
704 while (cptr->_bbox.b.x <= botRight->_bbox.b.x)
705 {
706 ShapeList& blocks = cptr->_blocks;
708 assert(std::find(blocks.begin(), blocks.end(), (int) shapeId) !=
709 blocks.end());
710 printf("%p - list %d remove %d\n", cptr,
711 (int) blocks.size(), shapeId);
712 cptr->_blocks.remove((int) shapeId);
714 cptr = cptr->_right;
715 }
717 curr = curr->_down;
718 }
720 // These two are safe since they don't invalidate the pointers
721 // to the regions that are inside the shape.
722 if (aboveBottom->safeToMerge(R_HORI))
723 {
724 aboveBottom->merge(R_HORI);
725 }
726 if (leftOfRight->safeToMerge(R_VERT))
727 {
728 leftOfRight->merge(R_VERT);
729 }
731 // Be a bit more careful with these.
732 double leftX = leftOfLeft->_bbox.b.x;
733 if (aboveTop->safeToMerge(R_HORI))
734 {
735 aboveTop->merge(R_HORI);
736 }
737 // leftOfLeft may have been freed, so look for the new block at
738 // that position.
739 leftOfLeft = aboveTop->findRegion(leftX, R_VERT, forMerge);
740 assert(leftOfLeft);
741 if (leftOfLeft->safeToMerge(R_VERT))
742 {
743 leftOfLeft->merge(R_VERT);
744 }
745 }
748 bool Region::safeToMerge(unsigned int dir)
749 {
750 bool unsafe = false;
752 if (dir == R_HORI)
753 {
754 printf("safeToMerge? y = %.3f... ", _bbox.b.y);
755 unsafe |= unsafeToMerge(R_RIGHT);
756 if (_left) unsafe |= _left->unsafeToMerge(R_LEFT);
757 }
758 else if (dir == R_VERT)
759 {
760 printf("safeToMerge? x = %.3f... ", _bbox.b.x);
761 unsafe |= unsafeToMerge(R_DOWN);
762 if (_up) unsafe |= _up->unsafeToMerge(R_UP);
763 }
764 printf("%s.\n", (unsafe) ? "no" : "yes");
766 return !unsafe;
767 }
770 bool Region::unsafeToMerge(unsigned int dir)
771 {
772 bool unsafe = false;
774 if (dir & R_HORI)
775 {
776 // If they are not the same on both sides then we can merge.
777 if (_blocks != _down->_blocks)
778 {
779 printf("\n _blocks:\n ");
780 for (ShapeList::iterator i = _blocks.begin(); i != _blocks.end();
781 ++i)
782 {
783 printf("%d ", *i);
784 }
785 printf("\n _down->_blocks:\n ");
786 for (ShapeList::iterator i = _down->_blocks.begin();
787 i != _down->_blocks.end(); ++i)
788 {
789 printf("%d ", *i);
790 }
791 unsafe |= true;
792 printf("\n");
793 }
795 if ((dir == R_LEFT) && _left)
796 {
797 unsafe |= _left->unsafeToMerge(dir);
798 }
799 else if ((dir == R_RIGHT) && _right)
800 {
801 unsafe |= _right->unsafeToMerge(dir);
802 }
803 }
804 else if (dir & R_VERT)
805 {
806 if (_blocks != _right->_blocks)
807 {
808 printf("\n _blocks:\n ");
809 for (ShapeList::iterator i = _blocks.begin(); i != _blocks.end();
810 ++i)
811 {
812 printf("%d ", *i);
813 }
814 printf("\n _right->_blocks:\n ");
815 for (ShapeList::iterator i = _right->_blocks.begin();
816 i != _right->_blocks.end(); ++i)
817 {
818 printf("%d ", *i);
819 }
820 unsafe |= true;
821 printf("\n");
822 }
824 if ((dir == R_UP) && _up)
825 {
826 unsafe |= _up->unsafeToMerge(dir);
827 }
828 else if ((dir == R_DOWN) && _down)
829 {
830 unsafe |= _down->unsafeToMerge(dir);
831 }
832 }
833 return unsafe;
835 }
838 Region *Region::getTopLeftRegion(void)
839 {
840 Region *curr = centerRegion;
842 while (curr && (curr->_up || curr->_left))
843 {
844 if (curr->_up)
845 {
846 curr = curr->_up;
847 }
848 else
849 {
850 curr = curr->_left;
851 }
852 }
853 return curr;
854 }
857 }