1 #define __LINE_GEOMETRY_C__
3 /*
4 * Routines for dealing with lines (intersections, etc.)
5 *
6 * Authors:
7 * Maximilian Albert <Anhalter42@gmx.de>
8 *
9 * Copyright (C) 2007 authors
10 *
11 * Released under GNU GPL, read the file 'COPYING' for more information
12 */
14 #include "line-geometry.h"
15 #include "inkscape.h"
16 #include "desktop-style.h"
17 #include "desktop-handles.h"
18 #include "display/sp-canvas.h"
19 #include "display/sodipodi-ctrl.h"
20 //#include "display/curve.cpp"
22 namespace Box3D {
24 /**
25 * Draw a line beginning at 'start'. If is_endpoint is true, use 'vec' as the endpoint
26 * of the segment. Otherwise interpret it as the direction of the line.
27 * FIXME: Think of a better way to distinguish between the two constructors of lines.
28 */
29 Line::Line(NR::Point const &start, NR::Point const &vec, bool is_endpoint) {
30 pt = start;
31 if (is_endpoint)
32 v_dir = vec - start;
33 else
34 v_dir = vec;
35 normal = v_dir.ccw();
36 d0 = NR::dot(normal, pt);
37 }
39 Line::Line(Line const &line) {
40 pt = line.pt;
41 v_dir = line.v_dir;
42 normal = line.normal;
43 d0 = line.d0;
44 }
46 Line &Line::operator=(Line const &line) {
47 pt = line.pt;
48 v_dir = line.v_dir;
49 normal = line.normal;
50 d0 = line.d0;
52 return *this;
53 }
55 NR::Maybe<NR::Point> Line::intersect(Line const &line) {
56 NR::Coord denom = NR::dot(v_dir, line.normal);
57 NR::Maybe<NR::Point> no_point = NR::Nothing();
58 if (fabs(denom) < 1e-6)
59 return no_point;
61 NR::Coord lambda = (line.d0 - NR::dot(pt, line.normal)) / denom;
62 return pt + lambda * v_dir;
63 }
65 void Line::set_direction(NR::Point const &dir)
66 {
67 v_dir = dir;
68 normal = v_dir.ccw();
69 d0 = NR::dot(normal, pt);
70 }
72 NR::Point Line::closest_to(NR::Point const &pt)
73 {
74 /* return the intersection of this line with a perpendicular line passing through pt */
75 NR::Maybe<NR::Point> result = this->intersect(Line(pt, (this->v_dir).ccw(), false));
76 g_return_val_if_fail (result, NR::Point (0.0, 0.0));
77 return *result;
78 }
80 double Line::lambda (NR::Point const pt)
81 {
82 double sign = (NR::dot (pt - this->pt, this->v_dir) > 0) ? 1.0 : -1.0;
83 double lambda = sign * NR::L2 (pt - this->pt);
84 // FIXME: It may speed things up (but how much?) if we assume that
85 // pt lies on the line and thus skip the following test
86 NR::Point test = point_from_lambda (lambda);
87 if (!pts_coincide (pt, test)) {
88 g_warning ("Point does not lie on line.\n");
89 return 0;
90 }
91 return lambda;
92 }
94 inline static double determinant (NR::Point const &a, NR::Point const &b)
95 {
96 return (a[NR::X] * b[NR::Y] - a[NR::Y] * b[NR::X]);
97 }
99 /* The coordinates of w with respect to the basis {v1, v2} */
100 std::pair<double, double> coordinates (NR::Point const &v1, NR::Point const &v2, NR::Point const &w)
101 {
102 double det = determinant (v1, v2);;
103 if (fabs (det) < epsilon) {
104 // vectors are not linearly independent; we indicate this in the return value(s)
105 return std::make_pair (HUGE_VAL, HUGE_VAL);
106 }
108 double lambda1 = determinant (w, v2) / det;
109 double lambda2 = determinant (v1, w) / det;
110 return std::make_pair (lambda1, lambda2);
111 }
113 /* whether w lies inside the sector spanned by v1 and v2 */
114 bool lies_in_sector (NR::Point const &v1, NR::Point const &v2, NR::Point const &w)
115 {
116 std::pair<double, double> coords = coordinates (v1, v2, w);
117 if (coords.first == HUGE_VAL) {
118 // catch the case that the vectors are not linearly independent
119 // FIXME: Can we assume that it's safe to return true if the vectors point in different directions?
120 return (NR::dot (v1, v2) < 0);
121 }
122 return (coords.first >= 0 and coords.second >= 0);
123 }
125 bool lies_in_quadrangle (NR::Point const &A, NR::Point const &B, NR::Point const &C, NR::Point const &D, NR::Point const &pt)
126 {
127 return (lies_in_sector (D - A, B - A, pt - A) && lies_in_sector (D - C, B - C, pt - C));
128 }
130 static double pos_angle (NR::Point v, NR::Point w)
131 {
132 return fabs (NR::atan2 (v) - NR::atan2 (w));
133 }
135 /*
136 * Returns the two corners of the quadrangle A, B, C, D spanning the edge that is hit by a semiline
137 * starting at pt and going into direction dir.
138 * If none of the sides is hit, it returns a pair containing two identical points.
139 */
140 std::pair<NR::Point, NR::Point>
141 side_of_intersection (NR::Point const &A, NR::Point const &B, NR::Point const &C, NR::Point const &D,
142 NR::Point const &pt, NR::Point const &dir)
143 {
144 NR::Point dir_A (A - pt);
145 NR::Point dir_B (B - pt);
146 NR::Point dir_C (C - pt);
147 NR::Point dir_D (D - pt);
149 std::pair<NR::Point, NR::Point> result;
150 double angle = -1;
151 double tmp_angle;
153 if (lies_in_sector (dir_A, dir_B, dir)) {
154 result = std::make_pair (A, B);
155 angle = pos_angle (dir_A, dir_B);
156 }
157 if (lies_in_sector (dir_B, dir_C, dir)) {
158 tmp_angle = pos_angle (dir_B, dir_C);
159 if (tmp_angle > angle) {
160 angle = tmp_angle;
161 result = std::make_pair (B, C);
162 }
163 }
164 if (lies_in_sector (dir_C, dir_D, dir)) {
165 tmp_angle = pos_angle (dir_C, dir_D);
166 if (tmp_angle > angle) {
167 angle = tmp_angle;
168 result = std::make_pair (C, D);
169 }
170 }
171 if (lies_in_sector (dir_D, dir_A, dir)) {
172 tmp_angle = pos_angle (dir_D, dir_A);
173 if (tmp_angle > angle) {
174 angle = tmp_angle;
175 result = std::make_pair (D, A);
176 }
177 }
178 if (angle == -1) {
179 // no intersection found; return a pair containing two identical points
180 return std::make_pair (A, A);
181 } else {
182 return result;
183 }
184 }
186 double cross_ratio (NR::Point const &A, NR::Point const &B, NR::Point const &C, NR::Point const &D)
187 {
188 Line line (A, D);
189 double lambda_A = line.lambda (A);
190 double lambda_B = line.lambda (B);
191 double lambda_C = line.lambda (C);
192 double lambda_D = line.lambda (D);
194 if (fabs (lambda_D - lambda_A) < epsilon || fabs (lambda_C - lambda_B) < epsilon) {
195 // We return NR_HUGE so that we can catch this case in the calling functions
196 return NR_HUGE;
197 }
198 return (((lambda_C - lambda_A) / (lambda_D - lambda_A)) * ((lambda_D - lambda_B) / (lambda_C - lambda_B)));
199 }
201 double cross_ratio (VanishingPoint const &V, NR::Point const &B, NR::Point const &C, NR::Point const &D)
202 {
203 if (V.is_finite()) {
204 return cross_ratio (V.get_pos(), B, C, D);
205 } else {
206 if (B == D) {
207 // catch this case so that the line BD below is non-degenerate
208 return 0;
209 }
210 Line line (B, D);
211 double lambda_B = line.lambda (B);
212 double lambda_C = line.lambda (C);
213 double lambda_D = line.lambda (D);
215 if (fabs (lambda_C - lambda_B) < epsilon) {
216 // We return NR_HUGE so that we can catch this case in the calling functions
217 return NR_HUGE;
218 }
219 return (lambda_D - lambda_B) / (lambda_C - lambda_B);
220 }
221 }
223 NR::Point fourth_pt_with_given_cross_ratio (NR::Point const &A, NR::Point const &C, NR::Point const &D, double gamma)
224 {
225 Line line (A, D);
226 double lambda_A = line.lambda (A);
227 double lambda_C = line.lambda (C);
228 double lambda_D = line.lambda (D);
230 double beta = (lambda_C - lambda_A) / (lambda_D - lambda_A);
231 if (fabs (beta - gamma) < epsilon) {
232 // FIXME: How to handle the case when the point can't be computed?
233 // g_warning ("Cannot compute point with given cross ratio.\n");
234 return NR::Point (0.0, 0.0);
235 }
236 return line.point_from_lambda ((beta * lambda_D - gamma * lambda_C) / (beta - gamma));
237 }
239 void create_canvas_point(NR::Point const &pos, double size, guint32 rgba)
240 {
241 SPDesktop *desktop = inkscape_active_desktop();
242 SPCanvasItem * canvas_pt = sp_canvas_item_new(sp_desktop_controls(desktop), SP_TYPE_CTRL,
243 "size", size,
244 "filled", 1,
245 "fill_color", rgba,
246 "stroked", 1,
247 "stroke_color", 0x000000ff,
248 NULL);
249 SP_CTRL(canvas_pt)->moveto(pos);
250 }
252 void create_canvas_line(NR::Point const &p1, NR::Point const &p2, guint32 rgba)
253 {
254 SPDesktop *desktop = inkscape_active_desktop();
255 SPCanvasItem *line = sp_canvas_item_new(sp_desktop_controls(desktop),
256 SP_TYPE_CTRLLINE, NULL);
257 sp_ctrlline_set_coords(SP_CTRLLINE(line), p1, p2);
258 sp_ctrlline_set_rgba32 (SP_CTRLLINE(line), rgba);
259 sp_canvas_item_show (line);
260 }
262 } // namespace Box3D
264 /*
265 Local Variables:
266 mode:c++
267 c-file-style:"stroustrup"
268 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
269 indent-tabs-mode:nil
270 fill-column:99
271 End:
272 */
273 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :