1 module gfm.math.box; 2 3 import std.math, 4 std.traits; 5 6 import gfm.math.vector, 7 gfm.math.funcs; 8 9 static if( __VERSION__ < 2066 ) private enum nogc = 1; 10 11 /// N-dimensional half-open interval [a, b[. 12 align(1) struct Box(T, int N) 13 { 14 align(1): 15 static assert(N > 0); 16 17 public 18 { 19 alias Vector!(T, N) bound_t; 20 21 bound_t min; // not enforced, the box can have negative volume 22 bound_t max; 23 24 /// Construct a box which extends between 2 points. 25 /// Boundaries: min is inside the box, max is just outside. 26 @nogc this(bound_t min_, bound_t max_) pure nothrow 27 { 28 min = min_; 29 max = max_; 30 } 31 32 static if (N == 1) 33 { 34 @nogc this(T min_, T max_) pure nothrow 35 { 36 min.x = min_; 37 max.x = max_; 38 } 39 } 40 41 static if (N == 2) 42 { 43 @nogc this(T min_x, T min_y, T max_x, T max_y) pure nothrow 44 { 45 min = bound_t(min_x, min_y); 46 max = bound_t(max_x, max_y); 47 } 48 } 49 50 static if (N == 3) 51 { 52 @nogc this(T min_x, T min_y, T min_z, T max_x, T max_y, T max_z) pure nothrow 53 { 54 min = bound_t(min_x, min_y, min_z); 55 max = bound_t(max_x, max_y, max_z); 56 } 57 } 58 59 60 @property 61 { 62 /// Returns: Dimensions of the box. 63 @nogc bound_t size() pure const nothrow 64 { 65 return max - min; 66 } 67 68 /// Returns: Center of the box. 69 @nogc bound_t center() pure const nothrow 70 { 71 return (min + max) / 2; 72 } 73 74 /// Returns: Width of the box, always applicable. 75 static if (N >= 1) 76 @nogc T width() pure const nothrow @property 77 { 78 return max.x - min.x; 79 } 80 81 /// Returns: Height of the box, if applicable. 82 static if (N >= 2) 83 @nogc T height() pure const nothrow @property 84 { 85 return max.y - min.y; 86 } 87 88 /// Returns: Depth of the box, if applicable. 89 static if (N >= 3) 90 @nogc T depth() pure const nothrow @property 91 { 92 return max.z - min.z; 93 } 94 95 /// Returns: Signed volume of the box. 96 @nogc T volume() pure const nothrow 97 { 98 T res = 1; 99 bound_t size = size(); 100 for(int i = 0; i < N; ++i) 101 res *= size[i]; 102 return res; 103 } 104 } 105 106 /// Returns: true if it contains point. 107 @nogc bool contains(bound_t point) pure const nothrow 108 { 109 assert(isSorted()); 110 for(int i = 0; i < N; ++i) 111 if ( !(point[i] >= min[i] && point[i] < max[i]) ) 112 return false; 113 114 return true; 115 } 116 117 /// Returns: true if it contains box other. 118 @nogc bool contains(Box other) pure const nothrow 119 { 120 assert(isSorted()); 121 assert(other.isSorted()); 122 123 for(int i = 0; i < N; ++i) 124 if (other.min[i] >= max[i] || other.max[i] < min[i]) 125 return false; 126 return true; 127 } 128 129 /// Euclidean squared distance from a point. 130 /// See_also: Numerical Recipes Third Edition (2007) 131 @nogc double squaredDistance(bound_t point) pure const nothrow 132 { 133 assert(isSorted()); 134 double distanceSquared = 0; 135 for (int i = 0; i < N; ++i) 136 { 137 if (point[i] < min[i]) 138 distanceSquared += (point[i] - min[i]) ^^ 2; 139 140 if (point[i] > max[i]) 141 distanceSquared += (point[i] - max[i]) ^^ 2; 142 } 143 return distanceSquared; 144 } 145 146 /// Euclidean distance from a point. 147 /// See_also: squaredDistance. 148 @nogc double distance(bound_t point) pure const nothrow 149 { 150 return sqrt(squaredDistance(point)); 151 } 152 153 /// Euclidean squared distance from another box. 154 /// See_also: Numerical Recipes Third Edition (2007) 155 @nogc double squaredDistance(Box o) pure const nothrow 156 { 157 assert(isSorted()); 158 assert(o.isSorted()); 159 double distanceSquared = 0; 160 for (int i = 0; i < N; ++i) 161 { 162 if (o.max[i] < min[i]) 163 distanceSquared += (o.max[i] - min[i]) ^^ 2; 164 165 if (o.min[i] > max[i]) 166 distanceSquared += (o.min[i] - max[i]) ^^ 2; 167 } 168 return distanceSquared; 169 } 170 171 /// Euclidean distance from another box. 172 /// See_also: squaredDistance. 173 @nogc double distance(Box o) pure const nothrow 174 { 175 return sqrt(squaredDistance(o)); 176 } 177 178 /// Assumes sorted boxes. 179 /// Returns: Intersection of two boxes. 180 @nogc Box intersection(Box o) pure const nothrow 181 { 182 assert(isSorted()); 183 assert(o.isSorted()); 184 Box result; 185 for (int i = 0; i < N; ++i) 186 { 187 T maxOfMins = (min.v[i] > o.min.v[i]) ? min.v[i] : o.min.v[i]; 188 T minOfMaxs = (max.v[i] < o.max.v[i]) ? max.v[i] : o.max.v[i]; 189 result.min.v[i] = maxOfMins; 190 result.max.v[i] = minOfMaxs; 191 } 192 return result; 193 } 194 195 /// Assumes sorted boxes. 196 /// Returns: true if boxes overlap. 197 bool intersects(Box other) 198 { 199 Box inter = this.intersection(other); 200 return inter.isSorted() && inter.volume() != 0; 201 } 202 203 /// Extends the area of this Box. 204 @nogc Box grow(bound_t space) pure const nothrow 205 { 206 Box res = this; 207 res.min -= space; 208 res.max += space; 209 return res; 210 } 211 212 /// Shrink the area of this Box. The box might became unsorted. 213 @nogc Box shrink(bound_t space) pure const nothrow 214 { 215 return grow(-space); 216 } 217 218 /// Extends the area of this Box. 219 @nogc Box grow(T space) pure const nothrow 220 { 221 return grow(bound_t(space)); 222 } 223 224 /// Shrink the area of this Box. 225 @nogc Box shrink(T space) pure const nothrow 226 { 227 return shrink(bound_t(space)); 228 } 229 230 /// Expand the box to include point. 231 @nogc Box expand(bound_t point) pure const nothrow 232 { 233 import vector = gfm.math.vector; 234 return Box(vector.min(min, point), vector.max(max, point)); 235 } 236 237 /// Returns: true if each dimension of the box is >= 0. 238 @nogc bool isSorted() pure const nothrow 239 { 240 for(int i = 0; i < N; ++i) 241 { 242 if (min[i] > max[i]) 243 return false; 244 } 245 return true; 246 } 247 248 /// Assign with another box. 249 @nogc ref Box opAssign(U)(U x) nothrow if (is(typeof(x.isBox))) 250 { 251 static if(is(U.element_t : T)) 252 { 253 static if(U._size == _size) 254 { 255 min = x.min; 256 max = x.max; 257 } 258 else 259 { 260 static assert(false, "no conversion between boxes with different dimensions"); 261 } 262 } 263 else 264 { 265 static assert(false, Format!("no conversion from %s to %s", U.element_t.stringof, element_t.stringof)); 266 } 267 return this; 268 } 269 270 /// Returns: true if comparing equal boxes. 271 @nogc bool opEquals(U)(U other) pure const nothrow if (is(U : Box)) 272 { 273 return (min == other.min) && (max == other.max); 274 } 275 } 276 277 private 278 { 279 enum isBox = true; 280 enum _size = N; 281 alias T element_t; 282 } 283 } 284 285 /// Instanciate to use a 2D box. 286 template box2(T) 287 { 288 alias Box!(T, 2) box2; 289 } 290 291 /// Instanciate to use a 3D box. 292 template box3(T) 293 { 294 alias Box!(T, 3) box3; 295 } 296 297 298 alias box2!int box2i; /// 2D box with integer coordinates. 299 alias box3!int box3i; /// 3D box with integer coordinates. 300 alias box2!float box2f; /// 2D box with float coordinates. 301 alias box3!float box3f; /// 3D box with float coordinates. 302 alias box2!double box2d; /// 2D box with double coordinates. 303 alias box3!double box3d; /// 3D box with double coordinates. 304 305 unittest 306 { 307 box2i a = box2i(1, 2, 3, 4); 308 assert(a.width == 2); 309 assert(a.height == 2); 310 assert(a.volume == 4); 311 box2i b = box2i(vec2i(1, 2), vec2i(3, 4)); 312 assert(a == b); 313 box2i c = box2i(0, 0, 1,1); 314 assert(c.contains(vec2i(0, 0))); 315 assert(!c.contains(vec2i(1, 1))); 316 assert(b.contains(b)); 317 box2i d = c.expand(vec2i(3, 3)); 318 assert(d.contains(vec2i(2, 2))); 319 }