1 /** 2 * N-dimensional half-open interval [a, b[. 3 * 4 * Copyright: Copyright Guillaume Piolat 2015-2021. 5 * Copyright Ahmet Sait 2021. 6 * Copyright Ryan Roden-Corrent 2016. 7 * Copyright Nathan Sashihara 2018. 8 * Copyright Colden Cullen 2014. 9 * 10 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) 11 */ 12 module dplug.math.box; 13 14 import std.math, 15 std.traits, 16 std.conv, 17 std.string; 18 19 import dplug.math.vector; 20 21 /// N-dimensional half-open interval [a, b[. 22 struct Box(T, int N) 23 { 24 static assert(N > 0); 25 26 public 27 { 28 alias bound_t = Vector!(T, N); 29 30 bound_t min; // not enforced, the box can have negative volume 31 bound_t max; 32 33 /// Construct a box which extends between 2 points. 34 /// Boundaries: min is inside the box, max is just outside. 35 @nogc this(bound_t min_, bound_t max_) pure nothrow 36 { 37 min = min_; 38 max = max_; 39 } 40 41 static if (N == 1) 42 { 43 @nogc this(T min_, T max_) pure nothrow 44 { 45 min.x = min_; 46 max.x = max_; 47 } 48 } 49 50 static if (N == 2) 51 { 52 @nogc this(T min_x, T min_y, T max_x, T max_y) pure nothrow 53 { 54 min = bound_t(min_x, min_y); 55 max = bound_t(max_x, max_y); 56 } 57 } 58 59 static if (N == 3) 60 { 61 @nogc this(T min_x, T min_y, T min_z, T max_x, T max_y, T max_z) pure nothrow 62 { 63 min = bound_t(min_x, min_y, min_z); 64 max = bound_t(max_x, max_y, max_z); 65 } 66 } 67 68 @property 69 { 70 /// Returns: Dimensions of the box. 71 @nogc bound_t size() pure const nothrow 72 { 73 return max - min; 74 } 75 76 /// Sets size of the box assuming min point is the pivot. 77 /// Returns: Dimensions of the box. 78 @nogc bound_t size(bound_t value) pure nothrow 79 { 80 max = min + value; 81 return value; 82 } 83 84 /// Returns: Center of the box. 85 @nogc bound_t center() pure const nothrow 86 { 87 return (min + max) / 2; 88 } 89 90 static if (N >= 1) 91 { 92 /// Returns: Width of the box, always applicable. 93 @nogc T width() pure const nothrow @property 94 { 95 return max.x - min.x; 96 } 97 98 /// Sets width of the box assuming min point is the pivot. 99 /// Returns: Width of the box, always applicable. 100 @nogc T width(T value) pure nothrow @property 101 { 102 max.x = min.x + value; 103 return value; 104 } 105 } 106 107 static if (N >= 2) 108 { 109 /// Returns: Height of the box, if applicable. 110 @nogc T height() pure const nothrow @property 111 { 112 return max.y - min.y; 113 } 114 115 /// Sets height of the box assuming min point is the pivot. 116 /// Returns: Height of the box, if applicable. 117 @nogc T height(T value) pure nothrow @property 118 { 119 max.y = min.y + value; 120 return value; 121 } 122 } 123 124 static if (N >= 3) 125 { 126 /// Returns: Depth of the box, if applicable. 127 @nogc T depth() pure const nothrow @property 128 { 129 return max.z - min.z; 130 } 131 132 /// Sets depth of the box assuming min point is the pivot. 133 /// Returns: Depth of the box, if applicable. 134 @nogc T depth(T value) pure nothrow @property 135 { 136 max.z = min.z + value; 137 return value; 138 } 139 } 140 141 /// Returns: Signed volume of the box. 142 @nogc T volume() pure const nothrow 143 { 144 T res = 1; 145 bound_t size = size(); 146 for(int i = 0; i < N; ++i) 147 res *= size[i]; 148 return res; 149 } 150 151 /// Returns: true if empty. 152 @nogc bool empty() pure const nothrow 153 { 154 bound_t size = size(); 155 mixin(generateLoopCode!("if (min[@] == max[@]) return true;", N)()); 156 return false; 157 } 158 } 159 160 /// Returns: true if it contains point. 161 @nogc bool contains(bound_t point) pure const nothrow 162 { 163 assert(isSorted()); 164 for(int i = 0; i < N; ++i) 165 if ( !(point[i] >= min[i] && point[i] < max[i]) ) 166 return false; 167 168 return true; 169 } 170 171 static if (N >= 2) 172 { 173 /// Returns: true if it contains point `x`, `y`. 174 @nogc bool contains(T x, T y) pure const nothrow 175 { 176 assert(isSorted()); 177 if ( !(x >= min.x && x < max.x) ) 178 return false; 179 if ( !(y >= min.y && y < max.y) ) 180 return false; 181 return true; 182 } 183 } 184 185 static if (N >= 3) 186 { 187 /// Returns: true if it contains point `x`, `y`, `z`. 188 @nogc bool contains(T x, T y, T z) pure const nothrow 189 { 190 assert(isSorted()); 191 if ( !(x >= min.x && x < max.x) ) 192 return false; 193 if ( !(y >= min.y && y < max.y) ) 194 return false; 195 if ( !(z >= min.z && z < max.z) ) 196 return false; 197 return true; 198 } 199 } 200 201 /// Returns: true if it contains box other. 202 @nogc bool contains(Box other) pure const nothrow 203 { 204 assert(isSorted()); 205 assert(other.isSorted()); 206 207 mixin(generateLoopCode!("if ( (other.min[@] < min[@]) || (other.max[@] > max[@]) ) return false;", N)()); 208 return true; 209 } 210 211 /// Euclidean squared distance from a point. 212 /// See_also: Numerical Recipes Third Edition (2007) 213 @nogc real squaredDistance(bound_t point) pure const nothrow 214 { 215 assert(isSorted()); 216 real distanceSquared = 0; 217 for (int i = 0; i < N; ++i) 218 { 219 if (point[i] < min[i]) 220 distanceSquared += (point[i] - min[i]) ^^ 2; 221 222 if (point[i] > max[i]) 223 distanceSquared += (point[i] - max[i]) ^^ 2; 224 } 225 return distanceSquared; 226 } 227 228 /// Euclidean distance from a point. 229 /// See_also: squaredDistance. 230 @nogc real distance(bound_t point) pure const nothrow 231 { 232 return sqrt(squaredDistance(point)); 233 } 234 235 /// Euclidean squared distance from another box. 236 /// See_also: Numerical Recipes Third Edition (2007) 237 @nogc real squaredDistance(Box o) pure const nothrow 238 { 239 assert(isSorted()); 240 assert(o.isSorted()); 241 real distanceSquared = 0; 242 for (int i = 0; i < N; ++i) 243 { 244 if (o.max[i] < min[i]) 245 distanceSquared += (o.max[i] - min[i]) ^^ 2; 246 247 if (o.min[i] > max[i]) 248 distanceSquared += (o.min[i] - max[i]) ^^ 2; 249 } 250 return distanceSquared; 251 } 252 253 /// Euclidean distance from another box. 254 /// See_also: squaredDistance. 255 @nogc real distance(Box o) pure const nothrow 256 { 257 return sqrt(squaredDistance(o)); 258 } 259 260 /// Assumes sorted boxes. 261 /// This function deals with empty boxes correctly. 262 /// Returns: Intersection of two boxes. 263 @nogc Box intersection(Box o) pure const nothrow 264 { 265 assert(isSorted()); 266 assert(o.isSorted()); 267 268 // Return an empty box if one of the boxes is empty 269 if (empty()) 270 return this; 271 272 if (o.empty()) 273 return o; 274 275 Box result = void; 276 for (int i = 0; i < N; ++i) 277 { 278 T maxOfMins = (min.v[i] > o.min.v[i]) ? min.v[i] : o.min.v[i]; 279 T minOfMaxs = (max.v[i] < o.max.v[i]) ? max.v[i] : o.max.v[i]; 280 result.min.v[i] = maxOfMins; 281 result.max.v[i] = minOfMaxs >= maxOfMins ? minOfMaxs : maxOfMins; 282 } 283 return result; 284 } 285 286 /// Assumes sorted boxes. 287 /// This function deals with empty boxes correctly. 288 /// Returns: Intersection of two boxes. 289 @nogc bool intersects(Box other) pure const nothrow 290 { 291 Box inter = this.intersection(other); 292 return inter.isSorted() && !inter.empty(); 293 } 294 295 /// Extends the area of this Box. 296 @nogc Box grow(bound_t space) pure const nothrow 297 { 298 Box res = this; 299 res.min -= space; 300 res.max += space; 301 return res; 302 } 303 304 /// Shrink the area of this Box. The box might became unsorted. 305 @nogc Box shrink(bound_t space) pure const nothrow 306 { 307 return grow(-space); 308 } 309 310 /// Extends the area of this Box. 311 @nogc Box grow(T space) pure const nothrow 312 { 313 return grow(bound_t(space)); 314 } 315 316 /// Translate this Box. 317 @nogc Box translate(bound_t offset) pure const nothrow 318 { 319 return Box(min + offset, max + offset); 320 } 321 322 /// Scale the box by factor `scale`, and round the result to integer if needed. 323 @nogc Box scaleByFactor(float scale) const nothrow 324 { 325 Box res; 326 static if (isFloatingPoint!T) 327 { 328 res.min.x = min.x * scale; 329 res.min.y = min.y * scale; 330 res.max.x = max.x * scale; 331 res.max.y = max.y * scale; 332 } 333 else 334 { 335 res.min.x = cast(T)( round(min.x * scale) ); 336 res.min.y = cast(T)( round(min.y * scale) ); 337 res.max.x = cast(T)( round(max.x * scale) ); 338 res.max.y = cast(T)( round(max.y * scale) ); 339 } 340 return res; 341 } 342 343 static if (N == 2) // useful for UI that have horizontal and vertical scale 344 { 345 /// Scale the box by factor `scaleX` horizontally and `scaleY` vetically. 346 /// Round the result to integer if needed. 347 @nogc Box scaleByFactor(float scaleX, float scaleY) const nothrow 348 { 349 Box res; 350 static if (isFloatingPoint!T) 351 { 352 res.min.x = min.x * scaleX; 353 res.min.y = min.y * scaleY; 354 res.max.x = max.x * scaleX; 355 res.max.y = max.y * scaleY; 356 } 357 else 358 { 359 res.min.x = cast(T)( round(min.x * scaleX) ); 360 res.min.y = cast(T)( round(min.y * scaleY) ); 361 res.max.x = cast(T)( round(max.x * scaleX) ); 362 res.max.y = cast(T)( round(max.y * scaleY) ); 363 } 364 return res; 365 } 366 } 367 368 static if (N >= 2) 369 { 370 /// Translate this Box by `x`, `y`. 371 @nogc Box translate(T x, T y) pure const nothrow 372 { 373 Box res = this; 374 res.min.x += x; 375 res.min.y += y; 376 res.max.x += x; 377 res.max.y += y; 378 return res; 379 } 380 } 381 382 static if (N >= 3) 383 { 384 /// Translate this Box by `x`, `y`. 385 @nogc Box translate(T x, T y, T z) pure const nothrow 386 { 387 Box res = this; 388 res.min.x += x; 389 res.min.y += y; 390 res.min.z += z; 391 res.max.x += x; 392 res.max.y += y; 393 res.max.z += z; 394 return res; 395 } 396 } 397 398 /// Shrinks the area of this Box. 399 /// Returns: Shrinked box. 400 @nogc Box shrink(T space) pure const nothrow 401 { 402 return shrink(bound_t(space)); 403 } 404 405 /// Expands the box to include point. 406 /// Returns: Expanded box. 407 @nogc Box expand(bound_t point) pure const nothrow 408 { 409 import vector = dplug.math.vector; 410 return Box(vector.minByElem(min, point), vector.maxByElem(max, point)); 411 } 412 413 /// Expands the box to include another box. 414 /// This function deals with empty boxes correctly. 415 /// Returns: Expanded box. 416 @nogc Box expand(Box other) pure const nothrow 417 { 418 assert(isSorted()); 419 assert(other.isSorted()); 420 421 // handle empty boxes 422 if (empty()) 423 return other; 424 if (other.empty()) 425 return this; 426 427 Box result = void; 428 for (int i = 0; i < N; ++i) 429 { 430 T minOfMins = (min.v[i] < other.min.v[i]) ? min.v[i] : other.min.v[i]; 431 T maxOfMaxs = (max.v[i] > other.max.v[i]) ? max.v[i] : other.max.v[i]; 432 result.min.v[i] = minOfMins; 433 result.max.v[i] = maxOfMaxs; 434 } 435 return result; 436 } 437 438 /// Returns: true if each dimension of the box is >= 0. 439 @nogc bool isSorted() pure const nothrow 440 { 441 for(int i = 0; i < N; ++i) 442 { 443 if (min[i] > max[i]) 444 return false; 445 } 446 return true; 447 } 448 449 /// Returns: Absolute value of the Box to ensure each dimension of the 450 /// box is >= 0. 451 @nogc Box abs() pure const nothrow 452 { 453 Box!(T, N) s = this; 454 for (int i = 0; i < N; ++i) 455 { 456 if (s.min.v[i] > s.max.v[i]) 457 { 458 T tmp = s.min.v[i]; 459 s.min.v[i] = s.max.v[i]; 460 s.max.v[i] = tmp; 461 } 462 } 463 return s; 464 } 465 466 /// Assign with another box. 467 @nogc ref Box opAssign(U)(U x) nothrow if (isBox!U) 468 { 469 static if(is(U.element_t : T)) 470 { 471 static if(U._size == _size) 472 { 473 min = x.min; 474 max = x.max; 475 } 476 else 477 { 478 static assert(false, "no conversion between boxes with different dimensions"); 479 } 480 } 481 else 482 { 483 static assert(false, "no conversion from " ~ U.element_t.stringof ~ " to " ~ element_t.stringof); 484 } 485 return this; 486 } 487 488 /// Returns: true if comparing equal boxes. 489 @nogc bool opEquals(U)(U other) pure const nothrow if (is(U : Box)) 490 { 491 return (min == other.min) && (max == other.max); 492 } 493 494 /// Cast to other box types. 495 @nogc U opCast(U)() pure const nothrow if (isBox!U) 496 { 497 U b = void; 498 for(int i = 0; i < N; ++i) 499 { 500 b.min[i] = cast(U.element_t)(min[i]); 501 b.max[i] = cast(U.element_t)(max[i]); 502 } 503 return b; // return a box where each element has been casted 504 } 505 506 static if (N == 2) 507 { 508 /// Helper function to create rectangle with a given point, width and height. 509 static @nogc Box rectangle(T x, T y, T width, T height) pure nothrow 510 { 511 return Box(x, y, x + width, y + height); 512 } 513 } 514 } 515 516 private 517 { 518 enum _size = N; 519 alias T element_t; 520 } 521 } 522 523 /// Instanciate to use a 2D box. 524 template box2(T) 525 { 526 alias Box!(T, 2) box2; 527 } 528 529 /// Instanciate to use a 3D box. 530 template box3(T) 531 { 532 alias Box!(T, 3) box3; 533 } 534 535 536 alias box2!int box2i; /// 2D box with integer coordinates. 537 alias box3!int box3i; /// 3D box with integer coordinates. 538 alias box2!float box2f; /// 2D box with float coordinates. 539 alias box3!float box3f; /// 3D box with float coordinates. 540 alias box2!double box2d; /// 2D box with double coordinates. 541 alias box3!double box3d; /// 3D box with double coordinates. 542 543 /// Returns: A 2D rectangle with point `x`,`y`, `width` and `height`. 544 box2i rectangle(int x, int y, int width, int height) pure nothrow @nogc 545 { 546 return box2i(x, y, x + width, y + height); 547 } 548 549 /// Returns: A 2D rectangle with point `x`,`y`, `width` and `height`. 550 box2f rectanglef(float x, float y, float width, float height) pure nothrow @nogc 551 { 552 return box2f(x, y, x + width, y + height); 553 } 554 555 /// Returns: A 2D rectangle with point `x`,`y`, `width` and `height`. 556 box2d rectangled(double x, double y, double width, double height) pure nothrow @nogc 557 { 558 return box2d(x, y, x + width, y + height); 559 } 560 561 562 unittest 563 { 564 box2i a = box2i(1, 2, 3, 4); 565 assert(a.width == 2); 566 assert(a.height == 2); 567 assert(a.volume == 4); 568 box2i b = box2i(vec2i(1, 2), vec2i(3, 4)); 569 assert(a == b); 570 571 box3i q = box3i(-3, -2, -1, 0, 1, 2); 572 q.bound_t s = q.bound_t(11, 17, 19); 573 q.bound_t q_min = q.min; 574 assert((q.size = s) == s); 575 assert(q.size == s); 576 assert(q.min == q_min); 577 assert(q.max == q.min + s); 578 assert(q.max - q.min == s); 579 580 assert((q.width = s.z) == s.z); 581 assert(q.width == s.z); 582 assert(q.min.x == q_min.x); 583 assert(q.max.x == q.min.x + s.z); 584 assert(q.max.x - q.min.x == s.z); 585 586 assert((q.height = s.y) == s.y); 587 assert(q.height == s.y); 588 assert(q.min.y == q_min.y); 589 assert(q.max.y == q.min.y + s.y); 590 assert(q.max.y - q.min.y == s.y); 591 592 assert((q.depth = s.x) == s.x); 593 assert(q.depth == s.x); 594 assert(q.min.z == q_min.z); 595 assert(q.max.z == q.min.z + s.x); 596 assert(q.max.z - q.min.z == s.x); 597 598 assert(q.size == s.zyx); 599 600 box3i n = box3i(2, 1, 0, -1, -2, -3); 601 assert(n.abs == box3i(-1, -2, -3, 2, 1, 0)); 602 603 box2f bf = cast(box2f)b; 604 assert(bf == box2f(1.0f, 2.0f, 3.0f, 4.0f)); 605 606 box3f qf = box3f(-0, 1f, 2.5f, 3.25f, 5.125f, 7.0625f); 607 qf.bound_t sf = qf.bound_t(-11.5f, -17.25f, -19.125f); 608 qf.bound_t qf_min = qf.min; 609 assert((qf.size = sf) == sf); 610 assert(qf.size == sf); 611 assert(qf.min == qf_min); 612 assert(qf.max == qf.min + sf); 613 assert(qf.max - qf.min == sf); 614 615 assert((qf.width = sf.z) == sf.z); 616 assert(qf.width == sf.z); 617 assert(qf.min.x == qf_min.x); 618 assert(qf.max.x == qf.min.x + sf.z); 619 assert(qf.max.x - qf.min.x == sf.z); 620 621 assert((qf.height = sf.y) == sf.y); 622 assert(qf.height == sf.y); 623 assert(qf.min.y == qf_min.y); 624 assert(qf.max.y == qf.min.y + sf.y); 625 assert(qf.max.y - qf.min.y == sf.y); 626 627 assert((qf.depth = sf.x) == sf.x); 628 assert(qf.depth == sf.x); 629 assert(qf.min.z == qf_min.z); 630 assert(qf.max.z == qf.min.z + sf.x); 631 assert(qf.max.z - qf.min.z == sf.x); 632 633 assert(qf.size == sf.zyx); 634 635 box2i c = box2i(0, 0, 1,1); 636 assert(c.translate(vec2i(3, 3)) == box2i(3, 3, 4, 4)); 637 assert(c.translate(3, 3) == box2i(3, 3, 4, 4)); 638 assert(c.contains(vec2i(0, 0))); 639 assert(c.contains(0, 0)); 640 assert(!c.contains(vec2i(1, 1))); 641 assert(!c.contains(1, 1)); 642 assert(b.contains(b)); 643 box2i d = c.expand(vec2i(3, 3)); 644 assert(d.contains(vec2i(2, 2))); 645 646 assert(d == d.expand(d)); 647 648 assert(!box2i(0, 0, 4, 4).contains(box2i(2, 2, 6, 6))); 649 650 assert(box2f(0, 0, 0, 0).empty()); 651 assert(!box2f(0, 2, 1, 1).empty()); 652 assert(!box2f(0, 0, 1, 1).empty()); 653 654 assert(box2i(260, 100, 360, 200).intersection(box2i(100, 100, 200, 200)).empty()); 655 656 // union with empty box is identity 657 assert(a.expand(box2i(10, 4, 10, 6)) == a); 658 659 // intersection with empty box is empty 660 assert(a.intersection(box2i(10, 4, 10, 6)).empty); 661 662 assert(box2i.rectangle(1, 2, 3, 4) == box2i(1, 2, 4, 6)); 663 assert(rectangle(1, 2, 3, 4) == box2i(1, 2, 4, 6)); 664 assert(rectanglef(1, 2, 3, 4) == box2f(1, 2, 4, 6)); 665 assert(rectangled(1, 2, 3, 4) == box2d(1, 2, 4, 6)); 666 667 assert(rectangle(10, 10, 20, 20).scaleByFactor(1.5f) == rectangle(15, 15, 30, 30)); 668 assert(rectangle(10, 10, 20, 20).scaleByFactor(1.5f, 2.0f) == rectangle(15, 20, 30, 40)); 669 } 670 671 /// True if `T` is a kind of Box 672 enum isBox(T) = is(T : Box!U, U...); 673 674 unittest 675 { 676 static assert( isBox!box2f); 677 static assert( isBox!box3d); 678 static assert( isBox!(Box!(real, 2))); 679 static assert(!isBox!vec2f); 680 } 681 682 /// Get the numeric type used to measure a box's dimensions. 683 alias DimensionType(T : Box!U, U...) = U[0]; 684 685 /// 686 unittest 687 { 688 static assert(is(DimensionType!box2f == float)); 689 static assert(is(DimensionType!box3d == double)); 690 } 691 692 private 693 { 694 static string generateLoopCode(string formatString, int N)() pure nothrow 695 { 696 string result; 697 for (int i = 0; i < N; ++i) 698 { 699 string index = ctIntToString(i); 700 // replace all @ by indices 701 result ~= formatString.replace("@", index); 702 } 703 return result; 704 } 705 706 // Speed-up CTFE conversions 707 static string ctIntToString(int n) pure nothrow 708 { 709 static immutable string[16] table = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]; 710 if (n < 10) 711 return table[n]; 712 else 713 return to!string(n); 714 } 715 }