ca7efde73ee8ed46b235d265494564bc2e9c39fe
1 #define __SP_DESKTOP_SNAP_C__
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 */
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>
24 SnapManager::SnapManager(SPNamedView const *v) : grid(v, 0), guide(v, 0), object(v, 0)
25 {
27 }
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 }
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 }
49 return (i != s.end());
50 }
53 /* FIXME: lots of cut-and-paste here. This needs some
54 ** functor voodoo to cut it all down a bit.
55 */
57 Inkscape::SnappedPoint SnapManager::freeSnap(Inkscape::Snapper::PointType t,
58 NR::Point const &p,
59 SPItem const *it) const
61 {
62 std::list<SPItem const *> lit;
63 lit.push_back(it);
64 return freeSnap(t, p, lit);
65 }
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);
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 }
82 return r;
83 }
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 }
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);
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 }
112 return r;
113 }
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 */
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 }
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;
142 for (std::vector<NR::Point>::const_iterator i = points.begin(); i != points.end(); i++) {
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 }
157 /* Snap it */
158 Inkscape::SnappedPoint const snapped = constrained ?
159 constrainedSnap(type, transformed, constraint, ignore) : freeSnap(type, transformed, ignore);
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 }
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 }
188 return std::make_pair(best_transformation, best_metric < NR_HUGE);
189 }
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 }
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 }
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 }
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 }
232 /// Minimal distance to norm before point is considered for snap.
233 static const double MIN_DIST_NORM = 1.0;
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 }
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 }
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 }
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 *
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));
282 SnapManager::SnapperList const snappers = nv->snap_manager.getSnappers();
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 }
293 return best;
294 }
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 */
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;
314 SnapManager const &m = nv->snap_manager;
316 if (m.willSnapSomething() == false) {
317 return std::make_pair(s[X], false);
318 }
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 }
339 return std::make_pair(ratio, dist < NR_HUGE);
340 }
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 }
359 g_assert(dim < 2);
361 NR::Coord dist = NR_HUGE;
362 double scale = sx;
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;
368 /* Scaled version of the point we are looking at */
369 check[dim] = (sx * (q - norm) + norm)[dim];
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]);
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 }
387 return std::make_pair(scale, dist < NR_HUGE);
388 }
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;
399 if (m.willSnapSomething() == false) {
400 return sx;
401 }
403 g_assert(dim < 2);
405 gdouble dist = NR_HUGE;
406 gdouble skew = sx;
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 }
422 return skew;
423 }
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 :