aboutsummaryrefslogtreecommitdiff
path: root/engines/sword25/math/polygon.cpp
blob: 9fcfd50158afd3a278f2a993ee123b7ace655a25 (plain)
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
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
/* 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
 *
 */

#include <math.h>

#include "sword25/kernel/outputpersistenceblock.h"
#include "sword25/kernel/inputpersistenceblock.h"

#include "sword25/math/polygon.h"
#include "sword25/math/line.h"

namespace Sword25 {

#define max(a,b) (((a) > (b)) ? (a) : (b))

// Constructor / Destructor
// --------------------------

Polygon::Polygon() : VertexCount(0), Vertecies(NULL) {
}

Polygon::Polygon(int VertexCount_, const Vertex *Vertecies_) : VertexCount(0), Vertecies(NULL) {
	Init(VertexCount_, Vertecies_);
}

Polygon::Polygon(const Polygon &Other) : VertexCount(0), Vertecies(NULL) {
	Init(Other.VertexCount, Other.Vertecies);
}

Polygon::Polygon(InputPersistenceBlock &Reader) : VertexCount(0), Vertecies(NULL) {
	unpersist(Reader);
}

Polygon::~Polygon() {
	delete[] Vertecies;
}

// Initialisation
// ---------------

bool Polygon::Init(int VertexCount_, const Vertex *Vertecies_) {
	// Rember the old obstate to restore it if an error occurs whilst initialising it with the new data
	int OldVertexCount = this->VertexCount;
	Vertex *OldVertecies = this->Vertecies;

	this->VertexCount = VertexCount_;
	this->Vertecies = new Vertex[VertexCount_ + 1];
	memcpy(this->Vertecies, Vertecies_, sizeof(Vertex) * VertexCount_);
	// TODO:
	// Duplicate and remove redundant vertecies (Superflous = 3 co-linear verts)
	// _WeedRepeatedVertecies();
	// The first vertex is repeated at the end of the vertex array; this simplifies
	// some algorithms, running through the edges and thus can save the overflow control.
	this->Vertecies[VertexCount_] = this->Vertecies[0];

	// If the polygon is self-intersecting, the object state is restore, and an error signalled
	if (CheckForSelfIntersection()) {
		delete[] this->Vertecies;
		this->Vertecies = OldVertecies;
		this->VertexCount = OldVertexCount;

		// BS_LOG_ERROR("POLYGON: Tried to create a self-intersecting polygon.\n");
		return false;
	}

	// Release old vertex list
	delete[] OldVertecies;

	// Calculate properties of the polygon
	m_IsCW = ComputeIsCW();
	m_IsConvex = ComputeIsConvex();
	m_Centroid = ComputeCentroid();

	return true;
}

// Review the order of the Vertecies
// ---------------------------------

bool Polygon::IsCW() const {
	return m_IsCW;
}

bool Polygon::IsCCW() const {
	return !IsCW();
}

bool Polygon::ComputeIsCW() const {
	if (VertexCount) {
		// Find the vertex on extreme bottom right
		int V2Index = FindLRVertexIndex();

		// Find the vertex before and after it
		int V1Index = (V2Index + (VertexCount - 1)) % VertexCount;
		int V3Index = (V2Index + 1) % VertexCount;

		// Cross product form
		// If the cross product of the vertex lying fartherest bottom left is positive,
		// the vertecies arrranged in a clockwise order. Otherwise counter-clockwise
		if (CrossProduct(Vertecies[V1Index], Vertecies[V2Index], Vertecies[V3Index]) >= 0) return true;
	}

	return false;
}

int Polygon::FindLRVertexIndex() const {
	if (VertexCount) {
		int CurIndex = 0;
		int MaxX = Vertecies[0].X;
		int MaxY = Vertecies[0].Y;

		for (int i = 1; i < VertexCount; i++) {
			if (Vertecies[i].Y > MaxY ||
			        (Vertecies[i].Y == MaxY && Vertecies[i].X > MaxX)) {
				MaxX = Vertecies[i].X;
				MaxY = Vertecies[i].Y;
				CurIndex = i;
			}
		}

		return CurIndex;
	}

	return -1;
}

// Testing for Convex / Concave
// ------------------------

bool Polygon::IsConvex() const {
	return m_IsConvex;
}

bool Polygon::IsConcave() const {
	return !IsConvex();
}

bool Polygon::ComputeIsConvex() const {
	// Polygons with three or less Vertecies can only be convex
	if (VertexCount <= 3) return true;

	// All angles in the polygon computed will have the same direction sign if the polygon is convex
	int Flag = 0;
	for (int i = 0; i < VertexCount; i++) {
		// Determine the next two vertecies to check
		int j = (i + 1) % VertexCount;
		int k = (i + 2) % VertexCount;

		// Calculate the cross product of the three vertecies
		int Cross = CrossProduct(Vertecies[i], Vertecies[j], Vertecies[k]);

		// The lower two bits of the flag represent the following:
		// 0: negative angle occurred
		// 1: positive angle occurred

		// The sign of the current angle is recorded in Flag
		if (Cross < 0)
			Flag |= 1;
		else if (Cross > 0)
			Flag |= 2;

		// If flag is 3, there are both positive and negative angles; so the polygon is concave
		if (Flag == 3) return false;
	}

	// Polygon is convex
	return true;
}

// Make a determine vertex order
// -----------------------------

void Polygon::EnsureCWOrder() {
	if (!IsCW())
		ReverseVertexOrder();
}

void Polygon::EnsureCCWOrder() {
	if (!IsCCW())
		ReverseVertexOrder();
}

// Reverse the order of vertecies
// ------------------------------

void Polygon::ReverseVertexOrder() {
	// Vertecies are exchanged in pairs, until the list has been completely reversed
	for (int i = 0; i < VertexCount / 2; i++) {
		Vertex tempVertex = Vertecies[i];
		Vertecies[i] = Vertecies[VertexCount - i - 1];
		Vertecies[VertexCount - i - 1] = tempVertex;
	}

	// Vertexordnung neu berechnen.
	m_IsCW = ComputeIsCW();
}

// Cross Product
// -------------

int Polygon::CrossProduct(const Vertex &V1, const Vertex &V2, const Vertex &V3) const {
	return (V2.X - V1.X) * (V3.Y - V2.Y) -
	       (V2.Y - V1.Y) * (V3.X - V2.X);
}

// Scalar Product
// --------------

int Polygon::DotProduct(const Vertex &V1, const Vertex &V2, const Vertex &V3) const {
	return (V1.X - V2.X) * (V3.X - V2.X) +
	       (V1.Y - V2.Y) * (V3.X - V2.Y);
}

// Check for self-intersections
// ----------------------------

bool Polygon::CheckForSelfIntersection() const {
	// TODO: Finish this
	/*
	float AngleSum = 0.0f;
	for (int i = 0; i < VertexCount; i++) {
	    int j = (i + 1) % VertexCount;
	    int k = (i + 2) % VertexCount;

	    float Dot = DotProduct(Vertecies[i], Vertecies[j], Vertecies[k]);

	    // Skalarproduct normalisieren
	    float Length1 = sqrt((Vertecies[i].X - Vertecies[j].X) * (Vertecies[i].X - Vertecies[j].X) +
	                         (Vertecies[i].Y - Vertecies[j].Y) * (Vertecies[i].Y - Vertecies[j].Y));
	    float Length2 = sqrt((Vertecies[k].X - Vertecies[j].X) * (Vertecies[k].X - Vertecies[j].X) +
	                         (Vertecies[k].Y - Vertecies[j].Y) * (Vertecies[k].Y - Vertecies[j].Y));
	    float Norm = Length1 * Length2;

	    if (Norm > 0.0f) {
	        Dot /= Norm;
	        AngleSum += acos(Dot);
	    }
	}
	*/

	return false;
}

// Move
// ----

void Polygon::operator+=(const Vertex &Delta) {
	// Move all vertecies
	for (int i = 0; i < VertexCount; i++)
		Vertecies[i] += Delta;

	// Shift the focus
	m_Centroid += Delta;
}

// Line of Sight
// -------------

bool Polygon::IsLineInterior(const Vertex &a, const Vertex &b) const {
	// Both points have to be in the polygon
	if (!IsPointInPolygon(a, true) || !IsPointInPolygon(b, true)) return false;

	// If the points are identical, the line is trivially within the polygon
	if (a == b) return true;

	// Test whether the line intersects a line segment strictly (proper intersection)
	for (int i = 0; i < VertexCount; i++) {
		int j = (i + 1) % VertexCount;
		const Vertex &VS = Vertecies[i];
		const Vertex &VE = Vertecies[j];

		// If the line intersects a line segment strictly (proper cross section) the line is not in the polygon
		if (Line::DoesIntersectProperly(a, b, VS, VE)) return false;

		// If one of the two line items is on the edge and the other is to the right of the edge,
		// then the line is not completely within the polygon
		if (Line::IsOnLineStrict(VS, VE, a) && Line::IsVertexRight(VS, VE, b)) return false;
		if (Line::IsOnLineStrict(VS, VE, b) && Line::IsVertexRight(VS, VE, a)) return false;

		// If one of the two line items is on a vertex, the line traces into the polygon
		if ((a == VS) && !IsLineInCone(i, b, true)) return false;
		if ((b == VS) && !IsLineInCone(i, a, true)) return false;
	}

	return true;
}

bool Polygon::IsLineExterior(const Vertex &a, const Vertex &b) const {
	// Neither of the two points must be strictly in the polygon (on the edge is allowed)
	if (IsPointInPolygon(a, false) || IsPointInPolygon(b, false)) return false;

	// If the points are identical, the line is trivially outside of the polygon
	if (a == b) return true;

	// Test whether the line intersects a line segment strictly (proper intersection)
	for (int i = 0; i < VertexCount; i++) {
		int j = (i + 1) % VertexCount;
		const Vertex &VS = Vertecies[i];
		const Vertex &VE = Vertecies[j];

		// If the line intersects a line segment strictly (proper intersection), then
		// the line is partially inside the polygon
		if (Line::DoesIntersectProperly(a, b, VS, VE)) return false;

		// If one of the two line items is on the edge and the other is to the right of the edge,
		// the line is not completely outside the polygon
		if (Line::IsOnLineStrict(VS, VE, a) && Line::IsVertexLeft(VS, VE, b)) return false;
		if (Line::IsOnLineStrict(VS, VE, b) && Line::IsVertexLeft(VS, VE, a)) return false;

		// If one of the lwo line items is on a vertex, the line must not run into the polygon
		if ((a == VS) && IsLineInCone(i, b, false)) return false;
		if ((b == VS) && IsLineInCone(i, a, false)) return false;

		// If the vertex with start and end point is collinear, (a VS) and (b, VS) is not in the polygon
		if (Line::IsOnLine(a, b, VS)) {
			if (IsLineInCone(i, a, false)) return false;
			if (IsLineInCone(i, b, false)) return false;
		}
	}

	return true;
}

bool Polygon::IsLineInCone(int StartVertexIndex, const Vertex &EndVertex, bool IncludeEdges) const {
	const Vertex &StartVertex = Vertecies[StartVertexIndex];
	const Vertex &NextVertex = Vertecies[(StartVertexIndex + 1) % VertexCount];
	const Vertex &PrevVertex = Vertecies[(StartVertexIndex + VertexCount - 1) % VertexCount];

	if (Line::IsVertexLeftOn(PrevVertex, StartVertex, NextVertex)) {
		if (IncludeEdges)
			return Line::IsVertexLeftOn(EndVertex, StartVertex, NextVertex) &&
			       Line::IsVertexLeftOn(StartVertex, EndVertex, PrevVertex);
		else
			return Line::IsVertexLeft(EndVertex, StartVertex, NextVertex) &&
			       Line::IsVertexLeft(StartVertex, EndVertex, PrevVertex);
	} else {
		if (IncludeEdges)
			return !(Line::IsVertexLeft(EndVertex, StartVertex, PrevVertex) &&
			         Line::IsVertexLeft(StartVertex, EndVertex, NextVertex));
		else
			return !(Line::IsVertexLeftOn(EndVertex, StartVertex, PrevVertex) &&
			         Line::IsVertexLeftOn(StartVertex, EndVertex, NextVertex));
	}
}

// Point-Polygon Tests
// -------------------

bool Polygon::IsPointInPolygon(int X, int Y, bool BorderBelongsToPolygon) const {
	return IsPointInPolygon(Vertex(X, Y), BorderBelongsToPolygon);
}

bool Polygon::IsPointInPolygon(const Vertex &Point, bool EdgesBelongToPolygon) const {
	int Rcross = 0; // Number of right-side overlaps
	int Lcross = 0; // Number of left-side overlaps

	// Each edge is checked whether it cuts the outgoing stream from the point
	for (int i = 0; i < VertexCount; i++) {
		const Vertex &EdgeStart = Vertecies[i];
		const Vertex &EdgeEnd = Vertecies[(i + 1) % VertexCount];

		// A vertex is a point? Then it lies on one edge of the polygon
		if (Point == EdgeStart) return EdgesBelongToPolygon;

		if ((EdgeStart.Y > Point.Y) != (EdgeEnd.Y > Point.Y)) {
			int Term1 = (EdgeStart.X - Point.X) * (EdgeEnd.Y - Point.Y) - (EdgeEnd.X - Point.X) * (EdgeStart.Y - Point.Y);
			int Term2 = (EdgeEnd.Y - Point.Y) - (EdgeStart.Y - EdgeEnd.Y);
			if ((Term1 > 0) == (Term2 >= 0)) Rcross++;
		}

		if ((EdgeStart.Y < Point.Y) != (EdgeEnd.Y < Point.Y)) {
			int Term1 = (EdgeStart.X - Point.X) * (EdgeEnd.Y - Point.Y) - (EdgeEnd.X - Point.X) * (EdgeStart.Y - Point.Y);
			int Term2 = (EdgeEnd.Y - Point.Y) - (EdgeStart.Y - EdgeEnd.Y);
			if ((Term1 < 0) == (Term2 <= 0)) Lcross++;
		}
	}

	// The point is on an adge, if the number of left and right intersections have the same even numbers
	if ((Rcross % 2) != (Lcross % 2)) return EdgesBelongToPolygon;

	// The point is strictly inside the polygon if and only if the number of overlaps is odd
	if ((Rcross % 2) == 1) return true;
	else return false;
}

bool Polygon::persist(OutputPersistenceBlock &writer) {
	writer.write(VertexCount);
	for (int i = 0; i < VertexCount; ++i) {
		writer.write(Vertecies[i].X);
		writer.write(Vertecies[i].Y);
	}

	return true;
}

bool Polygon::unpersist(InputPersistenceBlock &reader) {
	int StoredVertexCount;
	reader.read(StoredVertexCount);

	Common::Array<Vertex> StoredVertecies;
	for (int i = 0; i < StoredVertexCount; ++i) {
		int x, y;
		reader.read(x);
		reader.read(y);
		StoredVertecies.push_back(Vertex(x, y));
	}

	Init(StoredVertexCount, &StoredVertecies[0]);

	return reader.isGood();
}

// Main Focus
// ----------

Vertex Polygon::GetCentroid() const {
	return m_Centroid;
}

Vertex Polygon::ComputeCentroid() const {
	// Area of the polygon is calculated
	int DoubleArea = 0;
	for (int i = 0; i < VertexCount; ++i) {
		DoubleArea += Vertecies[i].X * Vertecies[i + 1].Y - Vertecies[i + 1].X * Vertecies[i].Y;
	}

	// Avoid division by zero in the next step
	if (DoubleArea == 0) return Vertex();

	// Calculate centroid
	Vertex Centroid;
	for (int i = 0; i < VertexCount; ++i) {
		int Area = Vertecies[i].X * Vertecies[i + 1].Y - Vertecies[i + 1].X * Vertecies[i].Y;
		Centroid.X += (Vertecies[i].X + Vertecies[i + 1].X) * Area;
		Centroid.Y += (Vertecies[i].Y + Vertecies[i + 1].Y) * Area;
	}
	Centroid.X /= 3 * DoubleArea;
	Centroid.Y /= 3 * DoubleArea;

	return Centroid;
}

} // End of namespace Sword25