← Back to branch summary

~valavanisalex/ubuntu/oneiric/inkscape/inkscape_0.48.1-2ubuntu4

« back to all changes in this revision

Viewing changes to src/line-geometry.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook, Kees Cook, Ted Gould
  • Date: 2008-02-10 14:20:16 UTC
  • mfrom: (1.1.6 upstream)
  • Revision ID: james.westby@ubuntu.com-20080210142016-vcnb2zqyhszu0xvb
Tags: 0.46~pre1-0ubuntu1
https://launchpad.net/bugs/183547
[ Kees Cook ]
* debian/control:
  - add libgtkspell-dev build-dep to gain GtkSpell features (LP: #183547).
  - update Standards version (no changes needed).
  - add Vcs and Homepage fields.
  - switch to new python-lxml dep.
* debian/{control,rules}: switch from dpatch to quilt for more sanity.
* debian/patches/20_fix_glib_and_gxx43_ftbfs.patch:
  - merged against upstream fixes.
  - added additional fixes for newly written code.
* debian/rules: enable parallel building.

[ Ted Gould ]
* Updating POTFILES.in to make it so things build correctly.
* debian/control:
  - add ImageMagick++ and libboost-dev to build-deps

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/line-geometry.cpp
 
1
#define __LINE_GEOMETRY_C__
 
2
 
 
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
 */
 
13
 
 
14
#include "line-geometry.h"
 
15
#include "inkscape.h"
 
16
#include "desktop.h"
 
17
#include "desktop-style.h"
 
18
#include "desktop-handles.h"
 
19
#include "display/sp-canvas.h"
 
20
#include "display/sodipodi-ctrl.h"
 
21
 
 
22
namespace Box3D {
 
23
 
 
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
}
 
38
 
 
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
}
 
45
 
 
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;
 
51
 
 
52
    return *this;
 
53
}
 
54
 
 
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;
 
60
 
 
61
    NR::Coord lambda = (line.d0 - NR::dot(pt, line.normal)) / denom;
 
62
    return pt + lambda * v_dir;
 
63
}
 
64
 
 
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
}
 
71
 
 
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
}
 
79
 
 
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
}
 
93
 
 
94
/* The coordinates of w with respect to the basis {v1, v2} */
 
95
std::pair<double, double> coordinates (NR::Point const &v1, NR::Point const &v2, NR::Point const &w)
 
96
{
 
97
    double det = determinant (v1, v2);;
 
98
    if (fabs (det) < epsilon) {
 
99
        // vectors are not linearly independent; we indicate this in the return value(s)
 
100
        return std::make_pair (HUGE_VAL, HUGE_VAL);
 
101
    }
 
102
 
 
103
    double lambda1 = determinant (w, v2) / det;
 
104
    double lambda2 = determinant (v1, w) / det;
 
105
    return std::make_pair (lambda1, lambda2);
 
106
}
 
107
 
 
108
/* whether w lies inside the sector spanned by v1 and v2 */
 
109
bool lies_in_sector (NR::Point const &v1, NR::Point const &v2, NR::Point const &w)
 
110
{
 
111
    std::pair<double, double> coords = coordinates (v1, v2, w);
 
112
    if (coords.first == HUGE_VAL) {
 
113
        // catch the case that the vectors are not linearly independent
 
114
        // FIXME: Can we assume that it's safe to return true if the vectors point in different directions?
 
115
        return (NR::dot (v1, v2) < 0);
 
116
    }
 
117
    return (coords.first >= 0 and coords.second >= 0);
 
118
}
 
119
 
 
120
bool lies_in_quadrangle (NR::Point const &A, NR::Point const &B, NR::Point const &C, NR::Point const &D, NR::Point const &pt)
 
121
{
 
122
    return (lies_in_sector (D - A, B - A, pt - A) && lies_in_sector (D - C, B - C, pt - C));
 
123
}
 
124
 
 
125
static double pos_angle (NR::Point v, NR::Point w)
 
126
{
 
127
    return fabs (NR::atan2 (v) - NR::atan2 (w));
 
128
}
 
129
 
 
130
/*
 
131
 * Returns the two corners of the quadrangle A, B, C, D spanning the edge that is hit by a semiline
 
132
 * starting at pt and going into direction dir.
 
133
 * If none of the sides is hit, it returns a pair containing two identical points.
 
134
 */
 
135
std::pair<NR::Point, NR::Point>
 
