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
|
/* 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.
*
*/
/*
* This code is based on Broken Sword 2.5 engine
*
* Copyright (c) Malte Thiesen, Daniel Queteschiner and Michael Elsdoerfer
*
* Licensed under GNU GPL v2
*
*/
/*
BS_Line
-------
This class contains only static methods, which have to do with straight line
segments. There is no real straight line segment class. Calculations will be
used with polygons, and it is important the process of starting and selecting
endpoints of lines is dynamic. This would prhobit a polygon from a set
being formed by fixed line segments
Autor: Malte Thiesen
*/
#ifndef SWORD25_LINE_H
#define SWORD25_LINE_H
#include "sword25/kernel/common.h"
namespace Sword25 {
class Line {
public:
/**
* Determines whether a piont is left of a line
* @param a The start point of a line
* @param b The end point of a line
* @param c The test point
* @return Returns true if the point is to the left of the line.
* If the point is to the right of the line or on the line, false is returned.
*/
static bool isVertexLeft(const Vertex &a, const Vertex &b, const Vertex &c) {
return triangleArea2(a, b, c) > 0;
}
static bool isVertexLeftOn(const Vertex &a, const Vertex &b, const Vertex &c) {
return triangleArea2(a, b, c) >= 0;
}
/**
* Determines whether a piont is right of a line
* @param a The start point of a line
* @param b The end point of a line
* @param c The test point
* @return Returns true if the point is to the right of the line.
* If the point is to the right of the line or on the line, false is returned.
*/
static bool isVertexRight(const Vertex &a, const Vertex &b, const Vertex &c) {
return triangleArea2(a, b, c) < 0;
}
static bool isVertexRightOn(const Vertex &a, const Vertex &b, const Vertex &c) {
return triangleArea2(a, b, c) <= 0;
}
/**
* Determines whether a piont is on a line
* @param a The start point of a line
* @param b The end point of a line
* @param c The test point
* @return Returns true if the point is on the line, false otherwise.
*/
static bool isVertexOn(const Vertex &a, const Vertex &b, const Vertex &c) {
return triangleArea2(a, b, c) == 0;
}
enum VERTEX_CLASSIFICATION {
LEFT,
RIGHT,
ON
};
/**
* Determines where a point is relative to a line.
* @param a The start point of a line
* @param b The end point of a line
* @param c The test point
* @return LEFT is returned if the point is to the left of the line.
* RIGHT is returned if the point is to the right of the line.
* ON is returned if the point is on the line.
*/
static VERTEX_CLASSIFICATION classifyVertexToLine(const Vertex &a, const Vertex &b, const Vertex &c) {
int area = triangleArea2(a, b, c);
if (area > 0) return LEFT;
if (area < 0) return RIGHT;
return ON;
}
/**
* Determines whether two lines intersect
* @param a The start point of the first line
* @param b The end point of the first line
* @param c The start point of the second line
* @param d The end point of the second line
* @remark In cases where a line only touches the other, false is returned (improper intersection)
*/
static bool doesIntersectProperly(const Vertex &a, const Vertex &b, const Vertex &c, const Vertex &d) {
VERTEX_CLASSIFICATION class1 = classifyVertexToLine(a, b, c);
VERTEX_CLASSIFICATION class2 = classifyVertexToLine(a, b, d);
VERTEX_CLASSIFICATION class3 = classifyVertexToLine(c, d, a);
VERTEX_CLASSIFICATION class4 = classifyVertexToLine(c, d, b);
if (class1 == ON || class2 == ON || class3 == ON || class4 == ON) return false;
return ((class1 == LEFT) ^(class2 == LEFT)) && ((class3 == LEFT) ^(class4 == LEFT));
}
/**
* Determines whether a point is on a line segment
* @param a The start point of a line
* @param b The end point of a line
* @param c The test point
*/
static bool isOnLine(const Vertex &a, const Vertex &b, const Vertex &c) {
// The items must all be Collinear, otherwise don't bothering testing the point
if (triangleArea2(a, b, c) != 0) return false;
// If the line segment is not vertical, check on the x-axis, otherwise the y-axis
if (a.x != b.x) {
return ((a.x <= c.x) &&
(c.x <= b.x)) ||
((a.x >= c.x) &&
(c.x >= b.x));
} else {
return ((a.y <= c.y) &&
(c.y <= b.y)) ||
((a.y >= c.y) &&
(c.y >= b.y));
}
}
static bool isOnLineStrict(const Vertex &a, const Vertex &b, const Vertex &c) {
// The items must all be Collinear, otherwise don't bothering testing the point
if (triangleArea2(a, b, c) != 0) return false;
// If the line segment is not vertical, check on the x-axis, otherwise the y-axis
if (a.x != b.x) {
return ((a.x < c.x) &&
(c.x < b.x)) ||
((a.x > c.x) &&
(c.x > b.x));
} else {
return ((a.y < c.y) &&
(c.y < b.y)) ||
((a.y > c.y) &&
(c.y > b.y));
}
}
private:
/**
* Return double the size of the triangle defined by the three passed points.
*
* The result is positive if the points are arrange counterclockwise,
* and negative if they are arranged counter-clockwise.
*/
static int triangleArea2(const Vertex &a, const Vertex &b, const Vertex &c) {
return a.x * b.y - a.y * b.x +
a.y * c.x - a.x * c.y +
b.x * c.y - c.x * b.y;
}
};
} // End of namespace Sword25
#endif
|
