src/ui/tool/path-manipulator.cpp

   1 /** @file
   2  * Path manipulator - 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 <string>
  12 #include <sstream>
  13 #include <deque>
  14 #include <stdexcept>
  15 #include <boost/shared_ptr.hpp>
  16 #include <2geom/bezier-curve.h>
  17 #include <2geom/bezier-utils.h>
  18 #include <2geom/svg-path.h>
  19 #include <glibmm.h>
  20 #include <glibmm/i18n.h>
  21 #include "ui/tool/path-manipulator.h"
  22 #include "desktop.h"
  23 #include "desktop-handles.h"
  24 #include "display/sp-canvas.h"
  25 #include "display/sp-canvas-util.h"
  26 #include "display/curve.h"
  27 #include "display/canvas-bpath.h"
  28 #include "document.h"
  29 #include "sp-path.h"
  30 #include "helper/geom.h"
  31 #include "preferences.h"
  32 #include "style.h"
  33 #include "ui/tool/control-point-selection.h"
  34 #include "ui/tool/curve-drag-point.h"
  35 #include "ui/tool/event-utils.h"
  36 #include "ui/tool/multi-path-manipulator.h"
  37 #include "xml/node.h"
  38 #include "xml/node-observer.h"
  39
  40 namespace Inkscape {
  41 namespace UI {
  42
  43 namespace {
  44 /// Types of path changes that we must react to.
  45 enum PathChange {
  46     PATH_CHANGE_D,
  47     PATH_CHANGE_TRANSFORM
  48 };
  49
  50 } // anonymous namespace
  51
  52 /**
  53  * Notifies the path manipulator when something changes the path being edited
  54  * (e.g. undo / redo)
  55  */
  56 class PathManipulatorObserver : public Inkscape::XML::NodeObserver {
  57 public:
  58     PathManipulatorObserver(PathManipulator *p) : _pm(p), _blocked(false) {}
  59     virtual void notifyAttributeChanged(Inkscape::XML::Node &, GQuark attr,
  60         Util::ptr_shared<char>, Util::ptr_shared<char>)
  61     {
  62         GQuark path_d = g_quark_from_static_string("d");
  63         GQuark path_transform = g_quark_from_static_string("transform");
  64         // do nothing if blocked
  65         if (_blocked) return;
  66
  67         // only react to "d" (path data) and "transform" attribute changes
  68         if (attr == path_d) {
  69             _pm->_externalChange(PATH_CHANGE_D);
  70         } else if (attr == path_transform) {
  71             _pm->_externalChange(PATH_CHANGE_TRANSFORM);
  72         }
  73     }
  74     void block() { _blocked = true; }
  75     void unblock() { _blocked = false; }
  76 private:
  77     PathManipulator *_pm;
  78     bool _blocked;
  79 };
  80
  81 void build_segment(Geom::PathBuilder &, Node *, Node *);
  82
  83 PathManipulator::PathManipulator(PathSharedData const &data, SPPath *path,
  84         Geom::Matrix const &et, guint32 outline_color)
  85     : PointManipulator(data.node_data.desktop, *data.node_data.selection)
  86     , _path_data(data)
  87     , _path(path)
  88     , _spcurve(sp_path_get_curve_for_edit(path))
  89     , _dragpoint(new CurveDragPoint(*this))
  90     , _observer(new PathManipulatorObserver(this))
  91     , _edit_transform(et)
  92     , _show_handles(true)
  93     , _show_outline(false)
  94 {
  95     /* Because curve drag point is always created first, it does not cover nodes */
  96     _i2d_transform = sp_item_i2d_affine(SP_ITEM(path));
  97     _d2i_transform = _i2d_transform.inverse();
  98     _dragpoint->setVisible(false);
  99
 100     _outline = sp_canvas_bpath_new(_path_data.outline_group, NULL);
 101     sp_canvas_item_hide(_outline);
 102     sp_canvas_bpath_set_stroke(SP_CANVAS_BPATH(_outline), outline_color, 1.0,
 103         SP_STROKE_LINEJOIN_MITER, SP_STROKE_LINECAP_BUTT);
 104     sp_canvas_bpath_set_fill(SP_CANVAS_BPATH(_outline), 0, SP_WIND_RULE_NONZERO);
 105
 106     _subpaths.signal_insert_node.connect(
 107         sigc::mem_fun(*this, &PathManipulator::_attachNodeHandlers));
 108     _subpaths.signal_remove_node.connect(
 109         sigc::mem_fun(*this, &PathManipulator::_removeNodeHandlers));
 110     _selection.signal_update.connect(
 111         sigc::mem_fun(*this, &PathManipulator::update));
 112     _selection.signal_point_changed.connect(
 113         sigc::mem_fun(*this, &PathManipulator::_selectionChanged));
 114     _dragpoint->signal_update.connect(
 115         sigc::mem_fun(*this, &PathManipulator::update));
 116     _desktop->signal_zoom_changed.connect(
 117         sigc::hide( sigc::mem_fun(*this, &PathManipulator::_updateOutlineOnZoomChange)));
 118
 119     _createControlPointsFromGeometry();
 120
 121     _path->repr->addObserver(*_observer);
 122 }
 123
 124 PathManipulator::~PathManipulator()
 125 {
 126     delete _dragpoint;
 127     if (_path) _path->repr->removeObserver(*_observer);
 128     delete _observer;
 129     gtk_object_destroy(_outline);
 130     _spcurve->unref();
 131     clear();
 132 }
 133
 134 /** Handle motion events to update the position of the curve drag point. */
 135 bool PathManipulator::event(GdkEvent *event)
 136 {
 137     if (empty()) return false;
 138
 139     switch (event->type)
 140     {
 141     case GDK_MOTION_NOTIFY:
 142         _updateDragPoint(event_point(event->motion));
 143         break;
 144     default: break;
 145     }
 146     return false;
 147 }
 148
 149 /** Check whether the manipulator has any nodes. */
 150 bool PathManipulator::empty() {
 151     return !_path || _subpaths.empty();
 152 }
 153
 154 /** Update the display and the outline of the path. */
 155 void PathManipulator::update()
 156 {
 157     _createGeometryFromControlPoints();
 158 }
 159
 160 /** Store the changes to the path in XML. */
 161 void PathManipulator::writeXML()
 162 {
 163     if (!_path) return;
 164     _observer->block();
 165     if (!empty()) {
 166         _path->updateRepr();
 167         _path->repr->setAttribute("sodipodi:nodetypes", _createTypeString().data());
 168     } else {
 169         // this manipulator will have to be destroyed right after this call
 170         _path->repr->removeObserver(*_observer);
 171         sp_object_ref(_path);
 172         _path->deleteObject(true, true);
 173         sp_object_unref(_path);
 174         _path = 0;
 175     }
 176     _observer->unblock();
 177 }
 178
 179 /** Remove all nodes from the path. */
 180 void PathManipulator::clear()
 181 {
 182     // no longer necessary since nodes remove themselves from selection on destruction
 183     //_removeNodesFromSelection();
 184     _subpaths.clear();
 185 }
 186
 187 /** Select all nodes in subpaths that have something selected. */
 188 void PathManipulator::selectSubpaths()
 189 {
 190     for (std::list<SubpathPtr>::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 191         NodeList::iterator sp_start = (*i)->begin(), sp_end = (*i)->end();
 192         for (NodeList::iterator j = sp_start; j != sp_end; ++j) {
 193             if (j->selected()) {
 194                 // if at least one of the nodes from this subpath is selected,
 195                 // select all nodes from this subpath
 196                 for (NodeList::iterator ins = sp_start; ins != sp_end; ++ins)
 197                     _selection.insert(ins.ptr());
 198                 continue;
 199             }
 200         }
 201     }
 202 }
 203
 204 /** Select all nodes in the path. */
 205 void PathManipulator::selectAll()
 206 {
 207     for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 208         for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 209             _selection.insert(j.ptr());
 210         }
 211     }
 212 }
 213
 214 /** Select points inside the given rectangle. If all points inside it are already selected,
 215  * they will be deselected.
 216  * @param area Area to select
 217  */
 218 void PathManipulator::selectArea(Geom::Rect const &area)
 219 {
 220     bool nothing_selected = true;
 221     std::vector<Node*> in_area;
 222     for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 223         for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 224             if (area.contains(j->position())) {
 225                 in_area.push_back(j.ptr());
 226                 if (!j->selected()) {
 227                     _selection.insert(j.ptr());
 228                     nothing_selected = false;
 229                 }
 230             }
 231         }
 232     }
 233     if (nothing_selected) {
 234         for (std::vector<Node*>::iterator i = in_area.begin(); i != in_area.end(); ++i) {
 235             _selection.erase(*i);
 236         }
 237     }
 238 }
 239
 240 /** Move the selection forward or backward by one node in each subpath, based on the sign
 241  * of the parameter. */
 242 void PathManipulator::shiftSelection(int dir)
 243 {
 244     if (dir == 0) return;
 245     // We cannot do any tricks here, like iterating in different directions based on
 246     // the sign and only setting the selection of nodes behind us, because it would break
 247     // for closed paths.
 248     for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 249         std::deque<bool> sels; // I hope this is specialized for bools!
 250         unsigned num = 0;
 251
 252         for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 253             sels.push_back(j->selected());
 254             _selection.erase(j.ptr());
 255             ++num;
 256         }
 257         if (num == 0) continue; // should never happen!
 258
 259         num = 0;
 260         // In closed subpath, shift the selection cyclically. In an open one,
 261         // let the selection 'slide into nothing' at ends.
 262         if (dir > 0) {
 263             if ((*i)->closed()) {
 264                 bool last = sels.back();
 265                 sels.pop_back();
 266                 sels.push_front(last);
 267             } else {
 268                 sels.push_front(false);
 269             }
 270         } else {
 271             if ((*i)->closed()) {
 272                 bool first = sels.front();
 273                 sels.pop_front();
 274                 sels.push_back(first);
 275             } else {
 276                 sels.push_back(false);
 277                 num = 1;
 278             }
 279         }
 280
 281         for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 282             if (sels[num]) _selection.insert(j.ptr());
 283             ++num;
 284         }
 285     }
 286 }
 287
 288 /** Invert selection in the entire path. */
 289 void PathManipulator::invertSelection()
 290 {
 291     for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 292         for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 293             if (j->selected()) _selection.erase(j.ptr());
 294             else _selection.insert(j.ptr());
 295         }
 296     }
 297 }
 298
 299 /** Invert selection in the selected subpaths. */
 300 void PathManipulator::invertSelectionInSubpaths()
 301 {
 302     for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 303         for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 304             if (j->selected()) {
 305                 // found selected node - invert selection in this subpath
 306                 for (NodeList::iterator k = (*i)->begin(); k != (*i)->end(); ++k) {
 307                     if (k->selected()) _selection.erase(k.ptr());
 308                     else _selection.insert(k.ptr());
 309                 }
 310                 // next subpath
 311                 break;
 312             }
 313         }
 314     }
 315 }
 316
 317 /** Insert a new node in the middle of each selected segment. */
 318 void PathManipulator::insertNodes()
 319 {
 320     if (!_num_selected) return;
 321
 322     for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 323         for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 324             NodeList::iterator k = j.next();
 325             if (k && j->selected() && k->selected()) {
 326                 j = subdivideSegment(j, 0.5);
 327                 _selection.insert(j.ptr());
 328             }
 329         }
 330     }
 331 }
 332
 333 /** Replace contiguous selections of nodes in each subpath with one node. */
 334 void PathManipulator::weldNodes(NodeList::iterator const &preserve_pos)
 335 {
 336     bool pos_valid = preserve_pos;
 337     for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 338         SubpathPtr sp = *i;
 339         unsigned num_selected = 0, num_unselected = 0;
 340         for (NodeList::iterator j = sp->begin(); j != sp->end(); ++j) {
 341             if (j->selected()) ++num_selected;
 342             else ++num_unselected;
 343         }
 344         if (num_selected < 2) continue;
 345         if (num_unselected == 0) {
 346             // if all nodes in a subpath are selected, the operation doesn't make much sense
 347             continue;
 348         }
 349
 350         // Start from unselected node in closed paths, so that we don't start in the middle
 351         // of a contiguous selection
 352         NodeList::iterator sel_beg = sp->begin(), sel_end;
 353         if (sp->closed()) {
 354             while (sel_beg->selected()) ++sel_beg;
 355         }
 356
 357         // Main loop
 358         while (num_selected > 0) {
 359             // Find selected node
 360             while (sel_beg && !sel_beg->selected()) sel_beg = sel_beg.next();
 361             if (!sel_beg) throw std::logic_error("Join nodes: end of open path reached, "
 362                 "but there are still nodes to process!");
 363
 364             unsigned num_points = 0;
 365             bool use_pos = false;
 366             Geom::Point back_pos, front_pos;
 367             back_pos = *sel_beg->back();
 368
 369             for (sel_end = sel_beg; sel_end && sel_end->selected(); sel_end = sel_end.next()) {
 370                 ++num_points;
 371                 front_pos = *sel_end->front();
 372                 if (pos_valid && sel_end == preserve_pos) use_pos = true;
 373             }
 374             if (num_points > 1) {
 375                 Geom::Point joined_pos;
 376                 if (use_pos) {
 377                     joined_pos = preserve_pos->position();
 378                     pos_valid = false;
 379                 } else {
 380                     joined_pos = Geom::middle_point(back_pos, front_pos);
 381                 }
 382                 sel_beg->setType(NODE_CUSP, false);
 383                 sel_beg->move(joined_pos);
 384                 // do not move handles if they aren't degenerate
 385                 if (!sel_beg->back()->isDegenerate()) {
 386                     sel_beg->back()->setPosition(back_pos);
 387                 }
 388                 if (!sel_end.prev()->front()->isDegenerate()) {
 389                     sel_beg->front()->setPosition(front_pos);
 390                 }
 391                 sel_beg = sel_beg.next();
 392                 while (sel_beg != sel_end) {
 393                     NodeList::iterator next = sel_beg.next();
 394                     sp->erase(sel_beg);
 395                     sel_beg = next;
 396                     --num_selected;
 397                 }
 398             }
 399             --num_selected; // for the joined node or single selected node
 400         }
 401     }
 402 }
 403
 404 /** Remove nodes in the middle of selected segments. */
 405 void PathManipulator::weldSegments()
 406 {
 407     // TODO
 408 }
 409
 410 /** Break the subpath at selected nodes. It also works for single node closed paths. */
 411 void PathManipulator::breakNodes()
 412 {
 413     for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 414         SubpathPtr sp = *i;
 415         NodeList::iterator cur = sp->begin(), end = sp->end();
 416         if (!sp->closed()) {
 417             // Each open path must have at least two nodes so no checks are required.
 418             // For 2-node open paths, cur == end
 419             ++cur;
 420             --end;
 421         }
 422         for (; cur != end; ++cur) {
 423             if (!cur->selected()) continue;
 424             SubpathPtr ins;
 425             bool becomes_open = false;
 426
 427             if (sp->closed()) {
 428                 // Move the node to break at to the beginning of path
 429                 if (cur != sp->begin())
 430                     sp->splice(sp->begin(), *sp, cur, sp->end());
 431                 sp->setClosed(false);
 432                 ins = sp;
 433                 becomes_open = true;
 434             } else {
 435                 SubpathPtr new_sp(new NodeList(_subpaths));
 436                 new_sp->splice(new_sp->end(), *sp, sp->begin(), cur);
 437                 _subpaths.insert(i, new_sp);
 438                 ins = new_sp;
 439             }
 440
 441             Node *n = new Node(_path_data.node_data, cur->position());
 442             ins->insert(ins->end(), n);
 443             cur->setType(NODE_CUSP, false);
 444             n->back()->setRelativePos(cur->back()->relativePos());
 445             cur->back()->retract();
 446             n->sink();
 447
 448             if (becomes_open) {
 449                 cur = sp->begin(); // this will be increased to ++sp->begin()
 450                 end = --sp->end();
 451             }
 452         }
 453     }
 454 }
 455
 456 /** Delete selected nodes in the path, optionally substituting deleted segments with bezier curves
 457  * in a way that attempts to preserve the original shape of the curve. */
 458 void PathManipulator::deleteNodes(bool keep_shape)
 459 {
 460     if (!_num_selected) return;
 461
 462     unsigned const samples_per_segment = 10;
 463     double const t_step = 1.0 / samples_per_segment;
 464
 465     for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end();) {
 466         SubpathPtr sp = *i;
 467
 468         // If there are less than 2 unselected nodes in an open subpath or no unselected nodes
 469         // in a closed one, delete entire subpath.
 470         unsigned num_unselected = 0, num_selected = 0;
 471         for (NodeList::iterator j = sp->begin(); j != sp->end(); ++j) {
 472             if (j->selected()) ++num_selected;
 473             else ++num_unselected;
 474         }
 475         if (num_selected == 0) continue;
 476         if (sp->closed() ? (num_unselected < 1) : (num_unselected < 2)) {
 477             _subpaths.erase(i++);
 478             continue;
 479         }
 480
 481         // In closed paths, start from an unselected node - otherwise we might start in the middle
 482         // of a selected stretch and the resulting bezier fit would be suboptimal
 483         NodeList::iterator sel_beg = sp->begin(), sel_end;
 484         if (sp->closed()) {
 485             while (sel_beg->selected()) ++sel_beg;
 486         }
 487         sel_end = sel_beg;
 488
 489         while (num_selected > 0) {
 490             while (!sel_beg->selected()) sel_beg = sel_beg.next();
 491             sel_end = sel_beg;
 492             unsigned del_len = 0;
 493             while (sel_end && sel_end->selected()) {
 494                 ++del_len;
 495                 sel_end = sel_end.next();
 496             }
 497
 498             // set surrounding node types to cusp if:
 499             // 1. keep_shape is on, or
 500             // 2. we are deleting at the end or beginning of an open path
 501             // if !sel_end then sel_beg.prev() must be valid, otherwise the entire subpath
 502             // would be deleted before we get here
 503             if (keep_shape || !sel_end) sel_beg.prev()->setType(NODE_CUSP, false);
 504             if (keep_shape || !sel_beg.prev()) sel_end->setType(NODE_CUSP, false);
 505
 506             if (keep_shape && sel_beg.prev() && sel_end) {
 507                 // Fill fit data
 508                 unsigned num_samples = (del_len + 1) * samples_per_segment + 1;
 509                 Geom::Point *bezier_data = new Geom::Point[num_samples];
 510                 Geom::Point result[4];
 511                 unsigned seg = 0;
 512
 513                 for (NodeList::iterator cur = sel_beg.prev(); cur != sel_end; cur = cur.next()) {
 514                     Geom::CubicBezier bc(*cur, *cur->front(), *cur.next(), *cur.next()->back());
 515                     for (unsigned s = 0; s < samples_per_segment; ++s) {
 516                         bezier_data[seg * samples_per_segment + s] = bc.pointAt(t_step * s);
 517                     }
 518                     ++seg;
 519                 }
 520                 // Fill last point
 521                 bezier_data[num_samples - 1] = sel_end->position();
 522                 // Compute replacement bezier curve
 523                 // TODO find out optimal error value
 524                 bezier_fit_cubic(result, bezier_data, num_samples, 0.5);
 525                 delete[] bezier_data;
 526
 527                 sel_beg.prev()->front()->setPosition(result[1]);
 528                 sel_end->back()->setPosition(result[2]);
 529             }
 530             // We cannot simply use sp->erase(sel_beg, sel_end), because it would break
 531             // for cases when the selected stretch crosses the beginning of the path
 532             while (sel_beg != sel_end) {
 533                 NodeList::iterator next = sel_beg.next();
 534                 sp->erase(sel_beg);
 535                 sel_beg = next;
 536             }
 537             num_selected -= del_len;
 538         }
 539         ++i;
 540     }
 541 }
 542
 543 /** Removes selected segments */
 544 void PathManipulator::deleteSegments()
 545 {
 546     if (_num_selected == 0) return;
 547     for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end();) {
 548         SubpathPtr sp = *i;
 549         bool has_unselected = false;
 550         unsigned num_selected = 0;
 551         for (NodeList::iterator j = sp->begin(); j != sp->end(); ++j) {
 552             if (j->selected()) {
 553                 ++num_selected;
 554             } else {
 555                 has_unselected = true;
 556             }
 557         }
 558         if (!has_unselected) {
 559             _subpaths.erase(i++);
 560             continue;
 561         }
 562
 563         NodeList::iterator sel_beg = sp->begin();
 564         if (sp->closed()) {
 565             while (sel_beg && sel_beg->selected()) ++sel_beg;
 566         }
 567         while (num_selected > 0) {
 568             if (!sel_beg->selected()) {
 569                 sel_beg = sel_beg.next();
 570                 continue;
 571             }
 572             NodeList::iterator sel_end = sel_beg;
 573             unsigned num_points = 0;
 574             while (sel_end && sel_end->selected()) {
 575                 sel_end = sel_end.next();
 576                 ++num_points;
 577             }
 578             if (num_points >= 2) {
 579                 // Retract end handles
 580                 sel_end.prev()->setType(NODE_CUSP, false);
 581                 sel_end.prev()->back()->retract();
 582                 sel_beg->setType(NODE_CUSP, false);
 583                 sel_beg->front()->retract();
 584                 if (sp->closed()) {
 585                     // In closed paths, relocate the beginning of the path to the last selected
 586                     // node and then unclose it. Remove the nodes from the first selected node
 587                     // to the new end of path.
 588                     if (sel_end.prev() != sp->begin())
 589                         sp->splice(sp->begin(), *sp, sel_end.prev(), sp->end());
 590                     sp->setClosed(false);
 591                     sp->erase(sel_beg.next(), sp->end());
 592                 } else {
 593                     // for open paths:
 594                     // 1. At end or beginning, delete including the node on the end or beginning
 595                     // 2. In the middle, delete only inner nodes
 596                     if (sel_beg == sp->begin()) {
 597                         sp->erase(sp->begin(), sel_end.prev());
 598                     } else if (sel_end == sp->end()) {
 599                         sp->erase(sel_beg.next(), sp->end());
 600                     } else {
 601                         SubpathPtr new_sp(new NodeList(_subpaths));
 602                         new_sp->splice(new_sp->end(), *sp, sp->begin(), sel_beg.next());
 603                         _subpaths.insert(i, new_sp);
 604                         if (sel_end.prev())
 605                             sp->erase(sp->begin(), sel_end.prev());
 606                     }
 607                 }
 608             }
 609             sel_beg = sel_end;
 610             num_selected -= num_points;
 611         }
 612         ++i;
 613     }
 614 }
 615
 616 /** Reverse the subpaths that have anything selected. */
 617 void PathManipulator::reverseSubpaths()
 618 {
 619     for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 620         for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 621             if (j->selected()) {
 622                 (*i)->reverse();
 623                 break; // continue with the next subpath
 624             }
 625         }
 626     }
 627 }
 628
 629 /** Make selected segments curves / lines. */
 630 void PathManipulator::setSegmentType(SegmentType type)
 631 {
 632     if (!_num_selected) return;
 633     for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 634         for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 635             NodeList::iterator k = j.next();
 636             if (!(k && j->selected() && k->selected())) continue;
 637             switch (type) {
 638             case SEGMENT_STRAIGHT:
 639                 if (j->front()->isDegenerate() && k->back()->isDegenerate())
 640                     break;
 641                 j->front()->move(*j);
 642                 k->back()->move(*k);
 643                 break;
 644             case SEGMENT_CUBIC_BEZIER:
 645                 if (!j->front()->isDegenerate() || !k->back()->isDegenerate())
 646                     break;
 647                 j->front()->move(j->position() + (k->position() - j->position()) / 3);
 648                 k->back()->move(k->position() + (j->position() - k->position()) / 3);
 649                 break;
 650             }
 651         }
 652     }
 653 }
 654
 655 /** Set the visibility of handles. */
 656 void PathManipulator::showHandles(bool show)
 657 {
 658     if (show == _show_handles) return;
 659     if (show) {
 660         for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 661             for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 662                 if (!j->selected()) continue;
 663                 j->showHandles(true);
 664                 if (j.prev()) j.prev()->showHandles(true);
 665                 if (j.next()) j.next()->showHandles(true);
 666             }
 667         }
 668     } else {
 669         for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 670             for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 671                 j->showHandles(false);
 672             }
 673         }
 674     }
 675     _show_handles = show;
 676 }
 677
 678 /** Set the visibility of outline. */
 679 void PathManipulator::showOutline(bool show)
 680 {
 681     if (show == _show_outline) return;
 682     _show_outline = show;
 683     _updateOutline();
 684 }
 685
 686 void PathManipulator::showPathDirection(bool show)
 687 {
 688     if (show == _show_path_direction) return;
 689     _show_path_direction = show;
 690     _updateOutline();
 691 }
 692
 693 /** Insert a node in the segment beginning with the supplied iterator,
 694  * at the given time value */
 695 NodeList::iterator PathManipulator::subdivideSegment(NodeList::iterator first, double t)
 696 {
 697     if (!first) throw std::invalid_argument("Subdivide after invalid iterator");
 698     NodeList &list = NodeList::get(first);
 699     NodeList::iterator second = first.next();
 700     if (!second) throw std::invalid_argument("Subdivide after last node in open path");
 701
 702     // We need to insert the segment after 'first'. We can't simply use 'second'
 703     // as the point of insertion, because when 'first' is the last node of closed path,
 704     // the new node will be inserted as the first node instead.
 705     NodeList::iterator insert_at = first;
 706     ++insert_at;
 707
 708     NodeList::iterator inserted;
 709     if (first->front()->isDegenerate() && second->back()->isDegenerate()) {
 710         // for a line segment, insert a cusp node
 711         Node *n = new Node(_path_data.node_data,
 712             Geom::lerp(t, first->position(), second->position()));
 713         n->setType(NODE_CUSP, false);
 714         inserted = list.insert(insert_at, n);
 715     } else {
 716         // build bezier curve and subdivide
 717         Geom::CubicBezier temp(first->position(), first->front()->position(),
 718             second->back()->position(), second->position());
 719         std::pair<Geom::CubicBezier, Geom::CubicBezier> div = temp.subdivide(t);
 720         std::vector<Geom::Point> seg1 = div.first.points(), seg2 = div.second.points();
 721
 722         // set new handle positions
 723         Node *n = new Node(_path_data.node_data, seg2[0]);
 724         n->back()->setPosition(seg1[2]);
 725         n->front()->setPosition(seg2[1]);
 726         n->setType(NODE_SMOOTH, false);
 727         inserted = list.insert(insert_at, n);
 728
 729         first->front()->move(seg1[1]);
 730         second->back()->move(seg2[2]);
 731     }
 732     return inserted;
 733 }
 734
 735 /** Called by the XML observer when something else than us modifies the path. */
 736 void PathManipulator::_externalChange(unsigned type)
 737 {
 738     switch (type) {
 739     case PATH_CHANGE_D: {
 740         _spcurve->unref();
 741         _spcurve = sp_path_get_curve_for_edit(_path);
 742
 743         // ugly: stored offsets of selected nodes in a vector
 744         // vector<bool> should be specialized so that it takes only 1 bit per value
 745         std::vector<bool> selpos;
 746         for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 747             for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 748                 selpos.push_back(j->selected());
 749             }
 750         }
 751         unsigned size = selpos.size(), curpos = 0;
 752
 753         _createControlPointsFromGeometry();
 754
 755         for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 756             for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 757                 if (curpos >= size) goto end_restore;
 758                 if (selpos[curpos]) _selection.insert(j.ptr());
 759                 ++curpos;
 760             }
 761         }
 762         end_restore:
 763
 764         _updateOutline();
 765         } break;
 766     case PATH_CHANGE_TRANSFORM: {
 767         Geom::Matrix i2d_change = _d2i_transform;
 768         _i2d_transform = sp_item_i2d_affine(SP_ITEM(_path));
 769         _d2i_transform = _i2d_transform.inverse();
 770         i2d_change *= _i2d_transform;
 771         for (SubpathList::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 772             for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 773                 j->transform(i2d_change);
 774             }
 775         }
 776         _updateOutline();
 777         } break;
 778     default: break;
 779     }
 780 }
 781
 782 /** Create nodes and handles based on the XML of the edited path. */
 783 void PathManipulator::_createControlPointsFromGeometry()
 784 {
 785     clear();
 786
 787     // sanitize pathvector and store it in SPCurve,
 788     // so that _updateDragPoint doesn't crash on paths with naked movetos
 789     Geom::PathVector pathv = pathv_to_linear_and_cubic_beziers(_spcurve->get_pathvector());
 790     for (Geom::PathVector::iterator i = pathv.begin(); i != pathv.end(); ) {
 791         if (i->empty()) pathv.erase(i++);
 792         else ++i;
 793     }
 794     _spcurve->set_pathvector(pathv);
 795
 796     pathv *= (_edit_transform * _i2d_transform);
 797
 798     // in this loop, we know that there are no zero-segment subpaths
 799     for (Geom::PathVector::const_iterator pit = pathv.begin(); pit != pathv.end(); ++pit) {
 800         // prepare new subpath
 801         SubpathPtr subpath(new NodeList(_subpaths));
 802         _subpaths.push_back(subpath);
 803
 804         Node *previous_node = new Node(_path_data.node_data, pit->initialPoint());
 805         subpath->push_back(previous_node);
 806         Geom::Curve const &cseg = pit->back_closed();
 807         bool fuse_ends = pit->closed()
 808             && Geom::are_near(cseg.initialPoint(), cseg.finalPoint());
 809
 810         for (Geom::Path::const_iterator cit = pit->begin(); cit != pit->end_open(); ++cit) {
 811             Geom::Point pos = cit->finalPoint();
 812             Node *current_node;
 813             // if the closing segment is degenerate and the path is closed, we need to move
 814             // the handle of the first node instead of creating a new one
 815             if (fuse_ends && cit == --(pit->end_open())) {
 816                 current_node = subpath->begin().get_pointer();
 817             } else {
 818                 /* regardless of segment type, create a new node at the end
 819                  * of this segment (unless this is the last segment of a closed path
 820                  * with a degenerate closing segment */
 821                 current_node = new Node(_path_data.node_data, pos);
 822                 subpath->push_back(current_node);
 823             }
 824             // if this is a bezier segment, move handles appropriately
 825             if (Geom::CubicBezier const *cubic_bezier =
 826                 dynamic_cast<Geom::CubicBezier const*>(&*cit))
 827             {
 828                 std::vector<Geom::Point> points = cubic_bezier->points();
 829
 830                 previous_node->front()->setPosition(points[1]);
 831                 current_node ->back() ->setPosition(points[2]);
 832             }
 833             previous_node = current_node;
 834         }
 835         // If the path is closed, make the list cyclic
 836         if (pit->closed()) subpath->setClosed(true);
 837     }
 838
 839     // we need to set the nodetypes after all the handles are in place,
 840     // so that pickBestType works correctly
 841     // TODO maybe migrate to inkscape:node-types?
 842     gchar const *nts_raw = _path ? _path->repr->attribute("sodipodi:nodetypes") : 0;
 843     std::string nodetype_string = nts_raw ? nts_raw : "";
 844     /* Calculate the needed length of the nodetype string.
 845      * For closed paths, the entry is duplicated for the starting node,
 846      * so we can just use the count of segments including the closing one
 847      * to include the extra end node. */
 848     std::string::size_type nodetype_len = 0;
 849     for (Geom::PathVector::const_iterator i = pathv.begin(); i != pathv.end(); ++i) {
 850         if (i->empty()) continue;
 851         nodetype_len += i->size_closed();
 852     }
 853     /* pad the string to required length with a bogus value.
 854      * 'b' and any other letter not recognized by the parser causes the best fit to be set
 855      * as the node type */
 856     if (nodetype_len > nodetype_string.size()) {
 857         nodetype_string.append(nodetype_len - nodetype_string.size(), 'b');
 858     }
 859     std::string::iterator tsi = nodetype_string.begin();
 860     for (std::list<SubpathPtr>::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 861         for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 862             j->setType(Node::parse_nodetype(*tsi++), false);
 863         }
 864         if ((*i)->closed()) {
 865             // STUPIDITY ALERT: it seems we need to use the duplicate type symbol instead of
 866             // the first one to remain backward compatible.
 867             (*i)->begin()->setType(Node::parse_nodetype(*tsi++), false);
 868         }
 869     }
 870 }
 871
 872 /** Construct the geometric representation of nodes and handles, update the outline
 873  * and display */
 874 void PathManipulator::_createGeometryFromControlPoints()
 875 {
 876     Geom::PathBuilder builder;
 877     for (std::list<SubpathPtr>::iterator spi = _subpaths.begin(); spi != _subpaths.end(); ) {
 878         SubpathPtr subpath = *spi;
 879         if (subpath->empty()) {
 880             _subpaths.erase(spi++);
 881             continue;
 882         }
 883         NodeList::iterator prev = subpath->begin();
 884         builder.moveTo(prev->position());
 885
 886         for (NodeList::iterator i = ++subpath->begin(); i != subpath->end(); ++i) {
 887             build_segment(builder, prev.ptr(), i.ptr());
 888             prev = i;
 889         }
 890         if (subpath->closed()) {
 891             // Here we link the last and first node if the path is closed.
 892             // If the last segment is Bezier, we add it.
 893             if (!prev->front()->isDegenerate() || !subpath->begin()->back()->isDegenerate()) {
 894                 build_segment(builder, prev.ptr(), subpath->begin().ptr());
 895             }
 896             // if that segment is linear, we just call closePath().
 897             builder.closePath();
 898         }
 899         ++spi;
 900     }
 901     builder.finish();
 902     _spcurve->set_pathvector(builder.peek() * (_edit_transform * _i2d_transform).inverse());
 903     _updateOutline();
 904     if (!empty()) sp_shape_set_curve(SP_SHAPE(_path), _spcurve, false);
 905 }
 906
 907 /** Build one segment of the geometric representation.
 908  * @relates PathManipulator */
 909 void build_segment(Geom::PathBuilder &builder, Node *prev_node, Node *cur_node)
 910 {
 911     if (cur_node->back()->isDegenerate() && prev_node->front()->isDegenerate())
 912     {
 913         // NOTE: It seems like the renderer cannot correctly handle vline / hline segments,
 914         // and trying to display a path using them results in funny artifacts.
 915         builder.lineTo(cur_node->position());
 916     } else {
 917         // this is a bezier segment
 918         builder.curveTo(
 919             prev_node->front()->position(),
 920             cur_node->back()->position(),
 921             cur_node->position());
 922     }
 923 }
 924
 925 /** Construct a node type string to store in the sodipodi:nodetypes attribute. */
 926 std::string PathManipulator::_createTypeString()
 927 {
 928     // precondition: no single-node subpaths
 929     std::stringstream tstr;
 930     for (std::list<SubpathPtr>::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
 931         for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
 932             tstr << j->type();
 933         }
 934         // nodestring format peculiarity: first node is counted twice for closed paths
 935         if ((*i)->closed()) tstr << (*i)->begin()->type();
 936     }
 937     return tstr.str();
 938 }
 939
 940 /** Update the path outline. */
 941 void PathManipulator::_updateOutline()
 942 {
 943     if (!_show_outline) {
 944         sp_canvas_item_hide(_outline);
 945         return;
 946     }
 947
 948     Geom::PathVector pv = _spcurve->get_pathvector();
 949     pv *= (_edit_transform * _i2d_transform);
 950     // This SPCurve thing has to be killed with extreme prejudice
 951     SPCurve *_hc = new SPCurve();
 952     if (_show_path_direction) {
 953         // To show the direction, we append additional subpaths which consist of a single
 954         // linear segment that starts at the time value of 0.5 and extends for 10 pixels
 955         // at an angle 150 degrees from the unit tangent. This creates the appearance
 956         // of little 'harpoons' that show the direction of the subpaths.
 957         Geom::PathVector arrows;
 958         for (Geom::PathVector::iterator i = pv.begin(); i != pv.end(); ++i) {
 959             Geom::Path &path = *i;
 960             for (Geom::Path::const_iterator j = path.begin(); j != path.end_default(); ++j) {
 961                 Geom::Point at = j->pointAt(0.5);
 962                 Geom::Point ut = j->unitTangentAt(0.5);
 963                 // rotate the point
 964                 ut *= Geom::Rotate(150.0 / 180.0 * M_PI);
 965                 Geom::Point arrow_end = _desktop->w2d(
 966                     _desktop->d2w(at) + Geom::unit_vector(_desktop->d2w(ut)) * 10.0);
 967
 968                 Geom::Path arrow(at);
 969                 arrow.appendNew<Geom::LineSegment>(arrow_end);
 970                 arrows.push_back(arrow);
 971             }
 972         }
 973         pv.insert(pv.end(), arrows.begin(), arrows.end());
 974     }
 975     _hc->set_pathvector(pv);
 976     sp_canvas_bpath_set_bpath(SP_CANVAS_BPATH(_outline), _hc);
 977     sp_canvas_item_show(_outline);
 978     _hc->unref();
 979 }
 980
 981 void PathManipulator::_attachNodeHandlers(Node *node)
 982 {
 983     Handle *handles[2] = { node->front(), node->back() };
 984     for (int i = 0; i < 2; ++i) {
 985         handles[i]->signal_update.connect(
 986             sigc::mem_fun(*this, &PathManipulator::update));
 987         handles[i]->signal_ungrabbed.connect(
 988             sigc::hide(
 989                 sigc::mem_fun(*this, &PathManipulator::_handleUngrabbed)));
 990         handles[i]->signal_grabbed.connect(
 991             sigc::bind_return(
 992                 sigc::hide(
 993                     sigc::mem_fun(*this, &PathManipulator::_handleGrabbed)),
 994                 false));
 995         handles[i]->signal_clicked.connect(
 996             sigc::bind<0>(
 997                 sigc::mem_fun(*this, &PathManipulator::_handleClicked),
 998                 handles[i]));
 999     }
1000     node->signal_clicked.connect(
1001         sigc::bind<0>(
1002             sigc::mem_fun(*this, &PathManipulator::_nodeClicked),
1003             node));
1004 }
1005 void PathManipulator::_removeNodeHandlers(Node *node)
1006 {
1007     // It is safe to assume that nobody else connected to handles' signals after us,
1008     // so we pop our slots from the back. This preserves existing connections
1009     // created by Node and Handle constructors.
1010     Handle *handles[2] = { node->front(), node->back() };
1011     for (int i = 0; i < 2; ++i) {
1012         handles[i]->signal_update.slots().pop_back();
1013         handles[i]->signal_grabbed.slots().pop_back();
1014         handles[i]->signal_ungrabbed.slots().pop_back();
1015         handles[i]->signal_clicked.slots().pop_back();
1016     }
1017     // Same for this one: CPS only connects to grab, drag, and ungrab
1018     node->signal_clicked.slots().pop_back();
1019 }
1020
1021 bool PathManipulator::_nodeClicked(Node *n, GdkEventButton *event)
1022 {
1023     // cycle between node types on ctrl+click
1024     if (event->button != 1 || !held_control(*event)) return false;
1025     if (n->isEndNode()) {
1026         if (n->type() == NODE_CUSP) {
1027             n->setType(NODE_SMOOTH);
1028         } else {
1029             n->setType(NODE_CUSP);
1030         }
1031     } else {
1032         n->setType(static_cast<NodeType>((n->type() + 1) % NODE_LAST_REAL_TYPE));
1033     }
1034     update();
1035     _commit(_("Cycle node type"));
1036     return true;
1037 }
1038
1039 void PathManipulator::_handleGrabbed()
1040 {
1041     _selection.hideTransformHandles();
1042 }
1043
1044 void PathManipulator::_handleUngrabbed()
1045 {
1046     _selection.restoreTransformHandles();
1047     _commit(_("Drag handle"));
1048 }
1049
1050 bool PathManipulator::_handleClicked(Handle *h, GdkEventButton *event)
1051 {
1052     // retracting by Ctrl+click
1053     if (event->button == 1 && held_control(*event)) {
1054         h->move(h->parent()->position());
1055         update();
1056         _commit(_("Retract handle"));
1057         return true;
1058     }
1059     return false;
1060 }
1061
1062 void PathManipulator::_selectionChanged(SelectableControlPoint *p, bool selected)
1063 {
1064     // don't do anything if we do not show handles
1065     if (!_show_handles) return;
1066
1067     // only do something if a node changed selection state
1068     Node *node = dynamic_cast<Node*>(p);
1069     if (!node) return;
1070
1071     // update handle display
1072     NodeList::iterator iters[5];
1073     iters[2] = NodeList::get_iterator(node);
1074     iters[1] = iters[2].prev();
1075     iters[3] = iters[2].next();
1076     if (selected) {
1077         // selection - show handles on this node and adjacent ones
1078         node->showHandles(true);
1079         if (iters[1]) iters[1]->showHandles(true);
1080         if (iters[3]) iters[3]->showHandles(true);
1081     } else {
1082         /* Deselection is more complex.
1083          * The change might affect 3 nodes - this one and two adjacent.
1084          * If the node and both its neighbors are deselected, hide handles.
1085          * Otherwise, leave as is. */
1086         if (iters[1]) iters[0] = iters[1].prev();
1087         if (iters[3]) iters[4] = iters[3].next();
1088         bool nodesel[5];
1089         for (int i = 0; i < 5; ++i) {
1090             nodesel[i] = iters[i] && iters[i]->selected();
1091         }
1092         for (int i = 1; i < 4; ++i) {
1093             if (iters[i] && !nodesel[i-1] && !nodesel[i] && !nodesel[i+1]) {
1094                 iters[i]->showHandles(false);
1095             }
1096         }
1097     }
1098
1099     if (selected) ++_num_selected;
1100     else --_num_selected;
1101 }
1102
1103 /** Removes all nodes belonging to this manipulator from the control pont selection */
1104 void PathManipulator::_removeNodesFromSelection()
1105 {
1106     // remove this manipulator's nodes from selection
1107     for (std::list<SubpathPtr>::iterator i = _subpaths.begin(); i != _subpaths.end(); ++i) {
1108         for (NodeList::iterator j = (*i)->begin(); j != (*i)->end(); ++j) {
1109             _selection.erase(j.get_pointer());
1110         }
1111     }
1112 }
1113
1114 /** Update the XML representation and put the specified annotation on the undo stack */
1115 void PathManipulator::_commit(Glib::ustring const &annotation)
1116 {
1117     writeXML();
1118     sp_document_done(sp_desktop_document(_desktop), SP_VERB_CONTEXT_NODE, annotation.data());
1119 }
1120
1121 /** Update the position of the curve drag point such that it is over the nearest
1122  * point of the path. */
1123 void PathManipulator::_updateDragPoint(Geom::Point const &evp)
1124 {
1125     // TODO find a way to make this faster (no transform required)
1126     Geom::PathVector pv = _spcurve->get_pathvector() * (_edit_transform * _i2d_transform);
1127     boost::optional<Geom::PathVectorPosition> pvp
1128         = Geom::nearestPoint(pv, _desktop->w2d(evp));
1129     if (!pvp) return;
1130     Geom::Point nearest_point = _desktop->d2w(pv.at(pvp->path_nr).pointAt(pvp->t));
1131
1132     double fracpart;
1133     std::list<SubpathPtr>::iterator spi = _subpaths.begin();
1134     for (unsigned i = 0; i < pvp->path_nr; ++i, ++spi) {}
1135     NodeList::iterator first = (*spi)->before(pvp->t, &fracpart);
1136
1137     double stroke_tolerance = _getStrokeTolerance();
1138     if (Geom::distance(evp, nearest_point) < stroke_tolerance) {
1139         _dragpoint->setVisible(true);
1140         _dragpoint->setPosition(_desktop->w2d(nearest_point));
1141         _dragpoint->setSize(2 * stroke_tolerance);
1142         _dragpoint->setTimeValue(fracpart);
1143         _dragpoint->setIterator(first);
1144     } else {
1145         _dragpoint->setVisible(false);
1146     }
1147 }
1148
1149 /// This is called on zoom change to update the direction arrows
1150 void PathManipulator::_updateOutlineOnZoomChange()
1151 {
1152     if (_show_path_direction) _updateOutline();
1153 }
1154
1155 /** Compute the radius from the edge of the path where clicks chould initiate a curve drag
1156  * or segment selection, in window coordinates. */
1157 double PathManipulator::_getStrokeTolerance()
1158 {
1159     /* Stroke event tolerance is equal to half the stroke's width plus the global
1160      * drag tolerance setting.  */
1161     Inkscape::Preferences *prefs = Inkscape::Preferences::get();
1162     double ret = prefs->getIntLimited("/options/dragtolerance/value", 2, 0, 100);
1163     if (_path && !SP_OBJECT_STYLE(_path)->stroke.isNone()) {
1164         ret += SP_OBJECT_STYLE(_path)->stroke_width.computed * 0.5
1165             * (_edit_transform * _i2d_transform).descrim() // scale to desktop coords
1166             * _desktop->current_zoom(); // == _d2w.descrim() - scale to window coords
1167     }
1168     return ret;
1169 }
1170
1171 } // namespace UI
1172 } // namespace Inkscape
1173
1174 /*
1175   Local Variables:
1176   mode:c++
1177   c-file-style:"stroustrup"
1178   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1179   indent-tabs-mode:nil
1180   fill-column:99
1181   End:
1182 */
1183 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :