1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
/*
* Rect.cpp, part of VCMI engine
*
* Authors: listed in file AUTHORS in main folder
*
* License: GNU General Public License v2.0 or later
* Full text of license available in license.txt file, in main folder
*
*/
#include "StdInc.h"
#include "Rect.h"
#include "int3.h"
VCMI_LIB_NAMESPACE_BEGIN
Point::Point(const int3 & a)
: x(a.x)
, y(a.y)
{
}
/// Returns rect union - rect that covers both this rect and provided rect
Rect Rect::include(const Rect & other) const
{
Point topLeft{
std::min(this->left(), other.left()),
std::min(this->top(), other.top())
};
Point bottomRight{
std::max(this->right(), other.right()),
std::max(this->bottom(), other.bottom())
};
return Rect(topLeft, bottomRight - topLeft);
}
Rect Rect::createCentered( const Point & around, const Point & dimensions )
{
return Rect(around - dimensions/2, dimensions);
}
Rect Rect::createAround(const Rect &r, int width)
{
return Rect(r.x - width, r.y - width, r.w + width * 2, r.h + width * 2);
}
Rect Rect::createCentered( const Rect & rect, const Point & dimensions)
{
return createCentered(rect.center(), dimensions);
}
bool Rect::intersectionTest(const Rect & other) const
{
// this rect is above other rect
if(this->bottom() < other.top())
return false;
// this rect is below other rect
if(this->top() > other.bottom() )
return false;
// this rect is to the left of other rect
if(this->right() < other.left())
return false;
// this rect is to the right of other rect
if(this->left() > other.right())
return false;
return true;
}
/// Algorithm to test whether line segment between points line1-line2 will intersect with
/// rectangle specified by top-left and bottom-right points
/// Note that in order to avoid floating point rounding errors algorithm uses integers with no divisions
bool Rect::intersectionTest(const Point & line1, const Point & line2) const
{
// check whether segment is located to the left of our rect
if (line1.x < left() && line2.x < left())
return false;
// check whether segment is located to the right of our rect
if (line1.x > right() && line2.x > right())
return false;
// check whether segment is located on top of our rect
if (line1.y < top() && line2.y < top())
return false;
// check whether segment is located below of our rect
if (line1.y > bottom() && line2.y > bottom())
return false;
Point vector { line2.x - line1.x, line2.y - line1.y};
// compute position of corners relative to our line
int tlTest = vector.y*topLeft().x - vector.x*topLeft().y + (line2.x*line1.y-line1.x*line2.y);
int trTest = vector.y*bottomRight().x - vector.x*topLeft().y + (line2.x*line1.y-line1.x*line2.y);
int blTest = vector.y*topLeft().x - vector.x*bottomRight().y + (line2.x*line1.y-line1.x*line2.y);
int brTest = vector.y*bottomRight().x - vector.x*bottomRight().y + (line2.x*line1.y-line1.x*line2.y);
// if all points are on the left of our line then there is no intersection
if ( tlTest > 0 && trTest > 0 && blTest > 0 && brTest > 0 )
return false;
// if all points are on the right of our line then there is no intersection
if ( tlTest < 0 && trTest < 0 && blTest < 0 && brTest < 0 )
return false;
// if all previous checks failed, this means that there is an intersection between line and AABB
return true;
}
Rect Rect::intersect(const Rect & other) const
{
if(intersectionTest(other))
{
Point topLeft{
std::max(this->left(), other.left()),
std::max(this->top(), other.top())
};
Point bottomRight{
std::min(this->right(), other.right()),
std::min(this->bottom(), other.bottom())
};
return Rect(topLeft, bottomRight - topLeft);
}
else
{
return Rect();
}
}
int Rect::distanceTo(const Point & target) const
{
int distanceX = std::max({left() - target.x, 0, target.x - right()});
int distanceY = std::max({top() - target.y, 0, target.y - bottom()});
return Point(distanceX, distanceY).length();
}
VCMI_LIB_NAMESPACE_END
|
