1 ///////////////////////////////////////////////////////////////////////////////
2 // BSD 3-Clause License
3 //
4 // Copyright (c) 2019, Nefelus Inc
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 // * Redistributions of source code must retain the above copyright notice, this
11 // list of conditions and the following disclaimer.
12 //
13 // * Redistributions in binary form must reproduce the above copyright notice,
14 // this list of conditions and the following disclaimer in the documentation
15 // and/or other materials provided with the distribution.
16 //
17 // * Neither the name of the copyright holder nor the names of its
18 // contributors may be used to endorse or promote products derived from
19 // this software without specific prior written permission.
20 //
21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
25 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 // POSSIBILITY OF SUCH DAMAGE.
32
33 #pragma once
34
35 #include <vector>
36
37 #include "odb.h"
38
39 namespace odb {
40
41 #ifndef MIN
42 #define MIN(a, b) ((a) < (b) ? (a) : (b))
43 #endif
44
45 #ifndef MAX
46 #define MAX(a, b) ((a) > (b) ? (a) : (b))
47 #endif
48
49 class dbIStream;
50 class dbOStream;
51
52 class Point
53 {
54 int _x;
55 int _y;
56
57 public:
58 Point();
59 Point(const Point& p);
60 Point(int x, int y);
61 ~Point() = default;
62 Point& operator=(const Point& p);
63 bool operator==(const Point& p) const;
64 bool operator!=(const Point& p) const;
65 bool operator<(const Point& p) const;
66
67 int getX() const;
68 int getY() const;
69 void setX(int x);
70 void setY(int y);
71
72 void rotate90();
73 void rotate180();
74 void rotate270();
75
x()76 int& x() { return _x; }
y()77 int& y() { return _y; }
x()78 const int& x() const { return _x; }
y()79 const int& y() const { return _y; }
80
81 // compute cross product of the vectors <p0,p1> and <p0,p2>
82 //
83 // p2
84 // +
85 // ^
86 // |
87 // | crossProduct(p0,p1,p2) > 0
88 // |
89 // +------------>+
90 // p0 p1
91 //
92 // p1
93 // +
94 // ^
95 // |
96 // | crossProduct(p0,p1,p2) < 0
97 // |
98 // +------------>+
99 // p0 p2
100 //
101 // Returns 0 if the vectors are colinear
102 // Returns > 0 if the vectors rotate counter clockwise
103 // Returns < 0 if the vectors rotate clockwise
104 static int64 crossProduct(Point p0, Point p1, Point p2);
105
106 // compute the rotation direction of the vectors <p0,p1> and <p0,p2>
107 // Returns 0 if the vectors are colinear
108 // Returns 1 if the vectors rotate counter clockwise
109 // Returns -1 if the vectors rotate clockwise
110 //
111 enum Rotation
112 {
113 COLINEAR = 0,
114 CW = -1,
115 CCW = 1
116 };
117 static int rotation(Point p0, Point p1, Point p2);
118
119 // compute the square distance between two points
120 static uint64 squaredDistance(Point p0, Point p1);
121
122 // compute the manhattan distance between two points
123 static uint64 manhattanDistance(Point p0, Point p1);
124
125 friend dbIStream& operator>>(dbIStream& stream, Point& p);
126 friend dbOStream& operator<<(dbOStream& stream, const Point& p);
127 };
128
129 class GeomShape
130 {
131 public:
132 virtual uint dx() const = 0;
133 virtual uint dy() const = 0;
134 virtual int xMin() const = 0;
135 virtual int yMin() const = 0;
136 virtual int xMax() const = 0;
137 virtual int yMax() const = 0;
138 virtual std::vector<Point> getPoints() const = 0;
139 virtual ~GeomShape() = default;
140 };
141
142 /*
143 an Oct represents a 45-degree routing segment as 2 connected octagons
144
145 DIR:RIGHT
146 ---------
147 / \
148 / \
149 / high |
150 / |
151 / /
152 / /
153 / /
154 / /
155 / /
156 / /
157 | /
158 | low /
159 \ /
160 \ /
161 ---------
162
163 DIR: LEFT
164 ---------
165 / \
166 / \
167 | high \
168 | \
169 \ \
170 \ \
171 \ \
172 \ \
173 \ \
174 \ \
175 \ |
176 \ low |
177 \ /
178 \ /
179 ---------
180 each octagon follows the model:
181 (-B,A) --------- (B,A)
182 / \
183 / \ (A,B)
184 (-A,B)|<---width--->|
185 | center |
186 | |
187 (-A,-B)\ /(A,-B)
188 \ /
189 (-B,-A)---------(B,-A)
190
191 A = W/2
192 B = [ceiling(W/(sqrt(2) * M) ) * M] - A
193 where W is wire width and M is the manufacturing grid
194 */
195 class Oct : public GeomShape
196 {
197 Point center_high; // the center of the higher octagon
198 Point center_low; // the center of the lower octagon
199 int A; // A=W/2 (the x distance from the center to the right or left edge)
200 public:
201 enum OCT_DIR // The direction of the higher octagon relative to the lower
202 // octagon ( / is right while \ is left)
203 {
204 RIGHT,
205 LEFT,
206 UNKNOWN
207 };
208 Oct();
209 Oct(const Oct& r) = default;
210 Oct(const Point p1, const Point p2, int width);
211 Oct(int x1, int y1, int x2, int y2, int width);
212 ~Oct() = default;
213 Oct& operator=(const Oct& r) = default;
214 bool operator==(const Oct& r) const;
215 bool operator!=(const Oct& r) const { return !(r == *this); };
216 void init(const Point p1, const Point p2, int width);
217 OCT_DIR getDir() const;
218 Point getCenterHigh() const;
219 Point getCenterLow() const;
220 int getWidth() const;
221
dx()222 uint dx() const override
223 {
224 OCT_DIR D = getDir();
225 if (D == RIGHT)
226 return abs(center_high.getX() + A - center_low.getX() + A);
227 else if (D == LEFT)
228 return abs(center_low.getX() + A - center_high.getX() + A);
229 else
230 return 0;
231 };
dy()232 uint dy() const override
233 {
234 return abs(center_high.getY() + A - center_low.getY() + A);
235 };
xMin()236 int xMin() const override
237 {
238 OCT_DIR D = getDir();
239 if (D == RIGHT)
240 return center_low.getX() - A;
241 else if (D == LEFT)
242 return center_high.getX() - A;
243 else
244 return 0;
245 };
yMin()246 int yMin() const override { return center_low.getY() - A; };
xMax()247 int xMax() const override
248 {
249 OCT_DIR D = getDir();
250 if (D == RIGHT)
251 return center_high.getX() + A;
252 else if (D == LEFT)
253 return center_low.getX() + A;
254 else
255 return 0;
256 };
yMax()257 int yMax() const override { return center_high.getY() + A; };
getPoints()258 std::vector<Point> getPoints() const override
259 {
260 OCT_DIR dir = getDir();
261 int B = ceil((A * 2) / (sqrt(2))) - A;
262 std::vector<Point> points(9);
263 points[0] = points[8] = Point(center_low.getX() - B,
264 center_low.getY() - A); // low oct (-B,-A)
265 points[1] = Point(center_low.getX() + B,
266 center_low.getY() - A); // low oct (B,-A)
267 points[4] = Point(center_high.getX() + B,
268 center_high.getY() + A); // high oct (B,A)
269 points[5] = Point(center_high.getX() - B,
270 center_high.getY() + A); // high oct (-B,A)
271 if (dir == RIGHT) {
272 points[2] = Point(center_high.getX() + A,
273 center_high.getY() - B); // high oct (A,-B)
274 points[3] = Point(center_high.getX() + A,
275 center_high.getY() + B); // high oct (A,B)
276 points[6] = Point(center_low.getX() - A,
277 center_low.getY() + B); // low oct (-A,B)
278 points[7] = Point(center_low.getX() - A,
279 center_low.getY() - B); // low oct (-A,-B)
280 } else {
281 points[2] = Point(center_low.getX() + A,
282 center_low.getY() - B); // low oct (A,-B)
283 points[3] = Point(center_low.getX() + A,
284 center_low.getY() + B); // low oct (A,B)
285 points[6] = Point(center_high.getX() - A,
286 center_high.getY() + B); // high oct (-A,B)
287 points[7] = Point(center_high.getX() - A,
288 center_high.getY() - B); // high oct (-A,-B)
289 }
290 return points;
291 };
292 friend dbIStream& operator>>(dbIStream& stream, Oct& o);
293 friend dbOStream& operator<<(dbOStream& stream, const Oct& o);
294 };
295
296 class Rect : public GeomShape
297 {
298 int _xlo;
299 int _ylo;
300 int _xhi;
301 int _yhi;
302
303 public:
304 Rect();
305 Rect(const Rect& r) = default;
306 Rect(const Point p1, const Point p2);
307 Rect(int x1, int y1, int x2, int y2);
308 ~Rect() = default;
309 Rect& operator=(const Rect& r) = default;
310 bool operator==(const Rect& r) const;
311 bool operator!=(const Rect& r) const;
312 bool operator<(const Rect& r) const;
313 bool operator>(const Rect& r) const { return r < *this; }
314 bool operator<=(const Rect& r) const { return !(*this > r); }
315 bool operator>=(const Rect& r) const { return !(*this < r); }
316
317 // Reinitialize the rectangle
318 void init(int x1, int y1, int x2, int y2);
319
320 // Reinitialize the rectangle without normalization
321 void reset(int x1, int y1, int x2, int y2);
322
323 // Moves the rectangle to the new point.
324 void moveTo(int x, int y);
325
326 // Moves the rectangle by the offset amount
327 void moveDelta(int dx, int dy);
328
329 // Set the coordinates to: min(INT_MAX, INT_MAX) max(INT_MIN, INT_MIN)
330 void mergeInit();
331
332 // Indicates if the box has a negative width or height
333 bool isInverted();
334
335 uint minDXDY();
336 uint maxDXDY();
337 int getDir();
338
339 void set_xlo(int x1);
340 void set_xhi(int x1);
341 void set_ylo(int x1);
342 void set_yhi(int x1);
343
xMin()344 int xMin() const override { return _xlo; };
yMin()345 int yMin() const override { return _ylo; };
xMax()346 int xMax() const override { return _xhi; };
yMax()347 int yMax() const override { return _yhi; };
dx()348 uint dx() const override { return (uint) (_xhi - _xlo); };
dy()349 uint dy() const override { return (uint) (_yhi - _ylo); };
getPoints()350 std::vector<Point> getPoints() const override
351 {
352 std::vector<Point> points(5);
353 points[0] = points[4] = ll();
354 points[1] = lr();
355 points[2] = ur();
356 points[3] = ul();
357 return points;
358 };
359 Point ll() const;
360 Point ul() const;
361 Point ur() const;
362 Point lr() const;
363
364 // Returns the lower point (lower-left)
365 Point low() const;
366
367 // Returns the upper point (upper-right)
368 Point high() const;
369
370 // A point intersects any part of this rectangle.
371 bool intersects(const Point& p) const;
372
373 // A rectangle intersects any part of this rectangle.
374 bool intersects(const Rect& r) const;
375
376 // A point intersects the interior of this rectangle
377 bool overlaps(const Point& p) const;
378
379 // A rectangle intersects the interior of this rectangle
380 bool overlaps(const Rect& r) const;
381
382 // A rectangle is contained in the interior of this rectangle
383 bool contains(const Rect& r) const;
384
385 // A rectangle is completely contained in the interior of this rectangle,
386 bool inside(const Rect& r) const;
387
388 // Compute the union of these two rectangles.
389 void merge(const Rect& r, Rect& result);
390
391 void merge(GeomShape* s, Rect& result);
392
393 // Compute the union of these two rectangles. The result is stored in this
394 // rectangle.
395 void merge(const Rect& r);
396
397 void merge(GeomShape* s);
398
399 // Compute the intersection of these two rectangles.
400 void intersection(const Rect& r, Rect& result);
401
402 // Compute the intersection of these two rectangles.
403 Rect intersect(const Rect& r);
404
405 uint64 area();
406 uint64 margin();
407
408 void notice(const char* prefix = "");
409 void printf(FILE* fp, const char* prefix = "");
410 void print(const char* prefix = "");
411
412 friend dbIStream& operator>>(dbIStream& stream, Rect& r);
413 friend dbOStream& operator<<(dbOStream& stream, const Rect& r);
414 };
415
Point()416 inline Point::Point()
417 {
418 _x = 0;
419 _y = 0;
420 }
421
Point(const Point & p)422 inline Point::Point(const Point& p)
423 {
424 _x = p._x;
425 _y = p._y;
426 }
427
Point(int x,int y)428 inline Point::Point(int x, int y)
429 {
430 _x = x;
431 _y = y;
432 }
433
434 inline Point& Point::operator=(const Point& p)
435 {
436 _x = p._x;
437 _y = p._y;
438 return *this;
439 }
440
441 inline bool Point::operator==(const Point& p) const
442 {
443 return (_x == p._x) && (_y == p._y);
444 }
445
446 inline bool Point::operator!=(const Point& p) const
447 {
448 return (_x != p._x) || (_y != p._y);
449 }
450
getX()451 inline int Point::getX() const
452 {
453 return _x;
454 }
455
getY()456 inline int Point::getY() const
457 {
458 return _y;
459 }
460
setX(int x)461 inline void Point::setX(int x)
462 {
463 _x = x;
464 }
465
setY(int y)466 inline void Point::setY(int y)
467 {
468 _y = y;
469 }
470
rotate90()471 inline void Point::rotate90()
472 {
473 int xp = -_y;
474 int yp = _x;
475 _x = xp;
476 _y = yp;
477 }
478
rotate180()479 inline void Point::rotate180()
480 {
481 int xp = -_x;
482 int yp = -_y;
483 _x = xp;
484 _y = yp;
485 }
486
rotate270()487 inline void Point::rotate270()
488 {
489 int xp = _y;
490 int yp = -_x;
491 _x = xp;
492 _y = yp;
493 }
494
crossProduct(Point p0,Point p1,Point p2)495 inline int64 Point::crossProduct(Point p0, Point p1, Point p2)
496 {
497 // because the cross-product might overflow in an "int"
498 // 64-bit arithmetic is used here
499 int64 x0 = p0._x;
500 int64 x1 = p1._x;
501 int64 x2 = p2._x;
502 int64 y0 = p0._y;
503 int64 y1 = p1._y;
504 int64 y2 = p2._y;
505 return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);
506 }
507
rotation(Point p0,Point p1,Point p2)508 inline int Point::rotation(Point p0, Point p1, Point p2)
509 {
510 int64 cp = crossProduct(p0, p1, p2);
511 return (cp == 0 ? 0 : cp < 0 ? -1 : 1);
512 }
513
squaredDistance(Point p0,Point p1)514 inline uint64 Point::squaredDistance(Point p0, Point p1)
515 {
516 int64 x0 = p0._x;
517 int64 x1 = p1._x;
518 int64 dx = x1 - x0;
519 int64 y0 = p0._y;
520 int64 y1 = p1._y;
521 int64 dy = y1 - y0;
522 return (uint64) (dx * dx + dy * dy);
523 }
524
manhattanDistance(Point p0,Point p1)525 inline uint64 Point::manhattanDistance(Point p0, Point p1)
526 {
527 int64 x0 = p0._x;
528 int64 x1 = p1._x;
529 int64 dx = x1 - x0;
530 if (dx < 0)
531 dx = -dx;
532 int64 y0 = p0._y;
533 int64 y1 = p1._y;
534 int64 dy = y1 - y0;
535 if (dy < 0)
536 dy = -dy;
537 return (uint64) (dx + dy);
538 }
539
540 inline bool Point::operator<(const Point& rhs) const
541 {
542 if (_x < rhs._x)
543 return true;
544
545 if (_x > rhs._x)
546 return false;
547
548 return _y < rhs._y;
549 }
550
551 inline bool Rect::operator<(const Rect& rhs) const
552 {
553 if (_xlo < rhs._xlo)
554 return true;
555
556 if (_xlo > rhs._xlo)
557 return false;
558
559 if (_ylo < rhs._ylo)
560 return true;
561
562 if (_ylo > rhs._ylo)
563 return false;
564
565 if (_xhi < rhs._xhi)
566 return true;
567
568 if (_xhi > rhs._xhi)
569 return false;
570
571 return _yhi < rhs._yhi;
572 }
573
Rect()574 inline Rect::Rect()
575 {
576 _xlo = _ylo = _xhi = _yhi = 0;
577 }
578
Rect(int x1,int y1,int x2,int y2)579 inline Rect::Rect(int x1, int y1, int x2, int y2)
580 {
581 if (x1 < x2) {
582 _xlo = x1;
583 _xhi = x2;
584 } else {
585 _xlo = x2;
586 _xhi = x1;
587 }
588
589 if (y1 < y2) {
590 _ylo = y1;
591 _yhi = y2;
592 } else {
593 _ylo = y2;
594 _yhi = y1;
595 }
596 }
597
Rect(const Point p1,const Point p2)598 inline Rect::Rect(const Point p1, const Point p2)
599 {
600 int x1 = p1.getX();
601 int y1 = p1.getY();
602 int x2 = p2.getX();
603 int y2 = p2.getY();
604
605 if (x1 < x2) {
606 _xlo = x1;
607 _xhi = x2;
608 } else {
609 _xlo = x2;
610 _xhi = x1;
611 }
612
613 if (y1 < y2) {
614 _ylo = y1;
615 _yhi = y2;
616 } else {
617 _ylo = y2;
618 _yhi = y1;
619 }
620 }
621
set_xlo(int x1)622 inline void Rect::set_xlo(int x1)
623 {
624 _xlo = x1;
625 }
set_xhi(int x2)626 inline void Rect::set_xhi(int x2)
627 {
628 _xhi = x2;
629 }
set_ylo(int y1)630 inline void Rect::set_ylo(int y1)
631 {
632 _ylo = y1;
633 }
set_yhi(int y2)634 inline void Rect::set_yhi(int y2)
635 {
636 _yhi = y2;
637 }
reset(int x1,int y1,int x2,int y2)638 inline void Rect::reset(int x1, int y1, int x2, int y2)
639 {
640 _xlo = x1;
641 _xhi = x2;
642 _ylo = y1;
643 _yhi = y2;
644 }
645
init(int x1,int y1,int x2,int y2)646 inline void Rect::init(int x1, int y1, int x2, int y2)
647 {
648 if (x1 < x2) {
649 _xlo = x1;
650 _xhi = x2;
651 } else {
652 _xlo = x2;
653 _xhi = x1;
654 }
655
656 if (y1 < y2) {
657 _ylo = y1;
658 _yhi = y2;
659 } else {
660 _ylo = y2;
661 _yhi = y1;
662 }
663 }
664
665 inline bool Rect::operator==(const Rect& r) const
666 {
667 return (_xlo == r._xlo) && (_ylo == r._ylo) && (_xhi == r._xhi)
668 && (_yhi == r._yhi);
669 }
670
671 inline bool Rect::operator!=(const Rect& r) const
672 {
673 return (_xlo != r._xlo) || (_ylo != r._ylo) || (_xhi != r._xhi)
674 || (_yhi != r._yhi);
675 }
676
minDXDY()677 inline uint Rect::minDXDY()
678 {
679 uint DX = dx();
680 uint DY = dy();
681 if (DX < DY)
682 return DX;
683 else
684 return DY;
685 }
maxDXDY()686 inline uint Rect::maxDXDY()
687 {
688 uint DX = dx();
689 uint DY = dy();
690 if (DX > DY)
691 return DX;
692 else
693 return DY;
694 }
getDir()695 inline int Rect::getDir()
696 {
697 uint DX = dx();
698 uint DY = dy();
699 if (DX < DY)
700 return 0;
701 else if (DX > DY)
702 return 1;
703 else
704 return -1;
705 }
moveTo(int x,int y)706 inline void Rect::moveTo(int x, int y)
707 {
708 uint DX = dx();
709 uint DY = dy();
710 _xlo = x;
711 _ylo = y;
712 _xhi = x + DX;
713 _yhi = y + DY;
714 }
715
moveDelta(int dx,int dy)716 inline void Rect::moveDelta(int dx, int dy)
717 {
718 _xlo += dx;
719 _ylo += dy;
720 _xhi += dx;
721 _yhi += dy;
722 }
723
ll()724 inline Point Rect::ll() const
725 {
726 return Point(_xlo, _ylo);
727 }
ul()728 inline Point Rect::ul() const
729 {
730 return Point(_xlo, _yhi);
731 }
ur()732 inline Point Rect::ur() const
733 {
734 return Point(_xhi, _yhi);
735 }
lr()736 inline Point Rect::lr() const
737 {
738 return Point(_xhi, _ylo);
739 }
low()740 inline Point Rect::low() const
741 {
742 return Point(_xlo, _ylo);
743 }
high()744 inline Point Rect::high() const
745 {
746 return Point(_xhi, _yhi);
747 }
748
intersects(const Point & p)749 inline bool Rect::intersects(const Point& p) const
750 {
751 return !((p.getX() < _xlo) || (p.getX() > _xhi) || (p.getY() < _ylo)
752 || (p.getY() > _yhi));
753 }
754
intersects(const Rect & r)755 inline bool Rect::intersects(const Rect& r) const
756 {
757 return !((r._xhi < _xlo) || (r._xlo > _xhi) || (r._yhi < _ylo)
758 || (r._ylo > _yhi));
759 }
760
overlaps(const Point & p)761 inline bool Rect::overlaps(const Point& p) const
762 {
763 return !((p.getX() <= _xlo) || (p.getX() >= _xhi) || (p.getY() <= _ylo)
764 || (p.getY() >= _yhi));
765 }
766
overlaps(const Rect & r)767 inline bool Rect::overlaps(const Rect& r) const
768 {
769 return !((r._xhi <= _xlo) || (r._xlo >= _xhi) || (r._yhi <= _ylo)
770 || (r._ylo >= _yhi));
771 }
772
contains(const Rect & r)773 inline bool Rect::contains(const Rect& r) const
774 {
775 return (_xlo <= r._xlo) && (_ylo <= r._ylo) && (_xhi >= r._xhi)
776 && (_yhi >= r._yhi);
777 }
778
inside(const Rect & r)779 inline bool Rect::inside(const Rect& r) const
780 {
781 return (_xlo < r._xlo) && (_ylo < r._ylo) && (_xhi > r._xhi)
782 && (_yhi > r._yhi);
783 }
784
785 // Compute the union of these two rectangles.
merge(const Rect & r,Rect & result)786 inline void Rect::merge(const Rect& r, Rect& result)
787 {
788 result._xlo = MIN(_xlo, r._xlo);
789 result._ylo = MIN(_ylo, r._ylo);
790 result._xhi = MAX(_xhi, r._xhi);
791 result._yhi = MAX(_yhi, r._yhi);
792 }
merge(GeomShape * s,Rect & result)793 inline void Rect::merge(GeomShape* s, Rect& result)
794 {
795 result._xlo = MIN(_xlo, s->xMin());
796 result._ylo = MIN(_ylo, s->yMin());
797 result._xhi = MAX(_xhi, s->xMax());
798 result._yhi = MAX(_yhi, s->yMax());
799 }
800
801 // Compute the union of these two rectangles.
merge(const Rect & r)802 inline void Rect::merge(const Rect& r)
803 {
804 _xlo = MIN(_xlo, r._xlo);
805 _ylo = MIN(_ylo, r._ylo);
806 _xhi = MAX(_xhi, r._xhi);
807 _yhi = MAX(_yhi, r._yhi);
808 }
merge(GeomShape * s)809 inline void Rect::merge(GeomShape* s)
810 {
811 _xlo = MIN(_xlo, s->xMin());
812 _ylo = MIN(_ylo, s->yMin());
813 _xhi = MAX(_xhi, s->xMax());
814 _yhi = MAX(_yhi, s->yMax());
815 }
816
817 // Compute the intersection of these two rectangles.
intersection(const Rect & r,Rect & result)818 inline void Rect::intersection(const Rect& r, Rect& result)
819 {
820 if (!intersects(r)) {
821 result._xlo = 0;
822 result._ylo = 0;
823 result._xhi = 0;
824 result._yhi = 0;
825 } else {
826 result._xlo = MAX(_xlo, r._xlo);
827 result._ylo = MAX(_ylo, r._ylo);
828 result._xhi = MIN(_xhi, r._xhi);
829 result._yhi = MIN(_yhi, r._yhi);
830 }
831 }
832
833 // Compute the intersection of these two rectangles.
intersect(const Rect & r)834 inline Rect Rect::intersect(const Rect& r)
835 {
836 assert(intersects(r));
837 Rect result;
838 result._xlo = MAX(_xlo, r._xlo);
839 result._ylo = MAX(_ylo, r._ylo);
840 result._xhi = MIN(_xhi, r._xhi);
841 result._yhi = MIN(_yhi, r._yhi);
842 return result;
843 }
844
area()845 inline uint64 Rect::area()
846 {
847 uint64 a = dx();
848 uint64 b = dy();
849 return a * b;
850 }
851
margin()852 inline uint64 Rect::margin()
853 {
854 uint64 DX = dx();
855 uint64 DY = dy();
856 return DX + DX + DY + DY;
857 }
858
mergeInit()859 inline void Rect::mergeInit()
860 {
861 _xlo = INT_MAX;
862 _ylo = INT_MAX;
863 _xhi = INT_MIN;
864 _yhi = INT_MIN;
865 }
866
isInverted()867 inline bool Rect::isInverted()
868 {
869 return _xlo > _xhi || _ylo > _yhi;
870 }
871
notice(const char *)872 inline void Rect::notice(const char*)
873 {
874 ; // notice(0, "%s%12d %12d - %12d %12d\n", prefix, _xlo, _ylo, dx, dy);
875 }
printf(FILE * fp,const char * prefix)876 inline void Rect::printf(FILE* fp, const char* prefix)
877 {
878 fprintf(fp, "%s%12d %12d - %12d %12d\n", prefix, _xlo, _ylo, dx(), dy());
879 }
print(const char * prefix)880 inline void Rect::print(const char* prefix)
881 {
882 fprintf(stdout, "%s%12d %12d - %12d %12d\n", prefix, _xlo, _ylo, dx(), dy());
883 }
884
Oct()885 inline Oct::Oct()
886 {
887 A = 0;
888 }
889
Oct(const Point p1,const Point p2,int width)890 inline Oct::Oct(const Point p1, const Point p2, int width)
891 {
892 init(p1, p2, width);
893 }
894
Oct(int x1,int y1,int x2,int y2,int width)895 inline Oct::Oct(int x1, int y1, int x2, int y2, int width)
896 {
897 Point p1(x1, y1);
898 Point p2(x2, y2);
899 init(p1, p2, width);
900 }
901
902 inline bool Oct::operator==(const Oct& r) const
903 {
904 if (center_low != r.center_low)
905 return false;
906 if (center_high != r.center_high)
907 return false;
908 if (A != r.A)
909 return false;
910 return true;
911 }
912
init(const Point p1,const Point p2,int width)913 inline void Oct::init(const Point p1, const Point p2, int width)
914 {
915 if (p1.getY() > p2.getY()) {
916 center_high = p1;
917 center_low = p2;
918 } else {
919 center_high = p2;
920 center_low = p1;
921 }
922 A = width / 2;
923 }
924
getDir()925 inline Oct::OCT_DIR Oct::getDir() const
926 {
927 if (center_low == center_high)
928 return UNKNOWN;
929 if (center_high.getX() > center_low.getX())
930 return RIGHT;
931 return LEFT;
932 }
933
getCenterHigh()934 inline Point Oct::getCenterHigh() const
935 {
936 return center_high;
937 }
getCenterLow()938 inline Point Oct::getCenterLow() const
939 {
940 return center_low;
941 }
getWidth()942 inline int Oct::getWidth() const
943 {
944 return A * 2;
945 }
946 } // namespace odb
947