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