136
side_of_intersection (NR::Point const &A, NR::Point const &B, NR::Point const &C, NR::Point const &D,
 
137
                      NR::Point const &pt, NR::Point const &dir)
 
138
{
 
139
    NR::Point dir_A (A - pt);
 
140
    NR::Point dir_B (B - pt);
 
141
    NR::Point dir_C (C - pt);
 
142
    NR::Point dir_D (D - pt);
 
143
 
 
144
    std::pair<NR::Point, NR::Point> result;
 
145
    double angle = -1;
 
146
    double tmp_angle;
 
147
 
 
148
    if (lies_in_sector (dir_A, dir_B, dir)) {
 
149
        result = std::make_pair (A, B);
 
150
        angle = pos_angle (dir_A, dir_B);
 
151
    }
 
152
    if (lies_in_sector (dir_B, dir_C, dir)) {
 
153
        tmp_angle = pos_angle (dir_B, dir_C);
 
154
        if (tmp_angle > angle) {
 
155
            angle = tmp_angle;
 
156
            result = std::make_pair (B, C);
 
157
        }
 
158
    }
 
159
    if (lies_in_sector (dir_C, dir_D, dir)) {
 
160
        tmp_angle = pos_angle (dir_C, dir_D);
 
161
        if (tmp_angle > angle) {
 
162
            angle = tmp_angle;
 
163
            result = std::make_pair (C, D);
 
164
        }
 
165
    }
 
166
    if (lies_in_sector (dir_D, dir_A, dir)) {
 
167
        tmp_angle = pos_angle (dir_D, dir_A);
 
168
        if (tmp_angle > angle) {
 
169
            angle = tmp_angle;
 
170
            result = std::make_pair (D, A);
 
171
        }
 
172
    }
 
173
    if (angle == -1) {
 
174
        // no intersection found; return a pair containing two identical points
 
175
        return std::make_pair (A, A);
 
176
    } else {
 
177
        return result;
 
178
    }
 
179
}
 
180
 
 
181
NR::Maybe<NR::Point> Line::intersection_with_viewbox (SPDesktop *desktop)
 
182
{
 
183
    NR::Rect vb = desktop->get_display_area();
 
184
    /* remaining viewbox corners */
 
185
    NR::Point ul (vb.min()[NR::X], vb.max()[NR::Y]);
 
186
    NR::Point lr (vb.max()[NR::X], vb.min()[NR::Y]);
 
187
 
 
188
    std::pair <NR::Point, NR::Point> e = side_of_intersection (vb.min(), lr, vb.max(), ul, this->pt, this->v_dir);
 
189
    if (e.first == e.second) {
 
190
        // perspective line lies outside the canvas
 
191
        return NR::Nothing();
 
192
    }
 
193
 
 
194
    Line line (e.first, e.second);
 
195
    return this->intersect (line);
 
196
}
 
197
 
 
198
void create_canvas_point(NR::Point const &pos, double size, guint32 rgba)
 
199
{
 
200
    SPDesktop *desktop = inkscape_active_desktop();
 
201
    SPCanvasItem * canvas_pt = sp_canvas_item_new(sp_desktop_controls(desktop), SP_TYPE_CTRL,
 
202
                          "size", size,
 
203
                          "filled", 1,
 
204
                          "fill_color", rgba,
 
205
                          "stroked", 1,
 
206
                          "stroke_color", 0x000000ff,
 
207
                          NULL);
 
208
    SP_CTRL(canvas_pt)->moveto(pos);
 
209
}
 
210
 
 
211
void create_canvas_line(NR::Point const &p1, NR::Point const &p2, guint32 rgba)
 
212
{
 
213
    SPDesktop *desktop = inkscape_active_desktop();
 
214
    SPCanvasItem *line = sp_canvas_item_new(sp_desktop_controls(desktop),
 
215
                                                            SP_TYPE_CTRLLINE, NULL);
 
216
    sp_ctrlline_set_coords(SP_CTRLLINE(line), p1, p2);
 
217
    sp_ctrlline_set_rgba32 (SP_CTRLLINE(line), rgba);
 
218
    sp_canvas_item_show (line);
 
219
}
 
220
 
 
221
} // namespace Box3D 
 
222
 
 
223
/*
 
224
  Local Variables:
 
225
  mode:c++
 
226
  c-file-style:"stroustrup"
 
227
  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 
228
  indent-tabs-mode:nil
 
229
  fill-column:99
 
230
  End:
 
231
*/
 
232
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :