src/ui/tool/node.cpp

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