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 <cstdlib>
24 #include <algorithm>
25 #include <cassert>
26 #include <cmath>
28 #include "libavoid/shape.h"
29 #include "libavoid/region.h"
32 namespace Avoid {
34 Region *centerRegion = NULL;
36 static const BBox screenBBox =
37 {Point(-INFINITY, -INFINITY), Point(INFINITY, INFINITY)};
40 Region::Region()
41 : _bbox(screenBBox)
42 , _left(NULL), _right(NULL), _up(NULL), _down(NULL)
43 {
44 _blocks.clear();
45 }
48 Region::Region(double x1, double y1, double x2, double y2)
49 : _left(NULL), _right(NULL), _up(NULL), _down(NULL)
50 {
51 _bbox.a.x = x1;
52 _bbox.a.y = y1;
53 _bbox.b.x = x2;
54 _bbox.b.y = y2;
56 _blocks.clear();
57 }
60 static const unsigned int R_INSIDE = 0;
61 static const unsigned int R_LEFT = 1;
62 static const unsigned int R_LEDGE = 2;
63 static const unsigned int R_RIGHT = 4;
64 static const unsigned int R_REDGE = 8;
65 static const unsigned int R_ABOVE = 16;
66 static const unsigned int R_TEDGE = 32;
67 static const unsigned int R_BELOW = 64;
68 static const unsigned int R_BEDGE = 128;
70 static const unsigned int R_NONE = R_INSIDE;
71 static const unsigned int R_UP = R_ABOVE;
72 static const unsigned int R_DOWN = R_BELOW;
73 static const unsigned int R_HORI = R_LEFT | R_RIGHT;
74 static const unsigned int R_VERT = R_UP | R_DOWN;
77 static void printBBox(const char *label, const BBox &bbox)
78 {
79 if (label)
80 {
81 printf("%s: ", label);
82 }
83 printf("(%.2f, %.2f)-(%.2f, %.2f)\n", bbox.a.x, bbox.a.y,
84 bbox.b.x, bbox.b.y);
85 }
88 bool Region::overlapCheck(BBox& bbox, unsigned int& p)
89 {
90 p = R_INSIDE;
91 Point& a = bbox.a;
92 Point& b = bbox.b;
93 Point& r = _bbox.a;
94 Point& s = _bbox.b;
96 if (s.x <= a.x)
97 {
98 // Wholly right.
99 p = R_RIGHT;
100 return false;
101 }
102 else if (r.x >= b.x)
103 {
104 // Wholly left.
105 p = R_LEFT;
106 return false;
107 }
109 if (s.y <= a.y)
110 {
111 // Wholly below.
112 p = R_BELOW;
113 return false;
114 }
115 else if (r.y >= b.y)
116 {
117 // Wholly above.
118 p = R_ABOVE;
119 return false;
120 }
122 if (a.y == r.y)
123 {
124 // Shared top edge.
125 p |= R_TEDGE;
126 }
127 else if (a.y < r.y)
128 {
129 // Need to split above.
130 p |= R_ABOVE;
131 }
133 if (b.y == s.y)
134 {
135 // Shared bottom edge.
136 p |= R_BEDGE;
137 }
138 else if (b.y > s.y)
139 {
140 // Need to split below.
141 p |= R_BELOW;
142 }
144 if (a.x == r.x)
145 {
146 // Shared left edge.
147 p |= R_LEDGE;
148 }
149 else if (a.x < r.x)
150 {
151 // Need to split left.
152 p |= R_LEFT;
153 }
155 if (b.x == s.x)
156 {
157 // Shared right edge.
158 p |= R_REDGE;
159 }
160 else if (b.x > s.x)
161 {
162 // Need to split right.
163 p |= R_RIGHT;
164 }
166 return true;
167 }
170 void Region::getBBox(BBox& bb)
171 {
172 bb.a = _bbox.a;
173 bb.b = _bbox.b;
174 }
177 Region *Region::up(void)
178 {
179 return _up;
180 }
183 Region *Region::down(void)
184 {
185 return _down;
186 }
189 Region *Region::left(void)
190 {
191 return _left;
192 }
195 Region *Region::right(void)
196 {
197 return _right;
198 }
201 bool Region::isBlock(void)
202 {
203 return !(_blocks.empty());
204 }
207 void Region::initialSplit(BBox& bbox, unsigned int pos, unsigned int& shapeId)
208 {
209 Point& n1 = bbox.a;
210 Point& n2 = bbox.b;
211 Region *newR = this;
212 Region *left, *right, *top, *bottom;
214 if (pos == R_INSIDE)
215 {
216 split(n2.y, R_HORI);
217 split(n2.x, R_VERT);
218 newR = split(n1.y, R_HORI);
219 newR = newR->split(n1.x, R_VERT);
221 printf("%X - list %d add %d\n", (int) newR,
222 (int) newR->_blocks.size(), shapeId);
223 newR->_blocks.push_back((int) shapeId);
224 newR->_blocks.sort();
225 newR->_blocks.unique();
226 }
227 else
228 {
229 Region *tar = NULL;
230 tar = newR->findRegion(n1.x, R_VERT);
231 if (pos & R_LEFT)
232 {
233 if (n1.x == tar->_bbox.a.x)
234 {
235 newR = tar->_right;
236 }
237 else if (n1.x == tar->_bbox.b.x)
238 {
239 newR = tar;
240 }
241 else
242 {
243 newR = tar->split(n1.x, R_VERT);
244 }
245 }
246 else if (!(pos & R_LEDGE))
247 {
248 newR = tar->split(n1.x, R_VERT);
249 }
250 left = newR;
252 tar = left->findRegion(n1.y, R_HORI);
253 if (pos & R_ABOVE)
254 {
255 if (n1.y == tar->_bbox.a.y)
256 {
257 newR = tar->_down;
258 }
259 else if (n1.y == tar->_bbox.b.y)
260 {
261 newR = tar;
262 }
263 else
264 {
265 newR = tar->split(n1.y, R_HORI);
266 }
267 }
268 else if (!(pos & R_TEDGE))
269 {
270 newR = tar->split(n1.y, R_HORI);
271 }
272 top = newR;
274 right = newR;
275 tar = newR->findRegion(n2.x, R_VERT);
276 if (pos & R_RIGHT)
277 {
279 if (n2.x == tar->_bbox.a.x)
280 {
281 right = tar->_left;
282 }
283 else if (n2.x == tar->_bbox.b.x)
284 {
285 right = tar;
286 }
287 else
288 {
289 tar->split(n2.x, R_VERT);
290 right = tar;
291 }
292 }
293 else if (!(pos & R_REDGE))
294 {
295 tar->split(n2.x, R_VERT);
296 right = tar;
297 }
299 bottom = right;
300 tar = right->findRegion(n2.y, R_HORI);
301 if (pos & R_BELOW)
302 {
303 if (n2.y == tar->_bbox.a.y)
304 {
305 bottom = tar->_up;
306 }
307 else if (n2.y == tar->_bbox.b.y)
308 {
309 bottom = tar;
310 }
311 else
312 {
313 tar->split(n2.y, R_HORI);
314 bottom = tar;
315 }
316 }
317 else if (!(pos & R_BEDGE))
318 {
319 tar->split(n2.y, R_HORI);
320 bottom = tar;
321 }
323 // top is actually top-left, and bottom is bottom-right.
324 Region *curr = top, *cptr = NULL;
325 while (curr->_bbox.b.y <= bottom->_bbox.b.y)
326 {
327 cptr = curr;
328 while (cptr->_bbox.b.x <= bottom->_bbox.b.x)
329 {
330 printf("%X - list %d add %d\n", (int) cptr,
331 (int) cptr->_blocks.size(), shapeId);
332 cptr->_blocks.push_back((int) shapeId);
333 cptr->_blocks.sort();
334 cptr->_blocks.unique();
336 cptr = cptr->_right;
337 }
339 curr = curr->_down;
340 }
341 }
342 }
345 // Returns the region containing the value 'pos' in the direction 'dir'.
346 // Thus, if looking for the x value 55, you would pass R_VERT as 'dir'.
347 // 'forMerge' specifies that the left or top block of a pair of regions
348 // with the split value of 'pos' should be returned.
349 Region *Region::findRegion(double pos, unsigned int dir, const bool forMerge)
350 {
351 Region *curr = this;
353 if (dir & R_VERT)
354 {
355 while (pos > curr->_bbox.b.x)
356 {
357 curr = curr->_right;
358 }
359 while (pos < curr->_bbox.a.x)
360 {
361 curr = curr->_left;
362 }
363 if (forMerge)
364 {
365 if (pos == curr->_bbox.a.x)
366 {
367 curr = curr->_left;
368 }
369 if (pos != curr->_bbox.b.x)
370 {
371 // 'pos' is not on the boundary.
372 return NULL;
373 }
374 }
375 }
376 else if (dir & R_HORI)
377 {
378 while (pos > curr->_bbox.b.y)
379 {
380 curr = curr->_down;
381 }
382 while (pos < curr->_bbox.a.y)
383 {
384 curr = curr->_up;
385 }
386 if (forMerge)
387 {
388 if (pos == curr->_bbox.a.y)
389 {
390 curr = curr->_up;
391 }
392 if (pos != curr->_bbox.b.y)
393 {
394 // 'pos' is not on the boundary.
395 return NULL;
396 }
397 }
398 }
399 return curr;
400 }
403 Region *Region::split(double pos, unsigned int dir)
404 {
405 Region *newR = NULL;
406 bool first = true;
408 if (dir & R_VERT)
409 {
410 newR = splitDir(pos, R_UP, first);
411 if (_down) _down->splitDir(pos, R_DOWN);
412 }
413 else if (dir & R_HORI)
414 {
415 newR = splitDir(pos, R_RIGHT, first);
416 if (_left) _left->splitDir(pos, R_LEFT);
417 }
418 return newR;
419 }
422 void Region::merge(unsigned int dir)
423 {
424 bool first = true;
426 if (dir & R_VERT)
427 {
428 mergeDir(R_UP, first);
429 if (_down) _down->mergeDir(R_DOWN);
430 }
431 else if (dir & R_HORI)
432 {
433 mergeDir(R_RIGHT, first);
434 if (_left) _left->mergeDir(R_LEFT);
435 }
436 }
439 void Region::mergeRegion(Region *src)
440 {
441 assert(src != NULL);
443 if (src == _left)
444 {
445 pairHor(src->_left, this);
446 _bbox.a.x = src->_bbox.a.x;
447 }
448 else if (src == _right)
449 {
450 pairHor(this, src->_right);
451 _bbox.b.x = src->_bbox.b.x;
452 }
453 else if (src == _up)
454 {
455 pairVer(src->_up, this);
456 _bbox.a.y = src->_bbox.a.y;
457 }
458 else if (src == _down)
459 {
460 pairVer(this, src->_down);
461 _bbox.b.y = src->_bbox.b.y;
462 }
463 else
464 {
465 fprintf(stderr, "Error: Avoid::Region::merge(): "
466 "Argument not adjoining region.\n");
467 abort();
468 }
469 mergeAttributes(src);
470 printf("DEL %X\n", (int) src);
471 delete src;
472 }
475 Region *Region::splitDir(double pos, unsigned int dir, bool first)
476 {
477 Point& o1 = _bbox.a;
478 Point& o2 = _bbox.b;
480 Region *newR = NULL;
482 if (dir & R_VERT)
483 {
484 assert(pos > _bbox.a.x);
485 assert(pos < _bbox.b.x);
487 // Vertical recursion:
489 // Create new block.
490 Region *r = new Region(pos, o1.y, o2.x, o2.y);
491 printf("NEW %X\n", (int) r);
492 r->copyAttributes(this);
494 Region *o_up = _up;
495 Region *o_down = _down;
497 // Resize old block.
498 o2.x = pos;
500 pairHor(r, _right);
501 pairHor(this, r);
503 if (dir & R_UP)
504 {
505 if (!first) pairVer(r, _down->_right);
507 if (o_up) o_up->splitDir(pos, R_UP);
508 }
509 else if (dir & R_DOWN)
510 {
511 if (!first) pairVer(_up->_right, r);
513 if (o_down) o_down->splitDir(pos, R_DOWN);
514 }
515 newR = r;
516 }
517 else if (dir & R_HORI)
518 {
519 // Vertical recursion:
521 // Create new block.
522 Region *b = new Region(o1.x, pos, o2.x, o2.y);
523 printf("NEW %X\n", (int) b);
524 b->copyAttributes(this);
526 Region *o_left = _left;
527 Region *o_right = _right;
529 // Resize old block.
530 o2.y = pos;
532 pairVer(b, _down);
533 pairVer(this, b);
535 if (dir & R_LEFT)
536 {
537 if (!first) pairHor(b, _right->_down);
539 if (o_left) o_left->splitDir(pos, R_LEFT);
540 }
541 else if (dir & R_RIGHT)
542 {
543 if (!first) pairHor(_left->_down, b);
545 if (o_right) o_right->splitDir(pos, R_RIGHT);
546 }
547 newR = b;
548 }
549 return newR;
550 }
553 void Region::mergeDir(unsigned int dir, bool first)
554 {
555 if (dir & R_VERT)
556 {
557 assert(_right != NULL);
559 mergeRegion(_right);
561 if (dir & R_UP)
562 {
563 if (_up) _up->mergeDir(dir, R_UP);
564 }
565 else if (dir & R_DOWN)
566 {
567 if (_down) _down->mergeDir(dir, R_DOWN);
568 }
569 }
570 else if (dir & R_HORI)
571 {
572 assert(_down != NULL);
574 mergeRegion(_down);
576 if (dir & R_LEFT)
577 {
578 if (_left) _left->mergeDir(dir, R_LEFT);
579 }
580 else if (dir & R_RIGHT)
581 {
582 if (_right) _right->mergeDir(dir, R_RIGHT);
583 }
584 }
585 }
588 void Region::copyAttributes(Region *src)
589 {
590 _blocks = src->_blocks;
591 }
594 void Region::mergeAttributes(Region *src)
595 {
596 _blocks.merge(src->_blocks);
597 _blocks.sort();
598 _blocks.unique();
599 }
602 //---------------------------
603 // Static member functions:
606 void Region::pairHor(Region *l, Region *r)
607 {
608 if (l) l->_right = r;
609 if (r) r->_left = l;
610 }
613 void Region::pairVer(Region *a, Region *b)
614 {
615 if (a) a->_down = b;
616 if (b) b->_up = a;
617 }
620 void Region::addShape(ShapeRef *shape)
621 {
622 if (!centerRegion)
623 {
624 // Add new default region.
625 centerRegion = new Region();
626 printf("NEW %X\n", (int) centerRegion);
627 }
628 BBox bbox;
629 // Get bounding box for added shape.
630 shape->boundingBox(bbox);
631 printBBox("Add", bbox);
633 unsigned int shapeId = shape->id();
635 // Find starting point for overlap
636 Region *curr = centerRegion;
637 unsigned int pos = R_INSIDE;
638 while (!(curr->overlapCheck(bbox, pos)))
639 {
640 if (pos & R_LEFT)
641 {
642 curr = curr->_left;
643 }
644 else if (pos & R_RIGHT)
645 {
646 curr = curr->_right;
647 }
648 else if (pos & R_ABOVE)
649 {
650 curr = curr->_up;
651 }
652 else if (pos & R_BELOW)
653 {
654 curr = curr->_down;
655 }
656 }
658 curr->initialSplit(bbox, pos, shapeId);
659 centerRegion = curr;
660 }
663 void Region::removeShape(ShapeRef *shape)
664 {
665 const bool forMerge = true;
667 BBox bbox;
668 // Get bounding box for added shape.
669 shape->boundingBox(bbox);
670 printBBox("Remove", bbox);
672 unsigned int shapeId = shape->id();
674 Region *aboveTop = centerRegion->findRegion(bbox.a.y, R_HORI, forMerge);
675 Region *aboveBottom = aboveTop->findRegion(bbox.b.y, R_HORI, forMerge);
676 Region *leftOfLeft = aboveBottom->findRegion(bbox.a.x, R_VERT, forMerge);
677 Region *leftOfRight = leftOfLeft->findRegion(bbox.b.x, R_VERT, forMerge);
679 assert(aboveTop != NULL);
680 assert(aboveBottom != NULL);
681 assert(leftOfLeft != NULL);
682 assert(leftOfRight != NULL);
684 // Find Top Left.
685 Region *topLeft = leftOfLeft->_right;
686 while (topLeft->_bbox.a.y != aboveTop->_bbox.b.y)
687 {
688 topLeft = topLeft->_up;
689 }
691 // Find Bottom Right.
692 Region *botRight = leftOfRight;
693 while (botRight->_bbox.b.y != aboveBottom->_bbox.b.y)
694 {
695 botRight = botRight->_down;
696 }
698 // Clear blocking flag.
699 Region *curr = topLeft, *cptr = NULL;
700 while (curr->_bbox.b.y <= botRight->_bbox.b.y)
701 {
702 cptr = curr;
703 while (cptr->_bbox.b.x <= botRight->_bbox.b.x)
704 {
705 ShapeList& blocks = cptr->_blocks;
707 assert(std::find(blocks.begin(), blocks.end(), (int) shapeId) !=
708 blocks.end());
709 printf("%X - list %d remove %d\n", (int) cptr,
710 (int) blocks.size(), shapeId);
711 cptr->_blocks.remove((int) shapeId);
713 cptr = cptr->_right;
714 }
716 curr = curr->_down;
717 }
719 // These two are safe since they don't invalidate the pointers
720 // to the regions that are inside the shape.
721 if (aboveBottom->safeToMerge(R_HORI))
722 {
723 aboveBottom->merge(R_HORI);
724 }
725 if (leftOfRight->safeToMerge(R_VERT))
726 {
727 leftOfRight->merge(R_VERT);
728 }
730 // Be a bit more careful with these.
731 double leftX = leftOfLeft->_bbox.b.x;
732 if (aboveTop->safeToMerge(R_HORI))
733 {
734 aboveTop->merge(R_HORI);
735 }
736 // leftOfLeft may have been freed, so look for the new block at
737 // that position.
738 leftOfLeft = aboveTop->findRegion(leftX, R_VERT, forMerge);
739 assert(leftOfLeft);
740 if (leftOfLeft->safeToMerge(R_VERT))
741 {
742 leftOfLeft->merge(R_VERT);
743 }
744 }
747 bool Region::safeToMerge(unsigned int dir)
748 {
749 bool unsafe = false;
751 if (dir == R_HORI)
752 {
753 printf("safeToMerge? y = %.3f... ", _bbox.b.y);
754 unsafe |= unsafeToMerge(R_RIGHT);
755 if (_left) unsafe |= _left->unsafeToMerge(R_LEFT);
756 }
757 else if (dir == R_VERT)
758 {
759 printf("safeToMerge? x = %.3f... ", _bbox.b.x);
760 unsafe |= unsafeToMerge(R_DOWN);
761 if (_up) unsafe |= _up->unsafeToMerge(R_UP);
762 }
763 printf("%s.\n", (unsafe) ? "no" : "yes");
765 return !unsafe;
766 }
769 bool Region::unsafeToMerge(unsigned int dir)
770 {
771 bool unsafe = false;
773 if (dir & R_HORI)
774 {
775 // If they are not the same on both sides then we can merge.
776 if (_blocks != _down->_blocks)
777 {
778 printf("\n _blocks:\n ");
779 for (ShapeList::iterator i = _blocks.begin(); i != _blocks.end();
780 ++i)
781 {
782 printf("%d ", *i);
783 }
784 printf("\n _down->_blocks:\n ");
785 for (ShapeList::iterator i = _down->_blocks.begin();
786 i != _down->_blocks.end(); ++i)
787 {
788 printf("%d ", *i);
789 }
790 unsafe |= true;
791 printf("\n");
792 }
794 if ((dir == R_LEFT) && _left)
795 {
796 unsafe |= _left->unsafeToMerge(dir);
797 }
798 else if ((dir == R_RIGHT) && _right)
799 {
800 unsafe |= _right->unsafeToMerge(dir);
801 }
802 }
803 else if (dir & R_VERT)
804 {
805 if (_blocks != _right->_blocks)
806 {
807 printf("\n _blocks:\n ");
808 for (ShapeList::iterator i = _blocks.begin(); i != _blocks.end();
809 ++i)
810 {
811 printf("%d ", *i);
812 }
813 printf("\n _right->_blocks:\n ");
814 for (ShapeList::iterator i = _right->_blocks.begin();
815 i != _right->_blocks.end(); ++i)
816 {
817 printf("%d ", *i);
818 }
819 unsafe |= true;
820 printf("\n");
821 }
823 if ((dir == R_UP) && _up)
824 {
825 unsafe |= _up->unsafeToMerge(dir);
826 }
827 else if ((dir == R_DOWN) && _down)
828 {
829 unsafe |= _down->unsafeToMerge(dir);
830 }
831 }
832 return unsafe;
834 }
837 Region *Region::getTopLeftRegion(void)
838 {
839 Region *curr = centerRegion;
841 while (curr && (curr->_up || curr->_left))
842 {
843 if (curr->_up)
844 {
845 curr = curr->_up;
846 }
847 else
848 {
849 curr = curr->_left;
850 }
851 }
852 return curr;
853 }
856 }