ScummVM API documentation
line.h
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 modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (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, see <http://www.gnu.org/licenses/>.
19 *
20 */
21
22/*
23 * This code is based on Broken Sword 2.5 engine
24 *
25 * Copyright (c) Malte Thiesen, Daniel Queteschiner and Michael Elsdoerfer
26 *
27 * Licensed under GNU GPL v2
28 *
29 */
30
31/*
32 BS_Line
33 -------
34 This class contains only static methods, which have to do with straight line
35 segments. There is no real straight line segment class. Calculations will be
36 used with polygons, and it is important the process of starting and selecting
37 endpoints of lines is dynamic. This would prhobit a polygon from a set
38 being formed by fixed line segments
39
40 Autor: Malte Thiesen
41*/
42
43#ifndef SWORD25_LINE_H
44#define SWORD25_LINE_H
45
46#include "sword25/kernel/common.h"
47
48namespace Sword25 {
49
50class Line {
51public:
60 static bool isVertexLeft(const Vertex &a, const Vertex &b, const Vertex &c) {
61 return triangleArea2(a, b, c) > 0;
62 }
63
64 static bool isVertexLeftOn(const Vertex &a, const Vertex &b, const Vertex &c) {
65 return triangleArea2(a, b, c) >= 0;
66 }
67
76 static bool isVertexRight(const Vertex &a, const Vertex &b, const Vertex &c) {
77 return triangleArea2(a, b, c) < 0;
78 }
79
80 static bool isVertexRightOn(const Vertex &a, const Vertex &b, const Vertex &c) {
81 return triangleArea2(a, b, c) <= 0;
82 }
83
91 static bool isVertexOn(const Vertex &a, const Vertex &b, const Vertex &c) {
92 return triangleArea2(a, b, c) == 0;
93 }
94
95 enum VERTEX_CLASSIFICATION {
96 LEFT,
97 RIGHT,
98 ON
99 };
100
110 static VERTEX_CLASSIFICATION classifyVertexToLine(const Vertex &a, const Vertex &b, const Vertex &c) {
111 int area = triangleArea2(a, b, c);
112 if (area > 0) return LEFT;
113 if (area < 0) return RIGHT;
114 return ON;
115 }
116
125 static bool doesIntersectProperly(const Vertex &a, const Vertex &b, const Vertex &c, const Vertex &d) {
126 VERTEX_CLASSIFICATION class1 = classifyVertexToLine(a, b, c);
127 VERTEX_CLASSIFICATION class2 = classifyVertexToLine(a, b, d);
128 VERTEX_CLASSIFICATION class3 = classifyVertexToLine(c, d, a);
129 VERTEX_CLASSIFICATION class4 = classifyVertexToLine(c, d, b);
130
131 if (class1 == ON || class2 == ON || class3 == ON || class4 == ON) return false;
132
133 return ((class1 == LEFT) ^(class2 == LEFT)) && ((class3 == LEFT) ^(class4 == LEFT));
134 }
135
142 static bool isOnLine(const Vertex &a, const Vertex &b, const Vertex &c) {
143 // The items must all be Collinear, otherwise don't bothering testing the point
144 if (triangleArea2(a, b, c) != 0) return false;
145
146 // If the line segment is not vertical, check on the x-axis, otherwise the y-axis
147 if (a.x != b.x) {
148 return ((a.x <= c.x) &&
149 (c.x <= b.x)) ||
150 ((a.x >= c.x) &&
151 (c.x >= b.x));
152 } else {
153 return ((a.y <= c.y) &&
154 (c.y <= b.y)) ||
155 ((a.y >= c.y) &&
156 (c.y >= b.y));
157 }
158 }
159
160 static bool isOnLineStrict(const Vertex &a, const Vertex &b, const Vertex &c) {
161 // The items must all be Collinear, otherwise don't bothering testing the point
162 if (triangleArea2(a, b, c) != 0) return false;
163
164 // If the line segment is not vertical, check on the x-axis, otherwise the y-axis
165 if (a.x != b.x) {
166 return ((a.x < c.x) &&
167 (c.x < b.x)) ||
168 ((a.x > c.x) &&
169 (c.x > b.x));
170 } else {
171 return ((a.y < c.y) &&
172 (c.y < b.y)) ||
173 ((a.y > c.y) &&
174 (c.y > b.y));
175 }
176 }
177
178private:
185 static int triangleArea2(const Vertex &a, const Vertex &b, const Vertex &c) {
186 return a.x * b.y - a.y * b.x +
187 a.y * c.x - a.x * c.y +
188 b.x * c.y - c.x * b.y;
189 }
190};
191
192} // End of namespace Sword25
193
194#endif
Definition: line.h:50
static bool doesIntersectProperly(const Vertex &a, const Vertex &b, const Vertex &c, const Vertex &d)
Definition: line.h:125
static bool isVertexLeft(const Vertex &a, const Vertex &b, const Vertex &c)
Definition: line.h:60
static VERTEX_CLASSIFICATION classifyVertexToLine(const Vertex &a, const Vertex &b, const Vertex &c)
Definition: line.h:110
static bool isOnLine(const Vertex &a, const Vertex &b, const Vertex &c)
Definition: line.h:142
static bool isVertexOn(const Vertex &a, const Vertex &b, const Vertex &c)
Definition: line.h:91
static bool isVertexRight(const Vertex &a, const Vertex &b, const Vertex &c)
Definition: line.h:76
Definition: vertex.h:52
Definition: console.h:27
T y
Definition: rect.h:49
T x
Definition: rect.h:48
Definition: display_client.h:53