Line data Source code
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
5 : * it under the terms of the GNU General Public License as published by
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 53 : inline bool PointIsInSquare(const CFixedVector2D& point, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize)
43 : {
44 53 : 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 : */
55 : CFixedVector2D GetHalfBoundingBox(const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize);
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 : */
71 : fixed DistanceToSquare(const CFixedVector2D& point,
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 : */
78 : fixed DistanceToSquareSquared(const CFixedVector2D& point,
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 : */
91 : CFixedVector2D NearestPointOnSquare(const CFixedVector2D& point,
92 : const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize);
93 :
94 : /**
95 : * Returns the shortest distance between two squares.
96 : */
97 : fixed DistanceSquareToSquare(const CFixedVector2D& relativePos,
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 : */
109 : fixed MaxDistanceToSquare(const CFixedVector2D& point,
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 : */
116 : fixed MaxDistanceSquareToSquare(const CFixedVector2D& relativePos,
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 : */
151 : fixed DistanceToSegment(
152 : const CFixedVector2D& point, const CFixedVector2D& a, const CFixedVector2D& b);
153 :
154 : } // namespace Geometry
155 :
156 : #endif // INCLUDED_HELPER_GEOMETRY
|
