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