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