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