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-style.h"
  17 #include "desktop-handles.h"
  18 #include "display/sp-canvas.h"
  19 #include "display/sodipodi-ctrl.h"
  20 //#include "display/curve.cpp"
  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     g_return_val_if_fail(fabs(denom) > 1e-6, NR::Nothing());
  58
  59     NR::Coord lambda = (line.d0 - NR::dot(pt, line.normal)) / denom;
  60     return pt + lambda * v_dir;
  61 }
  62
  63 void Line::set_direction(NR::Point const &dir)
  64 {
  65     v_dir = dir;
  66     normal = v_dir.ccw();
  67     d0 = NR::dot(normal, pt);
  68 }
  69
  70 NR::Point Line::closest_to(NR::Point const &pt)
  71 {
  72         /* return the intersection of this line with a perpendicular line passing through pt */
  73     NR::Maybe<NR::Point> result = this->intersect(Line(pt, (this->v_dir).ccw(), false));
  74     g_return_val_if_fail (result, NR::Point (0.0, 0.0));
  75     return *result;
  76 }
  77
  78 inline static double determinant (NR::Point const &a, NR::Point const &b)
  79 {
  80     return (a[NR::X] * b[NR::Y] - a[NR::Y] * b[NR::X]);
  81 }
  82
  83 /* The coordinates of w with respect to the basis {v1, v2} */
  84 std::pair<double, double> coordinates (NR::Point const &v1, NR::Point const &v2, NR::Point const &w)
  85 {
  86     double det = determinant (v1, v2);;
  87     if (fabs (det) < epsilon) {
  88         g_warning ("Vectors do not form a basis.\n");
  89         return std::make_pair (0.0, 0.0);
  90     }
  91
  92     double lambda1 = determinant (w, v2) / det;
  93     double lambda2 = determinant (v1, w) / det;
  94     return std::make_pair (lambda1, lambda2);
  95 }
  96
  97 /* whether w lies inside the sector spanned by v1 and v2 */
  98 bool lies_in_sector (NR::Point const &v1, NR::Point const &v2, NR::Point const &w)
  99 {
 100     std::pair<double, double> coords = coordinates (v1, v2, w);
 101     return (coords.first >= 0 and coords.second >= 0);
 102 }
 103
 104 static double pos_angle (NR::Point A, NR::Point B)
 105 {
 106     return fabs (NR::atan2 (A) - NR::atan2 (B));
 107 }
 108
 109 /*
 110  * Returns the two corners of the quadrangle A, B, C, D spanning the edge that is hit by a semiline
 111  * starting at pt and going into direction dir.
 112  * If none of the sides is hit, it returns a pair containing two identical points.
 113  */
 114 std::pair<NR::Point, NR::Point>
 115 side_of_intersection (NR::Point const &A, NR::Point const &B, NR::Point const &C, NR::Point const &D,
 116                       NR::Point const &pt, NR::Point const &dir)
 117 {
 118     NR::Point dir_A (A - pt);
 119     NR::Point dir_B (B - pt);
 120     NR::Point dir_C (C - pt);
 121     NR::Point dir_D (D - pt);
 122
 123     std::pair<NR::Point, NR::Point> result;
 124     double angle = -1;
 125     double tmp_angle;
 126
 127     if (lies_in_sector (dir_A, dir_B, dir)) {
 128         result = std::make_pair (A, B);
 129         angle = pos_angle (dir_A, dir_B);
 130     }
 131     if (lies_in_sector (dir_B, dir_C, dir)) {
 132         tmp_angle = pos_angle (dir_B, dir_C);
 133         if (tmp_angle > angle) {
 134             angle = tmp_angle;
 135             result = std::make_pair (B, C);
 136         }
 137     }
 138     if (lies_in_sector (dir_C, dir_D, dir)) {
 139         tmp_angle = pos_angle (dir_C, dir_D);
 140         if (tmp_angle > angle) {
 141             angle = tmp_angle;
 142             result = std::make_pair (C, D);
 143         }
 144     }
 145     if (lies_in_sector (dir_D, dir_A, dir)) {
 146         tmp_angle = pos_angle (dir_D, dir_A);
 147         if (tmp_angle > angle) {
 148             angle = tmp_angle;
 149             result = std::make_pair (D, A);
 150         }
 151     }
 152     if (angle == -1) {
 153         // no intersection found; return a pair containing two identical points
 154         return std::make_pair (A, A);
 155     } else {
 156         return result;
 157     }
 158 }
 159
 160 void create_canvas_point(NR::Point const &pos, double size, guint32 rgba)
 161 {
 162     SPDesktop *desktop = inkscape_active_desktop();
 163     SPCanvasItem * canvas_pt = sp_canvas_item_new(sp_desktop_controls(desktop), SP_TYPE_CTRL,
 164                           "size", size,
 165                           "filled", 1,
 166                           "fill_color", rgba,
 167                           "stroked", 1,
 168                           "stroke_color", 0x000000ff,
 169                           NULL);
 170     SP_CTRL(canvas_pt)->moveto(pos);
 171 }
 172
 173 void create_canvas_line(NR::Point const &p1, NR::Point const &p2, guint32 rgba)
 174 {
 175     SPDesktop *desktop = inkscape_active_desktop();
 176     SPCanvasItem *line = sp_canvas_item_new(sp_desktop_controls(desktop),
 177                                                             SP_TYPE_CTRLLINE, NULL);
 178     sp_ctrlline_set_coords(SP_CTRLLINE(line), p1, p2);
 179     sp_ctrlline_set_rgba32 (SP_CTRLLINE(line), rgba);
 180     sp_canvas_item_show (line);
 181 }
 182
 183 } // namespace Box3D
 184
 185 /*
 186   Local Variables:
 187   mode:c++
 188   c-file-style:"stroustrup"
 189   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 190   indent-tabs-mode:nil
 191   fill-column:99
 192   End:
 193 */
 194 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :