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
|
// SPDX-License-Identifier: GPL-2.0-or-later
/*
* Routines for dealing with lines (intersections, etc.)
*
* Authors:
* Maximilian Albert <Anhalter42@gmx.de>
*
* Copyright (C) 2007 authors
*
* Released under GNU GPL v2+, read the file 'COPYING' for more information.
*/
#include "line-geometry.h"
#include "desktop.h"
namespace Box3D {
/**
* Draw a line beginning at 'start'. If is_endpoint is true, use 'vec' as the endpoint
* of the segment. Otherwise interpret it as the direction of the line.
* FIXME: Think of a better way to distinguish between the two constructors of lines.
*/
Line::Line(Geom::Point const &start, Geom::Point const &vec, bool is_endpoint):
pt(start)
{
if (is_endpoint)
v_dir = vec - start;
else
v_dir = vec;
normal = v_dir.ccw();
d0 = Geom::dot(normal, pt);
}
Line::Line(Line const &line)
= default;
Line &Line::operator=(Line const &line) = default;
std::optional<Geom::Point> Line::intersect(Line const &line) {
Geom::Coord denom = Geom::dot(v_dir, line.normal);
std::optional<Geom::Point> no_point;
if (fabs(denom) < 1e-6)
return no_point;
Geom::Coord lambda = (line.d0 - Geom::dot(pt, line.normal)) / denom;
return pt + lambda * v_dir;
}
void Line::set_direction(Geom::Point const &dir)
{
v_dir = dir;
normal = v_dir.ccw();
d0 = Geom::dot(normal, pt);
}
Geom::Point Line::closest_to(Geom::Point const &pt)
{
/* return the intersection of this line with a perpendicular line passing through pt */
std::optional<Geom::Point> result = this->intersect(Line(pt, (this->v_dir).ccw(), false));
g_return_val_if_fail (result, Geom::Point (0.0, 0.0));
return *result;
}
double Line::lambda (Geom::Point const pt)
{
double sign = (Geom::dot (pt - this->pt, this->v_dir) > 0) ? 1.0 : -1.0;
double lambda = sign * Geom::L2 (pt - this->pt);
// FIXME: It may speed things up (but how much?) if we assume that
// pt lies on the line and thus skip the following test
Geom::Point test = point_from_lambda (lambda);
if (!pts_coincide (pt, test)) {
g_warning ("Point does not lie on line.\n");
return 0;
}
return lambda;
}
/* The coordinates of w with respect to the basis {v1, v2} */
std::pair<double, double> coordinates (Geom::Point const &v1, Geom::Point const &v2, Geom::Point const &w)
{
double det = determinant (v1, v2);;
if (fabs (det) < epsilon) {
// vectors are not linearly independent; we indicate this in the return value(s)
return std::make_pair (HUGE_VAL, HUGE_VAL);
}
double lambda1 = determinant (w, v2) / det;
double lambda2 = determinant (v1, w) / det;
return std::make_pair (lambda1, lambda2);
}
/* whether w lies inside the sector spanned by v1 and v2 */
bool lies_in_sector (Geom::Point const &v1, Geom::Point const &v2, Geom::Point const &w)
{
std::pair<double, double> coords = coordinates (v1, v2, w);
if (coords.first == HUGE_VAL) {
// catch the case that the vectors are not linearly independent
// FIXME: Can we assume that it's safe to return true if the vectors point in different directions?
return (Geom::dot (v1, v2) < 0);
}
return (coords.first >= 0 && coords.second >= 0);
}
bool lies_in_quadrangle (Geom::Point const &A, Geom::Point const &B, Geom::Point const &C, Geom::Point const &D, Geom::Point const &pt)
{
return (lies_in_sector (D - A, B - A, pt - A) && lies_in_sector (D - C, B - C, pt - C));
}
static double pos_angle (Geom::Point v, Geom::Point w)
{
return fabs (Geom::atan2 (v) - Geom::atan2 (w));
}
/*
* Returns the two corners of the quadrangle A, B, C, D spanning the edge that is hit by a semiline
* starting at pt and going into direction dir.
* If none of the sides is hit, it returns a pair containing two identical points.
*/
std::pair<Geom::Point, Geom::Point>
side_of_intersection (Geom::Point const &A, Geom::Point const &B, Geom::Point const &C, Geom::Point const &D,
Geom::Point const &pt, Geom::Point const &dir)
{
Geom::Point dir_A (A - pt);
Geom::Point dir_B (B - pt);
Geom::Point dir_C (C - pt);
Geom::Point dir_D (D - pt);
std::pair<Geom::Point, Geom::Point> result;
double angle = -1;
double tmp_angle;
if (lies_in_sector (dir_A, dir_B, dir)) {
result = std::make_pair (A, B);
angle = pos_angle (dir_A, dir_B);
}
if (lies_in_sector (dir_B, dir_C, dir)) {
tmp_angle = pos_angle (dir_B, dir_C);
if (tmp_angle > angle) {
angle = tmp_angle;
result = std::make_pair (B, C);
}
}
if (lies_in_sector (dir_C, dir_D, dir)) {
tmp_angle = pos_angle (dir_C, dir_D);
if (tmp_angle > angle) {
angle = tmp_angle;
result = std::make_pair (C, D);
}
}
if (lies_in_sector (dir_D, dir_A, dir)) {
tmp_angle = pos_angle (dir_D, dir_A);
if (tmp_angle > angle) {
angle = tmp_angle;
result = std::make_pair (D, A);
}
}
if (angle == -1) {
// no intersection found; return a pair containing two identical points
return std::make_pair (A, A);
} else {
return result;
}
}
std::optional<Geom::Point> Line::intersection_with_viewbox (SPDesktop *desktop)
{
auto vb = desktop->get_display_area();
std::pair <Geom::Point, Geom::Point> e = side_of_intersection (vb.corner(0), vb.corner(1), vb.corner(2), vb.corner(3), this->pt, this->v_dir);
if (e.first == e.second) {
// perspective line lies outside the canvas
return std::optional<Geom::Point>();
}
Line line (e.first, e.second);
return this->intersect (line);
}
} // namespace Box3D
/*
Local Variables:
mode:c++
c-file-style:"stroustrup"
c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
indent-tabs-mode:nil
fill-column:99
End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
|
