src/snap.cpp

   1 #define __SP_DESKTOP_SNAP_C__
   2
   3 /**
   4  * \file snap.cpp
   5  *
   6  * \brief Various snapping methods
   7  *
   8  * Authors:
   9  *   Lauris Kaplinski <lauris@kaplinski.com>
  10  *   Frank Felfe <innerspace@iname.com>
  11  *   Carl Hetherington <inkscape@carlh.net>
  12  *
  13  * Copyright (C) 1999-2002 Authors
  14  *
  15  * Released under GNU GPL, read the file 'COPYING' for more information
  16  */
  17
  18 #include "sp-namedview.h"
  19 #include "snap.h"
  20 #include <libnr/nr-point-fns.h>
  21 #include <libnr/nr-scale-ops.h>
  22 #include <libnr/nr-values.h>
  23
  24 SnapManager::SnapManager(SPNamedView const *v) : grid(v, 0), guide(v, 0), object(v, 0)
  25 {
  26
  27 }
  28
  29 SnapManager::SnapperList SnapManager::getSnappers() const
  30 {
  31     SnapManager::SnapperList s;
  32     s.push_back(&grid);
  33     s.push_back(&guide);
  34     s.push_back(&object);
  35     return s;
  36 }
  37
  38 /**
  39  * \return true if one of the snappers will try to snap something.
  40  */
  41 bool SnapManager::willSnapSomething() const
  42 {
  43     SnapperList const s = getSnappers();
  44     SnapperList::const_iterator i = s.begin();
  45     while (i != s.end() && (*i)->willSnapSomething() == false) {
  46         i++;
  47     }
  48
  49     return (i != s.end());
  50 }
  51
  52 Inkscape::SnappedPoint SnapManager::freeSnap(Inkscape::Snapper::PointType t,
  53                                              NR::Point const &p,
  54                                              SPItem const *it) const
  55
  56 {
  57     std::list<SPItem const *> lit;
  58     lit.push_back(it);
  59     return freeSnap(t, p, lit);
  60 }
  61
  62
  63 Inkscape::SnappedPoint SnapManager::freeSnap(Inkscape::Snapper::PointType t,
  64                                              NR::Point const &p,
  65                                              std::list<SPItem const *> const &it) const
  66 {
  67     Inkscape::SnappedPoint r(p, NR_HUGE);
  68
  69     SnapperList const snappers = getSnappers();
  70     for (SnapperList::const_iterator i = snappers.begin(); i != snappers.end(); i++) {
  71         Inkscape::SnappedPoint const s = (*i)->freeSnap(t, p, it);
  72         if (s.getDistance() < r.getDistance()) {
  73             r = s;
  74         }
  75     }
  76
  77     return r;
  78 }
  79
  80
  81 Inkscape::SnappedPoint SnapManager::constrainedSnap(Inkscape::Snapper::PointType t,
  82                                                     NR::Point const &p,
  83                                                     Inkscape::Snapper::ConstraintLine const &c,
  84                                                     SPItem const *it) const
  85 {
  86     std::list<SPItem const *> lit;
  87     lit.push_back(it);
  88     return constrainedSnap(t, p, c, lit);
  89 }
  90
  91
  92 Inkscape::SnappedPoint SnapManager::constrainedSnap(Inkscape::Snapper::PointType t,
  93                                                     NR::Point const &p,
  94                                                     Inkscape::Snapper::ConstraintLine const &c,
  95                                                     std::list<SPItem const *> const &it) const
  96 {
  97     Inkscape::SnappedPoint r(p, NR_HUGE);
  98
  99     SnapperList const snappers = getSnappers();
 100     for (SnapperList::const_iterator i = snappers.begin(); i != snappers.end(); i++) {
 101         Inkscape::SnappedPoint const s = (*i)->constrainedSnap(t, p, c, it);
 102         if (s.getDistance() < r.getDistance()) {
 103             r = s;
 104         }
 105     }
 106
 107     return r;
 108 }
 109
 110
 111 std::pair<NR::Point, bool> SnapManager::_snapTransformed(Inkscape::Snapper::PointType type,
 112                                                          std::vector<NR::Point> const &points,
 113                                                          std::list<SPItem const *> const &ignore,
 114                                                          bool constrained,
 115                                                          Inkscape::Snapper::ConstraintLine const &constraint,
 116                                                          Transformation transformation_type,
 117                                                          NR::Point const &transformation,
 118                                                          NR::Point const &origin) const
 119 {
 120     /* We have a list of points, which we are proposing to transform in some way.  We need to see
 121     ** if any of these points, when transformed, snap to anything.  If they do, we return the
 122     ** appropriate transformation with `true'; otherwise we return the original scale with `false'.
 123     */
 124
 125     /* Quick check to see if we have any snappers that are enabled */
 126     if (willSnapSomething() == false) {
 127         return std::make_pair(transformation, false);
 128     }
 129
 130     /* The current best transformation */
 131     NR::Point best_transformation = transformation;
 132     /* The current best metric for the best transformation; lower is better, NR_HUGE
 133     ** means that we haven't snapped anything.
 134     */
 135     NR::Coord best_metric = NR_HUGE;
 136
 137     for (std::vector<NR::Point>::const_iterator i = points.begin(); i != points.end(); i++) {
 138
 139         /* Work out the transformed version of this point */
 140         NR::Point transformed;
 141         switch (transformation_type) {
 142             case TRANSLATION:
 143                 transformed = *i + transformation;
 144                 break;
 145             case SCALE:
 146                 transformed = ((*i - origin) * NR::scale(transformation[NR::X], transformation[NR::Y])) + origin;
 147                 break;
 148             default:
 149                 g_assert_not_reached();
 150         }
 151
 152         /* Snap it */
 153         Inkscape::SnappedPoint const snapped = constrained ?
 154             constrainedSnap(type, transformed, constraint, ignore) : freeSnap(type, transformed, ignore);
 155
 156         if (snapped.getDistance() < NR_HUGE) {
 157             /* We snapped.  Find the transformation that describes where the snapped point has
 158             ** ended up, and also the metric for this transformation.
 159             */
 160             NR::Point result;
 161             NR::Coord metric;
 162             switch (transformation_type) {
 163                 case TRANSLATION:
 164                     result = snapped.getPoint() - *i;
 165                     metric = NR::L2(result);
 166                     break;
 167                 case SCALE:
 168                     NR::Point const a = (snapped.getPoint() - origin);
 169                     NR::Point const b = (*i - origin);
 170                     result = NR::Point(a[NR::X] / b[NR::X], a[NR::Y] / b[NR::Y]);
 171                     metric = std::abs(NR::L2(result) - NR::L2(transformation));
 172                     break;
 173             }
 174
 175             /* Note it if it's the best so far */
 176             if (metric < best_metric && metric != 0) {
 177                 best_transformation = result;
 178                 best_metric = metric;
 179             }
 180         }
 181     }
 182
 183     return std::make_pair(best_transformation, best_metric < NR_HUGE);
 184 }
 185
 186
 187 std::pair<NR::Point, bool> SnapManager::freeSnapTranslation(Inkscape::Snapper::PointType t,
 188                                                             std::vector<NR::Point> const &p,
 189                                                             std::list<SPItem const *> const &it,
 190                                                             NR::Point const &tr) const
 191 {
 192     return _snapTransformed(t, p, it, false, NR::Point(), TRANSLATION, tr, NR::Point(0, 0));
 193 }
 194
 195
 196
 197 std::pair<NR::Point, bool> SnapManager::constrainedSnapTranslation(Inkscape::Snapper::PointType t,
 198                                                                    std::vector<NR::Point> const &p,
 199                                                                    std::list<SPItem const *> const &it,
 200                                                                    Inkscape::Snapper::ConstraintLine const &c,
 201                                                                    NR::Point const &tr) const
 202 {
 203     return _snapTransformed(t, p, it, true, c, TRANSLATION, tr, NR::Point(0, 0));
 204 }
 205
 206 std::pair<NR::scale, bool> SnapManager::freeSnapScale(Inkscape::Snapper::PointType t,
 207                                                       std::vector<NR::Point> const &p,
 208                                                       std::list<SPItem const *> const &it,
 209                                                       NR::scale const &s,
 210                                                       NR::Point const &o) const
 211 {
 212     return _snapTransformed(t, p, it, false, NR::Point(0, 0), SCALE, NR::Point(s[NR::X], s[NR::Y]), o);
 213 }
 214
 215
 216 std::pair<NR::scale, bool> SnapManager::constrainedSnapScale(Inkscape::Snapper::PointType t,
 217                                                              std::vector<NR::Point> const &p,
 218                                                              std::list<SPItem const *> const &it,
 219                                                              Inkscape::Snapper::ConstraintLine const &c,
 220                                                              NR::scale const &s,
 221                                                              NR::Point const &o) const
 222 {
 223     return _snapTransformed(t, p, it, true, c, SCALE, NR::Point(s[NR::X], s[NR::Y]), o);
 224 }
 225
 226
 227 /// Minimal distance to norm before point is considered for snap.
 228 static const double MIN_DIST_NORM = 1.0;
 229
 230 /**
 231  * Try to snap \a req in one dimension.
 232  *
 233  * \param nv NamedView to use.
 234  * \param req Point to snap; updated to the snapped point if a snap occurred.
 235  * \param dim Dimension to snap in.
 236  * \return Distance to the snap point along the \a dim axis, or \c NR_HUGE
 237  *    if no snap occurred.
 238  */
 239 NR::Coord namedview_dim_snap(SPNamedView const *nv, Inkscape::Snapper::PointType t, NR::Point &req,
 240                              NR::Dim2 const dim, SPItem const *it)
 241 {
 242     return namedview_vector_snap(nv, t, req, component_vectors[dim], it);
 243 }
 244
 245 NR::Coord namedview_dim_snap(SPNamedView const *nv, Inkscape::Snapper::PointType t, NR::Point &req,
 246                              NR::Dim2 const dim, std::list<SPItem const *> const &it)
 247 {
 248     return namedview_vector_snap(nv, t, req, component_vectors[dim], it);
 249 }
 250
 251
 252 NR::Coord namedview_vector_snap(SPNamedView const *nv, Inkscape::Snapper::PointType t,
 253                                 NR::Point &req, NR::Point const &d,
 254                                 SPItem const *it)
 255 {
 256     std::list<SPItem const *> lit;
 257     lit.push_back(it);
 258     return namedview_vector_snap(nv, t, req, d, lit);
 259 }
 260
 261 /**
 262  * Look for snap point along the line described by the point \a req
 263  * and the direction vector \a d.
 264  * Modifies req to the snap point, if one is found.
 265  * \return The distance from \a req to the snap point along the vector \a d,
 266  * or \c NR_HUGE if no snap point was found.
 267  *
 268  * \pre d \81â\89\81  (0, 0).
 269  */
 270 NR::Coord namedview_vector_snap(SPNamedView const *nv, Inkscape::Snapper::PointType t,
 271                                 NR::Point &req, NR::Point const &d,
 272                                 std::list<SPItem const *> const &it)
 273 {
 274     g_assert(nv != NULL);
 275     g_assert(SP_IS_NAMEDVIEW(nv));
 276
 277     SnapManager::SnapperList const snappers = nv->snap_manager.getSnappers();
 278
 279     NR::Coord best = NR_HUGE;
 280     for (SnapManager::SnapperList::const_iterator i = snappers.begin(); i != snappers.end(); i++) {
 281         Inkscape::SnappedPoint const s = (*i)->constrainedSnap(t, req, d, it);
 282         if (s.getDistance() < best) {
 283             req = s.getPoint();
 284             best = s.getDistance();
 285         }
 286     }
 287
 288     return best;
 289 }
 290
 291
 292 /*
 293  * functions for lists of points
 294  *
 295  * All functions take a list of NR::Point and parameter indicating the proposed transformation.
 296  * They return the updated transformation parameter.
 297  */
 298
 299 /**
 300  * Snap list of points in two dimensions.
 301  */
 302 std::pair<double, bool> namedview_vector_snap_list(SPNamedView const *nv, Inkscape::Snapper::PointType t,
 303                                                    const std::vector<NR::Point> &p, NR::Point const &norm,
 304                                                    NR::scale const &s, std::list<SPItem const *> const &it)
 305 {
 306     using NR::X;
 307     using NR::Y;
 308
 309     SnapManager const &m = nv->snap_manager;
 310
 311     if (m.willSnapSomething() == false) {
 312         return std::make_pair(s[X], false);
 313     }
 314
 315     NR::Coord dist = NR_HUGE;
 316     double ratio = fabs(s[X]);
 317     for (std::vector<NR::Point>::const_iterator i = p.begin(); i != p.end(); i++) {
 318         NR::Point const &q = *i;
 319         NR::Point check = ( q - norm ) * s + norm;
 320         if (NR::LInfty( q - norm ) > MIN_DIST_NORM) {
 321             NR::Coord d = namedview_vector_snap(nv, t, check, check - norm, it);
 322             if (d < dist) {
 323                 dist = d;
 324                 NR::Dim2 const dominant = ( ( fabs( q[X] - norm[X] )  >
 325                                               fabs( q[Y] - norm[Y] ) )
 326                                             ? X
 327                                             : Y );
 328                 ratio = ( ( check[dominant] - norm[dominant] )
 329                           / ( q[dominant] - norm[dominant] ) );
 330             }
 331         }
 332     }
 333
 334     return std::make_pair(ratio, dist < NR_HUGE);
 335 }
 336
 337
 338 /**
 339  * Try to snap points in \a p after they have been scaled by \a sx with respect to
 340  * the origin \a norm.  The best snap is the one that changes the scale least.
 341  *
 342  * \return Pair containing snapped scale and a flag which is true if a snap was made.
 343  */
 344 std::pair<double, bool> namedview_dim_snap_list_scale(SPNamedView const *nv, Inkscape::Snapper::PointType t,
 345                                                       const std::vector<NR::Point> &p, NR::Point const &norm,
 346                                                       double const sx, NR::Dim2 dim,
 347                                                       std::list<const SPItem *> const &it)
 348 {
 349     SnapManager const &m = nv->snap_manager;
 350     if (m.willSnapSomething() == false) {
 351         return std::make_pair(sx, false);
 352     }
 353
 354     g_assert(dim < 2);
 355
 356     NR::Coord dist = NR_HUGE;
 357     double scale = sx;
 358
 359     for (std::vector<NR::Point>::const_iterator i = p.begin(); i != p.end(); i++) {
 360         NR::Point q = *i;
 361         NR::Point check = q;
 362
 363         /* Scaled version of the point we are looking at */
 364         check[dim] = (sx * (q - norm) + norm)[dim];
 365
 366         if (fabs (q[dim] - norm[dim]) > MIN_DIST_NORM) {
 367             /* Snap this point */
 368             const NR::Coord d = namedview_dim_snap (nv, t, check, dim, it);
 369             /* Work out the resulting scale factor */
 370             double snapped_scale = (check[dim] - norm[dim]) / (q[dim] - norm[dim]);
 371
 372             if (dist == NR_HUGE || fabs(snapped_scale - sx) < fabs(scale - sx)) {
 373                 /* This is either the first point, or the snapped scale
 374                 ** is the closest yet to the original.
 375                 */
 376                 scale = snapped_scale;
 377                 dist = d;
 378             }
 379         }
 380     }
 381
 382     return std::make_pair(scale, dist < NR_HUGE);
 383 }
 384
 385 /**
 386  * Try to snap points after they have been skewed.
 387  */
 388 double namedview_dim_snap_list_skew(SPNamedView const *nv, Inkscape::Snapper::PointType t,
 389                                     const std::vector<NR::Point> &p, NR::Point const &norm,
 390                                     double const sx, NR::Dim2 const dim)
 391 {
 392     SnapManager const &m = nv->snap_manager;
 393
 394     if (m.willSnapSomething() == false) {
 395         return sx;
 396     }
 397
 398     g_assert(dim < 2);
 399
 400     gdouble dist = NR_HUGE;
 401     gdouble skew = sx;
 402
 403     for (std::vector<NR::Point>::const_iterator i = p.begin(); i != p.end(); i++) {
 404         NR::Point q = *i;
 405         NR::Point check = q;
 406         // apply shear
 407         check[dim] += sx * (q[!dim] - norm[!dim]);
 408         if (fabs (q[!dim] - norm[!dim]) > MIN_DIST_NORM) {
 409             const gdouble d = namedview_dim_snap (nv, t, check, dim, NULL);
 410             if (d < fabs (dist)) {
 411                 dist = d;
 412                 skew = (check[dim] - q[dim]) / (q[!dim] - norm[!dim]);
 413             }
 414         }
 415     }
 416
 417     return skew;
 418 }
 419
 420
 421 /*
 422   Local Variables:
 423   mode:c++
 424   c-file-style:"stroustrup"
 425   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 426   indent-tabs-mode:nil
 427   fill-column:99
 428   End:
 429 */
 430 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :