src/snap.cpp

   1 #define __SP_DESKTOP_SNAP_C__
   2
   3 /**
   4  * \file snap.cpp
   5  * \brief SnapManager class.
   6  *
   7  * Authors:
   8  *   Lauris Kaplinski <lauris@kaplinski.com>
   9  *   Frank Felfe <innerspace@iname.com>
  10  *   Nathan Hurst <njh@njhurst.com>
  11  *   Carl Hetherington <inkscape@carlh.net>
  12  *   Diederik van Lierop <mail@diedenrezi.nl>
  13  *
  14  * Copyright (C) 2006-2007 Johan Engelen <johan@shouraizou.nl>
  15  * Copyrigth (C) 2004      Nathan Hurst
  16  * Copyright (C) 1999-2010 Authors
  17  *
  18  * Released under GNU GPL, read the file 'COPYING' for more information
  19  */
  20
  21 #include <utility>
  22
  23 #include "sp-namedview.h"
  24 #include "snap.h"
  25 #include "snap-enums.h"
  26 #include "snapped-line.h"
  27 #include "snapped-curve.h"
  28
  29 #include "display/canvas-grid.h"
  30 #include "display/snap-indicator.h"
  31
  32 #include "inkscape.h"
  33 #include "desktop.h"
  34 #include "selection.h"
  35 #include "sp-guide.h"
  36 #include "preferences.h"
  37 #include "event-context.h"
  38 #include "util/mathfns.h"
  39 using std::vector;
  40
  41 /**
  42  *  Construct a SnapManager for a SPNamedView.
  43  *
  44  *  \param v `Owning' SPNamedView.
  45  */
  46
  47 SnapManager::SnapManager(SPNamedView const *v) :
  48     guide(this, 0),
  49     object(this, 0),
  50     snapprefs(),
  51     _named_view(v),
  52     _rotation_center_source_items(NULL),
  53     _guide_to_ignore(NULL),
  54     _desktop(NULL),
  55     _unselected_nodes(NULL)
  56 {
  57 }
  58
  59 /**
  60  *  \brief Return a list of snappers
  61  *
  62  *  Inkscape snaps to objects, grids, and guides. For each of these snap targets a
  63  *  separate class is used, which has been derived from the base Snapper class. The
  64  *  getSnappers() method returns a list of pointers to instances of this class. This
  65  *  list contains exactly one instance of the guide snapper and of the object snapper
  66  *  class, but any number of grid snappers (because each grid has its own snapper
  67  *  instance)
  68  *
  69  *  \return List of snappers that we use.
  70  */
  71 SnapManager::SnapperList
  72 SnapManager::getSnappers() const
  73 {
  74     SnapManager::SnapperList s;
  75     s.push_back(&guide);
  76     s.push_back(&object);
  77
  78     SnapManager::SnapperList gs = getGridSnappers();
  79     s.splice(s.begin(), gs);
  80
  81     return s;
  82 }
  83
  84 /**
  85  *  \brief Return a list of gridsnappers
  86  *
  87  *  Each grid has its own instance of the snapper class. This way snapping can
  88  *  be enabled per grid individually. A list will be returned containing the
  89  *  pointers to these instances, but only for grids that are being displayed
  90  *  and for which snapping is enabled.
  91  *
  92  *  \return List of gridsnappers that we use.
  93  */
  94 SnapManager::SnapperList
  95 SnapManager::getGridSnappers() const
  96 {
  97     SnapperList s;
  98
  99     if (_desktop && _desktop->gridsEnabled() && snapprefs.getSnapToGrids()) {
 100         for ( GSList const *l = _named_view->grids; l != NULL; l = l->next) {
 101             Inkscape::CanvasGrid *grid = (Inkscape::CanvasGrid*) l->data;
 102             s.push_back(grid->snapper);
 103         }
 104     }
 105
 106     return s;
 107 }
 108
 109 /**
 110  * \brief Return true if any snapping might occur, whether its to grids, guides or objects
 111  *
 112  * Each snapper instance handles its own snapping target, e.g. grids, guides or
 113  * objects. This method iterates through all these snapper instances and returns
 114  * true if any of the snappers might possible snap, considering only the relevant
 115  * snapping preferences.
 116  *
 117  * \return true if one of the snappers will try to snap to something.
 118  */
 119
 120 bool SnapManager::someSnapperMightSnap() const
 121 {
 122     if ( !snapprefs.getSnapEnabledGlobally() || snapprefs.getSnapPostponedGlobally() ) {
 123         return false;
 124     }
 125
 126     SnapperList const s = getSnappers();
 127     SnapperList::const_iterator i = s.begin();
 128     while (i != s.end() && (*i)->ThisSnapperMightSnap() == false) {
 129         i++;
 130     }
 131
 132     return (i != s.end());
 133 }
 134
 135 /**
 136  * \return true if one of the grids might be snapped to.
 137  */
 138
 139 bool SnapManager::gridSnapperMightSnap() const
 140 {
 141     if ( !snapprefs.getSnapEnabledGlobally() || snapprefs.getSnapPostponedGlobally() ) {
 142         return false;
 143     }
 144
 145     SnapperList const s = getGridSnappers();
 146     SnapperList::const_iterator i = s.begin();
 147     while (i != s.end() && (*i)->ThisSnapperMightSnap() == false) {
 148         i++;
 149     }
 150
 151     return (i != s.end());
 152 }
 153
 154 /**
 155  *  \brief Try to snap a point to grids, guides or objects.
 156  *
 157  *  Try to snap a point to grids, guides or objects, in two degrees-of-freedom,
 158  *  i.e. snap in any direction on the two dimensional canvas to the nearest
 159  *  snap target. freeSnapReturnByRef() is equal in snapping behavior to
 160  *  freeSnap(), but the former returns the snapped point trough the referenced
 161  *  parameter p. This parameter p initially contains the position of the snap
 162  *  source and will we overwritten by the target position if snapping has occurred.
 163  *  This makes snapping transparent to the calling code. If this is not desired
 164  *  because either the calling code must know whether snapping has occurred, or
 165  *  because the original position should not be touched, then freeSnap() should be
 166  *  called instead.
 167  *
 168  *  PS:
 169  *  1) SnapManager::setup() must have been called before calling this method,
 170  *  but only once for a set of points
 171  *  2) Only to be used when a single source point is to be snapped; it assumes
 172  *  that source_num = 0, which is inefficient when snapping sets our source points
 173  *
 174  *  \param p Current position of the snap source; will be overwritten by the position of the snap target if snapping has occurred
 175  *  \param source_type Detailed description of the source type, will be used by the snap indicator
 176  *  \param bbox_to_snap Bounding box hulling the set of points, all from the same selection and having the same transformation
 177  */
 178
 179 void SnapManager::freeSnapReturnByRef(Geom::Point &p,
 180                                       Inkscape::SnapSourceType const source_type,
 181                                       Geom::OptRect const &bbox_to_snap) const
 182 {
 183     Inkscape::SnappedPoint const s = freeSnap(Inkscape::SnapCandidatePoint(p, source_type), bbox_to_snap);
 184     s.getPointIfSnapped(p);
 185 }
 186
 187
 188 /**
 189  *  \brief Try to snap a point to grids, guides or objects.
 190  *
 191  *  Try to snap a point to grids, guides or objects, in two degrees-of-freedom,
 192  *  i.e. snap in any direction on the two dimensional canvas to the nearest
 193  *  snap target. freeSnap() is equal in snapping behavior to
 194  *  freeSnapReturnByRef(). Please read the comments of the latter for more details
 195  *
 196  *  PS: SnapManager::setup() must have been called before calling this method,
 197  *  but only once for a set of points
 198  *
 199  *  \param p Source point to be snapped
 200  *  \param bbox_to_snap Bounding box hulling the set of points, all from the same selection and having the same transformation
 201  *  \return An instance of the SnappedPoint class, which holds data on the snap source, snap target, and various metrics
 202  */
 203
 204
 205 Inkscape::SnappedPoint SnapManager::freeSnap(Inkscape::SnapCandidatePoint const &p,
 206                                              Geom::OptRect const &bbox_to_snap) const
 207 {
 208     if (!someSnapperMightSnap()) {
 209         return Inkscape::SnappedPoint(p, Inkscape::SNAPTARGET_UNDEFINED, NR_HUGE, 0, false, false, false);
 210     }
 211
 212     SnappedConstraints sc;
 213     SnapperList const snappers = getSnappers();
 214
 215     for (SnapperList::const_iterator i = snappers.begin(); i != snappers.end(); i++) {
 216         (*i)->freeSnap(sc, p, bbox_to_snap, &_items_to_ignore, _unselected_nodes);
 217     }
 218
 219     return findBestSnap(p, sc, false);
 220 }
 221
 222 void SnapManager::preSnap(Inkscape::SnapCandidatePoint const &p)
 223 {
 224     // setup() must have been called before calling this method!
 225
 226     if (_snapindicator) {
 227         _snapindicator = false; // prevent other methods from drawing a snap indicator; we want to control this here
 228         Inkscape::SnappedPoint s = freeSnap(p);
 229         g_assert(_desktop != NULL);
 230         if (s.getSnapped()) {
 231             _desktop->snapindicator->set_new_snaptarget(s, true);
 232         } else {
 233             _desktop->snapindicator->remove_snaptarget(true);
 234         }
 235         _snapindicator = true; // restore the original value
 236     }
 237 }
 238
 239 /**
 240  * \brief Snap to the closest multiple of a grid pitch
 241  *
 242  * When pasting, we would like to snap to the grid. Problem is that we don't know which
 243  * nodes were aligned to the grid at the time of copying, so we don't know which nodes
 244  * to snap. If we'd snap an unaligned node to the grid, previously aligned nodes would
 245  * become unaligned. That's undesirable. Instead we will make sure that the offset
 246  * between the source and its pasted copy is a multiple of the grid pitch. If the source
 247  * was aligned, then the copy will therefore also be aligned.
 248  *
 249  * PS: Whether we really find a multiple also depends on the snapping range! Most users
 250  * will have "always snap" enabled though, in which case a multiple will always be found.
 251  * PS2: When multiple grids are present then the result will become ambiguous. There is no
 252  * way to control to which grid this method will snap.
 253  *
 254  * \param t Vector that represents the offset of the pasted copy with respect to the original
 255  * \return Offset vector after snapping to the closest multiple of a grid pitch
 256  */
 257
 258 Geom::Point SnapManager::multipleOfGridPitch(Geom::Point const &t, Geom::Point const &origin)
 259 {
 260     if (!snapprefs.getSnapEnabledGlobally() || snapprefs.getSnapPostponedGlobally())
 261         return t;
 262
 263     if (_desktop && _desktop->gridsEnabled()) {
 264         bool success = false;
 265         Geom::Point nearest_multiple;
 266         Geom::Coord nearest_distance = NR_HUGE;
 267         Inkscape::SnappedPoint bestSnappedPoint(t);
 268
 269         // It will snap to the grid for which we find the closest snap. This might be a different
 270         // grid than to which the objects were initially aligned. I don't see an easy way to fix
 271         // this, so when using multiple grids one can get unexpected results
 272
 273         // Cannot use getGridSnappers() because we need both the grids AND their snappers
 274         // Therefore we iterate through all grids manually
 275         for (GSList const *l = _named_view->grids; l != NULL; l = l->next) {
 276             Inkscape::CanvasGrid *grid = (Inkscape::CanvasGrid*) l->data;
 277             const Inkscape::Snapper* snapper = grid->snapper;
 278             if (snapper && snapper->ThisSnapperMightSnap()) {
 279                 // To find the nearest multiple of the grid pitch for a given translation t, we
 280                 // will use the grid snapper. Simply snapping the value t to the grid will do, but
 281                 // only if the origin of the grid is at (0,0). If it's not then compensate for this
 282                 // in the translation t
 283                 Geom::Point const t_offset = t + grid->origin;
 284                 SnappedConstraints sc;
 285                 // Only the first three parameters are being used for grid snappers
 286                 snapper->freeSnap(sc, Inkscape::SnapCandidatePoint(t_offset, Inkscape::SNAPSOURCE_GRID_PITCH),Geom::OptRect(), NULL, NULL);
 287                 // Find the best snap for this grid, including intersections of the grid-lines
 288                 bool old_val = _snapindicator;
 289                 _snapindicator = false;
 290                 Inkscape::SnappedPoint s = findBestSnap(Inkscape::SnapCandidatePoint(t_offset, Inkscape::SNAPSOURCE_GRID_PITCH), sc, false, false, true);
 291                 _snapindicator = old_val;
 292                 if (s.getSnapped() && (s.getSnapDistance() < nearest_distance)) {
 293                     // use getSnapDistance() instead of getWeightedDistance() here because the pointer's position
 294                     // doesn't tell us anything about which node to snap
 295                     success = true;
 296                     nearest_multiple = s.getPoint() - to_2geom(grid->origin);
 297                     nearest_distance = s.getSnapDistance();
 298                     bestSnappedPoint = s;
 299                 }
 300             }
 301         }
 302
 303         if (success) {
 304             bestSnappedPoint.setPoint(origin + nearest_multiple);
 305             _desktop->snapindicator->set_new_snaptarget(bestSnappedPoint);
 306             return nearest_multiple;
 307         }
 308     }
 309
 310     return t;
 311 }
 312
 313 /**
 314  *  \brief Try to snap a point along a constraint line to grids, guides or objects.
 315  *
 316  *  Try to snap a point to grids, guides or objects, in only one degree-of-freedom,
 317  *  i.e. snap in a specific direction on the two dimensional canvas to the nearest
 318  *  snap target.
 319  *
 320  *  constrainedSnapReturnByRef() is equal in snapping behavior to
 321  *  constrainedSnap(), but the former returns the snapped point trough the referenced
 322  *  parameter p. This parameter p initially contains the position of the snap
 323  *  source and will be overwritten by the target position if snapping has occurred.
 324  *  This makes snapping transparent to the calling code. If this is not desired
 325  *  because either the calling code must know whether snapping has occurred, or
 326  *  because the original position should not be touched, then constrainedSnap() should
 327  *  be called instead. If there's nothing to snap to or if snapping has been disabled,
 328  *  then this method will still apply the constraint (but without snapping)
 329  *
 330  *  PS:
 331  *  1) SnapManager::setup() must have been called before calling this method,
 332  *  but only once for a set of points
 333  *  2) Only to be used when a single source point is to be snapped; it assumes
 334  *  that source_num = 0, which is inefficient when snapping sets our source points
 335
 336  *
 337  *  \param p Current position of the snap source; will be overwritten by the position of the snap target if snapping has occurred
 338  *  \param source_type Detailed description of the source type, will be used by the snap indicator
 339  *  \param constraint The direction or line along which snapping must occur
 340  *  \param bbox_to_snap Bounding box hulling the set of points, all from the same selection and having the same transformation
 341  */
 342
 343 void SnapManager::constrainedSnapReturnByRef(Geom::Point &p,
 344                                              Inkscape::SnapSourceType const source_type,
 345                                              Inkscape::Snapper::SnapConstraint const &constraint,
 346                                              Geom::OptRect const &bbox_to_snap) const
 347 {
 348     Inkscape::SnappedPoint const s = constrainedSnap(Inkscape::SnapCandidatePoint(p, source_type), constraint, bbox_to_snap);
 349     p = s.getPoint(); // If we didn't snap, then we will return the point projected onto the constraint
 350 }
 351
 352 /**
 353  *  \brief Try to snap a point along a constraint line to grids, guides or objects.
 354  *
 355  *  Try to snap a point to grids, guides or objects, in only one degree-of-freedom,
 356  *  i.e. snap in a specific direction on the two dimensional canvas to the nearest
 357  *  snap target. constrainedSnap is equal in snapping behavior to
 358  *  constrainedSnapReturnByRef(). Please read the comments of the latter for more details.
 359  *
 360  *  PS: SnapManager::setup() must have been called before calling this method,
 361  *  but only once for a set of points
 362  *  PS: If there's nothing to snap to or if snapping has been disabled, then this
 363  *  method will still apply the constraint (but without snapping)
 364  *
 365  *  \param p Source point to be snapped
 366  *  \param constraint The direction or line along which snapping must occur
 367  *  \param bbox_to_snap Bounding box hulling the set of points, all from the same selection and having the same transformation
 368  */
 369
 370 Inkscape::SnappedPoint SnapManager::constrainedSnap(Inkscape::SnapCandidatePoint const &p,
 371                                                     Inkscape::Snapper::SnapConstraint const &constraint,
 372                                                     Geom::OptRect const &bbox_to_snap) const
 373 {
 374     // First project the mouse pointer onto the constraint
 375     Geom::Point pp = constraint.projection(p.getPoint());
 376
 377     Inkscape::SnappedPoint no_snap = Inkscape::SnappedPoint(pp, p.getSourceType(), p.getSourceNum(), Inkscape::SNAPTARGET_CONSTRAINT, NR_HUGE, 0, false, true, false);
 378
 379     if (!someSnapperMightSnap()) {
 380         // Always return point on constraint
 381         return no_snap;
 382     }
 383
 384     Inkscape::SnappedPoint result = no_snap;
 385
 386     Inkscape::Preferences *prefs = Inkscape::Preferences::get();
 387     if ((prefs->getBool("/options/snapmousepointer/value", false)) && p.isSingleHandle()) {
 388         // Snapping the mouse pointer instead of the constrained position of the knot allows
 389         // to snap to things which don't intersect with the constraint line; this is basically
 390         // then just a freesnap with the constraint applied afterwards
 391         // We'll only to this if we're dragging a single handle, and for example not when transforming an object in the selector tool
 392         result = freeSnap(p, bbox_to_snap);
 393         if (result.getSnapped()) {
 394             // only change the snap indicator if we really snapped to something
 395             if (_snapindicator && _desktop) {
 396                 _desktop->snapindicator->set_new_snaptarget(result);
 397             }
 398             // Apply the constraint
 399             result.setPoint(constraint.projection(result.getPoint()));
 400             return result;
 401         }
 402         return no_snap;
 403     }
 404
 405     SnappedConstraints sc;
 406     SnapperList const snappers = getSnappers();
 407     for (SnapperList::const_iterator i = snappers.begin(); i != snappers.end(); i++) {
 408         (*i)->constrainedSnap(sc, p, bbox_to_snap, constraint, &_items_to_ignore, _unselected_nodes);
 409     }
 410
 411     result = findBestSnap(p, sc, true);
 412
 413     if (result.getSnapped()) {
 414         // only change the snap indicator if we really snapped to something
 415         if (_snapindicator && _desktop) {
 416             _desktop->snapindicator->set_new_snaptarget(result);
 417         }
 418         return result;
 419     }
 420     return no_snap;
 421 }
 422
 423 /* See the documentation for constrainedSnap() directly above for more details.
 424  * The difference is that multipleConstrainedSnaps() will take a list of constraints instead of a single one,
 425  * and will try to snap the SnapCandidatePoint to all of the provided constraints and see which one fits best
 426  *  \param p Source point to be snapped
 427  *  \param constraints List of directions or lines along which snapping must occur
 428  *  \param dont_snap If true then we will only apply the constraint, without snapping
 429  *  \param bbox_to_snap Bounding box hulling the set of points, all from the same selection and having the same transformation
 430  */
 431
 432
 433 Inkscape::SnappedPoint SnapManager::multipleConstrainedSnaps(Inkscape::SnapCandidatePoint const &p,
 434                                                     std::vector<Inkscape::Snapper::SnapConstraint> const &constraints,
 435                                                     bool dont_snap,
 436                                                     Geom::OptRect const &bbox_to_snap) const
 437 {
 438
 439     Inkscape::SnappedPoint no_snap = Inkscape::SnappedPoint(p.getPoint(), p.getSourceType(), p.getSourceNum(), Inkscape::SNAPTARGET_CONSTRAINT, NR_HUGE, 0, false, true, false);
 440     if (constraints.size() == 0) {
 441         return no_snap;
 442     }
 443
 444     SnappedConstraints sc;
 445     SnapperList const snappers = getSnappers();
 446     std::vector<Geom::Point> projections;
 447     bool snapping_is_futile = !someSnapperMightSnap() || dont_snap;
 448
 449     Inkscape::SnappedPoint result = no_snap;
 450
 451     Inkscape::Preferences *prefs = Inkscape::Preferences::get();
 452     bool snap_mouse = prefs->getBool("/options/snapmousepointer/value", false);
 453
 454     for (std::vector<Inkscape::Snapper::SnapConstraint>::const_iterator c = constraints.begin(); c != constraints.end(); c++) {
 455         // Project the mouse pointer onto the constraint; In case we don't snap then we will
 456         // return the projection onto the constraint, such that the constraint is always enforced
 457         Geom::Point pp = (*c).projection(p.getPoint());
 458         projections.push_back(pp);
 459     }
 460
 461     if (snap_mouse && p.isSingleHandle() && !dont_snap) {
 462         // Snapping the mouse pointer instead of the constrained position of the knot allows
 463         // to snap to things which don't intersect with the constraint line; this is basically
 464         // then just a freesnap with the constraint applied afterwards
 465         // We'll only to this if we're dragging a single handle, and for example not when transforming an object in the selector tool
 466         result = freeSnap(p, bbox_to_snap);
 467     } else {
 468         // Iterate over the constraints
 469         for (std::vector<Inkscape::Snapper::SnapConstraint>::const_iterator c = constraints.begin(); c != constraints.end(); c++) {
 470             // Try to snap to the constraint
 471             if (!snapping_is_futile) {
 472                 for (SnapperList::const_iterator i = snappers.begin(); i != snappers.end(); i++) {
 473                     (*i)->constrainedSnap(sc, p, bbox_to_snap, *c, &_items_to_ignore,_unselected_nodes);
 474                 }
 475             }
 476         }
 477         result = findBestSnap(p, sc, true);
 478     }
 479
 480     if (result.getSnapped()) {
 481         if (snap_mouse) {
 482             // If "snap_mouse" then we still have to apply the constraint, because so far we only tried a freeSnap
 483             Geom::Point result_closest;
 484             for (std::vector<Inkscape::Snapper::SnapConstraint>::const_iterator c = constraints.begin(); c != constraints.end(); c++) {
 485                 // Project the mouse pointer onto the constraint; In case we don't snap then we will
 486                 // return the projection onto the constraint, such that the constraint is always enforced
 487                 Geom::Point result_p = (*c).projection(result.getPoint());
 488                 if (c == constraints.begin() || (Geom::L2(result_p - p.getPoint()) < Geom::L2(result_closest - p.getPoint()))) {
 489                     result_closest = result_p;
 490                 }
 491             }
 492             result.setPoint(result_closest);
 493         }
 494         return result;
 495     }
 496
 497     // So we didn't snap, but we still need to return a point on one of the constraints
 498     // Find out which of the constraints yielded the closest projection of point p
 499     for (std::vector<Geom::Point>::iterator pp = projections.begin(); pp != projections.end(); pp++) {
 500         if (pp != projections.begin()) {
 501             if (Geom::L2(*pp - p.getPoint()) < Geom::L2(no_snap.getPoint() - p.getPoint())) {
 502                 no_snap.setPoint(*pp);
 503             }
 504         } else {
 505             no_snap.setPoint(projections.front());
 506         }
 507     }
 508
 509     return no_snap;
 510 }
 511
 512 /**
 513  *  \brief Try to snap a point to something at a specific angle
 514  *
 515  *  When drawing a straight line or modifying a gradient, it will snap to specific angle increments
 516  *  if CTRL is being pressed. This method will enforce this angular constraint (even if there is nothing
 517  *  to snap to)
 518  *
 519  *  \param p Source point to be snapped
 520  *  \param p_ref Optional original point, relative to which the angle should be calculated. If empty then
 521  *  the angle will be calculated relative to the y-axis
 522  *  \param snaps Number of angular increments per PI radians; E.g. if snaps = 2 then we will snap every PI/2 = 90 degrees
 523  */
 524
 525 Inkscape::SnappedPoint SnapManager::constrainedAngularSnap(Inkscape::SnapCandidatePoint const &p,
 526                                                             boost::optional<Geom::Point> const &p_ref,
 527                                                             Geom::Point const &o,
 528                                                             unsigned const snaps) const
 529 {
 530     Inkscape::SnappedPoint sp;
 531     if (snaps > 0) { // 0 means no angular snapping
 532         // p is at an arbitrary angle. Now we should snap this angle to specific increments.
 533         // For this we'll calculate the closest two angles, one at each side of the current angle
 534         Geom::Line y_axis(Geom::Point(0, 0), Geom::Point(0, 1));
 535         Geom::Line p_line(o, p.getPoint());
 536         double angle = Geom::angle_between(y_axis, p_line);
 537         double angle_incr = M_PI / snaps;
 538         double angle_offset = 0;
 539         if (p_ref) {
 540             Geom::Line p_line_ref(o, *p_ref);
 541             angle_offset = Geom::angle_between(y_axis, p_line_ref);
 542         }
 543         double angle_ceil = round_to_upper_multiple_plus(angle, angle_incr, angle_offset);
 544         double angle_floor = round_to_lower_multiple_plus(angle, angle_incr, angle_offset);
 545         // We have two angles now. The constrained snapper will try each of them and return the closest
 546
 547         // Now do the snapping...
 548         std::vector<Inkscape::Snapper::SnapConstraint> constraints;
 549         constraints.push_back(Inkscape::Snapper::SnapConstraint(Geom::Line(o, angle_ceil - M_PI/2)));
 550         constraints.push_back(Inkscape::Snapper::SnapConstraint(Geom::Line(o, angle_floor - M_PI/2)));
 551         sp = multipleConstrainedSnaps(p, constraints); // Constraints will always be applied, even if we didn't snap
 552         if (!sp.getSnapped()) { // If we haven't snapped then we only had the constraint applied;
 553             sp.setTarget(Inkscape::SNAPTARGET_CONSTRAINED_ANGLE);
 554         }
 555     } else {
 556         sp = freeSnap(p);
 557     }
 558     return sp;
 559 }
 560
 561 /**
 562  *  \brief Try to snap a point of a guide to another guide or to a node
 563  *
 564  *  Try to snap a point of a guide to another guide or to a node in two degrees-
 565  *  of-freedom, i.e. snap in any direction on the two dimensional canvas to the
 566  *  nearest snap target. This method is used when dragging or rotating a guide
 567  *
 568  *  PS: SnapManager::setup() must have been called before calling this method,
 569  *
 570  *  \param p Current position of the point on the guide that is to be snapped; will be overwritten by the position of the snap target if snapping has occurred
 571  *  \param guide_normal Vector normal to the guide line
 572  */
 573 void SnapManager::guideFreeSnap(Geom::Point &p, Geom::Point const &guide_normal, SPGuideDragType drag_type) const
 574 {
 575     if (!snapprefs.getSnapEnabledGlobally() || snapprefs.getSnapPostponedGlobally()) {
 576         return;
 577     }
 578
 579     if (!(object.ThisSnapperMightSnap() || snapprefs.getSnapToGuides())) {
 580         return;
 581     }
 582
 583     Inkscape::SnapCandidatePoint candidate(p, Inkscape::SNAPSOURCE_GUIDE_ORIGIN);
 584     if (drag_type == SP_DRAG_ROTATE) {
 585         candidate = Inkscape::SnapCandidatePoint(p, Inkscape::SNAPSOURCE_GUIDE);
 586     }
 587
 588     // Snap to nodes
 589     SnappedConstraints sc;
 590     if (object.ThisSnapperMightSnap()) {
 591         object.guideFreeSnap(sc, p, guide_normal);
 592     }
 593
 594     // Snap to guides & grid lines
 595     SnapperList snappers = getGridSnappers();
 596     snappers.push_back(&guide);
 597     for (SnapperList::const_iterator i = snappers.begin(); i != snappers.end(); i++) {
 598         (*i)->freeSnap(sc, candidate, Geom::OptRect(), NULL, NULL);
 599     }
 600
 601     Inkscape::SnappedPoint const s = findBestSnap(candidate, sc, false, false);
 602
 603     s.getPointIfSnapped(p);
 604 }
 605
 606 /**
 607  *  \brief Try to snap a point on a guide to the intersection with another guide or a path
 608  *
 609  *  Try to snap a point on a guide to the intersection of that guide with another
 610  *  guide or with a path. The snapped point will lie somewhere on the guide-line,
 611  *  making this is a constrained snap, i.e. in only one degree-of-freedom.
 612  *  This method is used when dragging the origin of the guide along the guide itself.
 613  *
 614  *  PS: SnapManager::setup() must have been called before calling this method,
 615  *
 616  *  \param p Current position of the point on the guide that is to be snapped; will be overwritten by the position of the snap target if snapping has occurred
 617  *  \param guide_normal Vector normal to the guide line
 618  */
 619
 620 void SnapManager::guideConstrainedSnap(Geom::Point &p, SPGuide const &guideline) const
 621 {
 622     if (!snapprefs.getSnapEnabledGlobally() || snapprefs.getSnapPostponedGlobally()) {
 623         return;
 624     }
 625
 626     if (!(object.ThisSnapperMightSnap() || snapprefs.getSnapToGuides())) {
 627         return;
 628     }
 629
 630     Inkscape::SnapCandidatePoint candidate(p, Inkscape::SNAPSOURCE_GUIDE_ORIGIN, Inkscape::SNAPTARGET_UNDEFINED);
 631
 632     // Snap to nodes or paths
 633     SnappedConstraints sc;
 634     Inkscape::Snapper::SnapConstraint cl(guideline.point_on_line, Geom::rot90(guideline.normal_to_line));
 635     if (object.ThisSnapperMightSnap()) {
 636         object.constrainedSnap(sc, candidate, Geom::OptRect(), cl, NULL, NULL);
 637     }
 638
 639     // Snap to guides & grid lines
 640     SnapperList snappers = getGridSnappers();
 641     snappers.push_back(&guide);
 642     for (SnapperList::const_iterator i = snappers.begin(); i != snappers.end(); i++) {
 643         (*i)->constrainedSnap(sc, candidate, Geom::OptRect(), cl, NULL, NULL);
 644     }
 645
 646     Inkscape::SnappedPoint const s = findBestSnap(candidate, sc, false);
 647     s.getPointIfSnapped(p);
 648 }
 649
 650 /**
 651  *  \brief Method for snapping sets of points while they are being transformed
 652  *
 653  *  Method for snapping sets of points while they are being transformed, when using
 654  *  for example the selector tool. This method is for internal use only, and should
 655  *  not have to be called directly. Use freeSnapTransalation(), constrainedSnapScale(),
 656  *  etc. instead.
 657  *
 658  *  This is what is being done in this method: transform each point, find out whether
 659  *  a free snap or constrained snap is more appropriate, do the snapping, calculate
 660  *  some metrics to quantify the snap "distance", and see if it's better than the
 661  *  previous snap. Finally, the best ("nearest") snap from all these points is returned.
 662  *  If no snap has occurred and we're asked for a constrained snap then the constraint
 663  *  will be applied nevertheless
 664  *
 665  *  \param points Collection of points to snap (snap sources), at their untransformed position, all points undergoing the same transformation. Paired with an identifier of the type of the snap source.
 666  *  \param pointer Location of the mouse pointer at the time dragging started (i.e. when the selection was still untransformed).
 667  *  \param constrained true if the snap is constrained, e.g. for stretching or for purely horizontal translation.
 668  *  \param constraint The direction or line along which snapping must occur, if 'constrained' is true; otherwise undefined.
 669  *  \param transformation_type Type of transformation to apply to points before trying to snap them.
 670  *  \param transformation Description of the transformation; details depend on the type.
 671  *  \param origin Origin of the transformation, if applicable.
 672  *  \param dim Dimension to which the transformation applies, if applicable.
 673  *  \param uniform true if the transformation should be uniform; only applicable for stretching and scaling.
 674  *  \return An instance of the SnappedPoint class, which holds data on the snap source, snap target, and various metrics.
 675  */
 676
 677 Inkscape::SnappedPoint SnapManager::_snapTransformed(
 678     std::vector<Inkscape::SnapCandidatePoint> const &points,
 679     Geom::Point const &pointer,
 680     bool constrained,
 681     Inkscape::Snapper::SnapConstraint const &constraint,
 682     Transformation transformation_type,
 683     Geom::Point const &transformation,
 684     Geom::Point const &origin,
 685     Geom::Dim2 dim,
 686     bool uniform)
 687 {
 688     /* We have a list of points, which we are proposing to transform in some way.  We need to see
 689     ** if any of these points, when transformed, snap to anything.  If they do, we return the
 690     ** appropriate transformation with `true'; otherwise we return the original scale with `false'.
 691     */
 692
 693     if (points.size() == 0) {
 694         return Inkscape::SnappedPoint(pointer);
 695     }
 696
 697     std::vector<Inkscape::SnapCandidatePoint> transformed_points;
 698     Geom::Rect bbox;
 699
 700     long source_num = 0;
 701     for (std::vector<Inkscape::SnapCandidatePoint>::const_iterator i = points.begin(); i != points.end(); i++) {
 702
 703         /* Work out the transformed version of this point */
 704         Geom::Point transformed = _transformPoint(*i, transformation_type, transformation, origin, dim, uniform);
 705
 706         // add the current transformed point to the box hulling all transformed points
 707         if (i == points.begin()) {
 708             bbox = Geom::Rect(transformed, transformed);
 709         } else {
 710             bbox.expandTo(transformed);
 711         }
 712
 713         transformed_points.push_back(Inkscape::SnapCandidatePoint(transformed, (*i).getSourceType(), source_num, Inkscape::SNAPTARGET_UNDEFINED, Geom::OptRect()));
 714         source_num++;
 715     }
 716
 717     /* The current best transformation */
 718     Geom::Point best_transformation = transformation;
 719
 720     /* The current best metric for the best transformation; lower is better, NR_HUGE
 721     ** means that we haven't snapped anything.
 722     */
 723     Geom::Point best_scale_metric(NR_HUGE, NR_HUGE);
 724     Inkscape::SnappedPoint best_snapped_point;
 725     g_assert(best_snapped_point.getAlwaysSnap() == false); // Check initialization of snapped point
 726     g_assert(best_snapped_point.getAtIntersection() == false);
 727
 728     // Warnings for the devs
 729     if (constrained && transformation_type == SCALE && !uniform) {
 730         g_warning("Non-uniform constrained scaling is not supported!");
 731     }
 732
 733     if (!constrained && transformation_type == ROTATE) {
 734         // We do not yet allow for simultaneous rotation and scaling
 735         g_warning("Unconstrained rotation is not supported!");
 736     }
 737
 738     // We will try to snap a set of points, but we don't want to have a snap indicator displayed
 739     // for each of them. That's why it's temporarily disabled here, and re-enabled again after we
 740     // have finished calling the freeSnap() and constrainedSnap() methods
 741     bool _orig_snapindicator_status = _snapindicator;
 742     _snapindicator = false;
 743
 744     std::vector<Inkscape::SnapCandidatePoint>::iterator j = transformed_points.begin();
 745
 746     // std::cout << std::endl;
 747     bool first_free_snap = true;
 748     for (std::vector<Inkscape::SnapCandidatePoint>::const_iterator i = points.begin(); i != points.end(); i++) {
 749
 750         /* Snap it */
 751         Inkscape::SnappedPoint snapped_point;
 752         Inkscape::Snapper::SnapConstraint dedicated_constraint = constraint;
 753         Geom::Point const b = ((*i).getPoint() - origin); // vector to original point (not the transformed point! required for rotations!)
 754
 755         if (constrained) {
 756             if (((transformation_type == SCALE || transformation_type == STRETCH) && uniform)) {
 757                 // When uniformly scaling, each point will have its own unique constraint line,
 758                 // running from the scaling origin to the original untransformed point. We will
 759                 // calculate that line here
 760                 dedicated_constraint = Inkscape::Snapper::SnapConstraint(origin, b);
 761             } else if (transformation_type == ROTATE) {
 762                 Geom::Coord r = Geom::L2(b); // the radius of the circular constraint
 763                 if (r < 1e-9) { // points too close to the rotation center will not move. Don't try to snap these
 764                     // as they will always yield a perfect snap result if they're already snapped beforehand (e.g.
 765                     // when the transformation center has been snapped to a grid intersection in the selector tool)
 766                     continue; // skip this SnapCandidate and continue with the next one
 767                     // PS1: Apparently we don't have to do this for skewing, but why?
 768                     // PS2: We cannot easily filter these points upstream, e.g. in the grab() method (seltrans.cpp)
 769                     // because the rotation center will change when pressing shift, and grab() won't be recalled.
 770                     // Filtering could be done in handleRequest() (again in seltrans.cpp), by iterating through
 771                     // the snap candidates. But hey, we're iterating here anyway.
 772                 }
 773                 dedicated_constraint = Inkscape::Snapper::SnapConstraint(origin, b, r);
 774             } else if (transformation_type == STRETCH) { // when non-uniform stretching {
 775                 dedicated_constraint = Inkscape::Snapper::SnapConstraint((*i).getPoint(), component_vectors[dim]);
 776             } else if (transformation_type == TRANSLATE) {
 777                 // When doing a constrained translation, all points will move in the same direction, i.e.
 778                 // either horizontally or vertically. The lines along which they move are therefore all
 779                 // parallel, but might not be colinear. Therefore we will have to specify the point through
 780                 // which the constraint-line runs here, for each point individually. (we could also have done this
 781                 // earlier on, e.g. in seltrans.cpp but we're being lazy there and don't want to add an iteration loop)
 782                 dedicated_constraint = Inkscape::Snapper::SnapConstraint((*i).getPoint(), constraint.getDirection());
 783             } // else: leave the original constraint, e.g. for skewing
 784             snapped_point = constrainedSnap(*j, dedicated_constraint, bbox);
 785         } else {
 786             bool const c1 = fabs(b[Geom::X]) < 1e-6;
 787             bool const c2 = fabs(b[Geom::Y]) < 1e-6;
 788             if (transformation_type == SCALE && (c1 || c2) && !(c1 && c2)) {
 789                 // When scaling, a point aligned either horizontally or vertically with the origin can only
 790                 // move in that specific direction; therefore it should only snap in that direction, otherwise
 791                 // we will get snapped points with an invalid transformation
 792                 dedicated_constraint = Inkscape::Snapper::SnapConstraint(origin, component_vectors[c1]);
 793                 snapped_point = constrainedSnap(*j, dedicated_constraint, bbox);
 794             } else {
 795                 // If we have a collection of SnapCandidatePoints, with mixed constrained snapping and free snapping
 796                 // requirements, then freeSnap might never see the SnapCandidatePoint with source_num == 0. The freeSnap()
 797                 // method in the object snapper depends on this, because only for source-num == 0 the target nodes will
 798                 // be collected. Therefore we enforce that the first SnapCandidatePoint that is to be freeSnapped always
 799                 // has source_num == 0;
 800                 // TODO: This is a bit ugly so fix this; do we need sourcenum for anything else? if we don't then get rid
 801                 // of it and explicitely communicate to the object snapper that this is a first point
 802                 if (first_free_snap) {
 803                     (*j).setSourceNum(0);
 804                     first_free_snap = false;
 805                 }
 806                 snapped_point = freeSnap(*j, bbox);
 807             }
 808         }
 809         // std::cout << "dist = " << snapped_point.getSnapDistance() << std::endl;
 810         snapped_point.setPointerDistance(Geom::L2(pointer - (*i).getPoint()));
 811
 812         // Allow the snapindicator to be displayed again
 813         _snapindicator = _orig_snapindicator_status;
 814
 815         Geom::Point result;
 816
 817         /*Find the transformation that describes where the snapped point has
 818         ** ended up, and also the metric for this transformation.
 819         */
 820         Geom::Point const a = snapped_point.getPoint() - origin; // vector to snapped point
 821         //Geom::Point const b = (*i - origin); // vector to original point
 822
 823         switch (transformation_type) {
 824             case TRANSLATE:
 825                 result = snapped_point.getPoint() - (*i).getPoint();
 826                 /* Consider the case in which a box is almost aligned with a grid in both
 827                  * horizontal and vertical directions. The distance to the intersection of
 828                  * the grid lines will always be larger then the distance to a single grid
 829                  * line. If we prefer snapping to an intersection over to a single
 830                  * grid line, then we cannot use "metric = Geom::L2(result)". Therefore the
 831                  * snapped distance will be used as a metric. Please note that the snapped
 832                  * distance to an intersection is defined as the distance to the nearest line
 833                  *  of the intersection, and not to the intersection itself!
 834                  */
 835                 // Only for translations, the relevant metric will be the real snapped distance,
 836                 // so we don't have to do anything special here
 837                 break;
 838             case SCALE:
 839             {
 840                 result = Geom::Point(NR_HUGE, NR_HUGE);
 841                 // If this point *i is horizontally or vertically aligned with
 842                 // the origin of the scaling, then it will scale purely in X or Y
 843                 // We can therefore only calculate the scaling in this direction
 844                 // and the scaling factor for the other direction should remain
 845                 // untouched (unless scaling is uniform of course)
 846                 for (int index = 0; index < 2; index++) {
 847                     if (fabs(b[index]) > 1e-6) { // if SCALING CAN occur in this direction
 848                         if (fabs(fabs(a[index]/b[index]) - fabs(transformation[index])) > 1e-12) { // if SNAPPING DID occur in this direction
 849                             result[index] = a[index] / b[index]; // then calculate it!
 850                         }
 851                         // we might have left result[1-index] = NR_HUGE
 852                         // if scaling didn't occur in the other direction
 853                     }
 854                 }
 855                 if (uniform) {
 856                     if (fabs(result[0]) < fabs(result[1])) {
 857                         result[1] = result[0];
 858                     } else {
 859                         result[0] = result[1];
 860                     }
 861                 }
 862                 // Compare the resulting scaling with the desired scaling
 863                 Geom::Point scale_metric = Geom::abs(result - transformation); // One or both of its components might be NR_HUGE
 864                 if (scale_metric[0] == NR_HUGE || scale_metric[1] == NR_HUGE) {
 865                     snapped_point.setSnapDistance(std::min(scale_metric[0], scale_metric[1]));
 866                 } else {
 867                     snapped_point.setSnapDistance(Geom::L2(scale_metric));
 868                 }
 869                 snapped_point.setSecondSnapDistance(NR_HUGE);
 870                 break;
 871             }
 872             case STRETCH:
 873                 result = Geom::Point(NR_HUGE, NR_HUGE);
 874                 if (fabs(b[dim]) > 1e-6) { // if STRETCHING will occur for this point
 875                     result[dim] = a[dim] / b[dim];
 876                     result[1-dim] = uniform ? result[dim] : 1;
 877                 } else { // STRETCHING might occur for this point, but only when the stretching is uniform
 878                     if (uniform && fabs(b[1-dim]) > 1e-6) {
 879                        result[1-dim] = a[1-dim] / b[1-dim];
 880                        result[dim] = result[1-dim];
 881                     }
 882                 }
 883                 // Store the metric for this transformation as a virtual distance
 884                 snapped_point.setSnapDistance(std::abs(result[dim] - transformation[dim]));
 885                 snapped_point.setSecondSnapDistance(NR_HUGE);
 886                 break;
 887             case SKEW:
 888                 result[0] = (snapped_point.getPoint()[dim] - ((*i).getPoint())[dim]) / b[1 - dim]; // skew factor
 889                 result[1] = transformation[1]; // scale factor
 890                 // Store the metric for this transformation as a virtual distance
 891                 snapped_point.setSnapDistance(std::abs(result[0] - transformation[0]));
 892                 snapped_point.setSecondSnapDistance(NR_HUGE);
 893                 break;
 894             case ROTATE:
 895                 // a is vector to snapped point; b is vector to original point; now lets calculate angle between a and b
 896                 result[0] = atan2(Geom::dot(Geom::rot90(b), a), Geom::dot(b, a));
 897                 result[1] = result[1]; // how else should we store an angle in a point ;-)
 898                 // Store the metric for this transformation as a virtual distance (we're storing an angle)
 899                 snapped_point.setSnapDistance(std::abs(result[0] - transformation[0]));
 900                 snapped_point.setSecondSnapDistance(NR_HUGE);
 901                 break;
 902             default:
 903                 g_assert_not_reached();
 904         }
 905
 906         if (snapped_point.getSnapped()) {
 907             // We snapped; keep track of the best snap
 908             if (best_snapped_point.isOtherSnapBetter(snapped_point, true)) {
 909                 best_transformation = result;
 910                 best_snapped_point = snapped_point;
 911             }
 912         } else {
 913             // So we didn't snap for this point
 914             if (!best_snapped_point.getSnapped()) {
 915                 // ... and none of the points before snapped either
 916                 // We might still need to apply a constraint though, if we tried a constrained snap. And
 917                 // in case of a free snap we might have use for the transformed point, so let's return that
 918                 // point, whether it's constrained or not
 919                 if (best_snapped_point.isOtherSnapBetter(snapped_point, true)) {
 920                     // .. so we must keep track of the best non-snapped constrained point
 921                     best_transformation = result;
 922                     best_snapped_point = snapped_point;
 923                 }
 924             }
 925         }
 926
 927         j++;
 928     }
 929
 930     Geom::Coord best_metric;
 931     if (transformation_type == SCALE) {
 932         // When scaling, don't ever exit with one of scaling components set to NR_HUGE
 933         for (int index = 0; index < 2; index++) {
 934             if (best_transformation[index] == NR_HUGE) {
 935                 if (uniform && best_transformation[1-index] < NR_HUGE) {
 936                     best_transformation[index] = best_transformation[1-index];
 937                 } else {
 938                     best_transformation[index] = transformation[index];
 939                 }
 940             }
 941         }
 942     }
 943
 944     best_metric = best_snapped_point.getSnapDistance();
 945     best_snapped_point.setTransformation(best_transformation);
 946     // Using " < 1e6" instead of " < NR_HUGE" for catching some rounding errors
 947     // These rounding errors might be caused by NRRects, see bug #1584301
 948     best_snapped_point.setSnapDistance(best_metric < 1e6 ? best_metric : NR_HUGE);
 949
 950     if (_snapindicator) {
 951         if (best_snapped_point.getSnapped()) {
 952             _desktop->snapindicator->set_new_snaptarget(best_snapped_point);
 953         } else {
 954             _desktop->snapindicator->remove_snaptarget();
 955         }
 956     }
 957
 958     return best_snapped_point;
 959 }
 960
 961
 962 /**
 963  *  \brief Apply a translation to a set of points and try to snap freely in 2 degrees-of-freedom
 964  *
 965  *  \param p Collection of points to snap (snap sources), at their untransformed position, all points undergoing the same transformation. Paired with an identifier of the type of the snap source.
 966  *  \param pointer Location of the mouse pointer at the time dragging started (i.e. when the selection was still untransformed).
 967  *  \param tr Proposed translation; the final translation can only be calculated after snapping has occurred
 968  *  \return An instance of the SnappedPoint class, which holds data on the snap source, snap target, and various metrics.
 969  */
 970
 971 Inkscape::SnappedPoint SnapManager::freeSnapTranslate(std::vector<Inkscape::SnapCandidatePoint> const &p,
 972                                                         Geom::Point const &pointer,
 973                                                         Geom::Point const &tr)
 974 {
 975     Inkscape::SnappedPoint result = _snapTransformed(p, pointer, false, Geom::Point(0,0), TRANSLATE, tr, Geom::Point(0,0), Geom::X, false);
 976
 977     if (p.size() == 1) {
 978         _displaySnapsource(Inkscape::SnapCandidatePoint(result.getPoint(), p.at(0).getSourceType()));
 979     }
 980
 981     return result;
 982 }
 983
 984 /**
 985  *  \brief Apply a translation to a set of points and try to snap along a constraint
 986  *
 987  *  \param p Collection of points to snap (snap sources), at their untransformed position, all points undergoing the same transformation. Paired with an identifier of the type of the snap source.
 988  *  \param pointer Location of the mouse pointer at the time dragging started (i.e. when the selection was still untransformed).
 989  *  \param constraint The direction or line along which snapping must occur.
 990  *  \param tr Proposed translation; the final translation can only be calculated after snapping has occurred.
 991  *  \return An instance of the SnappedPoint class, which holds data on the snap source, snap target, and various metrics.
 992  */
 993
 994 Inkscape::SnappedPoint SnapManager::constrainedSnapTranslate(std::vector<Inkscape::SnapCandidatePoint> const &p,
 995                                                                Geom::Point const &pointer,
 996                                                                Inkscape::Snapper::SnapConstraint const &constraint,
 997                                                                Geom::Point const &tr)
 998 {
 999     Inkscape::SnappedPoint result = _snapTransformed(p, pointer, true, constraint, TRANSLATE, tr, Geom::Point(0,0), Geom::X, false);
1000
1001     if (p.size() == 1) {
1002         _displaySnapsource(Inkscape::SnapCandidatePoint(result.getPoint(), p.at(0).getSourceType()));
1003     }
1004
1005     return result;
1006 }
1007
1008
1009 /**
1010  *  \brief Apply a scaling to a set of points and try to snap freely in 2 degrees-of-freedom
1011  *
1012  *  \param p Collection of points to snap (snap sources), at their untransformed position, all points undergoing the same transformation. Paired with an identifier of the type of the snap source.
1013  *  \param pointer Location of the mouse pointer at the time dragging started (i.e. when the selection was still untransformed).
1014  *  \param s Proposed scaling; the final scaling can only be calculated after snapping has occurred
1015  *  \param o Origin of the scaling
1016  *  \return An instance of the SnappedPoint class, which holds data on the snap source, snap target, and various metrics.
1017  */
1018
1019 Inkscape::SnappedPoint SnapManager::freeSnapScale(std::vector<Inkscape::SnapCandidatePoint> const &p,
1020                                                   Geom::Point const &pointer,
1021                                                   Geom::Scale const &s,
1022                                                   Geom::Point const &o)
1023 {
1024     Inkscape::SnappedPoint result = _snapTransformed(p, pointer, false, Geom::Point(0,0), SCALE, Geom::Point(s[Geom::X], s[Geom::Y]), o, Geom::X, false);
1025
1026     if (p.size() == 1) {
1027         _displaySnapsource(Inkscape::SnapCandidatePoint(result.getPoint(), p.at(0).getSourceType()));
1028     }
1029
1030     return result;
1031 }
1032
1033
1034 /**
1035  *  \brief Apply a scaling to a set of points and snap such that the aspect ratio of the selection is preserved
1036  *
1037  *  \param p Collection of points to snap (snap sources), at their untransformed position, all points undergoing the same transformation. Paired with an identifier of the type of the snap source.
1038  *  \param pointer Location of the mouse pointer at the time dragging started (i.e. when the selection was still untransformed).
1039  *  \param s Proposed scaling; the final scaling can only be calculated after snapping has occurred
1040  *  \param o Origin of the scaling
1041  *  \return An instance of the SnappedPoint class, which holds data on the snap source, snap target, and various metrics.
1042  */
1043
1044 Inkscape::SnappedPoint SnapManager::constrainedSnapScale(std::vector<Inkscape::SnapCandidatePoint> const &p,
1045                                                          Geom::Point const &pointer,
1046                                                          Geom::Scale const &s,
1047                                                          Geom::Point const &o)
1048 {
1049     // When constrained scaling, only uniform scaling is supported.
1050     Inkscape::SnappedPoint result = _snapTransformed(p, pointer, true, Geom::Point(0,0), SCALE, Geom::Point(s[Geom::X], s[Geom::Y]), o, Geom::X, true);
1051
1052     if (p.size() == 1) {
1053         _displaySnapsource(Inkscape::SnapCandidatePoint(result.getPoint(), p.at(0).getSourceType()));
1054     }
1055
1056     return result;
1057 }
1058
1059 /**
1060  *  \brief Apply a stretch to a set of points and snap such that the direction of the stretch is preserved
1061  *
1062  *  \param p Collection of points to snap (snap sources), at their untransformed position, all points undergoing the same transformation. Paired with an identifier of the type of the snap source.
1063  *  \param pointer Location of the mouse pointer at the time dragging started (i.e. when the selection was still untransformed).
1064  *  \param s Proposed stretch; the final stretch can only be calculated after snapping has occurred
1065  *  \param o Origin of the stretching
1066  *  \param d Dimension in which to apply proposed stretch.
1067  *  \param u true if the stretch should be uniform (i.e. to be applied equally in both dimensions)
1068  *  \return An instance of the SnappedPoint class, which holds data on the snap source, snap target, and various metrics.
1069  */
1070
1071 Inkscape::SnappedPoint SnapManager::constrainedSnapStretch(std::vector<Inkscape::SnapCandidatePoint> const &p,
1072                                                             Geom::Point const &pointer,
1073                                                             Geom::Coord const &s,
1074                                                             Geom::Point const &o,
1075                                                             Geom::Dim2 d,
1076                                                             bool u)
1077 {
1078     Inkscape::SnappedPoint result = _snapTransformed(p, pointer, true, Geom::Point(0,0), STRETCH, Geom::Point(s, s), o, d, u);
1079
1080     if (p.size() == 1) {
1081         _displaySnapsource(Inkscape::SnapCandidatePoint(result.getPoint(), p.at(0).getSourceType()));
1082     }
1083
1084     return result;
1085 }
1086
1087 /**
1088  *  \brief Apply a skew to a set of points and snap such that the direction of the skew is preserved
1089  *
1090  *  \param p Collection of points to snap (snap sources), at their untransformed position, all points undergoing the same transformation. Paired with an identifier of the type of the snap source.
1091  *  \param pointer Location of the mouse pointer at the time dragging started (i.e. when the selection was still untransformed).
1092  *  \param constraint The direction or line along which snapping must occur.
1093  *  \param s Proposed skew; the final skew can only be calculated after snapping has occurred
1094  *  \param o Origin of the proposed skew
1095  *  \param d Dimension in which to apply proposed skew.
1096  *  \return An instance of the SnappedPoint class, which holds data on the snap source, snap target, and various metrics.
1097  */
1098
1099 Inkscape::SnappedPoint SnapManager::constrainedSnapSkew(std::vector<Inkscape::SnapCandidatePoint> const &p,
1100                                                  Geom::Point const &pointer,
1101                                                  Inkscape::Snapper::SnapConstraint const &constraint,
1102                                                  Geom::Point const &s,
1103                                                  Geom::Point const &o,
1104                                                  Geom::Dim2 d)
1105 {
1106     // "s" contains skew factor in s[0], and scale factor in s[1]
1107
1108     // Snapping the nodes of the bounding box of a selection that is being transformed, will only work if
1109     // the transformation of the bounding box is equal to the transformation of the individual nodes. This is
1110     // NOT the case for example when rotating or skewing. The bounding box itself cannot possibly rotate or skew,
1111     // so it's corners have a different transformation. The snappers cannot handle this, therefore snapping
1112     // of bounding boxes is not allowed here.
1113     if (p.size() > 0) {
1114         g_assert(!(p.at(0).getSourceType() & Inkscape::SNAPSOURCE_BBOX_CATEGORY));
1115     }
1116
1117     Inkscape::SnappedPoint result = _snapTransformed(p, pointer, true, constraint, SKEW, s, o, d, false);
1118
1119     if (p.size() == 1) {
1120         _displaySnapsource(Inkscape::SnapCandidatePoint(result.getPoint(), p.at(0).getSourceType()));
1121     }
1122
1123     return result;
1124 }
1125
1126 /**
1127  *  \brief Apply a rotation to a set of points and snap, without scaling
1128  *
1129  *  \param p Collection of points to snap (snap sources), at their untransformed position, all points undergoing the same transformation. Paired with an identifier of the type of the snap source.
1130  *  \param pointer Location of the mouse pointer at the time dragging started (i.e. when the selection was still untransformed).
1131  *  \param angle Proposed rotation (in radians); the final rotation can only be calculated after snapping has occurred
1132  *  \param o Origin of the rotation
1133  *  \return An instance of the SnappedPoint class, which holds data on the snap source, snap target, and various metrics.
1134  */
1135
1136 Inkscape::SnappedPoint SnapManager::constrainedSnapRotate(std::vector<Inkscape::SnapCandidatePoint> const &p,
1137                                                     Geom::Point const &pointer,
1138                                                     Geom::Coord const &angle,
1139                                                     Geom::Point const &o)
1140 {
1141     // Snapping the nodes of the bounding box of a selection that is being transformed, will only work if
1142     // the transformation of the bounding box is equal to the transformation of the individual nodes. This is
1143     // NOT the case for example when rotating or skewing. The bounding box itself cannot possibly rotate or skew,
1144     // so it's corners have a different transformation. The snappers cannot handle this, therefore snapping
1145     // of bounding boxes is not allowed here.
1146
1147     Inkscape::SnappedPoint result = _snapTransformed(p, pointer, true, Geom::Point(0,0), ROTATE, Geom::Point(angle, angle), o, Geom::X, false);
1148
1149     if (p.size() == 1) {
1150         _displaySnapsource(Inkscape::SnapCandidatePoint(result.getPoint(), p.at(0).getSourceType()));
1151     }
1152
1153     return result;
1154
1155 }
1156
1157 /**
1158  * \brief Given a set of possible snap targets, find the best target (which is not necessarily
1159  * also the nearest target), and show the snap indicator if requested
1160  *
1161  * \param p Source point to be snapped
1162  * \param sc A structure holding all snap targets that have been found so far
1163  * \param constrained True if the snap is constrained, e.g. for stretching or for purely horizontal translation.
1164  * \param noCurves If true, then do consider snapping to intersections of curves, but not to the curves themselves
1165  * \param allowOffScreen If true, then snapping to points which are off the screen is allowed (needed for example when pasting to the grid)
1166  * \return An instance of the SnappedPoint class, which holds data on the snap source, snap target, and various metrics
1167  */
1168
1169 Inkscape::SnappedPoint SnapManager::findBestSnap(Inkscape::SnapCandidatePoint const &p,
1170                                                  SnappedConstraints const &sc,
1171                                                  bool constrained,
1172                                                  bool noCurves,
1173                                                  bool allowOffScreen) const
1174 {
1175     g_assert(_desktop != NULL);
1176
1177     /*
1178     std::cout << "Type and number of snapped constraints: " << std::endl;
1179     std::cout << "  Points      : " << sc.points.size() << std::endl;
1180     std::cout << "  Lines       : " << sc.lines.size() << std::endl;
1181     std::cout << "  Grid lines  : " << sc.grid_lines.size()<< std::endl;
1182     std::cout << "  Guide lines : " << sc.guide_lines.size()<< std::endl;
1183     std::cout << "  Curves      : " << sc.curves.size()<< std::endl;
1184     */
1185
1186     // Store all snappoints
1187     std::list<Inkscape::SnappedPoint> sp_list;
1188
1189     // search for the closest snapped point
1190     Inkscape::SnappedPoint closestPoint;
1191     if (getClosestSP(sc.points, closestPoint)) {
1192         sp_list.push_back(closestPoint);
1193     }
1194
1195     // search for the closest snapped curve
1196     if (!noCurves) {
1197         Inkscape::SnappedCurve closestCurve;
1198         if (getClosestCurve(sc.curves, closestCurve)) {
1199             sp_list.push_back(Inkscape::SnappedPoint(closestCurve));
1200         }
1201     }
1202
1203     if (snapprefs.getSnapIntersectionCS()) {
1204         // search for the closest snapped intersection of curves
1205         Inkscape::SnappedPoint closestCurvesIntersection;
1206         if (getClosestIntersectionCS(sc.curves, p.getPoint(), closestCurvesIntersection, _desktop->dt2doc())) {
1207             closestCurvesIntersection.setSource(p.getSourceType());
1208             sp_list.push_back(closestCurvesIntersection);
1209         }
1210     }
1211
1212     // search for the closest snapped grid line
1213     Inkscape::SnappedLine closestGridLine;
1214     if (getClosestSL(sc.grid_lines, closestGridLine)) {
1215         sp_list.push_back(Inkscape::SnappedPoint(closestGridLine));
1216     }
1217
1218     // search for the closest snapped guide line
1219     Inkscape::SnappedLine closestGuideLine;
1220     if (getClosestSL(sc.guide_lines, closestGuideLine)) {
1221         sp_list.push_back(Inkscape::SnappedPoint(closestGuideLine));
1222     }
1223
1224     // When freely snapping to a grid/guide/path, only one degree of freedom is eliminated
1225     // Therefore we will try get fully constrained by finding an intersection with another grid/guide/path
1226
1227     // When doing a constrained snap however, we're already at an intersection of the constrained line and
1228     // the grid/guide/path we're snapping to. This snappoint is therefore fully constrained, so there's
1229     // no need to look for additional intersections
1230     if (!constrained) {
1231         // search for the closest snapped intersection of grid lines
1232         Inkscape::SnappedPoint closestGridPoint;
1233         if (getClosestIntersectionSL(sc.grid_lines, closestGridPoint)) {
1234             closestGridPoint.setSource(p.getSourceType());
1235             closestGridPoint.setTarget(Inkscape::SNAPTARGET_GRID_INTERSECTION);
1236             sp_list.push_back(closestGridPoint);
1237         }
1238
1239         // search for the closest snapped intersection of guide lines
1240         Inkscape::SnappedPoint closestGuidePoint;
1241         if (getClosestIntersectionSL(sc.guide_lines, closestGuidePoint)) {
1242             closestGuidePoint.setSource(p.getSourceType());
1243             closestGuidePoint.setTarget(Inkscape::SNAPTARGET_GUIDE_INTERSECTION);
1244             sp_list.push_back(closestGuidePoint);
1245         }
1246
1247         // search for the closest snapped intersection of grid with guide lines
1248         if (snapprefs.getSnapIntersectionGG()) {
1249             Inkscape::SnappedPoint closestGridGuidePoint;
1250             if (getClosestIntersectionSL(sc.grid_lines, sc.guide_lines, closestGridGuidePoint)) {
1251                 closestGridGuidePoint.setSource(p.getSourceType());
1252                 closestGridGuidePoint.setTarget(Inkscape::SNAPTARGET_GRID_GUIDE_INTERSECTION);
1253                 sp_list.push_back(closestGridGuidePoint);
1254             }
1255         }
1256     }
1257
1258     // now let's see which snapped point gets a thumbs up
1259     Inkscape::SnappedPoint bestSnappedPoint(p.getPoint());
1260     // std::cout << "Finding the best snap..." << std::endl;
1261     for (std::list<Inkscape::SnappedPoint>::const_iterator i = sp_list.begin(); i != sp_list.end(); i++) {
1262         // std::cout << "sp = " << (*i).getPoint() << " | source = " << (*i).getSource() << " | target = " << (*i).getTarget();
1263         bool onScreen = _desktop->get_display_area().contains((*i).getPoint());
1264         if (onScreen || allowOffScreen) { // Only snap to points which are not off the screen
1265             if ((*i).getSnapDistance() <= (*i).getTolerance()) { // Only snap to points within snapping range
1266                 // if it's the first point, or if it is closer than the best snapped point so far
1267                 if (i == sp_list.begin() || bestSnappedPoint.isOtherSnapBetter(*i, false)) {
1268                     // then prefer this point over the previous one
1269                     bestSnappedPoint = *i;
1270                 }
1271             }
1272         }
1273         // std::cout << std::endl;
1274     }
1275
1276     // Update the snap indicator, if requested
1277     if (_snapindicator) {
1278         if (bestSnappedPoint.getSnapped()) {
1279             _desktop->snapindicator->set_new_snaptarget(bestSnappedPoint);
1280         } else {
1281             _desktop->snapindicator->remove_snaptarget();
1282         }
1283     }
1284
1285     // std::cout << "findBestSnap = " << bestSnappedPoint.getPoint() << " | dist = " << bestSnappedPoint.getSnapDistance() << std::endl;
1286     return bestSnappedPoint;
1287 }
1288
1289 /// Convenience shortcut when there is only one item to ignore
1290 void SnapManager::setup(SPDesktop const *desktop,
1291                         bool snapindicator,
1292                         SPItem const *item_to_ignore,
1293                         std::vector<Inkscape::SnapCandidatePoint> *unselected_nodes,
1294                         SPGuide *guide_to_ignore)
1295 {
1296     g_assert(desktop != NULL);
1297     if (_desktop != NULL) {
1298         g_warning("The snapmanager has been set up before, but unSetup() hasn't been called afterwards. It possibly held invalid pointers");
1299     }
1300     _items_to_ignore.clear();
1301     _items_to_ignore.push_back(item_to_ignore);
1302     _desktop = desktop;
1303     _snapindicator = snapindicator;
1304     _unselected_nodes = unselected_nodes;
1305     _guide_to_ignore = guide_to_ignore;
1306     _rotation_center_source_items = NULL;
1307 }
1308
1309 /**
1310  * \brief Prepare the snap manager for the actual snapping, which includes building a list of snap targets
1311  * to ignore and toggling the snap indicator
1312  *
1313  * There are two overloaded setup() methods, of which the other one only allows for a single item to be ignored
1314  * whereas this one will take a list of items to ignore
1315  *
1316  * \param desktop Reference to the desktop to which this snap manager is attached
1317  * \param snapindicator If true then a snap indicator will be displayed automatically (when enabled in the preferences)
1318  * \param items_to_ignore These items will not be snapped to, e.g. the items that are currently being dragged. This avoids "self-snapping"
1319  * \param unselected_nodes Stationary nodes of the path that is currently being edited in the node tool and
1320  * that can be snapped too. Nodes not in this list will not be snapped to, to avoid "self-snapping". Of each
1321  * unselected node both the position (Geom::Point) and the type (Inkscape::SnapTargetType) will be stored
1322  * \param guide_to_ignore Guide that is currently being dragged and should not be snapped to
1323  */
1324
1325 void SnapManager::setup(SPDesktop const *desktop,
1326                         bool snapindicator,
1327                         std::vector<SPItem const *> &items_to_ignore,
1328                         std::vector<Inkscape::SnapCandidatePoint> *unselected_nodes,
1329                         SPGuide *guide_to_ignore)
1330 {
1331     g_assert(desktop != NULL);
1332     if (_desktop != NULL) {
1333         g_warning("The snapmanager has been set up before, but unSetup() hasn't been called afterwards. It possibly held invalid pointers");
1334     }
1335     _items_to_ignore = items_to_ignore;
1336     _desktop = desktop;
1337     _snapindicator = snapindicator;
1338     _unselected_nodes = unselected_nodes;
1339     _guide_to_ignore = guide_to_ignore;
1340     _rotation_center_source_items = NULL;
1341 }
1342
1343 /// Setup, taking the list of items to ignore from the desktop's selection.
1344 void SnapManager::setupIgnoreSelection(SPDesktop const *desktop,
1345                                       bool snapindicator,
1346                                       std::vector<Inkscape::SnapCandidatePoint> *unselected_nodes,
1347                                       SPGuide *guide_to_ignore)
1348 {
1349     g_assert(desktop != NULL);
1350     if (_desktop != NULL) {
1351         // Someone has been naughty here! This is dangerous
1352         g_warning("The snapmanager has been set up before, but unSetup() hasn't been called afterwards. It possibly held invalid pointers");
1353     }
1354     _desktop = desktop;
1355     _snapindicator = snapindicator;
1356     _unselected_nodes = unselected_nodes;
1357     _guide_to_ignore = guide_to_ignore;
1358     _rotation_center_source_items = NULL;
1359     _items_to_ignore.clear();
1360
1361     Inkscape::Selection *sel = _desktop->selection;
1362     GSList const *items = sel->itemList();
1363     for (GSList *i = const_cast<GSList*>(items); i; i = i->next) {
1364         _items_to_ignore.push_back(static_cast<SPItem const *>(i->data));
1365     }
1366 }
1367
1368 SPDocument *SnapManager::getDocument() const
1369 {
1370     return _named_view->document;
1371 }
1372
1373 /**
1374  * \brief Takes an untransformed point, applies the given transformation, and returns the transformed point. Eliminates lots of duplicated code
1375  *
1376  * \param p The untransformed position of the point, paired with an identifier of the type of the snap source.
1377  * \param transformation_type Type of transformation to apply.
1378  * \param transformation Mathematical description of the transformation; details depend on the type.
1379  * \param origin Origin of the transformation, if applicable.
1380  * \param dim Dimension to which the transformation applies, if applicable.
1381  * \param uniform true if the transformation should be uniform; only applicable for stretching and scaling.
1382  * \return The position of the point after transformation
1383  */
1384
1385 Geom::Point SnapManager::_transformPoint(Inkscape::SnapCandidatePoint const &p,
1386                                         Transformation const transformation_type,
1387                                         Geom::Point const &transformation,
1388                                         Geom::Point const &origin,
1389                                         Geom::Dim2 const dim,
1390                                         bool const uniform) const
1391 {
1392     /* Work out the transformed version of this point */
1393     Geom::Point transformed;
1394     switch (transformation_type) {
1395         case TRANSLATE:
1396             transformed = p.getPoint() + transformation;
1397             break;
1398         case SCALE:
1399             transformed = (p.getPoint() - origin) * Geom::Scale(transformation[Geom::X], transformation[Geom::Y]) + origin;
1400             break;
1401         case STRETCH:
1402         {
1403             Geom::Scale s(1, 1);
1404             if (uniform)
1405                 s[Geom::X] = s[Geom::Y] = transformation[dim];
1406             else {
1407                 s[dim] = transformation[dim];
1408                 s[1 - dim] = 1;
1409             }
1410             transformed = ((p.getPoint() - origin) * s) + origin;
1411             break;
1412         }
1413         case SKEW:
1414             // Apply the skew factor
1415             transformed[dim] = (p.getPoint())[dim] + transformation[0] * ((p.getPoint())[1 - dim] - origin[1 - dim]);
1416             // While skewing, mirroring and scaling (by integer multiples) in the opposite direction is also allowed.
1417             // Apply that scale factor here
1418             transformed[1-dim] = (p.getPoint() - origin)[1 - dim] * transformation[1] + origin[1 - dim];
1419             break;
1420         case ROTATE:
1421             // for rotations: transformation[0] stores the angle in radians
1422             transformed = (p.getPoint() - origin) * Geom::Rotate(transformation[0]) + origin;
1423             break;
1424         default:
1425             g_assert_not_reached();
1426     }
1427
1428     return transformed;
1429 }
1430
1431 /**
1432  * \brief Mark the location of the snap source (not the snap target!) on the canvas by drawing a symbol
1433  *
1434  * \param point_type Category of points to which the source point belongs: node, guide or bounding box
1435  * \param p The transformed position of the source point, paired with an identifier of the type of the snap source.
1436  */
1437
1438 void SnapManager::_displaySnapsource(Inkscape::SnapCandidatePoint const &p) const {
1439
1440     Inkscape::Preferences *prefs = Inkscape::Preferences::get();
1441     if (prefs->getBool("/options/snapclosestonly/value")) {
1442         bool p_is_a_node = p.getSourceType() & Inkscape::SNAPSOURCE_NODE_CATEGORY;
1443         bool p_is_a_bbox = p.getSourceType() & Inkscape::SNAPSOURCE_BBOX_CATEGORY;
1444         bool p_is_other = p.getSourceType() & Inkscape::SNAPSOURCE_OTHER_CATEGORY;
1445
1446         g_assert(_desktop != NULL);
1447         if (snapprefs.getSnapEnabledGlobally() && (p_is_other || (p_is_a_node && snapprefs.getSnapModeNode()) || (p_is_a_bbox && snapprefs.getSnapModeBBox()))) {
1448             _desktop->snapindicator->set_new_snapsource(p);
1449         } else {
1450             _desktop->snapindicator->remove_snapsource();
1451         }
1452     }
1453 }
1454
1455 void SnapManager::keepClosestPointOnly(std::vector<Inkscape::SnapCandidatePoint> &points, const Geom::Point &reference) const
1456 {
1457     if (points.size() < 2) return;
1458
1459     Inkscape::SnapCandidatePoint closest_point = Inkscape::SnapCandidatePoint(Geom::Point(NR_HUGE, NR_HUGE), Inkscape::SNAPSOURCE_UNDEFINED, Inkscape::SNAPTARGET_UNDEFINED);
1460     Geom::Coord closest_dist = NR_HUGE;
1461
1462     for(std::vector<Inkscape::SnapCandidatePoint>::const_iterator i = points.begin(); i != points.end(); i++) {
1463         Geom::Coord dist = Geom::L2((*i).getPoint() - reference);
1464         if (i == points.begin() || dist < closest_dist) {
1465             closest_point = *i;
1466             closest_dist = dist;
1467         }
1468     }
1469
1470     closest_point.setSourceNum(-1);
1471     points.clear();
1472     points.push_back(closest_point);
1473 }
1474
1475 /*
1476   Local Variables:
1477   mode:c++
1478   c-file-style:"stroustrup"
1479   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1480   indent-tabs-mode:nil
1481   fill-column:99
1482   End:
1483 */
1484 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :