Public Functions
lineToLineIntersect(const Point2F & a1, const Point2F & a2, const Point2F & b1, const Point2F & b2)
1
2//-----------------------------------------------------------------------------
3// Copyright (c) 2012 GarageGames, LLC
4//
5// Permission is hereby granted, free of charge, to any person obtaining a copy
6// of this software and associated documentation files (the "Software"), to
7// deal in the Software without restriction, including without limitation the
8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
9// sell copies of the Software, and to permit persons to whom the Software is
10// furnished to do so, subject to the following conditions:
11//
12// The above copyright notice and this permission notice shall be included in
13// all copies or substantial portions of the Software.
14//
15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21// IN THE SOFTWARE.
22//-----------------------------------------------------------------------------
23
24#ifndef _MRECT_H_
25#define _MRECT_H_
26
27#ifndef _MPOINT2_H_
28#include "math/mPoint2.h"
29#endif
30
31
32class RectI
33{
34 public:
35 Point2I point;
36 Point2I extent;
37
38 public:
39 RectI() { }
40 RectI(const Point2I& in_rMin,
41 const Point2I& in_rExtent);
42 RectI(const S32 in_left, const S32 in_top,
43 const S32 in_width, const S32 in_height);
44
45 void set(const Point2I& in_rMin, const Point2I& in_rExtent);
46 void set(const S32 in_left, const S32 in_top,
47 const S32 in_width, const S32 in_height);
48
49 bool intersect(const RectI& clipRect);
50 bool pointInRect(const Point2I& pt) const;
51 bool overlaps(RectI R) const;
52 bool contains(const RectI& R) const;
53 void inset(S32 x, S32 y);
54
55 void unionRects(const RectI&);
56
57 S32 len_x() const;
58 S32 len_y() const;
59
60 /// Returns the area of the rectangle.
61 S32 area() const { return extent.x * extent.y; }
62
63 bool operator==(const RectI&) const;
64 bool operator!=(const RectI&) const;
65
66 bool isValidRect() const { return (extent.x > 0 && extent.y > 0); }
67
68public:
69
70 /// A rect of zero extent.
71 static const RectI Zero;
72
73 /// A rect of 1,1 extent.
74 static const RectI One;
75
76};
77
78class RectF
79{
80 public:
81 Point2F point;
82 Point2F extent;
83
84 public:
85 RectF() { }
86 RectF(const Point2F& in_rMin,
87 const Point2F& in_rExtent);
88 RectF(const F32 in_left, const F32 in_top,
89 const F32 in_width, const F32 in_height);
90
91 void set(const Point2F& in_rMin, const Point2F& in_rExtent);
92 void set(const F32 in_left, const F32 in_top,
93 const F32 in_width, const F32 in_height);
94
95 void inset(F32 x, F32 y);
96
97 /// Return distance of the reference point to the rectangle.
98 F32 getDistanceToPoint( const Point2F &refPt ) const;
99
100 /// Return the squared distance of the reference point to the rectangle.
101 F32 getSqDistanceToPoint( const Point2F &refPt ) const;
102
103 bool intersect(const RectF& clipRect);
104 bool pointInRect(const Point2F& pt) const;
105 bool overlaps(const RectF&) const;
106 bool contains(const Point2F &p) const
107 {
108 Point2F minkowskiP = p - point;
109
110 // If we're beyond origin...
111 if(minkowskiP.x < 0 || minkowskiP.y < 0)
112 return false;
113
114 // Or past extent...
115 if(minkowskiP.x > extent.x || minkowskiP.y > extent.y)
116 return false;
117
118 // Otherwise we're ok.
119 return true;
120 }
121
122 bool contains(const RectF& R) const;
123
124 void unionRects( const RectF &rect );
125
126 F32 len_x() const;
127 F32 len_y() const;
128
129 bool isValidRect() const { return (extent.x > 0.0f && extent.y > 0.0f); }
130 inline bool intersectTriangle(const Point2F &a, const Point2F &b, const Point2F &c);
131
132};
133
134class RectD
135{
136 public:
137 Point2D point;
138 Point2D extent;
139
140 public:
141 RectD() { }
142 RectD(const Point2D& in_rMin,
143 const Point2D& in_rExtent);
144 RectD(const F64 in_left, const F64 in_top,
145 const F64 in_width, const F64 in_height);
146 void inset(F64 x, F64 y);
147
148 bool intersect(const RectD& clipRect);
149 F64 len_x() const;
150 F64 len_y() const;
151
152 bool isValidRect() const { return (extent.x > 0 && extent.y > 0); }
153};
154
155//------------------------------------------------------------------------------
156//-------------------------------------- INLINES (RectI)
157//
158inline
159RectI::RectI(const Point2I& in_rMin,
160 const Point2I& in_rExtent)
161 : point(in_rMin),
162 extent(in_rExtent)
163{
164 //
165}
166
167inline
168RectI::RectI(const S32 in_left, const S32 in_top,
169 const S32 in_width, const S32 in_height)
170 : point(in_left, in_top),
171 extent(in_width, in_height)
172{
173 //
174}
175
176inline void RectI::set(const Point2I& in_rMin, const Point2I& in_rExtent)
177{
178 point = in_rMin;
179 extent = in_rExtent;
180}
181
182inline void RectI::set(const S32 in_left, const S32 in_top,
183 const S32 in_width, const S32 in_height)
184{
185 point.set(in_left, in_top);
186 extent.set(in_width, in_height);
187}
188
189inline bool RectI::intersect(const RectI& clipRect)
190{
191 Point2I bottomL;
192 bottomL.x = getMin(point.x + extent.x - 1, clipRect.point.x + clipRect.extent.x - 1);
193 bottomL.y = getMin(point.y + extent.y - 1, clipRect.point.y + clipRect.extent.y - 1);
194
195 point.x = getMax(point.x, clipRect.point.x);
196 point.y = getMax(point.y, clipRect.point.y);
197
198 extent.x = bottomL.x - point.x + 1;
199 extent.y = bottomL.y - point.y + 1;
200
201 return isValidRect();
202}
203
204inline bool RectI::pointInRect(const Point2I &pt) const
205{
206 return (pt.x >= point.x && pt.x < point.x + extent.x && pt.y >= point.y && pt.y < point.y + extent.y);
207}
208
209inline bool RectI::contains(const RectI& R) const
210{
211 if (point.x <= R.point.x && point.y <= R.point.y)
212 if (R.point.x + R.extent.x <= point.x + extent.x)
213 if (R.point.y + R.extent.y <= point.y + extent.y)
214 return true;
215 return false;
216}
217
218inline bool RectI::overlaps(RectI R) const
219{
220 return R.intersect (* this);
221}
222
223inline void RectI::inset(S32 x, S32 y)
224{
225 point.x += x;
226 point.y += y;
227 extent.x -= 2 * x;
228 extent.y -= 2 * y;
229}
230
231inline void RectF::inset(F32 x, F32 y)
232{
233 point.x += x;
234 point.y += y;
235 extent.x -= 2.0f * x;
236 extent.y -= 2.0f * y;
237}
238
239inline void RectD::inset(F64 x, F64 y)
240{
241 point.x += x;
242 point.y += y;
243 extent.x -= 2.0 * x;
244 extent.y -= 2.0 * y;
245}
246
247
248inline void RectI::unionRects(const RectI& u)
249{
250 S32 minx = point.x < u.point.x ? point.x : u.point.x;
251 S32 miny = point.y < u.point.y ? point.y : u.point.y;
252 S32 maxx = (point.x + extent.x) > (u.point.x + u.extent.x) ? (point.x + extent.x) : (u.point.x + u.extent.x);
253 S32 maxy = (point.y + extent.y) > (u.point.y + u.extent.y) ? (point.y + extent.y) : (u.point.y + u.extent.y);
254
255 point.x = minx;
256 point.y = miny;
257 extent.x = maxx - minx;
258 extent.y = maxy - miny;
259}
260
261inline S32
262RectI::len_x() const
263{
264 return extent.x;
265}
266
267inline S32
268RectI::len_y() const
269{
270 return extent.y;
271}
272
273inline bool
274RectI::operator==(const RectI& in_rCompare) const
275{
276 return (point == in_rCompare.point) && (extent == in_rCompare.extent);
277}
278
279inline bool
280RectI::operator!=(const RectI& in_rCompare) const
281{
282 return (operator==(in_rCompare) == false);
283}
284
285//------------------------------------------------------------------------------
286//-------------------------------------- INLINES (RectF)
287//
288inline
289RectF::RectF(const Point2F& in_rMin,
290 const Point2F& in_rExtent)
291 : point(in_rMin),
292 extent(in_rExtent)
293{
294 //
295}
296
297inline
298RectF::RectF(const F32 in_left, const F32 in_top,
299 const F32 in_width, const F32 in_height)
300 : point(in_left, in_top),
301 extent(in_width, in_height)
302{
303 //
304}
305
306inline F32
307RectF::len_x() const
308{
309 return extent.x;
310}
311
312inline F32
313RectF::len_y() const
314{
315 return extent.y;
316}
317
318inline void RectF::set(const Point2F& in_rMin, const Point2F& in_rExtent)
319{
320 point = in_rMin;
321 extent = in_rExtent;
322}
323
324inline void RectF::set(const F32 in_left, const F32 in_top,
325 const F32 in_width, const F32 in_height)
326{
327 point.set(in_left, in_top);
328 extent.set(in_width, in_height);
329}
330
331inline F32 RectF::getDistanceToPoint( const Point2F &refPt ) const
332{
333 return mSqrt( getSqDistanceToPoint( refPt ) );
334}
335
336inline F32 RectF::getSqDistanceToPoint( const Point2F &refPt ) const
337{
338 const Point2F maxPoint( point + extent );
339
340 F32 sqDist = 0.0f;
341
342 for ( U32 i=0; i < 2; i++ )
343 {
344 const F32 v = refPt[i];
345 if ( v < point[i] )
346 sqDist += mSquared( point[i] - v );
347 else if ( v > maxPoint[i] )
348 sqDist += mSquared( v - maxPoint[i] );
349 }
350
351 return sqDist;
352}
353
354inline bool RectF::intersect(const RectF& clipRect)
355{
356 Point2F bottomL;
357 bottomL.x = getMin(point.x + extent.x, clipRect.point.x + clipRect.extent.x);
358 bottomL.y = getMin(point.y + extent.y, clipRect.point.y + clipRect.extent.y);
359
360 point.x = getMax(point.x, clipRect.point.x);
361 point.y = getMax(point.y, clipRect.point.y);
362
363 extent.x = bottomL.x - point.x;
364 extent.y = bottomL.y - point.y;
365
366 return isValidRect();
367}
368
369inline bool RectF::pointInRect(const Point2F &pt) const
370{
371 return (pt.x >= point.x && pt.x < point.x + extent.x && pt.y >= point.y && pt.y < point.y + extent.y);
372}
373
374inline bool RectF::overlaps(const RectF& clipRect) const
375{
376 RectF test = *this;
377 return test.intersect(clipRect);
378}
379
380inline bool lineToLineIntersect(const Point2F & a1, const Point2F & a2, const Point2F & b1, const Point2F & b2)
381{
382 const F32 ua_t = (b2.x - b1.x) * (a1.y - b1.y) - (b2.y - b1.y) * (a1.x - b1.x);
383 const F32 ub_t = (a2.x - a1.x) * (a1.y - b1.y) - (a2.y - a1.y) * (a1.x - b1.x);
384 const F32 u_b = (b2.y - b1.y) * (a2.x - a1.x) - (b2.x - b1.x) * (a2.y - a1.y);
385
386 if(u_b != 0)
387 {
388 const F32 ua = ua_t / u_b;
389 const F32 ub = ub_t / u_b;
390
391 return ( 0.0f <= ua && ua <= 1.0f && 0.0f <= ub && ub <= 1.0f );
392 }
393 else
394 {
395 return ( ua_t == 0 || ub_t == 0 );
396 }
397}
398
399inline bool RectF::intersectTriangle(const Point2F &a, const Point2F &b, const Point2F &c)
400{
401 const Point2F topLeft = point;
402 const Point2F topRight = Point2F( point.x + extent.x, point.y );
403 const Point2F bottomLeft = Point2F( point.x, point.y + extent.y );
404 const Point2F bottomRight = point + extent;
405
406 // 3 point plus 12 edge tests.
407
408 // Check each triangle point to see if it's in us.
409 if(contains(a) || contains(b) || contains(c))
410 return true;
411
412 // Check a-b against the rect.
413 if(lineToLineIntersect(topLeft, topRight, a, b))
414 return true;
415
416 if(lineToLineIntersect(topRight, bottomRight, a, b))
417 return true;
418
419 if(lineToLineIntersect(bottomRight, bottomLeft, a, b))
420 return true;
421
422 if(lineToLineIntersect(bottomLeft, topLeft, a, b))
423 return true;
424
425 // Check b-c
426 if(lineToLineIntersect(topLeft, topRight, b, c))
427 return true;
428
429 if(lineToLineIntersect(topRight, bottomRight, b, c))
430 return true;
431
432 if(lineToLineIntersect(bottomRight, bottomLeft, b, c))
433 return true;
434
435 if(lineToLineIntersect(bottomLeft, topLeft, b, c))
436 return true;
437
438 // Check c-a
439 if(lineToLineIntersect(topLeft, topRight, c, a))
440 return true;
441
442 if(lineToLineIntersect(topRight, bottomRight, c, a))
443 return true;
444
445 if(lineToLineIntersect(bottomRight, bottomLeft, c, a))
446 return true;
447
448 if(lineToLineIntersect(bottomLeft, topLeft, c, a))
449 return true;
450
451 return false;
452}
453
454inline bool RectF::contains(const RectF& R) const
455{
456 if (point.x <= R.point.x && point.y <= R.point.y)
457 if (R.point.x + R.extent.x <= point.x + extent.x)
458 if (R.point.y + R.extent.y <= point.y + extent.y)
459 return true;
460 return false;
461}
462
463inline void RectF::unionRects( const RectF &r )
464{
465 F32 minx = point.x < r.point.x ? point.x : r.point.x;
466 F32 miny = point.y < r.point.y ? point.y : r.point.y;
467 F32 maxx = (point.x + extent.x) > (r.point.x + r.extent.x) ? (point.x + extent.x) : (r.point.x + r.extent.x);
468 F32 maxy = (point.y + extent.y) > (r.point.y + r.extent.y) ? (point.y + extent.y) : (r.point.y + r.extent.y);
469
470 point.x = minx;
471 point.y = miny;
472 extent.x = maxx - minx;
473 extent.y = maxy - miny;
474}
475
476//------------------------------------------------------------------------------
477//-------------------------------------- INLINES (RectD)
478//
479inline
480RectD::RectD(const Point2D& in_rMin,
481 const Point2D& in_rExtent)
482 : point(in_rMin),
483 extent(in_rExtent)
484{
485 //
486}
487
488inline
489RectD::RectD(const F64 in_left, const F64 in_top,
490 const F64 in_width, const F64 in_height)
491 : point(in_left, in_top),
492 extent(in_width, in_height)
493{
494 //
495}
496
497inline F64
498RectD::len_x() const
499{
500 return extent.x;
501}
502
503inline F64
504RectD::len_y() const
505{
506 return extent.y;
507}
508
509inline bool RectD::intersect(const RectD& clipRect)
510{
511 Point2D bottomL;
512 bottomL.x = getMin(point.x + extent.x, clipRect.point.x + clipRect.extent.x);
513 bottomL.y = getMin(point.y + extent.y, clipRect.point.y + clipRect.extent.y);
514
515 point.x = getMax(point.x, clipRect.point.x);
516 point.y = getMax(point.y, clipRect.point.y);
517
518 extent.x = bottomL.x - point.x;
519 extent.y = bottomL.y - point.y;
520
521 return isValidRect();
522}
523
524#endif //_RECT_H_
525
