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(Geom::Point const &start, Geom::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 = Geom::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 boost::optional<Geom::Point> Line::intersect(Line const &line) {
  56     Geom::Coord denom = Geom::dot(v_dir, line.normal);
  57     boost::optional<Geom::Point> no_point;
  58     if (fabs(denom) < 1e-6)
  59         return no_point;
  60
  61     Geom::Coord lambda = (line.d0 - Geom::dot(pt, line.normal)) / denom;
  62     return pt + lambda * v_dir;
  63 }
  64
  65 void Line::set_direction(Geom::Point const &dir)
  66 {
  67     v_dir = dir;
  68     normal = v_dir.ccw();
  69     d0 = Geom::dot(normal, pt);
  70 }
  71
  72 Geom::Point Line::closest_to(Geom::Point const &pt)
  73 {
  74         /* return the intersection of this line with a perpendicular line passing through pt */
  75     boost::optional<Geom::Point> result = this->intersect(Line(pt, (this->v_dir).ccw(), false));
  76     g_return_val_if_fail (result, Geom::Point (0.0, 0.0));
  77     return *result;
  78 }
  79
  80 double Line::lambda (Geom::Point const pt)
  81 {
  82     double sign = (Geom::dot (pt - this->pt, this->v_dir) > 0) ? 1.0 : -1.0;
  83     double lambda = sign * Geom::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     Geom::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 (Geom::Point const &v1, Geom::Point const &v2, Geom::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 (Geom::Point const &v1, Geom::Point const &v2, Geom::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 (Geom::dot (v1, v2) < 0);
 116     }
 117     return (coords.first >= 0 and coords.second >= 0);
 118 }
 119
 120 bool lies_in_quadrangle (Geom::Point const &A, Geom::Point const &B, Geom::Point const &C, Geom::Point const &D, Geom::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 (Geom::Point v, Geom::Point w)
 126 {
 127     return fabs (Geom::atan2 (v) - Geom::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<Geom::Point, Geom::Point>
 136 side_of_intersection (Geom::Point const &A, Geom::Point const &B, Geom::Point const &C, Geom::Point const &D,
 137                       Geom::Point const &pt, Geom::Point const &dir)
 138 {
 139     Geom::Point dir_A (A - pt);
 140     Geom::Point dir_B (B - pt);
 141     Geom::Point dir_C (C - pt);
 142     Geom::Point dir_D (D - pt);
 143
 144     std::pair<Geom::Point, Geom::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 boost::optional<Geom::Point> Line::intersection_with_viewbox (SPDesktop *desktop)
 182 {
 183     Geom::Rect vb = desktop->get_display_area();
 184     /* remaining viewbox corners */
 185     Geom::Point ul (vb.min()[Geom::X], vb.max()[Geom::Y]);
 186     Geom::Point lr (vb.max()[Geom::X], vb.min()[Geom::Y]);
 187
 188     std::pair <Geom::Point, Geom::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 boost::optional<Geom::Point>();
 192     }
 193
 194     Line line (e.first, e.second);
 195     return this->intersect (line);
 196 }
 197
 198 void create_canvas_point(Geom::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(Geom::Point const &p1, Geom::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 :