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