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 Geom::Point Handle::_saved_other_pos(0, 0);
  81 double Handle::_saved_length = 0.0;
  82 bool Handle::_drag_out = false;
  83
  84 Handle::Handle(NodeSharedData const &data, Geom::Point const &initial_pos, Node *parent)
  85     : ControlPoint(data.desktop, initial_pos, Gtk::ANCHOR_CENTER, SP_CTRL_SHAPE_CIRCLE, 7.0,
  86         &handle_colors, data.handle_group)
  87     , _parent(parent)
  88     , _degenerate(true)
  89 {
  90     _cset = &handle_colors;
  91     _handle_line = sp_canvas_item_new(data.handle_line_group, SP_TYPE_CTRLLINE, NULL);
  92     setVisible(false);
  93 }
  94 Handle::~Handle()
  95 {
  96     //sp_canvas_item_hide(_handle_line);
  97     gtk_object_destroy(GTK_OBJECT(_handle_line));
  98 }
  99
 100 void Handle::setVisible(bool v)
 101 {
 102     ControlPoint::setVisible(v);
 103     if (v) sp_canvas_item_show(_handle_line);
 104     else sp_canvas_item_hide(_handle_line);
 105 }
 106
 107 void Handle::move(Geom::Point const &new_pos)
 108 {
 109     Handle *other = this->other();
 110     Node *node_towards = _parent->nodeToward(this); // node in direction of this handle
 111     Node *node_away = _parent->nodeAwayFrom(this); // node in the opposite direction
 112     Handle *towards = node_towards ? node_towards->handleAwayFrom(_parent) : NULL;
 113     Handle *towards_second = node_towards ? node_towards->handleToward(_parent) : NULL;
 114
 115     if (Geom::are_near(new_pos, _parent->position())) {
 116         // The handle becomes degenerate.
 117         // Adjust node type as necessary.
 118         if (other->isDegenerate()) {
 119             // If both handles become degenerate, convert to parent cusp node
 120             _parent->setType(NODE_CUSP, false);
 121         } else {
 122             // Only 1 handle becomes degenerate
 123             switch (_parent->type()) {
 124             case NODE_AUTO:
 125             case NODE_SYMMETRIC:
 126                 _parent->setType(NODE_SMOOTH, false);
 127                 break;
 128             default:
 129                 // do nothing for other node types
 130                 break;
 131             }
 132         }
 133         // If the segment between the handle and the node
 134         // in its direction becomes linear and there are smooth nodes
 135         // at its ends, make their handles colinear with the segment
 136         if (towards && towards_second->isDegenerate()) {
 137             if (node_towards->type() == NODE_SMOOTH) {
 138                 towards->setDirection(*_parent, *node_towards);
 139             }
 140             if (_parent->type() == NODE_SMOOTH) {
 141                 other->setDirection(*node_towards, *_parent);
 142             }
 143         }
 144         setPosition(new_pos);
 145         return;
 146     }
 147
 148     if (_parent->type() == NODE_SMOOTH && Node::_is_line_segment(_parent, node_away)) {
 149         // restrict movement to the line joining the nodes
 150         Geom::Point direction = _parent->position() - node_away->position();
 151         Geom::Point delta = new_pos - _parent->position();
 152         // project the relative position on the direction line
 153         Geom::Point new_delta = (Geom::dot(delta, direction)
 154             / Geom::L2sq(direction)) * direction;
 155         setRelativePos(new_delta);
 156         return;
 157     }
 158
 159     switch (_parent->type()) {
 160     case NODE_AUTO:
 161         _parent->setType(NODE_SMOOTH, false);
 162         // fall through - auto nodes degrade into smooth nodes
 163     case NODE_SMOOTH: {
 164         /* for smooth nodes, we need to rotate the other handle so that it's colinear
 165          * with the dragged one while conserving length. */
 166         other->setDirection(new_pos, *_parent);
 167         } break;
 168     case NODE_SYMMETRIC:
 169         // for symmetric nodes, place the other handle on the opposite side
 170         other->setRelativePos(-(new_pos - _parent->position()));
 171         break;
 172     default: break;
 173     }
 174
 175     setPosition(new_pos);
 176 }
 177
 178 void Handle::setPosition(Geom::Point const &p)
 179 {
 180     Geom::Point old_pos = position();
 181     ControlPoint::setPosition(p);
 182     sp_ctrlline_set_coords(SP_CTRLLINE(_handle_line), _parent->position(), position());
 183
 184     // update degeneration info and visibility
 185     if (Geom::are_near(position(), _parent->position()))
 186         _degenerate = true;
 187     else _degenerate = false;
 188
 189     if (_parent->_handles_shown && _parent->visible() && !_degenerate) {
 190         setVisible(true);
 191     } else {
 192         setVisible(false);
 193     }
 194 }
 195
 196 void Handle::setLength(double len)
 197 {
 198     if (isDegenerate()) return;
 199     Geom::Point dir = Geom::unit_vector(relativePos());
 200     setRelativePos(dir * len);
 201 }
 202
 203 void Handle::retract()
 204 {
 205     move(_parent->position());
 206 }
 207
 208 void Handle::setDirection(Geom::Point const &from, Geom::Point const &to)
 209 {
 210     setDirection(to - from);
 211 }
 212
 213 void Handle::setDirection(Geom::Point const &dir)
 214 {
 215     Geom::Point unitdir = Geom::unit_vector(dir);
 216     setRelativePos(unitdir * length());
 217 }
 218
 219 char const *Handle::handle_type_to_localized_string(NodeType type)
 220 {
 221     switch(type) {
 222     case NODE_CUSP: return _("Cusp node handle");
 223     case NODE_SMOOTH: return _("Smooth node handle");
 224     case NODE_SYMMETRIC: return _("Symmetric node handle");
 225     case NODE_AUTO: return _("Auto-smooth node handle");
 226     default: return "";
 227     }
 228 }
 229
 230 bool Handle::_eventHandler(GdkEvent *event)
 231 {
 232     switch (event->type)
 233     {
 234     case GDK_KEY_PRESS:
 235         switch (shortcut_key(event->key))
 236         {
 237         case GDK_s:
 238         case GDK_S:
 239             if (held_only_shift(event->key) && _parent->_type == NODE_CUSP) {
 240                 // when Shift+S is pressed when hovering over a handle belonging to a cusp node,
 241                 // hold this handle in place; otherwise process normally
 242                 // this handle is guaranteed not to be degenerate
 243                 other()->move(_parent->position() - (position() - _parent->position()));
 244                 _parent->setType(NODE_SMOOTH, false);
 245                 _parent->_pm().update(); // magic triple combo to add undo event
 246                 _parent->_pm().writeXML();
 247                 _parent->_pm()._commit(_("Change node type"));
 248                 return true;
 249             }
 250             break;
 251         default: break;
 252         }
 253     default: break;
 254     }
 255
 256     return ControlPoint::_eventHandler(event);
 257 }
 258
 259 bool Handle::grabbed(GdkEventMotion *)
 260 {
 261     _saved_other_pos = other()->position();
 262     _saved_length = _drag_out ? 0 : length();
 263     _pm()._handleGrabbed();
 264     return false;
 265 }
 266
 267 void Handle::dragged(Geom::Point &new_pos, GdkEventMotion *event)
 268 {
 269     Geom::Point parent_pos = _parent->position();
 270     Geom::Point origin = _last_drag_origin();
 271     SnapManager &sm = _desktop->namedview->snap_manager;
 272     bool snap = sm.someSnapperMightSnap();
 273     boost::optional<Inkscape::Snapper::SnapConstraint> ctrl_constraint;
 274
 275     // with Alt, preserve length
 276     if (held_alt(*event)) {
 277         new_pos = parent_pos + Geom::unit_vector(new_pos - parent_pos) * _saved_length;
 278         snap = false;
 279     }
 280     // with Ctrl, constrain to M_PI/rotationsnapsperpi increments from vertical
 281     // and the original position.
 282     if (held_control(*event)) {
 283         Inkscape::Preferences *prefs = Inkscape::Preferences::get();
 284         int snaps = 2 * prefs->getIntLimited("/options/rotationsnapsperpi/value", 12, 1, 1000);
 285
 286         // note: if snapping to the original position is only desired in the original
 287         // direction of the handle, change to Ray instead of Line
 288         Geom::Line original_line(parent_pos, origin);
 289         Geom::Line perp_line(parent_pos, parent_pos + Geom::rot90(origin - parent_pos));
 290         Geom::Point snap_pos = parent_pos + Geom::constrain_angle(
 291             Geom::Point(0,0), new_pos - parent_pos, snaps, Geom::Point(1,0));
 292         Geom::Point orig_pos = original_line.pointAt(original_line.nearestPoint(new_pos));
 293         Geom::Point perp_pos = perp_line.pointAt(perp_line.nearestPoint(new_pos));
 294
 295         Geom::Point result = snap_pos;
 296         ctrl_constraint = Inkscape::Snapper::SnapConstraint(parent_pos, parent_pos - snap_pos);
 297         if (Geom::distance(orig_pos, new_pos) < Geom::distance(result, new_pos)) {
 298             result = orig_pos;
 299             ctrl_constraint = Inkscape::Snapper::SnapConstraint(parent_pos, parent_pos - orig_pos);
 300         }
 301         if (Geom::distance(perp_pos, new_pos) < Geom::distance(result, new_pos)) {
 302             result = perp_pos;
 303             ctrl_constraint = Inkscape::Snapper::SnapConstraint(parent_pos, parent_pos - perp_pos);
 304         }
 305         new_pos = result;
 306     }
 307
 308     std::vector<Inkscape::SnapCandidatePoint> unselected;
 309     if (snap) {
 310         typedef ControlPointSelection::Set Set;
 311         Set &nodes = _parent->_selection.allPoints();
 312         for (Set::iterator i = nodes.begin(); i != nodes.end(); ++i) {
 313             Node *n = static_cast<Node*>(*i);
 314             Inkscape::SnapCandidatePoint p(n->position(), n->_snapSourceType(), n->_snapTargetType());
 315             unselected.push_back(p);
 316         }
 317         sm.setupIgnoreSelection(_desktop, true, &unselected);
 318
 319         Node *node_away = _parent->nodeAwayFrom(this);
 320         if (_parent->type() == NODE_SMOOTH && Node::_is_line_segment(_parent, node_away)) {
 321             Inkscape::Snapper::SnapConstraint cl(_parent->position(),
 322                 _parent->position() - node_away->position());
 323             Inkscape::SnappedPoint p;
 324             p = sm.constrainedSnap(Inkscape::SnapCandidatePoint(new_pos, SNAPSOURCE_NODE_HANDLE), cl);
 325             new_pos = p.getPoint();
 326         } else if (ctrl_constraint) {
 327             // NOTE: this is subtly wrong.
 328             // We should get all possible constraints and snap along them using
 329             // multipleConstrainedSnaps, instead of first snapping to angle and the to objects
 330             Inkscape::SnappedPoint p;
 331             p = sm.constrainedSnap(Inkscape::SnapCandidatePoint(new_pos, SNAPSOURCE_NODE_HANDLE), *ctrl_constraint);
 332             new_pos = p.getPoint();
 333         } else {
 334             sm.freeSnapReturnByRef(new_pos, SNAPSOURCE_NODE_HANDLE);
 335         }
 336         sm.unSetup();
 337     }
 338
 339
 340     // with Shift, if the node is cusp, rotate the other handle as well
 341     if (_parent->type() == NODE_CUSP && !_drag_out) {
 342         if (held_shift(*event)) {
 343             Geom::Point other_relpos = _saved_other_pos - parent_pos;
 344             other_relpos *= Geom::Rotate(Geom::angle_between(origin - parent_pos, new_pos - parent_pos));
 345             other()->setRelativePos(other_relpos);
 346         } else {
 347             // restore the position
 348             other()->setPosition(_saved_other_pos);
 349         }
 350     }
 351     move(new_pos); // needed for correct update, even though it's redundant
 352     _pm().update();
 353 }
 354
 355 void Handle::ungrabbed(GdkEventButton *event)
 356 {
 357     // hide the handle if it's less than dragtolerance away from the node
 358     // TODO is this actually desired?
 359     Inkscape::Preferences *prefs = Inkscape::Preferences::get();
 360     int drag_tolerance = prefs->getIntLimited("/options/dragtolerance/value", 0, 0, 100);
 361
 362     Geom::Point dist = _desktop->d2w(_parent->position()) - _desktop->d2w(position());
 363     if (dist.length() <= drag_tolerance) {
 364         move(_parent->position());
 365     }
 366
 367     // HACK: If the handle was dragged out, call parent's ungrabbed handler,
 368     // so that transform handles reappear
 369     if (_drag_out) {
 370         _parent->ungrabbed(event);
 371     }
 372     _drag_out = false;
 373
 374     _pm()._handleUngrabbed();
 375 }
 376
 377 bool Handle::clicked(GdkEventButton *event)
 378 {
 379     _pm()._handleClicked(this, event);
 380     return true;
 381 }
 382
 383 Handle *Handle::other()
 384 {
 385     if (this == &_parent->_front) return &_parent->_back;
 386     return &_parent->_front;
 387 }
 388
 389 static double snap_increment_degrees() {
 390     Inkscape::Preferences *prefs = Inkscape::Preferences::get();
 391     int snaps = prefs->getIntLimited("/options/rotationsnapsperpi/value", 12, 1, 1000);
 392     return 180.0 / snaps;
 393 }
 394
 395 Glib::ustring Handle::_getTip(unsigned state)
 396 {
 397     char const *more;
 398     bool can_shift_rotate = _parent->type() == NODE_CUSP && !other()->isDegenerate();
 399     if (can_shift_rotate) {
 400         more = C_("Path handle tip", "more: Shift, Ctrl, Alt");
 401     } else {
 402         more = C_("Path handle tip", "more: Ctrl, Alt");
 403     }
 404     if (state_held_alt(state)) {
 405         if (state_held_control(state)) {
 406             if (state_held_shift(state) && can_shift_rotate) {
 407                 return format_tip(C_("Path handle tip",
 408                     "<b>Shift+Ctrl+Alt</b>: preserve length and snap rotation angle to %g° "
 409                     "increments while rotating both handles"),
 410                     snap_increment_degrees());
 411             } else {
 412                 return format_tip(C_("Path handle tip",
 413                     "<b>Ctrl+Alt</b>: preserve length and snap rotation angle to %g° increments"),
 414                     snap_increment_degrees());
 415             }
 416         } else {
 417             if (state_held_shift(state) && can_shift_rotate) {
 418                 return C_("Path handle tip",
 419                     "<b>Shift+Alt</b>: preserve handle length and rotate both handles");
 420             } else {
 421                 return C_("Path handle tip",
 422                     "<b>Alt</b>: preserve handle length while dragging");
 423             }
 424         }
 425     } else {
 426         if (state_held_control(state)) {
 427             if (state_held_shift(state) && can_shift_rotate) {
 428                 return format_tip(C_("Path handle tip",
 429                     "<b>Shift+Ctrl</b>: snap rotation angle to %g° increments and rotate both handles"),
 430                     snap_increment_degrees());
 431             } else {
 432                 return format_tip(C_("Path handle tip",
 433                     "<b>Ctrl</b>: snap rotation angle to %g° increments, click to retract"),
 434                     snap_increment_degrees());
 435             }
 436         } else if (state_held_shift(state) && can_shift_rotate) {
 437             return C_("Path hande tip",
 438                 "<b>Shift</b>: rotate both handles by the same angle");
 439         }
 440     }
 441
 442     switch (_parent->type()) {
 443     case NODE_AUTO:
 444         return format_tip(C_("Path handle tip",
 445             "<b>Auto node handle</b>: drag to convert to smooth node (%s)"), more);
 446     default:
 447         return format_tip(C_("Path handle tip",
 448             "<b>%s</b>: drag to shape the segment (%s)"),
 449             handle_type_to_localized_string(_parent->type()), more);
 450     }
 451 }
 452
 453 Glib::ustring Handle::_getDragTip(GdkEventMotion */*event*/)
 454 {
 455     Geom::Point dist = position() - _last_drag_origin();
 456     // report angle in mathematical convention
 457     double angle = Geom::angle_between(Geom::Point(-1,0), position() - _parent->position());
 458     angle += M_PI; // angle is (-M_PI...M_PI] - offset by +pi and scale to 0...360
 459     angle *= 360.0 / (2 * M_PI);
 460     GString *x = SP_PX_TO_METRIC_STRING(dist[Geom::X], _desktop->namedview->getDefaultMetric());
 461     GString *y = SP_PX_TO_METRIC_STRING(dist[Geom::Y], _desktop->namedview->getDefaultMetric());
 462     GString *len = SP_PX_TO_METRIC_STRING(length(), _desktop->namedview->getDefaultMetric());
 463     Glib::ustring ret = format_tip(C_("Path handle tip",
 464         "Move handle by %s, %s; angle %.2f°, length %s"), x->str, y->str, angle, len->str);
 465     g_string_free(x, TRUE);
 466     g_string_free(y, TRUE);
 467     g_string_free(len, TRUE);
 468     return ret;
 469 }
 470
 471 /**
 472  * @class Node
 473  * @brief Curve endpoint in an editable path.
 474  *
 475  * The method move() keeps node type invariants during translations.
 476  */
 477
 478 Node::Node(NodeSharedData const &data, Geom::Point const &initial_pos)
 479     : SelectableControlPoint(data.desktop, initial_pos, Gtk::ANCHOR_CENTER,
 480         SP_CTRL_SHAPE_DIAMOND, 9.0, *data.selection, &node_colors, data.node_group)
 481     , _front(data, initial_pos, this)
 482     , _back(data, initial_pos, this)
 483     , _type(NODE_CUSP)
 484     , _handles_shown(false)
 485 {
 486     // NOTE we do not set type here, because the handles are still degenerate
 487 }
 488
 489 // NOTE: not using iterators won't make this much quicker because iterators can be 100% inlined.
 490 Node *Node::_next()
 491 {
 492     NodeList::iterator n = NodeList::get_iterator(this).next();
 493     if (n) return n.ptr();
 494     return NULL;
 495 }
 496 Node *Node::_prev()
 497 {
 498     NodeList::iterator p = NodeList::get_iterator(this).prev();
 499     if (p) return p.ptr();
 500     return NULL;
 501 }
 502
 503 void Node::move(Geom::Point const &new_pos)
 504 {
 505     // move handles when the node moves.
 506     Geom::Point old_pos = position();
 507     Geom::Point delta = new_pos - position();
 508     setPosition(new_pos);
 509     _front.setPosition(_front.position() + delta);
 510     _back.setPosition(_back.position() + delta);
 511
 512     // if the node has a smooth handle after a line segment, it should be kept colinear
 513     // with the segment
 514     _fixNeighbors(old_pos, new_pos);
 515 }
 516
 517 void Node::transform(Geom::Matrix const &m)
 518 {
 519     Geom::Point old_pos = position();
 520     setPosition(position() * m);
 521     _front.setPosition(_front.position() * m);
 522     _back.setPosition(_back.position() * m);
 523
 524     /* Affine transforms keep handle invariants for smooth and symmetric nodes,
 525      * but smooth nodes at ends of linear segments and auto nodes need special treatment */
 526     _fixNeighbors(old_pos, position());
 527 }
 528
 529 Geom::Rect Node::bounds()
 530 {
 531     Geom::Rect b(position(), position());
 532     b.expandTo(_front.position());
 533     b.expandTo(_back.position());
 534     return b;
 535 }
 536
 537 void Node::_fixNeighbors(Geom::Point const &old_pos, Geom::Point const &new_pos)
 538 {
 539     /* This method restores handle invariants for neighboring nodes,
 540      * and invariants that are based on positions of those nodes for this one. */
 541
 542     /* Fix auto handles */
 543     if (_type == NODE_AUTO) _updateAutoHandles();
 544     if (old_pos != new_pos) {
 545         if (_next() && _next()->_type == NODE_AUTO) _next()->_updateAutoHandles();
 546         if (_prev() && _prev()->_type == NODE_AUTO) _prev()->_updateAutoHandles();
 547     }
 548
 549     /* Fix smooth handles at the ends of linear segments.
 550      * Rotate the appropriate handle to be colinear with the segment.
 551      * If there is a smooth node at the other end of the segment, rotate it too. */
 552     Handle *handle, *other_handle;
 553     Node *other;
 554     if (_is_line_segment(this, _next())) {
 555         handle = &_back;
 556         other = _next();
 557         other_handle = &_next()->_front;
 558     } else if (_is_line_segment(_prev(), this)) {
 559         handle = &_front;
 560         other = _prev();
 561         other_handle = &_prev()->_back;
 562     } else return;
 563
 564     if (_type == NODE_SMOOTH && !handle->isDegenerate()) {
 565         handle->setDirection(other->position(), new_pos);
 566     }
 567     // also update the handle on the other end of the segment
 568     if (other->_type == NODE_SMOOTH && !other_handle->isDegenerate()) {
 569         other_handle->setDirection(new_pos, other->position());
 570     }
 571 }
 572
 573 void Node::_updateAutoHandles()
 574 {
 575     // Recompute the position of automatic handles.
 576     // For endnodes, retract both handles. (It's only possible to create an end auto node
 577     // through the XML editor.)
 578     if (isEndNode()) {
 579         _front.retract();
 580         _back.retract();
 581         return;
 582     }
 583
 584     // Auto nodes automaticaly adjust their handles to give an appearance of smoothness,
 585     // no matter what their surroundings are.
 586     Geom::Point vec_next = _next()->position() - position();
 587     Geom::Point vec_prev = _prev()->position() - position();
 588     double len_next = vec_next.length(), len_prev = vec_prev.length();
 589     if (len_next > 0 && len_prev > 0) {
 590         // "dir" is an unit vector perpendicular to the bisector of the angle created
 591         // by the previous node, this auto node and the next node.
 592         Geom::Point dir = Geom::unit_vector((len_prev / len_next) * vec_next - vec_prev);
 593         // Handle lengths are equal to 1/3 of the distance from the adjacent node.
 594         _back.setRelativePos(-dir * (len_prev / 3));
 595         _front.setRelativePos(dir * (len_next / 3));
 596     } else {
 597         // If any of the adjacent nodes coincides, retract both handles.
 598         _front.retract();
 599         _back.retract();
 600     }
 601 }
 602
 603 void Node::showHandles(bool v)
 604 {
 605     _handles_shown = v;
 606     if (!_front.isDegenerate()) _front.setVisible(v);
 607     if (!_back.isDegenerate()) _back.setVisible(v);
 608 }
 609
 610 /** Sets the node type and optionally restores the invariants associated with the given type.
 611  * @param type The type to set
 612  * @param update_handles Whether to restore invariants associated with the given type.
 613  *                       Passing false is useful e.g. wen initially creating the path,
 614  *                       and when making cusp nodes during some node algorithms.
 615  *                       Pass true when used in response to an UI node type button.
 616  */
 617 void Node::setType(NodeType type, bool update_handles)
 618 {
 619     if (type == NODE_PICK_BEST) {
 620         pickBestType();
 621         updateState(); // The size of the control might have changed
 622         return;
 623     }
 624
 625     // if update_handles is true, adjust handle positions to match the node type
 626     // handle degenerate handles appropriately
 627     if (update_handles) {
 628         switch (type) {
 629         case NODE_CUSP:
 630             // nothing to do
 631             break;
 632         case NODE_AUTO:
 633             // auto handles make no sense for endnodes
 634             if (isEndNode()) return;
 635             _updateAutoHandles();
 636             break;
 637         case NODE_SMOOTH: {
 638             // ignore attempts to make smooth endnodes.
 639             if (isEndNode()) return;
 640             // rotate handles to be colinear
 641             // for degenerate nodes set positions like auto handles
 642             bool prev_line = _is_line_segment(_prev(), this);
 643             bool next_line = _is_line_segment(this, _next());
 644             if (_type == NODE_SMOOTH) {
 645                 // For a node that is already smooth and has a degenerate handle,
 646                 // drag out the second handle without changing the direction of the first one.
 647                 if (_front.isDegenerate()) {
 648                     double dist = Geom::distance(_next()->position(), position());
 649                     _front.setRelativePos(Geom::unit_vector(-_back.relativePos()) * dist / 3);
 650                 }
 651                 if (_back.isDegenerate()) {
 652                     double dist = Geom::distance(_prev()->position(), position());
 653                     _back.setRelativePos(Geom::unit_vector(-_front.relativePos()) * dist / 3);
 654                 }
 655             } else if (isDegenerate()) {
 656                 _updateAutoHandles();
 657             } else if (_front.isDegenerate()) {
 658                 // if the front handle is degenerate and this...next is a line segment,
 659                 // make back colinear; otherwise pull out the other handle
 660                 // to 1/3 of distance to prev
 661                 if (next_line) {
 662                     _back.setDirection(*_next(), *this);
 663                 } else if (_prev()) {
 664                     Geom::Point dir = direction(_back, *this);
 665                     _front.setRelativePos(Geom::distance(_prev()->position(), position()) / 3 * dir);
 666                 }
 667             } else if (_back.isDegenerate()) {
 668                 if (prev_line) {
 669                     _front.setDirection(*_prev(), *this);
 670                 } else if (_next()) {
 671                     Geom::Point dir = direction(_front, *this);
 672                     _back.setRelativePos(Geom::distance(_next()->position(), position()) / 3 * dir);
 673                 }
 674             } else {
 675                 // both handles are extended. make colinear while keeping length
 676                 // first make back colinear with the vector front ---> back,
 677                 // then make front colinear with back ---> node
 678                 // (not back ---> front because back's position was changed in the first call)
 679                 _back.setDirection(_front, _back);
 680                 _front.setDirection(_back, *this);
 681             }
 682             } break;
 683         case NODE_SYMMETRIC:
 684             if (isEndNode()) return; // symmetric handles make no sense for endnodes
 685             if (isDegenerate()) {
 686                 // similar to auto handles but set the same length for both
 687                 Geom::Point vec_next = _next()->position() - position();
 688                 Geom::Point vec_prev = _prev()->position() - position();
 689                 double len_next = vec_next.length(), len_prev = vec_prev.length();
 690                 double len = (len_next + len_prev) / 6; // take 1/3 of average
 691                 if (len == 0) return;
 692
 693                 Geom::Point dir = Geom::unit_vector((len_prev / len_next) * vec_next - vec_prev);
 694                 _back.setRelativePos(-dir * len);
 695                 _front.setRelativePos(dir * len);
 696             } else {
 697                 // Both handles are extended. Compute average length, use direction from
 698                 // back handle to front handle. This also works correctly for degenerates
 699                 double len = (_front.length() + _back.length()) / 2;
 700                 Geom::Point dir = direction(_back, _front);
 701                 _front.setRelativePos(dir * len);
 702                 _back.setRelativePos(-dir * len);
 703             }
 704             break;
 705         default: break;
 706         }
 707     }
 708     _type = type;
 709     _setShape(_node_type_to_shape(type));
 710     updateState();
 711 }
 712
 713 /** Pick the best type for this node, based on the position of its handles.
 714  * This is what assigns types to nodes created using the pen tool. */
 715 void Node::pickBestType()
 716 {
 717     _type = NODE_CUSP;
 718     bool front_degen = _front.isDegenerate();
 719     bool back_degen = _back.isDegenerate();
 720     bool both_degen = front_degen && back_degen;
 721     bool neither_degen = !front_degen && !back_degen;
 722     do {
 723         // if both handles are degenerate, do nothing
 724         if (both_degen) break;
 725         // if neither are degenerate, check their respective positions
 726         if (neither_degen) {
 727             Geom::Point front_delta = _front.position() - position();
 728             Geom::Point back_delta = _back.position() - position();
 729             // for now do not automatically make nodes symmetric, it can be annoying
 730             /*if (Geom::are_near(front_delta, -back_delta)) {
 731                 _type = NODE_SYMMETRIC;
 732                 break;
 733             }*/
 734             if (Geom::are_near(Geom::unit_vector(front_delta),
 735                 Geom::unit_vector(-back_delta)))
 736             {
 737                 _type = NODE_SMOOTH;
 738                 break;
 739             }
 740         }
 741         // check whether the handle aligns with the previous line segment.
 742         // we know that if front is degenerate, back isn't, because
 743         // both_degen was false
 744         if (front_degen && _next() && _next()->_back.isDegenerate()) {
 745             Geom::Point segment_delta = Geom::unit_vector(_next()->position() - position());
 746             Geom::Point handle_delta = Geom::unit_vector(_back.position() - position());
 747             if (Geom::are_near(segment_delta, -handle_delta)) {
 748                 _type = NODE_SMOOTH;
 749                 break;
 750             }
 751         } else if (back_degen && _prev() && _prev()->_front.isDegenerate()) {
 752             Geom::Point segment_delta = Geom::unit_vector(_prev()->position() - position());
 753             Geom::Point handle_delta = Geom::unit_vector(_front.position() - position());
 754             if (Geom::are_near(segment_delta, -handle_delta)) {
 755                 _type = NODE_SMOOTH;
 756                 break;
 757             }
 758         }
 759     } while (false);
 760     _setShape(_node_type_to_shape(_type));
 761     updateState();
 762 }
 763
 764 bool Node::isEndNode()
 765 {
 766     return !_prev() || !_next();
 767 }
 768
 769 /** Move the node to the bottom of its canvas group. Useful for node break, to ensure that
 770  * the selected nodes are above the unselected ones. */
 771 void Node::sink()
 772 {
 773     sp_canvas_item_move_to_z(_canvas_item, 0);
 774 }
 775
 776 NodeType Node::parse_nodetype(char x)
 777 {
 778     switch (x) {
 779     case 'a': return NODE_AUTO;
 780     case 'c': return NODE_CUSP;
 781     case 's': return NODE_SMOOTH;
 782     case 'z': return NODE_SYMMETRIC;
 783     default: return NODE_PICK_BEST;
 784     }
 785 }
 786
 787 /** Customized event handler to catch scroll events needed for selection grow/shrink. */
 788 bool Node::_eventHandler(GdkEvent *event)
 789 {
 790     int dir = 0;
 791
 792     switch (event->type)
 793     {
 794     case GDK_SCROLL:
 795         if (event->scroll.direction == GDK_SCROLL_UP) {
 796             dir = 1;
 797         } else if (event->scroll.direction == GDK_SCROLL_DOWN) {
 798             dir = -1;
 799         } else break;
 800         if (held_control(event->scroll)) {
 801             _linearGrow(dir);
 802         } else {
 803             _selection.spatialGrow(this, dir);
 804         }
 805         return true;
 806     case GDK_KEY_PRESS:
 807         switch (shortcut_key(event->key))
 808         {
 809         case GDK_Page_Up:
 810             dir = 1;
 811             break;
 812         case GDK_Page_Down:
 813             dir = -1;
 814             break;
 815         default: goto bail_out;
 816         }
 817
 818         if (held_control(event->key)) {
 819             _linearGrow(dir);
 820         } else {
 821             _selection.spatialGrow(this, dir);
 822         }
 823         return true;
 824     default:
 825         break;
 826     }
 827
 828     bail_out:
 829     return ControlPoint::_eventHandler(event);
 830 }
 831
 832 // TODO Move this to 2Geom!
 833 static double bezier_length (Geom::Point a0, Geom::Point a1, Geom::Point a2, Geom::Point a3)
 834 {
 835     double lower = Geom::distance(a0, a3);
 836     double upper = Geom::distance(a0, a1) + Geom::distance(a1, a2) + Geom::distance(a2, a3);
 837
 838     if (upper - lower < Geom::EPSILON) return (lower + upper)/2;
 839
 840     Geom::Point // Casteljau subdivision
 841         b0 = a0,
 842         c0 = a3,
 843         b1 = 0.5*(a0 + a1),
 844         t0 = 0.5*(a1 + a2),
 845         c1 = 0.5*(a2 + a3),
 846         b2 = 0.5*(b1 + t0),
 847         c2 = 0.5*(t0 + c1),
 848         b3 = 0.5*(b2 + c2); // == c3
 849     return bezier_length(b0, b1, b2, b3) + bezier_length(b3, c2, c1, c0);
 850 }
 851
 852 /** Select or deselect a node in this node's subpath based on its path distance from this node.
 853  * @param dir If negative, shrink selection by one node; if positive, grow by one node */
 854 void Node::_linearGrow(int dir)
 855 {
 856     // Interestingly, we do not need any help from PathManipulator when doing linear grow.
 857     // First handle the trivial case of growing over an unselected node.
 858     if (!selected() && dir > 0) {
 859         _selection.insert(this);
 860         return;
 861     }
 862
 863     NodeList::iterator this_iter = NodeList::get_iterator(this);
 864     NodeList::iterator fwd = this_iter, rev = this_iter;
 865     double distance_back = 0, distance_front = 0;
 866
 867     // Linear grow is simple. We find the first unselected nodes in each direction
 868     // and compare the linear distances to them.
 869     if (dir > 0) {
 870         if (!selected()) {
 871             _selection.insert(this);
 872             return;
 873         }
 874
 875         // find first unselected nodes on both sides
 876         while (fwd && fwd->selected()) {
 877             NodeList::iterator n = fwd.next();
 878             distance_front += bezier_length(*fwd, fwd->_front, n->_back, *n);
 879             fwd = n;
 880             if (fwd == this_iter)
 881                 // there is no unselected node in this cyclic subpath
 882                 return;
 883         }
 884         // do the same for the second direction. Do not check for equality with
 885         // this node, because there is at least one unselected node in the subpath,
 886         // so we are guaranteed to stop.
 887         while (rev && rev->selected()) {
 888             NodeList::iterator p = rev.prev();
 889             distance_back += bezier_length(*rev, rev->_back, p->_front, *p);
 890             rev = p;
 891         }
 892
 893         NodeList::iterator t; // node to select
 894         if (fwd && rev) {
 895             if (distance_front <= distance_back) t = fwd;
 896             else t = rev;
 897         } else {
 898             if (fwd) t = fwd;
 899             if (rev) t = rev;
 900         }
 901         if (t) _selection.insert(t.ptr());
 902
 903     // Linear shrink is more complicated. We need to find the farthest selected node.
 904     // This means we have to check the entire subpath. We go in the direction in which
 905     // the distance we traveled is lower. We do this until we run out of nodes (ends of path)
 906     // or the two iterators meet. On the way, we store the last selected node and its distance
 907     // in each direction (if any). At the end, we choose the one that is farther and deselect it.
 908     } else {
 909         // both iterators that store last selected nodes are initially empty
 910         NodeList::iterator last_fwd, last_rev;
 911         double last_distance_back = 0, last_distance_front = 0;
 912
 913         while (rev || fwd) {
 914             if (fwd && (!rev || distance_front <= distance_back)) {
 915                 if (fwd->selected()) {
 916                     last_fwd = fwd;
 917                     last_distance_front = distance_front;
 918                 }
 919                 NodeList::iterator n = fwd.next();
 920                 if (n) distance_front += bezier_length(*fwd, fwd->_front, n->_back, *n);
 921                 fwd = n;
 922             } else if (rev && (!fwd || distance_front > distance_back)) {
 923                 if (rev->selected()) {
 924                     last_rev = rev;
 925                     last_distance_back = distance_back;
 926                 }
 927                 NodeList::iterator p = rev.prev();
 928                 if (p) distance_back += bezier_length(*rev, rev->_back, p->_front, *p);
 929                 rev = p;
 930             }
 931             // Check whether we walked the entire cyclic subpath.
 932             // This is initially true because both iterators start from this node,
 933             // so this check cannot go in the while condition.
 934             // When this happens, we need to check the last node, pointed to by the iterators.
 935             if (fwd && fwd == rev) {
 936                 if (!fwd->selected()) break;
 937                 NodeList::iterator fwdp = fwd.prev(), revn = rev.next();
 938                 double df = distance_front + bezier_length(*fwdp, fwdp->_front, fwd->_back, *fwd);
 939                 double db = distance_back + bezier_length(*revn, revn->_back, rev->_front, *rev);
 940                 if (df > db) {
 941                     last_fwd = fwd;
 942                     last_distance_front = df;
 943                 } else {
 944                     last_rev = rev;
 945                     last_distance_back = db;
 946                 }
 947                 break;
 948             }
 949         }
 950
 951         NodeList::iterator t;
 952         if (last_fwd && last_rev) {
 953             if (last_distance_front >= last_distance_back) t = last_fwd;
 954             else t = last_rev;
 955         } else {
 956             if (last_fwd) t = last_fwd;
 957             if (last_rev) t = last_rev;
 958         }
 959         if (t) _selection.erase(t.ptr());
 960     }
 961 }
 962
 963 void Node::_setState(State state)
 964 {
 965     // change node size to match type and selection state
 966     switch (_type) {
 967     case NODE_AUTO:
 968     case NODE_CUSP:
 969         if (selected()) _setSize(11);
 970         else _setSize(9);
 971         break;
 972     default:
 973         if(selected()) _setSize(9);
 974         else _setSize(7);
 975         break;
 976     }
 977     SelectableControlPoint::_setState(state);
 978 }
 979
 980 bool Node::grabbed(GdkEventMotion *event)
 981 {
 982     if (SelectableControlPoint::grabbed(event))
 983         return true;
 984
 985     // Dragging out handles with Shift + drag on a node.
 986     if (!held_shift(*event)) return false;
 987
 988     Handle *h;
 989     Geom::Point evp = event_point(*event);
 990     Geom::Point rel_evp = evp - _last_click_event_point();
 991
 992     // This should work even if dragtolerance is zero and evp coincides with node position.
 993     double angle_next = HUGE_VAL;
 994     double angle_prev = HUGE_VAL;
 995     bool has_degenerate = false;
 996     // determine which handle to drag out based on degeneration and the direction of drag
 997     if (_front.isDegenerate() && _next()) {
 998         Geom::Point next_relpos = _desktop->d2w(_next()->position())
 999             - _desktop->d2w(position());
1000         angle_next = fabs(Geom::angle_between(rel_evp, next_relpos));
1001         has_degenerate = true;
1002     }
1003     if (_back.isDegenerate() && _prev()) {
1004         Geom::Point prev_relpos = _desktop->d2w(_prev()->position())
1005             - _desktop->d2w(position());
1006         angle_prev = fabs(Geom::angle_between(rel_evp, prev_relpos));
1007         has_degenerate = true;
1008     }
1009     if (!has_degenerate) return false;
1010     h = angle_next < angle_prev ? &_front : &_back;
1011
1012     h->setPosition(_desktop->w2d(evp));
1013     h->setVisible(true);
1014     h->transferGrab(this, event);
1015     Handle::_drag_out = true;
1016     return true;
1017 }
1018
1019 void Node::dragged(Geom::Point &new_pos, GdkEventMotion *event)
1020 {
1021     // For a note on how snapping is implemented in Inkscape, see snap.h.
1022     SnapManager &sm = _desktop->namedview->snap_manager;
1023     // even if we won't really snap, we might still call the one of the
1024     // constrainedSnap() methods to enforce the constraints, so we need
1025     // to setup the snapmanager anyway; this is also required for someSnapperMightSnap()
1026     sm.setup(_desktop);
1027
1028     // do not snap when Shift is pressed
1029     bool snap = !held_shift(*event) && sm.someSnapperMightSnap();
1030
1031     Inkscape::SnappedPoint sp;
1032     std::vector<Inkscape::SnapCandidatePoint> unselected;
1033     if (snap) {
1034         /* setup
1035          * TODO We are doing this every time a snap happens. It should once be done only once
1036          *      per drag - maybe in the grabbed handler?
1037          * TODO Unselected nodes vector must be valid during the snap run, because it is not
1038          *      copied. Fix this in snap.h and snap.cpp, then the above.
1039          * TODO Snapping to unselected segments of selected paths doesn't work yet. */
1040
1041         // Build the list of unselected nodes.
1042         typedef ControlPointSelection::Set Set;
1043         Set &nodes = _selection.allPoints();
1044         for (Set::iterator i = nodes.begin(); i != nodes.end(); ++i) {
1045             if (!(*i)->selected()) {
1046                 Node *n = static_cast<Node*>(*i);
1047                 Inkscape::SnapCandidatePoint p(n->position(), n->_snapSourceType(), n->_snapTargetType());
1048                 unselected.push_back(p);
1049             }
1050         }
1051         sm.unSetup();
1052         sm.setupIgnoreSelection(_desktop, true, &unselected);
1053     }
1054
1055     if (held_control(*event)) {
1056         Geom::Point origin = _last_drag_origin();
1057         std::vector<Inkscape::Snapper::SnapConstraint> constraints;
1058         if (held_alt(*event)) {
1059             // with Ctrl+Alt, constrain to handle lines
1060             // project the new position onto a handle line that is closer;
1061             // also snap to perpendiculars of handle lines
1062
1063             Inkscape::Preferences *prefs = Inkscape::Preferences::get();
1064             int snaps = prefs->getIntLimited("/options/rotationsnapsperpi/value", 12, 1, 1000);
1065             double min_angle = M_PI / snaps;
1066
1067             boost::optional<Geom::Point> front_point, back_point, fperp_point, bperp_point;
1068             if (_front.isDegenerate()) {
1069                 if (_is_line_segment(this, _next()))
1070                     front_point = _next()->position() - origin;
1071             } else {
1072                 front_point = _front.relativePos();
1073             }
1074             if (_back.isDegenerate()) {
1075                 if (_is_line_segment(_prev(), this))
1076                     back_point = _prev()->position() - origin;
1077             } else {
1078                 back_point = _back.relativePos();
1079             }
1080             if (front_point) {
1081                 constraints.push_back(Inkscape::Snapper::SnapConstraint(origin, *front_point));
1082                 fperp_point = Geom::rot90(*front_point);
1083             }
1084             if (back_point) {
1085                 constraints.push_back(Inkscape::Snapper::SnapConstraint(origin, *back_point));
1086                 bperp_point = Geom::rot90(*back_point);
1087             }
1088             // perpendiculars only snap when they are further than snap increment away
1089             // from the second handle constraint
1090             if (fperp_point && (!back_point ||
1091                 (fabs(Geom::angle_between(*fperp_point, *back_point)) > min_angle &&
1092                  fabs(Geom::angle_between(*fperp_point, *back_point)) < M_PI - min_angle)))
1093             {
1094                 constraints.push_back(Inkscape::Snapper::SnapConstraint(origin, *fperp_point));
1095             }
1096             if (bperp_point && (!front_point ||
1097                 (fabs(Geom::angle_between(*bperp_point, *front_point)) > min_angle &&
1098                  fabs(Geom::angle_between(*bperp_point, *front_point)) < M_PI - min_angle)))
1099             {
1100                 constraints.push_back(Inkscape::Snapper::SnapConstraint(origin, *bperp_point));
1101             }
1102
1103             sp = sm.multipleConstrainedSnaps(Inkscape::SnapCandidatePoint(new_pos, _snapSourceType()), constraints, held_shift(*event));
1104         } else {
1105             // with Ctrl, constrain to axes
1106             constraints.push_back(Inkscape::Snapper::SnapConstraint(origin, Geom::Point(1, 0)));
1107             constraints.push_back(Inkscape::Snapper::SnapConstraint(origin, Geom::Point(0, 1)));
1108             sp = sm.multipleConstrainedSnaps(Inkscape::SnapCandidatePoint(new_pos, _snapSourceType()), constraints, held_shift(*event));
1109         }
1110         new_pos = sp.getPoint();
1111     } else if (snap) {
1112         sp = sm.freeSnap(Inkscape::SnapCandidatePoint(new_pos, _snapSourceType()));
1113         new_pos = sp.getPoint();
1114     }
1115
1116     sm.unSetup();
1117
1118     SelectableControlPoint::dragged(new_pos, event);
1119 }
1120
1121 bool Node::clicked(GdkEventButton *event)
1122 {
1123     if(_pm()._nodeClicked(this, event))
1124         return true;
1125     return SelectableControlPoint::clicked(event);
1126 }
1127
1128 Inkscape::SnapSourceType Node::_snapSourceType()
1129 {
1130     if (_type == NODE_SMOOTH || _type == NODE_AUTO)
1131         return SNAPSOURCE_NODE_SMOOTH;
1132     return SNAPSOURCE_NODE_CUSP;
1133 }
1134 Inkscape::SnapTargetType Node::_snapTargetType()
1135 {
1136     if (_type == NODE_SMOOTH || _type == NODE_AUTO)
1137         return SNAPTARGET_NODE_SMOOTH;
1138     return SNAPTARGET_NODE_CUSP;
1139 }
1140
1141 /** @brief Gets the handle that faces the given adjacent node.
1142  * Will abort with error if the given node is not adjacent. */
1143 Handle *Node::handleToward(Node *to)
1144 {
1145     if (_next() == to) {
1146         return front();
1147     }
1148     if (_prev() == to) {
1149         return back();
1150     }
1151     g_error("Node::handleToward(): second node is not adjacent!");
1152 }
1153
1154 /** @brief Gets the node in the direction of the given handle.
1155  * Will abort with error if the handle doesn't belong to this node. */
1156 Node *Node::nodeToward(Handle *dir)
1157 {
1158     if (front() == dir) {
1159         return _next();
1160     }
1161     if (back() == dir) {
1162         return _prev();
1163     }
1164     g_error("Node::nodeToward(): handle is not a child of this node!");
1165 }
1166
1167 /** @brief Gets the handle that goes in the direction opposite to the given adjacent node.
1168  * Will abort with error if the given node is not adjacent. */
1169 Handle *Node::handleAwayFrom(Node *to)
1170 {
1171     if (_next() == to) {
1172         return back();
1173     }
1174     if (_prev() == to) {
1175         return front();
1176     }
1177     g_error("Node::handleAwayFrom(): second node is not adjacent!");
1178 }
1179
1180 /** @brief Gets the node in the direction opposite to the given handle.
1181  * Will abort with error if the handle doesn't belong to this node. */
1182 Node *Node::nodeAwayFrom(Handle *h)
1183 {
1184     if (front() == h) {
1185         return _prev();
1186     }
1187     if (back() == h) {
1188         return _next();
1189     }
1190     g_error("Node::nodeAwayFrom(): handle is not a child of this node!");
1191 }
1192
1193 Glib::ustring Node::_getTip(unsigned state)
1194 {
1195     if (state_held_shift(state)) {
1196         bool can_drag_out = (_next() && _front.isDegenerate()) || (_prev() && _back.isDegenerate());
1197         if (can_drag_out) {
1198             /*if (state_held_control(state)) {
1199                 return format_tip(C_("Path node tip",
1200                     "<b>Shift+Ctrl:</b> drag out a handle and snap its angle "
1201                     "to %f° increments"), snap_increment_degrees());
1202             }*/
1203             return C_("Path node tip",
1204                 "<b>Shift</b>: drag out a handle, click to toggle selection");
1205         }
1206         return C_("Path node tip", "<b>Shift</b>: click to toggle selection");
1207     }
1208
1209     if (state_held_control(state)) {
1210         if (state_held_alt(state)) {
1211             return C_("Path node tip", "<b>Ctrl+Alt</b>: move along handle lines, click to delete node");
1212         }
1213         return C_("Path node tip",
1214             "<b>Ctrl</b>: move along axes, click to change node type");
1215     }
1216
1217     if (state_held_alt(state)) {
1218         return C_("Path node tip", "<b>Alt</b>: sculpt nodes");
1219     }
1220
1221     // No modifiers: assemble tip from node type
1222     char const *nodetype = node_type_to_localized_string(_type);
1223     if (_selection.transformHandlesEnabled() && selected()) {
1224         if (_selection.size() == 1) {
1225             return format_tip(C_("Path node tip",
1226                 "<b>%s</b>: drag to shape the path (more: Shift, Ctrl, Alt)"), nodetype);
1227         }
1228         return format_tip(C_("Path node tip",
1229             "<b>%s</b>: drag to shape the path, click to toggle scale/rotation handles (more: Shift, Ctrl, Alt)"), nodetype);
1230     }
1231     return format_tip(C_("Path node tip",
1232         "<b>%s</b>: drag to shape the path, click to select only this node (more: Shift, Ctrl, Alt)"), nodetype);
1233 }
1234
1235 Glib::ustring Node::_getDragTip(GdkEventMotion */*event*/)
1236 {
1237     Geom::Point dist = position() - _last_drag_origin();
1238     GString *x = SP_PX_TO_METRIC_STRING(dist[Geom::X], _desktop->namedview->getDefaultMetric());
1239     GString *y = SP_PX_TO_METRIC_STRING(dist[Geom::Y], _desktop->namedview->getDefaultMetric());
1240     Glib::ustring ret = format_tip(C_("Path node tip", "Move node by %s, %s"),
1241         x->str, y->str);
1242     g_string_free(x, TRUE);
1243     g_string_free(y, TRUE);
1244     return ret;
1245 }
1246
1247 char const *Node::node_type_to_localized_string(NodeType type)
1248 {
1249     switch (type) {
1250     case NODE_CUSP: return _("Cusp node");
1251     case NODE_SMOOTH: return _("Smooth node");
1252     case NODE_SYMMETRIC: return _("Symmetric node");
1253     case NODE_AUTO: return _("Auto-smooth node");
1254     default: return "";
1255     }
1256 }
1257
1258 /** Determine whether two nodes are joined by a linear segment. */
1259 bool Node::_is_line_segment(Node *first, Node *second)
1260 {
1261     if (!first || !second) return false;
1262     if (first->_next() == second)
1263         return first->_front.isDegenerate() && second->_back.isDegenerate();
1264     if (second->_next() == first)
1265         return second->_front.isDegenerate() && first->_back.isDegenerate();
1266     return false;
1267 }
1268
1269 SPCtrlShapeType Node::_node_type_to_shape(NodeType type)
1270 {
1271     switch(type) {
1272     case NODE_CUSP: return SP_CTRL_SHAPE_DIAMOND;
1273     case NODE_SMOOTH: return SP_CTRL_SHAPE_SQUARE;
1274     case NODE_AUTO: return SP_CTRL_SHAPE_CIRCLE;
1275     case NODE_SYMMETRIC: return SP_CTRL_SHAPE_SQUARE;
1276     default: return SP_CTRL_SHAPE_DIAMOND;
1277     }
1278 }
1279
1280
1281 /**
1282  * @class NodeList
1283  * @brief An editable list of nodes representing a subpath.
1284  *
1285  * It can optionally be cyclic to represent a closed path.
1286  * The list has iterators that act like plain node iterators, but can also be used
1287  * to obtain shared pointers to nodes.
1288  */
1289
1290 NodeList::NodeList(SubpathList &splist)
1291     : _list(splist)
1292     , _closed(false)
1293 {
1294     this->ln_list = this;
1295     this->ln_next = this;
1296     this->ln_prev = this;
1297 }
1298
1299 NodeList::~NodeList()
1300 {
1301     clear();
1302 }
1303
1304 bool NodeList::empty()
1305 {
1306     return ln_next == this;
1307 }
1308
1309 NodeList::size_type NodeList::size()
1310 {
1311     size_type sz = 0;
1312     for (ListNode *ln = ln_next; ln != this; ln = ln->ln_next) ++sz;
1313     return sz;
1314 }
1315
1316 bool NodeList::closed()
1317 {
1318     return _closed;
1319 }
1320
1321 /** A subpath is degenerate if it has no segments - either one node in an open path
1322  * or no nodes in a closed path */
1323 bool NodeList::degenerate()
1324 {
1325     return closed() ? empty() : ++begin() == end();
1326 }
1327
1328 NodeList::iterator NodeList::before(double t, double *fracpart)
1329 {
1330     double intpart;
1331     *fracpart = std::modf(t, &intpart);
1332     int index = intpart;
1333
1334     iterator ret = begin();
1335     std::advance(ret, index);
1336     return ret;
1337 }
1338
1339 // insert a node before i
1340 NodeList::iterator NodeList::insert(iterator i, Node *x)
1341 {
1342     ListNode *ins = i._node;
1343     x->ln_next = ins;
1344     x->ln_prev = ins->ln_prev;
1345     ins->ln_prev->ln_next = x;
1346     ins->ln_prev = x;
1347     x->ln_list = this;
1348     return iterator(x);
1349 }
1350
1351 void NodeList::splice(iterator pos, NodeList &list)
1352 {
1353     splice(pos, list, list.begin(), list.end());
1354 }
1355
1356 void NodeList::splice(iterator pos, NodeList &list, iterator i)
1357 {
1358     NodeList::iterator j = i;
1359     ++j;
1360     splice(pos, list, i, j);
1361 }
1362
1363 void NodeList::splice(iterator pos, NodeList &/*list*/, iterator first, iterator last)
1364 {
1365     ListNode *ins_beg = first._node, *ins_end = last._node, *at = pos._node;
1366     for (ListNode *ln = ins_beg; ln != ins_end; ln = ln->ln_next) {
1367         ln->ln_list = this;
1368     }
1369     ins_beg->ln_prev->ln_next = ins_end;
1370     ins_end->ln_prev->ln_next = at;
1371     at->ln_prev->ln_next = ins_beg;
1372
1373     ListNode *atprev = at->ln_prev;
1374     at->ln_prev = ins_end->ln_prev;
1375     ins_end->ln_prev = ins_beg->ln_prev;
1376     ins_beg->ln_prev = atprev;
1377 }
1378
1379 void NodeList::shift(int n)
1380 {
1381     // 1. make the list perfectly cyclic
1382     ln_next->ln_prev = ln_prev;
1383     ln_prev->ln_next = ln_next;
1384     // 2. find new begin
1385     ListNode *new_begin = ln_next;
1386     if (n > 0) {
1387         for (; n > 0; --n) new_begin = new_begin->ln_next;
1388     } else {
1389         for (; n < 0; ++n) new_begin = new_begin->ln_prev;
1390     }
1391     // 3. relink begin to list
1392     ln_next = new_begin;
1393     ln_prev = new_begin->ln_prev;
1394     new_begin->ln_prev->ln_next = this;
1395     new_begin->ln_prev = this;
1396 }
1397
1398 void NodeList::reverse()
1399 {
1400     for (ListNode *ln = ln_next; ln != this; ln = ln->ln_prev) {
1401         std::swap(ln->ln_next, ln->ln_prev);
1402         Node *node = static_cast<Node*>(ln);
1403         Geom::Point save_pos = node->front()->position();
1404         node->front()->setPosition(node->back()->position());
1405         node->back()->setPosition(save_pos);
1406     }
1407     std::swap(ln_next, ln_prev);
1408 }
1409
1410 void NodeList::clear()
1411 {
1412     for (iterator i = begin(); i != end();) erase (i++);
1413 }
1414
1415 NodeList::iterator NodeList::erase(iterator i)
1416 {
1417     // some gymnastics are required to ensure that the node is valid when deleted;
1418     // otherwise the code that updates handle visibility will break
1419     Node *rm = static_cast<Node*>(i._node);
1420     ListNode *rmnext = rm->ln_next, *rmprev = rm->ln_prev;
1421     ++i;
1422     delete rm;
1423     rmprev->ln_next = rmnext;
1424     rmnext->ln_prev = rmprev;
1425     return i;
1426 }
1427
1428 // TODO this method is very ugly!
1429 // converting SubpathList to an intrusive list might allow us to get rid of it
1430 void NodeList::kill()
1431 {
1432     for (SubpathList::iterator i = _list.begin(); i != _list.end(); ++i) {
1433         if (i->get() == this) {
1434             _list.erase(i);
1435             return;
1436         }
1437     }
1438 }
1439
1440 NodeList &NodeList::get(Node *n) {
1441     return n->nodeList();
1442 }
1443 NodeList &NodeList::get(iterator const &i) {
1444     return *(i._node->ln_list);
1445 }
1446
1447
1448 /**
1449  * @class SubpathList
1450  * @brief Editable path composed of one or more subpaths
1451  */
1452
1453 } // namespace UI
1454 } // namespace Inkscape
1455
1456 /*
1457   Local Variables:
1458   mode:c++
1459   c-file-style:"stroustrup"
1460   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1461   indent-tabs-mode:nil
1462   fill-column:99
1463   End:
1464 */
1465 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :