Pyrogenesis  trunk
Geometry.h
Go to the documentation of this file.
1 /* Copyright (C) 2020 Wildfire Games.
2  * This file is part of 0 A.D.
3  *
4  * 0 A.D. is free software: you can redistribute it and/or modify
6  * the Free Software Foundation, either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * 0 A.D. is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16  */
17
18 #ifndef INCLUDED_HELPER_GEOMETRY
19 #define INCLUDED_HELPER_GEOMETRY
20
21 /**
22  * @file
23  * Helper functions related to geometry algorithms
24  */
25
26 #include "maths/Fixed.h"
27 #include "maths/FixedVector2D.h"
28 #include "maths/MathUtil.h"
29
30 namespace Geometry
31 {
32
33 /**
34  * Checks if a point is inside the given rotated rectangle.
35  * Points precisely on an edge are considered to be inside.
36  *
37  * The rectangle is defined by the four vertexes
38  * (+/-u*halfSize.X +/-v*halfSize.Y)
39  *
40  * The @p u and @p v vectors must be perpendicular.
41  */
42 inline bool PointIsInSquare(const CFixedVector2D& point, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize)
43 {
44  return point.Dot(u).Absolute() <= halfSize.X && point.Dot(v).Absolute() <= halfSize.Y;
45 }
46
47 /**
48  * Returns a vector (bx,by) such that every point inside
49  * the given rotated rectangle has coordinates
50  * (x,y) with -bx <= x <= bx, -by <= y < by.
51  *
52  * The rectangle is defined by the four vertexes
53  * (+/-u*halfSize.X +/-v*halfSize.Y).
54  */
56
57 /**
58  * Returns the minimum Euclidean distance from the given point to
59  * any point on the boundary of the given rotated rectangle.
60  *
61  * If @p countInsideAsZero is true, and the point is inside the rectangle,
62  * it will return 0.
63  * If @p countInsideAsZero is false, the (positive) distance to the boundary
64  * will be returned regardless of where the point is.
65  *
66  * The rectangle is defined by the four vertexes
67  * (+/-u*halfSize.X +/-v*halfSize.Y).
68  *
69  * The @p u and @p v vectors must be perpendicular and unit length.
70  */
72  const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize,
73  bool countInsideAsZero = false);
74
75 /**
76  * Similar to above but never uses sqrt, so it returns the squared distance.
77  */
79  const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize,
80  bool countInsideAsZero = false);
81 /**
82  * Returns a point on the boundary of the given rotated rectangle
83  * that is closest (or equally closest) to the given point
84  * in Euclidean distance.
85  *
86  * The rectangle is defined by the four vertexes
87  * (+/-u*halfSize.X +/-v*halfSize.Y).
88  *
89  * The @p u and @p v vectors must be perpendicular and unit length.
90  */
92  const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize);
93
94 /**
95  * Returns the shortest distance between two squares.
96  */
98  const CFixedVector2D& u1, const CFixedVector2D& v1, const CFixedVector2D& halfSize1,
99  const CFixedVector2D& u2, const CFixedVector2D& v2, const CFixedVector2D& halfSize2);
100
101 /**
102  * Returns the greatest straight line distance from a point to a square.
103  *
104  * If @p countInsideAsZero is true, and the point is inside the rectangle,
105  * it will return 0.
106  * If @p countInsideAsZero is false, the greatest (positive) distance to the boundary
107  * will be returned regardless of where the point is.
108  */
110  const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize,
111  bool countInsideAsZero = false);
112
113 /**
114  * Return the greatest straight line distance between two squares.
115  */
117  const CFixedVector2D& u1, const CFixedVector2D& v1, const CFixedVector2D& halfSize1,
118  const CFixedVector2D& u2, const CFixedVector2D& v2, const CFixedVector2D& halfSize2);
119
120 bool TestRaySquare(const CFixedVector2D& a, const CFixedVector2D& b, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize);
121
122 bool TestRayAASquare(const CFixedVector2D& a, const CFixedVector2D& b, const CFixedVector2D& halfSize);
123
124 bool TestSquareSquare(
125  const CFixedVector2D& c0, const CFixedVector2D& u0, const CFixedVector2D& v0, const CFixedVector2D& halfSize0,
126  const CFixedVector2D& c1, const CFixedVector2D& u1, const CFixedVector2D& v1, const CFixedVector2D& halfSize1);
127
128 /**
129  * Used in Footprint when spawning units:
130  * Given a grid point (x, y) on the rectangle [-x_max, x_max] x [-y_max, y_max],
131  * this returns the distance travelled in moving from (x_max, 0) to the the point while
132  * walking counter-clockwise along the perimeter of the rectangle.
133  */
134 int GetPerimeterDistance(int x_max, int y_max, int x, int y);
135
136 /**
137  * Used in Footprint when spawning units:
138  * This returns the grid point on the rectangle [-x_max, x_max] x [-y_max, y_max]
139  * reached after starting at (x_max, 0) and walking a distance k
140  * counter-clockwise along the perimeter of the rectangle.
141  */
142 std::pair<int, int> GetPerimeterCoordinates(int x_max, int y_max, int k);
143
144 /**
145  * Returns the minimum Euclidean distance from the given point to
146  * any point on the given segment.
147  *
148  * @a and @b represents segment's points.
149  *
150  */
152  const CFixedVector2D& point, const CFixedVector2D& a, const CFixedVector2D& b);
153
154 } // namespace Geometry
155
156 #endif // INCLUDED_HELPER_GEOMETRY
A simple fixed-point number class.
Definition: Fixed.h:119
fixed DistanceSquareToSquare(const CFixedVector2D &relativePos, const CFixedVector2D &u1, const CFixedVector2D &v1, const CFixedVector2D &halfSize1, const CFixedVector2D &u2, const CFixedVector2D &v2, const CFixedVector2D &halfSize2)
Returns the shortest distance between two squares.
Definition: Geometry.cpp:190
Definition: FixedVector2D.h:24
std::pair< int, int > GetPerimeterCoordinates(int x_max, int y_max, int k)
Used in Footprint when spawning units: This returns the grid point on the rectangle [-x_max...
Definition: Geometry.cpp:408
int GetPerimeterDistance(int x_max, int y_max, int x, int y)
Used in Footprint when spawning units: Given a grid point (x, y) on the rectangle [-x_max...
Definition: Geometry.cpp:389
CFixedVector2D NearestPointOnSquare(const CFixedVector2D &point, const CFixedVector2D &u, const CFixedVector2D &v, const CFixedVector2D &halfSize)
Returns a point on the boundary of the given rotated rectangle that is closest (or equally closest) t...
Definition: Geometry.cpp:116
bool TestSquareSquare(const CFixedVector2D &c0, const CFixedVector2D &u0, const CFixedVector2D &v0, const CFixedVector2D &halfSize0, const CFixedVector2D &c1, const CFixedVector2D &u1, const CFixedVector2D &v1, const CFixedVector2D &halfSize1)
Definition: Geometry.cpp:357
fixed DistanceToSquare(const CFixedVector2D &point, const CFixedVector2D &u, const CFixedVector2D &v, const CFixedVector2D &halfSize, bool countInsideAsZero)
Returns the minimum Euclidean distance from the given point to any point on the boundary of the given...
Definition: Geometry.cpp:35
CFixedVector2D GetHalfBoundingBox(const CFixedVector2D &u, const CFixedVector2D &v, const CFixedVector2D &halfSize)
Returns a vector (bx,by) such that every point inside the given rotated rectangle has coordinates (x...
Definition: Geometry.cpp:27
bool TestRayAASquare(const CFixedVector2D &a, const CFixedVector2D &b, const CFixedVector2D &halfSize)
Definition: Geometry.cpp:306
fixed Y
Definition: FixedVector2D.h:27
fixed DistanceToSquareSquared(const CFixedVector2D &point, const CFixedVector2D &u, const CFixedVector2D &v, const CFixedVector2D &halfSize, bool countInsideAsZero)
Similar to above but never uses sqrt, so it returns the squared distance.
Definition: Geometry.cpp:91
bool TestRaySquare(const CFixedVector2D &a, const CFixedVector2D &b, const CFixedVector2D &u, const CFixedVector2D &v, const CFixedVector2D &halfSize)
Definition: Geometry.cpp:257
fixed DistanceToSegment(const CFixedVector2D &point, const CFixedVector2D &a, const CFixedVector2D &b)
Returns the minimum Euclidean distance from the given point to any point on the given segment...
Definition: Geometry.cpp:429
constexpr CFixed Absolute() const
Definition: Fixed.h:315
fixed Dot(const CFixedVector2D &v) const
Compute the dot product of this vector with another.
Definition: FixedVector2D.h:209
fixed MaxDistanceSquareToSquare(const CFixedVector2D &relativePos, const CFixedVector2D &u1, const CFixedVector2D &v1, const CFixedVector2D &halfSize1, const CFixedVector2D &u2, const CFixedVector2D &v2, const CFixedVector2D &halfSize2)
Return the greatest straight line distance between two squares.
Definition: Geometry.cpp:241
fixed X
Definition: FixedVector2D.h:27
bool PointIsInSquare(const CFixedVector2D &point, const CFixedVector2D &u, const CFixedVector2D &v, const CFixedVector2D &halfSize)
Checks if a point is inside the given rotated rectangle.
Definition: Geometry.h:42
fixed MaxDistanceToSquare(const CFixedVector2D &point, const CFixedVector2D &u, const CFixedVector2D &v, const CFixedVector2D &halfSize, bool countInsideAsZero)
Returns the greatest straight line distance from a point to a square.
Definition: Geometry.cpp:221
Definition: Geometry.cpp:22