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
148
149
150
151
152
153
154
155
156
|
/* Copyright (C) 2020 Wildfire Games.
* This file is part of 0 A.D.
*
* 0 A.D. is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 2 of the License, or
* (at your option) any later version.
*
* 0 A.D. is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef INCLUDED_HELPER_GEOMETRY
#define INCLUDED_HELPER_GEOMETRY
/**
* @file
* Helper functions related to geometry algorithms
*/
#include "maths/Fixed.h"
#include "maths/FixedVector2D.h"
#include "maths/MathUtil.h"
namespace Geometry
{
/**
* Checks if a point is inside the given rotated rectangle.
* Points precisely on an edge are considered to be inside.
*
* The rectangle is defined by the four vertexes
* (+/-u*halfSize.X +/-v*halfSize.Y)
*
* The @p u and @p v vectors must be perpendicular.
*/
inline bool PointIsInSquare(const CFixedVector2D& point, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize)
{
return point.Dot(u).Absolute() <= halfSize.X && point.Dot(v).Absolute() <= halfSize.Y;
}
/**
* Returns a vector (bx,by) such that every point inside
* the given rotated rectangle has coordinates
* (x,y) with -bx <= x <= bx, -by <= y < by.
*
* The rectangle is defined by the four vertexes
* (+/-u*halfSize.X +/-v*halfSize.Y).
*/
CFixedVector2D GetHalfBoundingBox(const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize);
/**
* Returns the minimum Euclidean distance from the given point to
* any point on the boundary of the given rotated rectangle.
*
* If @p countInsideAsZero is true, and the point is inside the rectangle,
* it will return 0.
* If @p countInsideAsZero is false, the (positive) distance to the boundary
* will be returned regardless of where the point is.
*
* The rectangle is defined by the four vertexes
* (+/-u*halfSize.X +/-v*halfSize.Y).
*
* The @p u and @p v vectors must be perpendicular and unit length.
*/
fixed DistanceToSquare(const CFixedVector2D& point,
const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize,
bool countInsideAsZero = false);
/**
* Similar to above but never uses sqrt, so it returns the squared distance.
*/
fixed DistanceToSquareSquared(const CFixedVector2D& point,
const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize,
bool countInsideAsZero = false);
/**
* Returns a point on the boundary of the given rotated rectangle
* that is closest (or equally closest) to the given point
* in Euclidean distance.
*
* The rectangle is defined by the four vertexes
* (+/-u*halfSize.X +/-v*halfSize.Y).
*
* The @p u and @p v vectors must be perpendicular and unit length.
*/
CFixedVector2D NearestPointOnSquare(const CFixedVector2D& point,
const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize);
/**
* Returns the shortest distance between two squares.
*/
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 greatest straight line distance from a point to a square.
*
* If @p countInsideAsZero is true, and the point is inside the rectangle,
* it will return 0.
* If @p countInsideAsZero is false, the greatest (positive) distance to the boundary
* will be returned regardless of where the point is.
*/
fixed MaxDistanceToSquare(const CFixedVector2D& point,
const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize,
bool countInsideAsZero = false);
/**
* Return the greatest straight line distance between two squares.
*/
fixed MaxDistanceSquareToSquare(const CFixedVector2D& relativePos,
const CFixedVector2D& u1, const CFixedVector2D& v1, const CFixedVector2D& halfSize1,
const CFixedVector2D& u2, const CFixedVector2D& v2, const CFixedVector2D& halfSize2);
bool TestRaySquare(const CFixedVector2D& a, const CFixedVector2D& b, const CFixedVector2D& u, const CFixedVector2D& v, const CFixedVector2D& halfSize);
bool TestRayAASquare(const CFixedVector2D& a, const CFixedVector2D& b, const CFixedVector2D& halfSize);
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);
/**
* Used in Footprint when spawning units:
* Given a grid point (x, y) on the rectangle [-x_max, x_max] x [-y_max, y_max],
* this returns the distance travelled in moving from (x_max, 0) to the the point while
* walking counter-clockwise along the perimeter of the rectangle.
*/
int GetPerimeterDistance(int x_max, int y_max, int x, int y);
/**
* Used in Footprint when spawning units:
* This returns the grid point on the rectangle [-x_max, x_max] x [-y_max, y_max]
* reached after starting at (x_max, 0) and walking a distance k
* counter-clockwise along the perimeter of the rectangle.
*/
std::pair<int, int> GetPerimeterCoordinates(int x_max, int y_max, int k);
/**
* Returns the minimum Euclidean distance from the given point to
* any point on the given segment.
*
* @a and @b represents segment's points.
*
*/
fixed DistanceToSegment(
const CFixedVector2D& point, const CFixedVector2D& a, const CFixedVector2D& b);
} // namespace Geometry
#endif // INCLUDED_HELPER_GEOMETRY
|
