1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 /*
24 * This code is based on Broken Sword 2.5 engine
25 *
26 * Copyright (c) Malte Thiesen, Daniel Queteschiner and Michael Elsdoerfer
27 *
28 * Licensed under GNU GPL v2
29 *
30 */
31
32 #include "sword25/kernel/outputpersistenceblock.h"
33 #include "sword25/kernel/inputpersistenceblock.h"
34
35 #include "sword25/math/polygon.h"
36 #include "sword25/math/line.h"
37
38 namespace Sword25 {
39
Polygon()40 Polygon::Polygon() : vertexCount(0), vertices(NULL) {
41 }
42
Polygon(int vertexCount_,const Vertex * vertices_)43 Polygon::Polygon(int vertexCount_, const Vertex *vertices_) : vertexCount(0), vertices(NULL) {
44 init(vertexCount_, vertices_);
45 }
46
Polygon(const Polygon & other)47 Polygon::Polygon(const Polygon &other) : Persistable(other), vertexCount(0), vertices(NULL) {
48 init(other.vertexCount, other.vertices);
49 }
50
Polygon(InputPersistenceBlock & Reader)51 Polygon::Polygon(InputPersistenceBlock &Reader) : vertexCount(0), vertices(NULL) {
52 unpersist(Reader);
53 }
54
~Polygon()55 Polygon::~Polygon() {
56 delete[] vertices;
57 }
58
init(int vertexCount_,const Vertex * vertices_)59 bool Polygon::init(int vertexCount_, const Vertex *vertices_) {
60 // Rember the old obstate to restore it if an error occurs whilst initializing it with the new data
61 int oldvertexCount = this->vertexCount;
62 Vertex *oldvertices = this->vertices;
63
64 this->vertexCount = vertexCount_;
65 this->vertices = new Vertex[vertexCount_ + 1];
66 memcpy(this->vertices, vertices_, sizeof(Vertex) * vertexCount_);
67 // TODO:
68 // Duplicate and remove redundant vertecies (Superflous = 3 co-linear verts)
69 // _WeedRepeatedvertices();
70 // The first vertex is repeated at the end of the vertex array; this simplifies
71 // some algorithms, running through the edges and thus can save the overflow control.
72 this->vertices[vertexCount_] = this->vertices[0];
73
74 // If the polygon is self-intersecting, the object state is restore, and an error signalled
75 if (checkForSelfIntersection()) {
76 delete[] this->vertices;
77 this->vertices = oldvertices;
78 this->vertexCount = oldvertexCount;
79
80 // BS_LOG_ERROR("POLYGON: Tried to create a self-intersecting polygon.\n");
81 return false;
82 }
83
84 // Release old vertex list
85 delete[] oldvertices;
86
87 // Calculate properties of the polygon
88 _isCW = computeIsCW();
89 _centroid = computeCentroid();
90
91 return true;
92 }
93
94 // Review the order of the vertices
95 // ---------------------------------
96
isCW() const97 bool Polygon::isCW() const {
98 return _isCW;
99 }
computeIsCW() const100 bool Polygon::computeIsCW() const {
101 if (vertexCount) {
102 // Find the vertex on extreme bottom right
103 int v2Index = findLRVertexIndex();
104
105 // Find the vertex before and after it
106 int v1Index = (v2Index + (vertexCount - 1)) % vertexCount;
107 int v3Index = (v2Index + 1) % vertexCount;
108
109 // Cross product form
110 // If the cross product of the vertex lying fartherest bottom left is positive,
111 // the vertecies arranged in a clockwise order. Otherwise counter-clockwise
112 if (crossProduct(vertices[v1Index], vertices[v2Index], vertices[v3Index]) >= 0)
113 return true;
114 }
115
116 return false;
117 }
118
findLRVertexIndex() const119 int Polygon::findLRVertexIndex() const {
120 if (vertexCount) {
121 int curIndex = 0;
122 int maxX = vertices[0].x;
123 int maxY = vertices[0].y;
124
125 for (int i = 1; i < vertexCount; i++) {
126 if (vertices[i].y > maxY ||
127 (vertices[i].y == maxY && vertices[i].x > maxX)) {
128 maxX = vertices[i].x;
129 maxY = vertices[i].y;
130 curIndex = i;
131 }
132 }
133
134 return curIndex;
135 }
136
137 return -1;
138 }
139 // Make a determine vertex order
140 // -----------------------------
141
ensureCWOrder()142 void Polygon::ensureCWOrder() {
143 if (!isCW())
144 reverseVertexOrder();
145 }
146 // Reverse the order of vertecies
147 // ------------------------------
148
reverseVertexOrder()149 void Polygon::reverseVertexOrder() {
150 // vertices are exchanged in pairs, until the list has been completely reversed
151 for (int i = 0; i < vertexCount / 2; i++) {
152 Vertex tempVertex = vertices[i];
153 vertices[i] = vertices[vertexCount - i - 1];
154 vertices[vertexCount - i - 1] = tempVertex;
155 }
156
157 // Vertexordnung neu berechnen.
158 _isCW = computeIsCW();
159 }
160
161 // Cross Product
162 // -------------
163
crossProduct(const Vertex & v1,const Vertex & v2,const Vertex & v3) const164 int Polygon::crossProduct(const Vertex &v1, const Vertex &v2, const Vertex &v3) const {
165 return (v2.x - v1.x) * (v3.y - v2.y) -
166 (v2.y - v1.y) * (v3.x - v2.x);
167 }
168 // Check for self-intersections
169 // ----------------------------
170
checkForSelfIntersection() const171 bool Polygon::checkForSelfIntersection() const {
172 // TODO: Finish this
173 /*
174 float AngleSum = 0.0f;
175 for (int i = 0; i < vertexCount; i++) {
176 int j = (i + 1) % vertexCount;
177 int k = (i + 2) % vertexCount;
178
179 float Dot = DotProduct(vertices[i], vertices[j], vertices[k]);
180
181 // Skalarproduct normalisieren
182 float Length1 = sqrt((vertices[i].x - vertices[j].x) * (vertices[i].x - vertices[j].x) +
183 (vertices[i].y - vertices[j].y) * (vertices[i].y - vertices[j].y));
184 float Length2 = sqrt((vertices[k].x - vertices[j].x) * (vertices[k].x - vertices[j].x) +
185 (vertices[k].y - vertices[j].y) * (vertices[k].y - vertices[j].y));
186 float Norm = Length1 * Length2;
187
188 if (Norm > 0.0f) {
189 Dot /= Norm;
190 AngleSum += acos(Dot);
191 }
192 }
193 */
194
195 return false;
196 }
197
198 // Move
199 // ----
200
operator +=(const Vertex & delta)201 void Polygon::operator+=(const Vertex &delta) {
202 // Move all vertecies
203 for (int i = 0; i < vertexCount; i++)
204 vertices[i] += delta;
205
206 // Shift the focus
207 _centroid += delta;
208 }
209
210 // Line of Sight
211 // -------------
212
isLineInterior(const Vertex & a,const Vertex & b) const213 bool Polygon::isLineInterior(const Vertex &a, const Vertex &b) const {
214 // Both points have to be in the polygon
215 if (!isPointInPolygon(a, true) || !isPointInPolygon(b, true))
216 return false;
217
218 // If the points are identical, the line is trivially within the polygon
219 if (a == b)
220 return true;
221
222 // Test whether the line intersects a line segment strictly (proper intersection)
223 for (int i = 0; i < vertexCount; i++) {
224 int j = (i + 1) % vertexCount;
225 const Vertex &vs = vertices[i];
226 const Vertex &ve = vertices[j];
227
228 // If the line intersects a line segment strictly (proper cross section) the line is not in the polygon
229 if (Line::doesIntersectProperly(a, b, vs, ve))
230 return false;
231
232 // If one of the two line items is on the edge and the other is to the right of the edge,
233 // then the line is not completely within the polygon
234 if (Line::isOnLineStrict(vs, ve, a) && Line::isVertexRight(vs, ve, b))
235 return false;
236 if (Line::isOnLineStrict(vs, ve, b) && Line::isVertexRight(vs, ve, a))
237 return false;
238
239 // If one of the two line items is on a vertex, the line traces into the polygon
240 if ((a == vs) && !isLineInCone(i, b, true))
241 return false;
242 if ((b == vs) && !isLineInCone(i, a, true))
243 return false;
244 }
245
246 return true;
247 }
248
isLineExterior(const Vertex & a,const Vertex & b) const249 bool Polygon::isLineExterior(const Vertex &a, const Vertex &b) const {
250 // Neither of the two points must be strictly in the polygon (on the edge is allowed)
251 if (isPointInPolygon(a, false) || isPointInPolygon(b, false))
252 return false;
253
254 // If the points are identical, the line is trivially outside of the polygon
255 if (a == b)
256 return true;
257
258 // Test whether the line intersects a line segment strictly (proper intersection)
259 for (int i = 0; i < vertexCount; i++) {
260 int j = (i + 1) % vertexCount;
261 const Vertex &vs = vertices[i];
262 const Vertex &ve = vertices[j];
263
264 // If the line intersects a line segment strictly (proper intersection), then
265 // the line is partially inside the polygon
266 if (Line::doesIntersectProperly(a, b, vs, ve))
267 return false;
268
269 // If one of the two line items is on the edge and the other is to the right of the edge,
270 // the line is not completely outside the polygon
271 if (Line::isOnLineStrict(vs, ve, a) && Line::isVertexLeft(vs, ve, b))
272 return false;
273 if (Line::isOnLineStrict(vs, ve, b) && Line::isVertexLeft(vs, ve, a))
274 return false;
275
276 // If one of the lwo line items is on a vertex, the line must not run into the polygon
277 if ((a == vs) && isLineInCone(i, b, false))
278 return false;
279 if ((b == vs) && isLineInCone(i, a, false))
280 return false;
281
282 // If the vertex with start and end point is collinear, (a vs) and (b, vs) is not in the polygon
283 if (Line::isOnLine(a, b, vs)) {
284 if (isLineInCone(i, a, false))
285 return false;
286 if (isLineInCone(i, b, false))
287 return false;
288 }
289 }
290
291 return true;
292 }
293
isLineInCone(int startVertexIndex,const Vertex & endVertex,bool includeEdges) const294 bool Polygon::isLineInCone(int startVertexIndex, const Vertex &endVertex, bool includeEdges) const {
295 const Vertex &startVertex = vertices[startVertexIndex];
296 const Vertex &nextVertex = vertices[(startVertexIndex + 1) % vertexCount];
297 const Vertex &prevVertex = vertices[(startVertexIndex + vertexCount - 1) % vertexCount];
298
299 if (Line::isVertexLeftOn(prevVertex, startVertex, nextVertex)) {
300 if (includeEdges)
301 return Line::isVertexLeftOn(endVertex, startVertex, nextVertex) &&
302 Line::isVertexLeftOn(startVertex, endVertex, prevVertex);
303 else
304 return Line::isVertexLeft(endVertex, startVertex, nextVertex) &&
305 Line::isVertexLeft(startVertex, endVertex, prevVertex);
306 } else {
307 if (includeEdges)
308 return !(Line::isVertexLeft(endVertex, startVertex, prevVertex) &&
309 Line::isVertexLeft(startVertex, endVertex, nextVertex));
310 else
311 return !(Line::isVertexLeftOn(endVertex, startVertex, prevVertex) &&
312 Line::isVertexLeftOn(startVertex, endVertex, nextVertex));
313 }
314 }
315
316 // Point-Polygon Tests
317 // -------------------
318
isPointInPolygon(int x,int y,bool borderBelongsToPolygon) const319 bool Polygon::isPointInPolygon(int x, int y, bool borderBelongsToPolygon) const {
320 return isPointInPolygon(Vertex(x, y), borderBelongsToPolygon);
321 }
322
isPointInPolygon(const Vertex & point,bool edgesBelongToPolygon) const323 bool Polygon::isPointInPolygon(const Vertex &point, bool edgesBelongToPolygon) const {
324 int rcross = 0; // Number of right-side overlaps
325 int lcross = 0; // Number of left-side overlaps
326
327 // Each edge is checked whether it cuts the outgoing stream from the point
328 for (int i = 0; i < vertexCount; i++) {
329 const Vertex &edgeStart = vertices[i];
330 const Vertex &edgeEnd = vertices[(i + 1) % vertexCount];
331
332 // A vertex is a point? Then it lies on one edge of the polygon
333 if (point == edgeStart)
334 return edgesBelongToPolygon;
335
336 if ((edgeStart.y > point.y) != (edgeEnd.y > point.y)) {
337 int term1 = (edgeStart.x - point.x) * (edgeEnd.y - point.y) - (edgeEnd.x - point.x) * (edgeStart.y - point.y);
338 int term2 = (edgeEnd.y - point.y) - (edgeStart.y - edgeEnd.y);
339 if ((term1 > 0) == (term2 >= 0))
340 rcross++;
341 }
342
343 if ((edgeStart.y < point.y) != (edgeEnd.y < point.y)) {
344 int term1 = (edgeStart.x - point.x) * (edgeEnd.y - point.y) - (edgeEnd.x - point.x) * (edgeStart.y - point.y);
345 int term2 = (edgeEnd.y - point.y) - (edgeStart.y - edgeEnd.y);
346 if ((term1 < 0) == (term2 <= 0))
347 lcross++;
348 }
349 }
350
351 // The point is on an adge, if the number of left and right intersections have the same even numbers
352 if ((rcross % 2) != (lcross % 2))
353 return edgesBelongToPolygon;
354
355 // The point is strictly inside the polygon if and only if the number of overlaps is odd
356 if ((rcross % 2) == 1)
357 return true;
358 else
359 return false;
360 }
361
persist(OutputPersistenceBlock & writer)362 bool Polygon::persist(OutputPersistenceBlock &writer) {
363 writer.write(vertexCount);
364 for (int i = 0; i < vertexCount; ++i) {
365 writer.write((int32)vertices[i].x);
366 writer.write((int32)vertices[i].y);
367 }
368
369 return true;
370 }
371
unpersist(InputPersistenceBlock & reader)372 bool Polygon::unpersist(InputPersistenceBlock &reader) {
373 int32 storedvertexCount;
374 reader.read(storedvertexCount);
375
376 Common::Array<Vertex> storedvertices;
377 for (int i = 0; i < storedvertexCount; ++i) {
378 int32 x, y;
379 reader.read(x);
380 reader.read(y);
381 storedvertices.push_back(Vertex(x, y));
382 }
383
384 init(storedvertexCount, &storedvertices[0]);
385
386 return reader.isGood();
387 }
388
389 // Main Focus
390 // ----------
391
getCentroid() const392 Vertex Polygon::getCentroid() const {
393 return _centroid;
394 }
395
computeCentroid() const396 Vertex Polygon::computeCentroid() const {
397 // Area of the polygon is calculated
398 int doubleArea = 0;
399 for (int i = 0; i < vertexCount; ++i) {
400 doubleArea += vertices[i].x * vertices[i + 1].y - vertices[i + 1].x * vertices[i].y;
401 }
402
403 // Avoid division by zero in the next step
404 if (doubleArea == 0)
405 return Vertex();
406
407 // Calculate centroid
408 Vertex centroid;
409 for (int i = 0; i < vertexCount; ++i) {
410 int area = vertices[i].x * vertices[i + 1].y - vertices[i + 1].x * vertices[i].y;
411 centroid.x += (vertices[i].x + vertices[i + 1].x) * area;
412 centroid.y += (vertices[i].y + vertices[i + 1].y) * area;
413 }
414 centroid.x /= 3 * doubleArea;
415 centroid.y /= 3 * doubleArea;
416
417 return centroid;
418 }
419
420 } // End of namespace Sword25
421