src/ui/tool/node.cpp

   1 /** @file
   2  * Editable node - implementation
   3  */
   4 /* Authors:
   5  *   Krzysztof Kosiński <tweenk.pl@gmail.com>
   6  *
   7  * Copyright (C) 2009 Authors
   8  * Released under GNU GPL, read the file 'COPYING' for more information
   9  */
  10
  11 #include <iostream>
  12 #include <stdexcept>
  13 #include <boost/utility.hpp>
  14 #include <glib.h>
  15 #include <glib/gi18n.h>
  16 #include <2geom/bezier-utils.h>
  17 #include <2geom/transforms.h>
  18
  19 #include "display/sp-ctrlline.h"
  20 #include "display/sp-canvas.h"
  21 #include "display/sp-canvas-util.h"
  22 #include "desktop.h"
  23 #include "desktop-handles.h"
  24 #include "preferences.h"
  25 #include "snap.h"
  26 #include "snap-preferences.h"
  27 #include "sp-metrics.h"
  28 #include "sp-namedview.h"
  29 #include "ui/tool/control-point-selection.h"
  30 #include "ui/tool/event-utils.h"
  31 #include "ui/tool/multi-path-manipulator.h"
  32 #include "ui/tool/node.h"
  33 #include "ui/tool/path-manipulator.h"
  34
  35 namespace Inkscape {
  36 namespace UI {
  37
  38 static SelectableControlPoint::ColorSet node_colors = {
  39     {
  40         {0xbfbfbf00, 0x000000ff}, // normal fill, stroke
  41         {0xff000000, 0x000000ff}, // mouseover fill, stroke
  42         {0xff000000, 0x000000ff}  // clicked fill, stroke
  43     },
  44     {0x0000ffff, 0x000000ff}, // normal fill, stroke when selected
  45     {0xff000000, 0x000000ff}, // mouseover fill, stroke when selected
  46     {0xff000000, 0x000000ff}  // clicked fill, stroke when selected
  47 };
  48
  49 static ControlPoint::ColorSet handle_colors = {
  50     {0xffffffff, 0x000000ff}, // normal fill, stroke
  51     {0xff000000, 0x000000ff}, // mouseover fill, stroke
  52     {0xff000000, 0x000000ff}  // clicked fill, stroke
  53 };
  54
  55 std::ostream &operator<<(std::ostream &out, NodeType type)
  56 {
  57     switch(type) {
  58     case NODE_CUSP: out << 'c'; break;
  59     case NODE_SMOOTH: out << 's'; break;
  60     case NODE_AUTO: out << 'a'; break;
  61     case NODE_SYMMETRIC: out << 'z'; break;
  62     default: out << 'b'; break;
  63     }
  64     return out;
  65 }
  66
  67 /** Computes an unit vector of the direction from first to second control point */
  68 static Geom::Point direction(Geom::Point const &first, Geom::Point const &second) {
  69     return Geom::unit_vector(second - first);
  70 }
  71
  72 /**
  73  * @class Handle
  74  * @brief Control point of a cubic Bezier curve in a path.
  75  *
  76  * Handle keeps the node type invariant only for the opposite handle of the same node.
  77  * Keeping the invariant on node moves is left to the %Node class.
  78  */
  79
  80 double Handle::_saved_length = 0.0;
  81 bool Handle::_drag_out = false;
  82
  83 Handle::Handle(NodeSharedData const &data, Geom::Point const &initial_pos, Node *parent)
  84     : ControlPoint(data.desktop, initial_pos, Gtk::ANCHOR_CENTER, SP_CTRL_SHAPE_CIRCLE, 7.0,
  85         &handle_colors, data.handle_group)
  86     , _parent(parent)
  87     , _degenerate(true)
  88 {
  89     _cset = &handle_colors;
  90     _handle_line = sp_canvas_item_new(data.handle_line_group, SP_TYPE_CTRLLINE, NULL);
  91     setVisible(false);
  92     signal_grabbed.connect(
  93         sigc::bind_return(
  94             sigc::hide(
  95                 sigc::mem_fun(*this, &Handle::_grabbedHandler)),
  96             false));
  97     signal_dragged.connect(
  98         sigc::hide<0>(
  99             sigc::mem_fun(*this, &Handle::_draggedHandler)));
 100     signal_ungrabbed.connect(
 101         sigc::hide(sigc::mem_fun(*this, &Handle::_ungrabbedHandler)));
 102 }
 103 Handle::~Handle()
 104 {
 105     sp_canvas_item_hide(_handle_line);
 106     gtk_object_destroy(GTK_OBJECT(_handle_line));
 107 }
 108
 109 void Handle::setVisible(bool v)
 110 {
 111     ControlPoint::setVisible(v);
 112     if (v) sp_canvas_item_show(_handle_line);
 113     else sp_canvas_item_hide(_handle_line);
 114 }
 115
 116 void Handle::move(Geom::Point const &new_pos)
 117 {
 118     Handle *other, *towards, *towards_second;
 119     Node *node_towards; // node in direction of this handle
 120     Node *node_away; // node in the opposite direction
 121     if (this == &_parent->_front) {
 122         other = &_parent->_back;
 123         node_towards = _parent->_next();
 124         node_away = _parent->_prev();
 125         towards = node_towards ? &node_towards->_back : 0;
 126         towards_second = node_towards ? &node_towards->_front : 0;
 127     } else {
 128         other = &_parent->_front;
 129         node_towards = _parent->_prev();
 130         node_away = _parent->_next();
 131         towards = node_towards ? &node_towards->_front : 0;
 132         towards_second = node_towards ? &node_towards->_back : 0;
 133     }
 134
 135     if (Geom::are_near(new_pos, _parent->position())) {
 136         // The handle becomes degenerate. If the segment between it and the node
 137         // in its direction becomes linear and there are smooth nodes
 138         // at its ends, make their handles colinear with the segment
 139         if (towards && towards->isDegenerate()) {
 140             if (node_towards->type() == NODE_SMOOTH) {
 141                 towards_second->setDirection(*_parent, *node_towards);
 142             }
 143             if (_parent->type() == NODE_SMOOTH) {
 144                 other->setDirection(*node_towards, *_parent);
 145             }
 146         }
 147         setPosition(new_pos);
 148         return;
 149     }
 150
 151     if (_parent->type() == NODE_SMOOTH && Node::_is_line_segment(_parent, node_away)) {
 152         // restrict movement to the line joining the nodes
 153         Geom::Point direction = _parent->position() - node_away->position();
 154         Geom::Point delta = new_pos - _parent->position();
 155         // project the relative position on the direction line
 156         Geom::Point new_delta = (Geom::dot(delta, direction)
 157             / Geom::L2sq(direction)) * direction;
 158         setRelativePos(new_delta);
 159         return;
 160     }
 161
 162     switch (_parent->type()) {
 163     case NODE_AUTO:
 164         _parent->setType(NODE_SMOOTH, false);
 165         // fall through - auto nodes degrade into smooth nodes
 166     case NODE_SMOOTH: {
 167         /* for smooth nodes, we need to rotate the other handle so that it's colinear
 168          * with the dragged one while conserving length. */
 169         other->setDirection(new_pos, *_parent);
 170         } break;
 171     case NODE_SYMMETRIC:
 172         // for symmetric nodes, place the other handle on the opposite side
 173         other->setRelativePos(-(new_pos - _parent->position()));
 174         break;
 175     default: break;
 176     }
 177
 178     setPosition(new_pos);
 179 }
 180
 181 void Handle::setPosition(Geom::Point const &p)
 182 {
 183     ControlPoint::setPosition(p);
 184     sp_ctrlline_set_coords(SP_CTRLLINE(_handle_line), _parent->position(), position());
 185
 186     // update degeneration info and visibility
 187     if (Geom::are_near(position(), _parent->position()))
 188         _degenerate = true;
 189     else _degenerate = false;
 190     if (_parent->_handles_shown && _parent->visible() && !_degenerate) {
 191         setVisible(true);
 192     } else {
 193         setVisible(false);
 194     }
 195     // If both handles become degenerate, convert to parent cusp node
 196     if (_parent->isDegenerate()) {
 197         _parent->setType(NODE_CUSP, false);
 198     }
 199 }
 200
 201 void Handle::setLength(double len)
 202 {
 203     if (isDegenerate()) return;
 204     Geom::Point dir = Geom::unit_vector(relativePos());
 205     setRelativePos(dir * len);
 206 }
 207
 208 void Handle::retract()
 209 {
 210     setPosition(_parent->position());
 211 }
 212
 213 void Handle::setDirection(Geom::Point const &from, Geom::Point const &to)
 214 {
 215     setDirection(to - from);
 216 }
 217
 218 void Handle::setDirection(Geom::Point const &dir)
 219 {
 220     Geom::Point unitdir = Geom::unit_vector(dir);
 221     setRelativePos(unitdir * length());
 222 }
 223
 224 char const *Handle::handle_type_to_localized_string(NodeType type)
 225 {
 226     switch(type) {
 227     case NODE_CUSP: return _("Cusp node handle");
 228     case NODE_SMOOTH: return _("Smooth node handle");
 229     case NODE_SYMMETRIC: return _("Symmetric node handle");
 230     case NODE_AUTO: return _("Auto-smooth node handle");
 231     default: return "";
 232     }
 233 }
 234
 235 void Handle::_grabbedHandler()
 236 {
 237     _saved_length = _drag_out ? 0 : length();
 238 }
 239
 240 void Handle::_draggedHandler(Geom::Point &new_pos, GdkEventMotion *event)
 241 {
 242     Geom::Point parent_pos = _parent->position();
 243     // with Alt, preserve length
 244     if (held_alt(*event)) {
 245         new_pos = parent_pos + Geom::unit_vector(new_pos - parent_pos) * _saved_length;
 246     }
 247     // with Ctrl, constrain to M_PI/rotationsnapsperpi increments.
 248     if (held_control(*event)) {
 249         Inkscape::Preferences *prefs = Inkscape::Preferences::get();
 250         int snaps = 2 * prefs->getIntLimited("/options/rotationsnapsperpi/value", 12, 1, 1000);
 251         Geom::Point origin = _last_drag_origin();
 252         Geom::Point rel_origin = origin - parent_pos;
 253         new_pos = parent_pos + Geom::constrain_angle(Geom::Point(0,0), new_pos - parent_pos, snaps,
 254             _drag_out ? Geom::Point(1,0) : Geom::unit_vector(rel_origin));
 255     }
 256     signal_update.emit();
 257 }
 258
 259 void Handle::_ungrabbedHandler()
 260 {
 261     // hide the handle if it's less than dragtolerance away from the node
 262     Inkscape::Preferences *prefs = Inkscape::Preferences::get();
 263     int drag_tolerance = prefs->getIntLimited("/options/dragtolerance/value", 0, 0, 100);
 264
 265     Geom::Point dist = _desktop->d2w(_parent->position()) - _desktop->d2w(position());
 266     if (dist.length() <= drag_tolerance) {
 267         move(_parent->position());
 268     }
 269     _drag_out = false;
 270 }
 271
 272 static double snap_increment_degrees() {
 273     Inkscape::Preferences *prefs = Inkscape::Preferences::get();
 274     int snaps = prefs->getIntLimited("/options/rotationsnapsperpi/value", 12, 1, 1000);
 275     return 180.0 / snaps;
 276 }
 277
 278 Glib::ustring Handle::_getTip(unsigned state)
 279 {
 280     if (state_held_alt(state)) {
 281         if (state_held_control(state)) {
 282             return format_tip(C_("Path handle tip",
 283                 "<b>Ctrl+Alt</b>: preserve length and snap rotation angle to %f° increments"),
 284                 snap_increment_degrees());
 285         } else {
 286             return C_("Path handle tip",
 287                 "<b>Alt:</b> preserve handle length while dragging");
 288         }
 289     } else {
 290         if (state_held_control(state)) {
 291             return format_tip(C_("Path handle tip",
 292                 "<b>Ctrl:</b> snap rotation angle to %f° increments, click to retract"),
 293                 snap_increment_degrees());
 294         }
 295     }
 296     switch (_parent->type()) {
 297     case NODE_AUTO:
 298         return C_("Path handle tip",
 299             "<b>Auto node handle:</b> drag to convert to smooth node");
 300     default:
 301         return format_tip(C_("Path handle tip", "<b>%s:</b> drag to shape the curve"),
 302             handle_type_to_localized_string(_parent->type()));
 303     }
 304 }
 305
 306 Glib::ustring Handle::_getDragTip(GdkEventMotion *event)
 307 {
 308     Geom::Point dist = position() - _last_drag_origin();
 309     // report angle in mathematical convention
 310     double angle = Geom::angle_between(Geom::Point(-1,0), position() - _parent->position());
 311     angle += M_PI; // angle is (-M_PI...M_PI] - offset by +pi and scale to 0...360
 312     angle *= 360.0 / (2 * M_PI);
 313     GString *x = SP_PX_TO_METRIC_STRING(dist[Geom::X], _desktop->namedview->getDefaultMetric());
 314     GString *y = SP_PX_TO_METRIC_STRING(dist[Geom::Y], _desktop->namedview->getDefaultMetric());
 315     GString *len = SP_PX_TO_METRIC_STRING(length(), _desktop->namedview->getDefaultMetric());
 316     Glib::ustring ret = format_tip(C_("Path handle tip",
 317         "Move by %s, %s; angle %.2f°, length %s"), x->str, y->str, angle, len->str);
 318     g_string_free(x, TRUE);
 319     g_string_free(y, TRUE);
 320     g_string_free(len, TRUE);
 321     return ret;
 322 }
 323
 324 /**
 325  * @class Node
 326  * @brief Curve endpoint in an editable path.
 327  *
 328  * The method move() keeps node type invariants during translations.
 329  */
 330
 331 Node::Node(NodeSharedData const &data, Geom::Point const &initial_pos)
 332     : SelectableControlPoint(data.desktop, initial_pos, Gtk::ANCHOR_CENTER,
 333         SP_CTRL_SHAPE_DIAMOND, 9.0, *data.selection, &node_colors, data.node_group)
 334     , _front(data, initial_pos, this)
 335     , _back(data, initial_pos, this)
 336     , _type(NODE_CUSP)
 337     , _handles_shown(false)
 338 {
 339     // NOTE we do not set type here, because the handles are still degenerate
 340     // connect to own grabbed signal - dragging out handles
 341     signal_grabbed.connect(
 342         sigc::mem_fun(*this, &Node::_grabbedHandler));
 343     signal_dragged.connect( sigc::hide<0>(
 344         sigc::mem_fun(*this, &Node::_draggedHandler)));
 345 }
 346
 347 // NOTE: not using iterators won't make this much quicker because iterators can be 100% inlined.
 348 Node *Node::_next()
 349 {
 350     NodeList::iterator n = NodeList::get_iterator(this).next();
 351     if (n) return n.ptr();
 352     return NULL;
 353 }
 354 Node *Node::_prev()
 355 {
 356     NodeList::iterator p = NodeList::get_iterator(this).prev();
 357     if (p) return p.ptr();
 358     return NULL;
 359 }
 360
 361 void Node::move(Geom::Point const &new_pos)
 362 {
 363     // move handles when the node moves.
 364     Geom::Point old_pos = position();
 365     Geom::Point delta = new_pos - position();
 366     setPosition(new_pos);
 367     _front.setPosition(_front.position() + delta);
 368     _back.setPosition(_back.position() + delta);
 369
 370     // if the node has a smooth handle after a line segment, it should be kept colinear
 371     // with the segment
 372     _fixNeighbors(old_pos, new_pos);
 373 }
 374
 375 void Node::transform(Geom::Matrix const &m)
 376 {
 377     Geom::Point old_pos = position();
 378     setPosition(position() * m);
 379     _front.setPosition(_front.position() * m);
 380     _back.setPosition(_back.position() * m);
 381
 382     /* Affine transforms keep handle invariants for smooth and symmetric nodes,
 383      * but smooth nodes at ends of linear segments and auto nodes need special treatment */
 384     _fixNeighbors(old_pos, position());
 385 }
 386
 387 Geom::Rect Node::bounds()
 388 {
 389     Geom::Rect b(position(), position());
 390     b.expandTo(_front.position());
 391     b.expandTo(_back.position());
 392     return b;
 393 }
 394
 395 void Node::_fixNeighbors(Geom::Point const &old_pos, Geom::Point const &new_pos)
 396 {
 397     /* This method restores handle invariants for neighboring nodes,
 398      * and invariants that are based on positions of those nodes for this one. */
 399
 400     /* Fix auto handles */
 401     if (_type == NODE_AUTO) _updateAutoHandles();
 402     if (old_pos != new_pos) {
 403         if (_next() && _next()->_type == NODE_AUTO) _next()->_updateAutoHandles();
 404         if (_prev() && _prev()->_type == NODE_AUTO) _prev()->_updateAutoHandles();
 405     }
 406
 407     /* Fix smooth handles at the ends of linear segments.
 408      * Rotate the appropriate handle to be colinear with the segment.
 409      * If there is a smooth node at the other end of the segment, rotate it too. */
 410     Handle *handle, *other_handle;
 411     Node *other;
 412     if (_is_line_segment(this, _next())) {
 413         handle = &_back;
 414         other = _next();
 415         other_handle = &_next()->_front;
 416     } else if (_is_line_segment(_prev(), this)) {
 417         handle = &_front;
 418         other = _prev();
 419         other_handle = &_prev()->_back;
 420     } else return;
 421
 422     if (_type == NODE_SMOOTH && !handle->isDegenerate()) {
 423         handle->setDirection(other->position(), new_pos);
 424     }
 425     // also update the handle on the other end of the segment
 426     if (other->_type == NODE_SMOOTH && !other_handle->isDegenerate()) {
 427         other_handle->setDirection(new_pos, other->position());
 428     }
 429 }
 430
 431 void Node::_updateAutoHandles()
 432 {
 433     // Recompute the position of automatic handles.
 434     // For endnodes, retract both handles. (It's only possible to create an end auto node
 435     // through the XML editor.)
 436     if (isEndNode()) {
 437         _front.retract();
 438         _back.retract();
 439         return;
 440     }
 441
 442     // Auto nodes automaticaly adjust their handles to give an appearance of smoothness,
 443     // no matter what their surroundings are.
 444     Geom::Point vec_next = _next()->position() - position();
 445     Geom::Point vec_prev = _prev()->position() - position();
 446     double len_next = vec_next.length(), len_prev = vec_prev.length();
 447     if (len_next > 0 && len_prev > 0) {
 448         // "dir" is an unit vector perpendicular to the bisector of the angle created
 449         // by the previous node, this auto node and the next node.
 450         Geom::Point dir = Geom::unit_vector((len_prev / len_next) * vec_next - vec_prev);
 451         // Handle lengths are equal to 1/3 of the distance from the adjacent node.
 452         _back.setRelativePos(-dir * (len_prev / 3));
 453         _front.setRelativePos(dir * (len_next / 3));
 454     } else {
 455         // If any of the adjacent nodes coincides, retract both handles.
 456         _front.retract();
 457         _back.retract();
 458     }
 459 }
 460
 461 void Node::showHandles(bool v)
 462 {
 463     _handles_shown = v;
 464     if (!_front.isDegenerate()) _front.setVisible(v);
 465     if (!_back.isDegenerate()) _back.setVisible(v);
 466 }
 467
 468 /** Sets the node type and optionally restores the invariants associated with the given type.
 469  * @param type The type to set
 470  * @param update_handles Whether to restore invariants associated with the given type.
 471  *                       Passing false is useful e.g. wen initially creating the path,
 472  *                       and when making cusp nodes during some node algorithms.
 473  *                       Pass true when used in response to an UI node type button.
 474  */
 475 void Node::setType(NodeType type, bool update_handles)
 476 {
 477     if (type == NODE_PICK_BEST) {
 478         pickBestType();
 479         updateState(); // The size of the control might have changed
 480         return;
 481     }
 482
 483     // if update_handles is true, adjust handle positions to match the node type
 484     // handle degenerate handles appropriately
 485     if (update_handles) {
 486         switch (type) {
 487         case NODE_CUSP:
 488             // if the existing type is also NODE_CUSP, retract handles
 489             if (_type == NODE_CUSP) {
 490                 _front.retract();
 491                 _back.retract();
 492             }
 493             break;
 494         case NODE_AUTO:
 495             // auto handles make no sense for endnodes
 496             if (isEndNode()) return;
 497             _updateAutoHandles();
 498             break;
 499         case NODE_SMOOTH: {
 500             // rotate handles to be colinear
 501             // for degenerate nodes set positions like auto handles
 502             bool prev_line = _is_line_segment(_prev(), this);
 503             bool next_line = _is_line_segment(this, _next());
 504             if (isDegenerate()) {
 505                 _updateAutoHandles();
 506             } else if (_front.isDegenerate()) {
 507                 // if the front handle is degenerate and this...next is a line segment,
 508                 // make back colinear; otherwise pull out the other handle
 509                 // to 1/3 of distance to prev
 510                 if (next_line) {
 511                     _back.setDirection(*_next(), *this);
 512                 } else if (_prev()) {
 513                     Geom::Point dir = direction(_back, *this);
 514                     _front.setRelativePos((_prev()->position() - position()).length() / 3 * dir);
 515                 }
 516             } else if (_back.isDegenerate()) {
 517                 if (prev_line) {
 518                     _front.setDirection(*_prev(), *this);
 519                 } else if (_next()) {
 520                     Geom::Point dir = direction(_front, *this);
 521                     _back.setRelativePos((_next()->position() - position()).length() / 3 * dir);
 522                 }
 523             } else {
 524                 // both handles are extended. make colinear while keeping length
 525                 // first make back colinear with the vector front ---> back,
 526                 // then make front colinear with back ---> node
 527                 // (not back ---> front because back's position was changed in the first call)
 528                 _back.setDirection(_front, _back);
 529                 _front.setDirection(_back, *this);
 530             }
 531             } break;
 532         case NODE_SYMMETRIC:
 533             if (isEndNode()) return; // symmetric handles make no sense for endnodes
 534             if (isDegenerate()) {
 535                 // similar to auto handles but set the same length for both
 536                 Geom::Point vec_next = _next()->position() - position();
 537                 Geom::Point vec_prev = _prev()->position() - position();
 538                 double len_next = vec_next.length(), len_prev = vec_prev.length();
 539                 double len = (len_next + len_prev) / 6; // take 1/3 of average
 540                 if (len == 0) return;
 541
 542                 Geom::Point dir = Geom::unit_vector((len_prev / len_next) * vec_next - vec_prev);
 543                 _back.setRelativePos(-dir * len);
 544                 _front.setRelativePos(dir * len);
 545             } else {
 546                 // Both handles are extended. Compute average length, use direction from
 547                 // back handle to front handle. This also works correctly for degenerates
 548                 double len = (_front.length() + _back.length()) / 2;
 549                 Geom::Point dir = direction(_back, _front);
 550                 _front.setRelativePos(dir * len);
 551                 _back.setRelativePos(-dir * len);
 552             }
 553             break;
 554         default: break;
 555         }
 556     }
 557     _type = type;
 558     _setShape(_node_type_to_shape(type));
 559     updateState();
 560 }
 561
 562 /** Pick the best type for this node, based on the position of its handles.
 563  * This is what assigns types to nodes created using the pen tool. */
 564 void Node::pickBestType()
 565 {
 566     _type = NODE_CUSP;
 567     bool front_degen = _front.isDegenerate();
 568     bool back_degen = _back.isDegenerate();
 569     bool both_degen = front_degen && back_degen;
 570     bool neither_degen = !front_degen && !back_degen;
 571     do {
 572         // if both handles are degenerate, do nothing
 573         if (both_degen) break;
 574         // if neither are degenerate, check their respective positions
 575         if (neither_degen) {
 576             Geom::Point front_delta = _front.position() - position();
 577             Geom::Point back_delta = _back.position() - position();
 578             // for now do not automatically make nodes symmetric, it can be annoying
 579             /*if (Geom::are_near(front_delta, -back_delta)) {
 580                 _type = NODE_SYMMETRIC;
 581                 break;
 582             }*/
 583             if (Geom::are_near(Geom::unit_vector(front_delta),
 584                 Geom::unit_vector(-back_delta)))
 585             {
 586                 _type = NODE_SMOOTH;
 587                 break;
 588             }
 589         }
 590         // check whether the handle aligns with the previous line segment.
 591         // we know that if front is degenerate, back isn't, because
 592         // both_degen was false
 593         if (front_degen && _next() && _next()->_back.isDegenerate()) {
 594             Geom::Point segment_delta = Geom::unit_vector(_next()->position() - position());
 595             Geom::Point handle_delta = Geom::unit_vector(_back.position() - position());
 596             if (Geom::are_near(segment_delta, -handle_delta)) {
 597                 _type = NODE_SMOOTH;
 598                 break;
 599             }
 600         } else if (back_degen && _prev() && _prev()->_front.isDegenerate()) {
 601             Geom::Point segment_delta = Geom::unit_vector(_prev()->position() - position());
 602             Geom::Point handle_delta = Geom::unit_vector(_front.position() - position());
 603             if (Geom::are_near(segment_delta, -handle_delta)) {
 604                 _type = NODE_SMOOTH;
 605                 break;
 606             }
 607         }
 608     } while (false);
 609     _setShape(_node_type_to_shape(_type));
 610     updateState();
 611 }
 612
 613 bool Node::isEndNode()
 614 {
 615     return !_prev() || !_next();
 616 }
 617
 618 /** Move the node to the bottom of its canvas group. Useful for node break, to ensure that
 619  * the selected nodes are above the unselected ones. */
 620 void Node::sink()
 621 {
 622     sp_canvas_item_move_to_z(_canvas_item, 0);
 623 }
 624
 625 NodeType Node::parse_nodetype(char x)
 626 {
 627     switch (x) {
 628     case 'a': return NODE_AUTO;
 629     case 'c': return NODE_CUSP;
 630     case 's': return NODE_SMOOTH;
 631     case 'z': return NODE_SYMMETRIC;
 632     default: return NODE_PICK_BEST;
 633     }
 634 }
 635
 636 /** Customized event handler to catch scroll events needed for selection grow/shrink. */
 637 bool Node::_eventHandler(GdkEvent *event)
 638 {
 639     static NodeList::iterator origin;
 640     static int dir;
 641
 642     switch (event->type)
 643     {
 644     case GDK_SCROLL:
 645         if (event->scroll.direction == GDK_SCROLL_UP) {
 646             dir = 1;
 647         } else if (event->scroll.direction == GDK_SCROLL_DOWN) {
 648             dir = -1;
 649         } else break;
 650         if (held_control(event->scroll)) {
 651             _selection.spatialGrow(this, dir);
 652         } else {
 653             _linearGrow(dir);
 654         }
 655         return true;
 656     default:
 657         break;
 658     }
 659     return ControlPoint::_eventHandler(event);
 660 }
 661
 662 // TODO Move this to 2Geom!
 663 static double bezier_length (Geom::Point a0, Geom::Point a1, Geom::Point a2, Geom::Point a3)
 664 {
 665     double lower = Geom::distance(a0, a3);
 666     double upper = Geom::distance(a0, a1) + Geom::distance(a1, a2) + Geom::distance(a2, a3);
 667
 668     if (upper - lower < Geom::EPSILON) return (lower + upper)/2;
 669
 670     Geom::Point // Casteljau subdivision
 671         b0 = a0,
 672         c0 = a3,
 673         b1 = 0.5*(a0 + a1),
 674         t0 = 0.5*(a1 + a2),
 675         c1 = 0.5*(a2 + a3),
 676         b2 = 0.5*(b1 + t0),
 677         c2 = 0.5*(t0 + c1),
 678         b3 = 0.5*(b2 + c2); // == c3
 679     return bezier_length(b0, b1, b2, b3) + bezier_length(b3, c2, c1, c0);
 680 }
 681
 682 /** Select or deselect a node in this node's subpath based on its path distance from this node.
 683  * @param dir If negative, shrink selection by one node; if positive, grow by one node */
 684 void Node::_linearGrow(int dir)
 685 {
 686     // Interestingly, we do not need any help from PathManipulator when doing linear grow.
 687     // First handle the trivial case of growing over an unselected node.
 688     if (!selected() && dir > 0) {
 689         _selection.insert(this);
 690         return;
 691     }
 692
 693     NodeList::iterator this_iter = NodeList::get_iterator(this);
 694     NodeList::iterator fwd = this_iter, rev = this_iter;
 695     double distance_back = 0, distance_front = 0;
 696
 697     // Linear grow is simple. We find the first unselected nodes in each direction
 698     // and compare the linear distances to them.
 699     if (dir > 0) {
 700         if (!selected()) {
 701             _selection.insert(this);
 702             return;
 703         }
 704
 705         // find first unselected nodes on both sides
 706         while (fwd && fwd->selected()) {
 707             NodeList::iterator n = fwd.next();
 708             distance_front += bezier_length(*fwd, fwd->_front, n->_back, *n);
 709             fwd = n;
 710             if (fwd == this_iter)
 711                 // there is no unselected node in this cyclic subpath
 712                 return;
 713         }
 714         // do the same for the second direction. Do not check for equality with
 715         // this node, because there is at least one unselected node in the subpath,
 716         // so we are guaranteed to stop.
 717         while (rev && rev->selected()) {
 718             NodeList::iterator p = rev.prev();
 719             distance_back += bezier_length(*rev, rev->_back, p->_front, *p);
 720             rev = p;
 721         }
 722
 723         NodeList::iterator t; // node to select
 724         if (fwd && rev) {
 725             if (distance_front <= distance_back) t = fwd;
 726             else t = rev;
 727         } else {
 728             if (fwd) t = fwd;
 729             if (rev) t = rev;
 730         }
 731         if (t) _selection.insert(t.ptr());
 732
 733     // Linear shrink is more complicated. We need to find the farthest selected node.
 734     // This means we have to check the entire subpath. We go in the direction in which
 735     // the distance we traveled is lower. We do this until we run out of nodes (ends of path)
 736     // or the two iterators meet. On the way, we store the last selected node and its distance
 737     // in each direction (if any). At the end, we choose the one that is farther and deselect it.
 738     } else {
 739         // both iterators that store last selected nodes are initially empty
 740         NodeList::iterator last_fwd, last_rev;
 741         double last_distance_back = 0, last_distance_front = 0;
 742
 743         while (rev || fwd) {
 744             if (fwd && (!rev || distance_front <= distance_back)) {
 745                 if (fwd->selected()) {
 746                     last_fwd = fwd;
 747                     last_distance_front = distance_front;
 748                 }
 749                 NodeList::iterator n = fwd.next();
 750                 if (n) distance_front += bezier_length(*fwd, fwd->_front, n->_back, *n);
 751                 fwd = n;
 752             } else if (rev && (!fwd || distance_front > distance_back)) {
 753                 if (rev->selected()) {
 754                     last_rev = rev;
 755                     last_distance_back = distance_back;
 756                 }
 757                 NodeList::iterator p = rev.prev();
 758                 if (p) distance_back += bezier_length(*rev, rev->_back, p->_front, *p);
 759                 rev = p;
 760             }
 761             // Check whether we walked the entire cyclic subpath.
 762             // This is initially true because both iterators start from this node,
 763             // so this check cannot go in the while condition.
 764             // When this happens, we need to check the last node, pointed to by the iterators.
 765             if (fwd && fwd == rev) {
 766                 if (!fwd->selected()) break;
 767                 NodeList::iterator fwdp = fwd.prev(), revn = rev.next();
 768                 double df = distance_front + bezier_length(*fwdp, fwdp->_front, fwd->_back, *fwd);
 769                 double db = distance_back + bezier_length(*revn, revn->_back, rev->_front, *rev);
 770                 if (df > db) {
 771                     last_fwd = fwd;
 772                     last_distance_front = df;
 773                 } else {
 774                     last_rev = rev;
 775                     last_distance_back = db;
 776                 }
 777                 break;
 778             }
 779         }
 780
 781         NodeList::iterator t;
 782         if (last_fwd && last_rev) {
 783             if (last_distance_front >= last_distance_back) t = last_fwd;
 784             else t = last_rev;
 785         } else {
 786             if (last_fwd) t = last_fwd;
 787             if (last_rev) t = last_rev;
 788         }
 789         if (t) _selection.erase(t.ptr());
 790     }
 791 }
 792
 793 void Node::_setState(State state)
 794 {
 795     // change node size to match type and selection state
 796     switch (_type) {
 797     case NODE_AUTO:
 798     case NODE_CUSP:
 799         if (selected()) _setSize(11);
 800         else _setSize(9);
 801         break;
 802     default:
 803         if(selected()) _setSize(9);
 804         else _setSize(7);
 805         break;
 806     }
 807     SelectableControlPoint::_setState(state);
 808 }
 809
 810 bool Node::_grabbedHandler(GdkEventMotion *event)
 811 {
 812     // Dragging out handles with Shift + drag on a node.
 813     if (!held_shift(*event)) return false;
 814
 815     Handle *h;
 816     Geom::Point evp = event_point(*event);
 817     Geom::Point rel_evp = evp - _last_click_event_point();
 818
 819     // This should work even if dragtolerance is zero and evp coincides with node position.
 820     double angle_next = HUGE_VAL;
 821     double angle_prev = HUGE_VAL;
 822     bool has_degenerate = false;
 823     // determine which handle to drag out based on degeneration and the direction of drag
 824     if (_front.isDegenerate() && _next()) {
 825         Geom::Point next_relpos = _desktop->d2w(_next()->position())
 826             - _desktop->d2w(position());
 827         angle_next = fabs(Geom::angle_between(rel_evp, next_relpos));
 828         has_degenerate = true;
 829     }
 830     if (_back.isDegenerate() && _prev()) {
 831         Geom::Point prev_relpos = _desktop->d2w(_prev()->position())
 832             - _desktop->d2w(position());
 833         angle_prev = fabs(Geom::angle_between(rel_evp, prev_relpos));
 834         has_degenerate = true;
 835     }
 836     if (!has_degenerate) return false;
 837     h = angle_next < angle_prev ? &_front : &_back;
 838
 839     h->setPosition(_desktop->w2d(evp));
 840     h->setVisible(true);
 841     h->transferGrab(this, event);
 842     Handle::_drag_out = true;
 843     return true;
 844 }
 845
 846 void Node::_draggedHandler(Geom::Point &new_pos, GdkEventMotion *event)
 847 {
 848     // For a note on how snapping is implemented in Inkscape, see snap.h.
 849     SnapManager &sm = _desktop->namedview->snap_manager;
 850     Inkscape::SnapPreferences::PointType t = Inkscape::SnapPreferences::SNAPPOINT_NODE;
 851     bool snap = sm.someSnapperMightSnap();
 852     std::vector<Inkscape::SnapCandidatePoint> unselected;
 853     if (snap) {
 854         /* setup
 855          * TODO We are doing this every time a snap happens. It should once be done only once
 856          *      per drag - maybe in the grabbed handler?
 857          * TODO Unselected nodes vector must be valid during the snap run, because it is not
 858          *      copied. Fix this in snap.h and snap.cpp, then the above.
 859          * TODO Snapping to unselected segments of selected paths doesn't work yet. */
 860
 861         // Build the list of unselected nodes.
 862         typedef ControlPointSelection::Set Set;
 863         Set nodes = _selection.allPoints();
 864         for (Set::iterator i = nodes.begin(); i != nodes.end(); ++i) {
 865             if (!(*i)->selected()) {
 866                 Node *n = static_cast<Node*>(*i);
 867                 Inkscape::SnapCandidatePoint p(n->position(), n->_snapSourceType(), n->_snapTargetType());
 868                 unselected.push_back(p);
 869             }
 870         }
 871         sm.setupIgnoreSelection(_desktop, true, &unselected);
 872     }
 873
 874     if (held_control(*event)) {
 875         Geom::Point origin = _last_drag_origin();
 876         if (held_alt(*event)) {
 877             // with Ctrl+Alt, constrain to handle lines
 878             // project the new position onto a handle line that is closer
 879             Inkscape::Snapper::ConstraintLine line_front(origin, _front.relativePos());
 880             Inkscape::Snapper::ConstraintLine line_back(origin, _back.relativePos());
 881
 882             // TODO: combine these two branches by modifying snap.h / snap.cpp
 883             if (snap) {
 884                 Inkscape::SnappedPoint fp, bp;
 885                 fp = sm.constrainedSnap(t, Inkscape::SnapCandidatePoint(position(), _snapSourceType()), line_front);
 886                 bp = sm.constrainedSnap(t, Inkscape::SnapCandidatePoint(position(), _snapSourceType()), line_back);
 887
 888                 if (fp.isOtherSnapBetter(bp, false)) {
 889                     bp.getPoint(new_pos);
 890                 } else {
 891                     fp.getPoint(new_pos);
 892                 }
 893             } else {
 894                 Geom::Point p_front = line_front.projection(new_pos);
 895                 Geom::Point p_back = line_back.projection(new_pos);
 896                 if (Geom::distance(new_pos, p_front) < Geom::distance(new_pos, p_back)) {
 897                     new_pos = p_front;
 898                 } else {
 899                     new_pos = p_back;
 900                 }
 901             }
 902         } else {
 903             // with Ctrl, constrain to axes
 904             // TODO combine the two branches
 905             if (snap) {
 906                 Inkscape::SnappedPoint fp, bp;
 907                 Inkscape::Snapper::ConstraintLine line_x(origin, Geom::Point(1, 0));
 908                 Inkscape::Snapper::ConstraintLine line_y(origin, Geom::Point(0, 1));
 909                 fp = sm.constrainedSnap(t, Inkscape::SnapCandidatePoint(position(), _snapSourceType()), line_x);
 910                 bp = sm.constrainedSnap(t, Inkscape::SnapCandidatePoint(position(), _snapSourceType()), line_y);
 911
 912                 if (fp.isOtherSnapBetter(bp, false)) {
 913                     fp = bp;
 914                 }
 915                 fp.getPoint(new_pos);
 916             } else {
 917                 Geom::Point origin = _last_drag_origin();
 918                 Geom::Point delta = new_pos - origin;
 919                 Geom::Dim2 d = (fabs(delta[Geom::X]) < fabs(delta[Geom::Y])) ? Geom::X : Geom::Y;
 920                 new_pos[d] = origin[d];
 921             }
 922         }
 923     } else if (snap) {
 924         sm.freeSnapReturnByRef(Inkscape::SnapPreferences::SNAPPOINT_NODE, new_pos, _snapSourceType());
 925     }
 926 }
 927
 928 Inkscape::SnapSourceType Node::_snapSourceType()
 929 {
 930     if (_type == NODE_SMOOTH || _type == NODE_AUTO)
 931         return SNAPSOURCE_NODE_SMOOTH;
 932     return SNAPSOURCE_NODE_CUSP;
 933 }
 934 Inkscape::SnapTargetType Node::_snapTargetType()
 935 {
 936     if (_type == NODE_SMOOTH || _type == NODE_AUTO)
 937         return SNAPTARGET_NODE_SMOOTH;
 938     return SNAPTARGET_NODE_CUSP;
 939 }
 940
 941 Glib::ustring Node::_getTip(unsigned state)
 942 {
 943     if (state_held_shift(state)) {
 944         if ((_next() && _front.isDegenerate()) || (_prev() && _back.isDegenerate())) {
 945             if (state_held_control(state)) {
 946                 return format_tip(C_("Path node tip",
 947                     "<b>Shift+Ctrl:</b> drag out a handle and snap its angle "
 948                     "to %f° increments"), snap_increment_degrees());
 949             }
 950             return C_("Path node tip",
 951                 "<b>Shift:</b> drag out a handle, click to toggle selection");
 952         }
 953         return C_("Path node tip", "<b>Shift:</b> click to toggle selection");
 954     }
 955
 956     if (state_held_control(state)) {
 957         if (state_held_alt(state)) {
 958             return C_("Path node tip", "<b>Ctrl+Alt:</b> move along handle lines");
 959         }
 960         return C_("Path node tip",
 961             "<b>Ctrl:</b> move along axes, click to change node type");
 962     }
 963
 964     // assemble tip from node name
 965     char const *nodetype = node_type_to_localized_string(_type);
 966     return format_tip(C_("Path node tip",
 967         "<b>%s:</b> drag to shape the path, click to select this node"), nodetype);
 968 }
 969
 970 Glib::ustring Node::_getDragTip(GdkEventMotion *event)
 971 {
 972     Geom::Point dist = position() - _last_drag_origin();
 973     GString *x = SP_PX_TO_METRIC_STRING(dist[Geom::X], _desktop->namedview->getDefaultMetric());
 974     GString *y = SP_PX_TO_METRIC_STRING(dist[Geom::Y], _desktop->namedview->getDefaultMetric());
 975     Glib::ustring ret = format_tip(C_("Path node tip", "Move by %s, %s"),
 976         x->str, y->str);
 977     g_string_free(x, TRUE);
 978     g_string_free(y, TRUE);
 979     return ret;
 980 }
 981
 982 char const *Node::node_type_to_localized_string(NodeType type)
 983 {
 984     switch (type) {
 985     case NODE_CUSP: return _("Cusp node");
 986     case NODE_SMOOTH: return _("Smooth node");
 987     case NODE_SYMMETRIC: return _("Symmetric node");
 988     case NODE_AUTO: return _("Auto-smooth node");
 989     default: return "";
 990     }
 991 }
 992
 993 /** Determine whether two nodes are joined by a linear segment. */
 994 bool Node::_is_line_segment(Node *first, Node *second)
 995 {
 996     if (!first || !second) return false;
 997     if (first->_next() == second)
 998         return first->_front.isDegenerate() && second->_back.isDegenerate();
 999     if (second->_next() == first)
1000         return second->_front.isDegenerate() && first->_back.isDegenerate();
1001     return false;
1002 }
1003
1004 SPCtrlShapeType Node::_node_type_to_shape(NodeType type)
1005 {
1006     switch(type) {
1007     case NODE_CUSP: return SP_CTRL_SHAPE_DIAMOND;
1008     case NODE_SMOOTH: return SP_CTRL_SHAPE_SQUARE;
1009     case NODE_AUTO: return SP_CTRL_SHAPE_CIRCLE;
1010     case NODE_SYMMETRIC: return SP_CTRL_SHAPE_SQUARE;
1011     default: return SP_CTRL_SHAPE_DIAMOND;
1012     }
1013 }
1014
1015
1016 /**
1017  * @class NodeList
1018  * @brief An editable list of nodes representing a subpath.
1019  *
1020  * It can optionally be cyclic to represent a closed path.
1021  * The list has iterators that act like plain node iterators, but can also be used
1022  * to obtain shared pointers to nodes.
1023  */
1024
1025 NodeList::NodeList(SubpathList &splist)
1026     : _list(splist)
1027     , _closed(false)
1028 {
1029     this->list = this;
1030     this->next = this;
1031     this->prev = this;
1032 }
1033
1034 NodeList::~NodeList()
1035 {
1036     clear();
1037 }
1038
1039 bool NodeList::empty()
1040 {
1041     return next == this;
1042 }
1043
1044 NodeList::size_type NodeList::size()
1045 {
1046     size_type sz = 0;
1047     for (ListNode *ln = next; ln != this; ln = ln->next) ++sz;
1048     return sz;
1049 }
1050
1051 bool NodeList::closed()
1052 {
1053     return _closed;
1054 }
1055
1056 /** A subpath is degenerate if it has no segments - either one node in an open path
1057  * or no nodes in a closed path */
1058 bool NodeList::degenerate()
1059 {
1060     return closed() ? empty() : ++begin() == end();
1061 }
1062
1063 NodeList::iterator NodeList::before(double t, double *fracpart)
1064 {
1065     double intpart;
1066     *fracpart = std::modf(t, &intpart);
1067     int index = intpart;
1068
1069     iterator ret = begin();
1070     std::advance(ret, index);
1071     return ret;
1072 }
1073
1074 // insert a node before i
1075 NodeList::iterator NodeList::insert(iterator i, Node *x)
1076 {
1077     ListNode *ins = i._node;
1078     x->next = ins;
1079     x->prev = ins->prev;
1080     ins->prev->next = x;
1081     ins->prev = x;
1082     x->ListNode::list = this;
1083     _list.signal_insert_node.emit(x);
1084     return iterator(x);
1085 }
1086
1087 void NodeList::splice(iterator pos, NodeList &list)
1088 {
1089     splice(pos, list, list.begin(), list.end());
1090 }
1091
1092 void NodeList::splice(iterator pos, NodeList &list, iterator i)
1093 {
1094     NodeList::iterator j = i;
1095     ++j;
1096     splice(pos, list, i, j);
1097 }
1098
1099 void NodeList::splice(iterator pos, NodeList &list, iterator first, iterator last)
1100 {
1101     ListNode *ins_beg = first._node, *ins_end = last._node, *at = pos._node;
1102     for (ListNode *ln = ins_beg; ln != ins_end; ln = ln->next) {
1103         list._list.signal_remove_node.emit(static_cast<Node*>(ln));
1104         ln->list = this;
1105         _list.signal_insert_node.emit(static_cast<Node*>(ln));
1106     }
1107     ins_beg->prev->next = ins_end;
1108     ins_end->prev->next = at;
1109     at->prev->next = ins_beg;
1110
1111     ListNode *atprev = at->prev;
1112     at->prev = ins_end->prev;
1113     ins_end->prev = ins_beg->prev;
1114     ins_beg->prev = atprev;
1115 }
1116
1117 void NodeList::shift(int n)
1118 {
1119     // 1. make the list perfectly cyclic
1120     next->prev = prev;
1121     prev->next = next;
1122     // 2. find new begin
1123     ListNode *new_begin = next;
1124     if (n > 0) {
1125         for (; n > 0; --n) new_begin = new_begin->next;
1126     } else {
1127         for (; n < 0; ++n) new_begin = new_begin->prev;
1128     }
1129     // 3. relink begin to list
1130     next = new_begin;
1131     prev = new_begin->prev;
1132     new_begin->prev->next = this;
1133     new_begin->prev = this;
1134 }
1135
1136 void NodeList::reverse()
1137 {
1138     for (ListNode *ln = next; ln != this; ln = ln->prev) {
1139         std::swap(ln->next, ln->prev);
1140         Node *node = static_cast<Node*>(ln);
1141         Geom::Point save_pos = node->front()->position();
1142         node->front()->setPosition(node->back()->position());
1143         node->back()->setPosition(save_pos);
1144     }
1145     std::swap(next, prev);
1146 }
1147
1148 void NodeList::clear()
1149 {
1150     for (iterator i = begin(); i != end();) erase (i++);
1151 }
1152
1153 NodeList::iterator NodeList::erase(iterator i)
1154 {
1155     // some gymnastics are required to ensure that the node is valid when deleted;
1156     // otherwise the code that updates handle visibility will break
1157     Node *rm = static_cast<Node*>(i._node);
1158     ListNode *rmnext = rm->next, *rmprev = rm->prev;
1159     ++i;
1160     _list.signal_remove_node.emit(rm);
1161     delete rm;
1162     rmprev->next = rmnext;
1163     rmnext->prev = rmprev;
1164     return i;
1165 }
1166
1167 // TODO this method is very ugly!
1168 // converting SubpathList to an intrusive list might allow us to get rid of it
1169 void NodeList::kill()
1170 {
1171     for (SubpathList::iterator i = _list.begin(); i != _list.end(); ++i) {
1172         if (i->get() == this) {
1173             _list.erase(i);
1174             return;
1175         }
1176     }
1177 }
1178
1179 NodeList &NodeList::get(Node *n) {
1180     return *(n->list());
1181 }
1182 NodeList &NodeList::get(iterator const &i) {
1183     return *(i._node->list);
1184 }
1185
1186
1187 /**
1188  * @class SubpathList
1189  * @brief Editable path composed of one or more subpaths
1190  */
1191
1192 } // namespace UI
1193 } // namespace Inkscape
1194
1195 /*
1196   Local Variables:
1197   mode:c++
1198   c-file-style:"stroustrup"
1199   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1200   indent-tabs-mode:nil
1201   fill-column:99
1202   End:
1203 */
1204 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :