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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
|
/* ScummVM - Graphic Adventure Engine
*
* ScummVM is the legal property of its developers, whose names
* are too numerous to list here. Please refer to the COPYRIGHT
* file distributed with this source distribution.
*
* This program 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.
* This program 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 this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
* $URL$
* $Id$
*
*/
/*
* This code is based on Broken Sword 2.5 engine
*
* Copyright (c) Malte Thiesen, Daniel Queteschiner and Michael Elsdoerfer
*
* Licensed under GNU GPL v2
*
*/
#ifndef SWORD25_POLYGON_H
#define SWORD25_POLYGON_H
// Includes
#include "sword25/kernel/common.h"
#include "sword25/kernel/persistable.h"
#include "sword25/math/vertex.h"
namespace Sword25 {
class Vertex;
/**
@brief Eine Polygonklasse.
*/
class Polygon : public Persistable {
public:
/**
* Creates an object of type #BS_Polygon, containing 0 Vertecies.
*
* With the method Init(), Vertices can be added in later
*/
Polygon();
/**
* Copy constructor
*/
Polygon(const Polygon &other);
/**
* Creates a polygon using persisted data
*/
Polygon(InputPersistenceBlock &reader);
/**
* Creaes an object of type #BS_Polygon, and assigns Vertices to it
* @param VertexCount The number of vertices being passed
* @param Vertecies An array of BS_Vertex objects representing the vertices in the polygon.
* @remark The Vertecies that define a polygon must not have any self-intersections.
* If the polygon does have self-intersections, then an empty polygon object is created.
*/
Polygon(int vertexCount_, const Vertex *vertices_);
/**
* Deletes the BS_Polygon object
*/
virtual ~Polygon();
/**
* Initialises the BS_Polygon with a list of Vertecies.
*
* The Vertices need to define a polygon must not have self-intersections.
* If a polygon already has verticies, this will re-initialise it with the new list.
*
* @param VertexCount The number of vertices being passed
* @param Vertecies An array of BS_Vertex objects representing the vertices in the polygon.
* @return Returns false if the Vertecies have self-intersections. In this case,
* the object is not initialised.
*/
bool init(int vertexCount_, const Vertex *vertices_);
//
// ** Exploratory methods **
//
/**
* Checks whether the Vertecies of the polygon are arranged in a clockwise direction.
* @return Returns true if the Vertecies of the polygon are arranged clockwise or co-planar.
* Returns false if the Vertecies of the polygon are arrange counter-clockwise.
* @remark This method only returns a meaningful result if the polygon has at least three Vertecies.
*/
bool isCW() const;
/**
* Checks whether the Vertices of the polygon are arranged in a counter-clockwise direction.
* @return Returns true if the Vertecies of the polygon are arranged counter-clockwise.
* Returns false if the Vertecies of the polygon are arranged clockwise or co-planar.
* @remark This method only returns a meaningful result if the polygon has at least three Vertecies.
*/
bool isCCW() const;
/**
* Checks whether the polygon is convex.
* @return Returns true if the polygon is convex. Returns false if the polygon is concave.
* @remark This method only returns a meaningful result if the polygon has at least three Vertecies.
*/
bool isConvex() const;
/**
* Checks whether the polygon is concave.
* @return Returns true if the polygon is concave. Returns false if the polygon is convex.
* @remark This method only returns a meaningful result if the polygon has at least three Vertecies.
*/
bool isConcave() const;
/**
* Checks whether a point is inside the polygon
* @param Vertex A Vertex with the co-ordinates of the point to be tested.
* @param BorderBelongsToPolygon Specifies whether the edge of the polygon should be considered
* @return Returns true if the point is inside the polygon, false if it is outside.
*/
bool isPointInPolygon(const Vertex &vertex, bool borderBelongsToPolygon = true) const;
/**
* Checks whether a point is inside the polygon
* @param X The X position of the point
* @param Y The Y position of the point
* @param BorderBelongsToPolygon Specifies whether the edge of the polygon should be considered
* @return Returns true if the point is inside the polygon, false if it is outside.
*/
bool isPointInPolygon(int x, int y, bool borderBelongsToPolygon = true) const;
/**
* Returns the focus/centroid of the polygon
*/
Vertex getCentroid() const;
// Edge belongs to the polygon
// Polygon must be CW
bool isLineInterior(const Vertex &a, const Vertex &b) const;
// Edge does not belong to the polygon
// Polygon must be CW
bool isLineExterior(const Vertex &a, const Vertex &b) const;
//
// Manipulation methods
//
/**
* Ensures that the Vertecies of the polygon are arranged in a clockwise direction
*/
void ensureCWOrder();
/**
* Ensures that the Vertecies of the polygon are arranged in a counter-clockwise direction
*/
void ensureCCWOrder();
/**
* Reverses the Vertecies order.
*/
void reverseVertexOrder();
/**
* Moves the polygon.
* @param Delta The vertex around the polygon to be moved.
*/
void operator+=(const Vertex &delta);
//
//------------------
//
/// Specifies the number of Vertecies in the Vertecies array.
int vertexCount;
/// COntains the Vertecies of the polygon
Vertex *vertices;
virtual bool persist(OutputPersistenceBlock &writer);
virtual bool unpersist(InputPersistenceBlock &reader);
Polygon &operator=(const Polygon &p) {
init(p.vertexCount, p.vertices);
return *this;
}
private:
bool _isCW;
bool _isConvex;
Vertex _centroid;
/**
* Computes the centroid of the polygon.
*/
Vertex computeCentroid() const;
/**
* Determines how the Vertecies of the polygon are arranged.
* @return Returns true if the Vertecies are arranged in a clockwise
* direction, otherwise false.
*/
bool computeIsCW() const;
/**
* Determines whether the polygon is convex or concave.
* @return Returns true if the polygon is convex, otherwise false.
*/
bool computeIsConvex() const;
/**
* Calculates the cross product of three Vertecies
* @param V1 The first Vertex
* @param V2 The second Vertex
* @param V3 The third Vertex
* @return Returns the cross-product of the three vertecies
* @todo This method would be better as a method of the BS_Vertex class
*/
int crossProduct(const Vertex &v1, const Vertex &v2, const Vertex &v3) const;
/**
* Computes the scalar product of two vectors spanning three vertecies
*
* The vectors are spanned by V2->V1 and V2->V3
*
* @param V1 The first Vertex
* @param V2 The second Vertex
* @param V3 The third Vertex
* @return Returns the dot product of the three Vertecies.
* @todo This method would be better as a method of the BS_Vertex class
*/
int dotProduct(const Vertex &v1, const Vertex &v2, const Vertex &v3) const;
/**
* Checks whether the polygon is self-intersecting
* @return Returns true if the polygon is self-intersecting.
* Returns false if the polygon is not self-intersecting.
*/
bool checkForSelfIntersection() const;
/**
* Find the vertex of the polygon that is located below the right-most point,
* and returns it's index in the vertex array.
* @return Returns the index of the vertex at the bottom-right of the polygon.
* Returns -1 if the vertex list is empty.
*/
int findLRVertexIndex() const;
bool isLineInCone(int startVertexIndex, const Vertex &endVertex, bool includeEdges) const;
};
} // End of namespace Sword25
#endif
|
