summaryrefslogtreecommitdiffstats
path: root/src/object-snapper.cpp
blob: 61c440fbe9dfb78d414662770b6c9d194b08ad31 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
// SPDX-License-Identifier: GPL-2.0-or-later
/*
 *  Snapping things to objects.
 *
 * Authors:
 *   Carl Hetherington <inkscape@carlh.net>
 *   Diederik van Lierop <mail@diedenrezi.nl>
 *   Jon A. Cruz <jon@joncruz.org>
 *   Abhishek Sharma
 *
 * Copyright (C) 2005 - 2012 Authors
 *
 * Released under GNU GPL v2+, read the file 'COPYING' for more information.
 */

#include <2geom/circle.h>
#include <2geom/line.h>
#include <2geom/path-intersection.h>
#include <2geom/path-sink.h>

#include "desktop.h"
#include "document.h"
#include "inkscape.h"
#include "preferences.h"
#include "text-editing.h"

#include "splivarot.h"   // curve_for_item, pathvector_for_curves
#include "object/sp-clippath.h"
#include "object/sp-flowtext.h"
#include "object/sp-image.h"
#include "object/sp-item-group.h"
#include "object/sp-mask.h"
#include "object/sp-namedview.h"
#include "object/sp-path.h"
#include "object/sp-root.h"
#include "object/sp-shape.h"
#include "object/sp-text.h"
#include "object/sp-use.h"

#include "svg/svg.h"

Inkscape::ObjectSnapper::ObjectSnapper(SnapManager *sm, Geom::Coord const d)
    : Snapper(sm, d)
{
    _candidates = new std::vector<SnapCandidateItem>;
    _points_to_snap_to = new std::vector<SnapCandidatePoint>;
    _paths_to_snap_to = new std::vector<SnapCandidatePath >;
}

Inkscape::ObjectSnapper::~ObjectSnapper()
{
    _candidates->clear();
    delete _candidates;

    _points_to_snap_to->clear();
    delete _points_to_snap_to;

    _clear_paths();
    delete _paths_to_snap_to;
}

Geom::Coord Inkscape::ObjectSnapper::getSnapperTolerance() const
{
    SPDesktop const *dt = _snapmanager->getDesktop();
    double const zoom =  dt ? dt->current_zoom() : 1;
    return _snapmanager->snapprefs.getObjectTolerance() / zoom;
}

bool Inkscape::ObjectSnapper::getSnapperAlwaysSnap() const
{
    return _snapmanager->snapprefs.getObjectTolerance() == 10000; //TODO: Replace this threshold of 10000 by a constant; see also tolerance-slider.cpp
}

void Inkscape::ObjectSnapper::_findCandidates(SPObject* parent,
                                              std::vector<SPItem const *> const *it,
                                              bool const &first_point,
                                              Geom::Rect const &bbox_to_snap,
                                              bool const clip_or_mask,
                                              Geom::Affine const additional_affine) const // transformation of the item being clipped / masked
{
    SPDesktop const *dt = _snapmanager->getDesktop();
    if (dt == nullptr) {
        g_warning("desktop == NULL, so we cannot snap; please inform the developers of this bug");
        // Apparently the setup() method from the SnapManager class hasn't been called before trying to snap.
    }

    if (first_point) {
        _candidates->clear();
    }

    Geom::Rect bbox_to_snap_incl = bbox_to_snap; // _incl means: will include the snapper tolerance
    bbox_to_snap_incl.expandBy(getSnapperTolerance()); // see?

    for (auto& o: parent->children) {
        g_assert(dt != nullptr);
        SPItem *item = dynamic_cast<SPItem *>(&o);
        if (item && !(dt->itemIsHidden(item) && !clip_or_mask)) {
            // Snapping to items in a locked layer is allowed
            // Don't snap to hidden objects, unless they're a clipped path or a mask
            /* See if this item is on the ignore list */
            std::vector<SPItem const *>::const_iterator i;
            if (it != nullptr) {
                i = it->begin();
                while (i != it->end() && *i != &o) {
                    ++i;
                }
            }

            if (it == nullptr || i == it->end()) {
                if (item) {
                    if (!clip_or_mask) { // cannot clip or mask more than once
                        // The current item is not a clipping path or a mask, but might
                        // still be the subject of clipping or masking itself ; if so, then
                        // we should also consider that path or mask for snapping to
                        SPObject *obj = item->getClipObject();
                        if (obj && _snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_PATH_CLIP)) {
                            _findCandidates(obj, it, false, bbox_to_snap, true, item->i2doc_affine());
                        }
                        obj = item->getMaskObject();
                        if (obj && _snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_PATH_MASK)) {
                            _findCandidates(obj, it, false, bbox_to_snap, true, item->i2doc_affine());
                        }
                    }

                    if (dynamic_cast<SPGroup *>(item)) {
                        _findCandidates(&o, it, false, bbox_to_snap, clip_or_mask, additional_affine);
                    } else {
                        Geom::OptRect bbox_of_item;
                        Preferences *prefs = Preferences::get();
                        int prefs_bbox = prefs->getBool("/tools/bounding_box", false);
                        // We'll only need to obtain the visual bounding box if the user preferences tell
                        // us to, AND if we are snapping to the bounding box itself. If we're snapping to
                        // paths only, then we can just as well use the geometric bounding box (which is faster)
                        SPItem::BBoxType bbox_type = (!prefs_bbox && _snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_BBOX_CATEGORY)) ?
                            SPItem::VISUAL_BBOX : SPItem::GEOMETRIC_BBOX;
                        if (clip_or_mask) {
                            // Oh oh, this will get ugly. We cannot use sp_item_i2d_affine directly because we need to
                            // insert an additional transformation in document coordinates (code copied from sp_item_i2d_affine)
                            bbox_of_item = item->bounds(bbox_type, item->i2doc_affine() * additional_affine * dt->doc2dt());
                        } else {
                            bbox_of_item = item->desktopBounds(bbox_type);
                        }
                        if (bbox_of_item) {
                            // See if the item is within range
                            if (bbox_to_snap_incl.intersects(*bbox_of_item)
                                    || (_snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_ROTATION_CENTER) && bbox_to_snap_incl.contains(item->getCenter()))) { // rotation center might be outside of the bounding box
                                // This item is within snapping range, so record it as a candidate
                                _candidates->push_back(SnapCandidateItem(item, clip_or_mask, additional_affine));
                                // For debugging: print the id of the candidate to the console
                                // SPObject *obj = (SPObject*)item;
                                // std::cout << "Snap candidate added: " << obj->getId() << std::endl;
                                if (_candidates->size() > 200) { // This makes Inkscape crawl already
                                    std::cout << "Warning: limit of 200 snap target paths reached, some will be ignored" << std::endl;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}


void Inkscape::ObjectSnapper::_collectNodes(SnapSourceType const &t,
                                            bool const &first_point) const
{
    // Now, let's first collect all points to snap to. If we have a whole bunch of points to snap,
    // e.g. when translating an item using the selector tool, then we will only do this for the
    // first point and store the collection for later use. This significantly improves the performance
    if (first_point) {
        _points_to_snap_to->clear();

         // Determine the type of bounding box we should snap to
        SPItem::BBoxType bbox_type = SPItem::GEOMETRIC_BBOX;

        bool p_is_a_node = t & SNAPSOURCE_NODE_CATEGORY;
        bool p_is_a_bbox = t & SNAPSOURCE_BBOX_CATEGORY;
        bool p_is_other = (t & SNAPSOURCE_OTHERS_CATEGORY) || (t & SNAPSOURCE_DATUMS_CATEGORY);

        // A point considered for snapping should be either a node, a bbox corner or a guide/other. Pick only ONE!
        if (((p_is_a_node && p_is_a_bbox) || (p_is_a_bbox && p_is_other) || (p_is_a_node && p_is_other))) {
            g_warning("Snap warning: node type is ambiguous");
        }

        if (_snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_BBOX_CORNER, SNAPTARGET_BBOX_EDGE_MIDPOINT, SNAPTARGET_BBOX_MIDPOINT)) {
            Preferences *prefs = Preferences::get();
            bool prefs_bbox = prefs->getBool("/tools/bounding_box");
            bbox_type = !prefs_bbox ?
                SPItem::VISUAL_BBOX : SPItem::GEOMETRIC_BBOX;
        }

        // Consider the page border for snapping to
        if (_snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_PAGE_CORNER)) {
            _getBorderNodes(_points_to_snap_to);
        }

        for (const auto & _candidate : *_candidates) {
            //Geom::Affine i2doc(Geom::identity());
            SPItem *root_item = _candidate.item;

            SPUse *use = dynamic_cast<SPUse *>(_candidate.item);
            if (use) {
                root_item = use->root();
            }
            g_return_if_fail(root_item);

            //Collect all nodes so we can snap to them
            if (p_is_a_node || p_is_other || (p_is_a_bbox && !_snapmanager->snapprefs.getStrictSnapping())) {
                // Note: there are two ways in which intersections are considered:
                // Method 1: Intersections are calculated for each shape individually, for both the
                //           snap source and snap target (see sp_shape_snappoints)
                // Method 2: Intersections are calculated for each curve or line that we've snapped to, i.e. only for
                //           the target (see the intersect() method in the SnappedCurve and SnappedLine classes)
                // Some differences:
                // - Method 1 doesn't find intersections within a set of multiple objects
                // - Method 2 only works for targets
                // When considering intersections as snap targets:
                // - Method 1 only works when snapping to nodes, whereas
                // - Method 2 only works when snapping to paths
                // - There will be performance differences too!
                // If both methods are being used simultaneously, then this might lead to duplicate targets!

                // Well, here we will be looking for snap TARGETS. Both methods can therefore be used.
                // When snapping to paths, we will get a collection of snapped lines and snapped curves. findBestSnap() will
                // go hunting for intersections (but only when asked to in the prefs of course). In that case we can just
                // temporarily block the intersections in sp_item_snappoints, we don't need duplicates. If we're not snapping to
                // paths though but only to item nodes then we should still look for the intersections in sp_item_snappoints()
                bool old_pref = _snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_PATH_INTERSECTION);
                if (_snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_PATH)) {
                    // So if we snap to paths, then findBestSnap will find the intersections
                    // and therefore we temporarily disable SNAPTARGET_PATH_INTERSECTION, which will
                    // avoid root_item->getSnappoints() below from returning intersections
                    _snapmanager->snapprefs.setTargetSnappable(SNAPTARGET_PATH_INTERSECTION, false);
                }

                // We should not snap a transformation center to any of the centers of the items in the
                // current selection (see the comment in SelTrans::centerRequest())
                bool old_pref2 = _snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_ROTATION_CENTER);
                if (old_pref2) {
                	std::vector<SPItem*> rotationSource=_snapmanager->getRotationCenterSource();
                    for (auto itemlist : rotationSource) {
                        if (_candidate.item == itemlist) {
                            // don't snap to this item's rotation center
                            _snapmanager->snapprefs.setTargetSnappable(SNAPTARGET_ROTATION_CENTER, false);
                            break;
                        }
                    }
                }

                root_item->getSnappoints(*_points_to_snap_to, &_snapmanager->snapprefs);

                // restore the original snap preferences
                _snapmanager->snapprefs.setTargetSnappable(SNAPTARGET_PATH_INTERSECTION, old_pref);
                _snapmanager->snapprefs.setTargetSnappable(SNAPTARGET_ROTATION_CENTER, old_pref2);
            }

            //Collect the bounding box's corners so we can snap to them
            if (p_is_a_bbox || (!_snapmanager->snapprefs.getStrictSnapping() && p_is_a_node) || p_is_other) {
                // Discard the bbox of a clipped path / mask, because we don't want to snap to both the bbox
                // of the item AND the bbox of the clipping path at the same time
                if (!_candidate.clip_or_mask) {
                    Geom::OptRect b = root_item->desktopBounds(bbox_type);
                    getBBoxPoints(b, _points_to_snap_to, true,
                            _snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_BBOX_CORNER),
                            _snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_BBOX_EDGE_MIDPOINT),
                            _snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_BBOX_MIDPOINT));
                }
            }
        }
    }
}

void Inkscape::ObjectSnapper::_snapNodes(IntermSnapResults &isr,
                                         SnapCandidatePoint const &p,
                                         std::vector<SnapCandidatePoint> *unselected_nodes,
                                         SnapConstraint const &c,
                                         Geom::Point const &p_proj_on_constraint) const
{
    // Iterate through all nodes, find out which one is the closest to p, and snap to it!

    _collectNodes(p.getSourceType(), p.getSourceNum() <= 0);

    if (unselected_nodes != nullptr && unselected_nodes->size() > 0) {
        g_assert(_points_to_snap_to != nullptr);
        _points_to_snap_to->insert(_points_to_snap_to->end(), unselected_nodes->begin(), unselected_nodes->end());
    }

    SnappedPoint s;
    bool success = false;
    bool strict_snapping = _snapmanager->snapprefs.getStrictSnapping();

    for (const auto & k : *_points_to_snap_to) {
        if (_allowSourceToSnapToTarget(p.getSourceType(), k.getTargetType(), strict_snapping)) {
            Geom::Point target_pt = k.getPoint();
            Geom::Coord dist = Geom::L2(target_pt - p.getPoint()); // Default: free (unconstrained) snapping
            if (!c.isUndefined()) {
                // We're snapping to nodes along a constraint only, so find out if this node
                // is at the constraint, while allowing for a small margin
                if (Geom::L2(target_pt - c.projection(target_pt)) > 1e-9) {
                    // The distance from the target point to its projection on the constraint
                    // is too large, so this point is not on the constraint. Skip it!
                    continue;
                }
                dist = Geom::L2(target_pt - p_proj_on_constraint);
            }

            if (dist < getSnapperTolerance() && dist < s.getSnapDistance()) {
                s = SnappedPoint(target_pt, p.getSourceType(), p.getSourceNum(), k.getTargetType(), dist, getSnapperTolerance(), getSnapperAlwaysSnap(), false, true, k.getTargetBBox());
                success = true;
            }
        }
    }

    if (success) {
        isr.points.push_back(s);
    }
}

void Inkscape::ObjectSnapper::_snapTranslatingGuide(IntermSnapResults &isr,
                                         Geom::Point const &p,
                                         Geom::Point const &guide_normal) const
{
    // Iterate through all nodes, find out which one is the closest to this guide, and snap to it!
    _collectNodes(SNAPSOURCE_GUIDE, true);

    if (_snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_PATH, SNAPTARGET_PATH_INTERSECTION, SNAPTARGET_BBOX_EDGE, SNAPTARGET_PAGE_BORDER, SNAPTARGET_TEXT_BASELINE)) {
        _collectPaths(p, SNAPSOURCE_GUIDE, true);
        _snapPaths(isr, SnapCandidatePoint(p, SNAPSOURCE_GUIDE), nullptr, nullptr);
    }

    SnappedPoint s;

    Geom::Coord tol = getSnapperTolerance();

    for (const auto & k : *_points_to_snap_to) {
        Geom::Point target_pt = k.getPoint();
        // Project each node (*k) on the guide line (running through point p)
        Geom::Point p_proj = Geom::projection(target_pt, Geom::Line(p, p + Geom::rot90(guide_normal)));
        Geom::Coord dist = Geom::L2(target_pt - p_proj); // distance from node to the guide
        Geom::Coord dist2 = Geom::L2(p - p_proj); // distance from projection of node on the guide, to the mouse location
        if ((dist < tol && dist2 < tol) || getSnapperAlwaysSnap()) {
            s = SnappedPoint(target_pt, SNAPSOURCE_GUIDE, 0, k.getTargetType(), dist, tol, getSnapperAlwaysSnap(), false, true, k.getTargetBBox());
            isr.points.push_back(s);
        }
    }
}


/// @todo investigate why Geom::Point p is passed in but ignored.
void Inkscape::ObjectSnapper::_collectPaths(Geom::Point /*p*/,
                                         SnapSourceType const source_type,
                                         bool const &first_point) const
{
    // Now, let's first collect all paths to snap to. If we have a whole bunch of points to snap,
    // e.g. when translating an item using the selector tool, then we will only do this for the
    // first point and store the collection for later use. This significantly improves the performance
    if (first_point) {
        _clear_paths();

        // Determine the type of bounding box we should snap to
        SPItem::BBoxType bbox_type = SPItem::GEOMETRIC_BBOX;

        bool p_is_a_node = source_type & SNAPSOURCE_NODE_CATEGORY;
        bool p_is_a_bbox = source_type & SNAPSOURCE_BBOX_CATEGORY;
        bool p_is_other = (source_type & SNAPSOURCE_OTHERS_CATEGORY) || (source_type & SNAPSOURCE_DATUMS_CATEGORY);

        if (_snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_BBOX_EDGE)) {
            Preferences *prefs = Preferences::get();
            int prefs_bbox = prefs->getBool("/tools/bounding_box", false);
            bbox_type = !prefs_bbox ?
                SPItem::VISUAL_BBOX : SPItem::GEOMETRIC_BBOX;
        }

        // Consider the page border for snapping
        if (_snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_PAGE_BORDER) && _snapmanager->snapprefs.isAnyCategorySnappable()) {
            Geom::PathVector *border_path = _getBorderPathv();
            if (border_path != nullptr) {
                _paths_to_snap_to->push_back(SnapCandidatePath(border_path, SNAPTARGET_PAGE_BORDER, Geom::OptRect()));
            }
        }

        for (const auto & _candidate : *_candidates) {

            /* Transform the requested snap point to this item's coordinates */
            Geom::Affine i2doc(Geom::identity());
            SPItem *root_item = nullptr;
            /* We might have a clone at hand, so make sure we get the root item */
            SPUse *use = dynamic_cast<SPUse *>(_candidate.item);
            if (use) {
                i2doc = use->get_root_transform();
                root_item = use->root();
                g_return_if_fail(root_item);
            } else {
                i2doc = _candidate.item->i2doc_affine();
                root_item = _candidate.item;
            }

            //Build a list of all paths considered for snapping to

            //Add the item's path to snap to
            if (_snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_PATH, SNAPTARGET_PATH_INTERSECTION, SNAPTARGET_TEXT_BASELINE)) {
                if (p_is_other || p_is_a_node || (!_snapmanager->snapprefs.getStrictSnapping() && p_is_a_bbox)) {
                    if (dynamic_cast<SPText *>(root_item) || dynamic_cast<SPFlowtext *>(root_item)) {
                        if (_snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_TEXT_BASELINE)) {
                            // Snap to the text baseline
                            Text::Layout const *layout = te_get_layout(static_cast<SPItem *>(root_item));
                            if (layout != nullptr && layout->outputExists()) {
                                Geom::PathVector *pv = new Geom::PathVector();
                                pv->push_back(layout->baseline() * root_item->i2dt_affine() * _candidate.additional_affine * _snapmanager->getDesktop()->doc2dt());
                                _paths_to_snap_to->push_back(SnapCandidatePath(pv, SNAPTARGET_TEXT_BASELINE, Geom::OptRect()));
                            }
                        }
                    } else {
                        // Snapping for example to a traced bitmap is very stressing for
                        // the CPU, so we'll only snap to paths having no more than 500 nodes
                        // This also leads to a lag of approx. 500 msec (in my lousy test set-up).
                        bool very_complex_path = false;
                        SPPath *path = dynamic_cast<SPPath *>(root_item);
                        if (path) {
                            very_complex_path = path->nodesInPath() > 500;
                        }

                        if (!very_complex_path && root_item && _snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_PATH, SNAPTARGET_PATH_INTERSECTION)) {
                            SPCurve *curve = nullptr;
                            SPShape *shape = dynamic_cast<SPShape *>(root_item);
                            if (shape) {
                               curve = shape->getCurve();
                            }/* else if (dynamic_cast<SPText *>(root_item) || dynamic_cast<SPFlowtext *>(root_item)) {
                               curve = te_get_layout(root_item)->convertToCurves();
                            }*/
                            if (curve) {
                                // We will get our own copy of the pathvector, which must be freed at some point

                                // Geom::PathVector *pv = pathvector_for_curve(root_item, curve, true, true, Geom::identity(), (*i).additional_affine);

                                Geom::PathVector *pv = new Geom::PathVector(curve->get_pathvector());
                                (*pv) *= root_item->i2dt_affine() * _candidate.additional_affine * _snapmanager->getDesktop()->doc2dt(); // (_edit_transform * _i2d_transform);

                                _paths_to_snap_to->push_back(SnapCandidatePath(pv, SNAPTARGET_PATH, Geom::OptRect())); // Perhaps for speed, get a reference to the Geom::pathvector, and store the transformation besides it.
                                curve->unref();
                            }
                        }
                    }
                }
            }

            //Add the item's bounding box to snap to
            if (_snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_BBOX_EDGE)) {
                if (p_is_other || p_is_a_bbox || (!_snapmanager->snapprefs.getStrictSnapping() && p_is_a_node)) {
                    // Discard the bbox of a clipped path / mask, because we don't want to snap to both the bbox
                    // of the item AND the bbox of the clipping path at the same time
                    if (!_candidate.clip_or_mask) {
                        Geom::OptRect rect = root_item->bounds(bbox_type, i2doc);
                        if (rect) {
                            Geom::PathVector *path = _getPathvFromRect(*rect);
                            rect = root_item->desktopBounds(bbox_type);
                            _paths_to_snap_to->push_back(SnapCandidatePath(path, SNAPTARGET_BBOX_EDGE, rect));
                        }
                    }
                }
            }
        }
    }
}

void Inkscape::ObjectSnapper::_snapPaths(IntermSnapResults &isr,
                                     SnapCandidatePoint const &p,
                                     std::vector<SnapCandidatePoint> *unselected_nodes,
                                     SPPath const *selected_path) const
{
    _collectPaths(p.getPoint(), p.getSourceType(), p.getSourceNum() <= 0);
    // Now we can finally do the real snapping, using the paths collected above

    SPDesktop const *dt = _snapmanager->getDesktop();
    g_assert(dt != nullptr);
    Geom::Point const p_doc = dt->dt2doc(p.getPoint());

    bool const node_tool_active = _snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_PATH, SNAPTARGET_PATH_INTERSECTION) && selected_path != nullptr;

    if (p.getSourceNum() <= 0) {
        /* findCandidates() is used for snapping to both paths and nodes. It ignores the path that is
         * currently being edited, because that path requires special care: when snapping to nodes
         * only the unselected nodes of that path should be considered, and these will be passed on separately.
         * This path must not be ignored however when snapping to the paths, so we add it here
         * manually when applicable.
         * */
        if (node_tool_active) {
            // TODO fix the function to be const correct:
            SPCurve *curve = curve_for_item(const_cast<SPPath*>(selected_path));
            if (curve) {
                Geom::PathVector *pathv = pathvector_for_curve(const_cast<SPPath*>(selected_path),
                                                               curve,
                                                               true,
                                                               true,
                                                               Geom::identity(),
                                                               Geom::identity()); // We will get our own copy of the path, which must be freed at some point
                _paths_to_snap_to->push_back(SnapCandidatePath(pathv, SNAPTARGET_PATH, Geom::OptRect(), true));
                curve->unref();
            }
        }
    }

    int num_path = 0; // _paths_to_snap_to contains multiple path_vectors, each containing multiple paths.
                      // num_path will count the paths, and will not be zeroed for each path_vector. It will
                      // continue counting

    bool strict_snapping = _snapmanager->snapprefs.getStrictSnapping();
    bool snap_perp = _snapmanager->snapprefs.getSnapPerp();
    bool snap_tang = _snapmanager->snapprefs.getSnapTang();

    //dt->snapindicator->remove_debugging_points();
    for (const auto & it_p : *_paths_to_snap_to) {
        if (_allowSourceToSnapToTarget(p.getSourceType(), it_p.target_type, strict_snapping)) {
            bool const being_edited = node_tool_active && it_p.currently_being_edited;
            //if true then this pathvector it_pv is currently being edited in the node tool

            for(Geom::PathVector::iterator it_pv = (it_p.path_vector)->begin(); it_pv != (it_p.path_vector)->end(); ++it_pv) {
                // Find a nearest point for each curve within this path
                // n curves will return n time values with 0 <= t <= 1
                std::vector<double> anp = (*it_pv).nearestTimePerCurve(p_doc);

                //std::cout << "#nearest points = " << anp.size() << " | p = " << p.getPoint() << std::endl;
                // Now we will examine each of the nearest points, and determine whether it's within snapping range and if we should snap to it
                std::vector<double>::const_iterator np = anp.begin();
                unsigned int index = 0;
                for (; np != anp.end(); ++np, index++) {
                    Geom::Curve const *curve = &(it_pv->at(index));
                    Geom::Point const sp_doc = curve->pointAt(*np);
                    //dt->snapindicator->set_new_debugging_point(sp_doc*dt->doc2dt());
                    bool c1 = true;
                    bool c2 = true;
                    if (being_edited) {
                        /* If the path is being edited, then we should only snap though to stationary pieces of the path
                         * and not to the pieces that are being dragged around. This way we avoid
                         * self-snapping. For this we check whether the nodes at both ends of the current
                         * piece are unselected; if they are then this piece must be stationary
                         */
                        g_assert(unselected_nodes != nullptr);
                        Geom::Point start_pt = dt->doc2dt(curve->pointAt(0));
                        Geom::Point end_pt = dt->doc2dt(curve->pointAt(1));
                        c1 = isUnselectedNode(start_pt, unselected_nodes);
                        c2 = isUnselectedNode(end_pt, unselected_nodes);
                        /* Unfortunately, this might yield false positives for coincident nodes. Inkscape might therefore mistakenly
                         * snap to path segments that are not stationary. There are at least two possible ways to overcome this:
                         * - Linking the individual nodes of the SPPath we have here, to the nodes of the NodePath::SubPath class as being
                         *   used in sp_nodepath_selected_nodes_move. This class has a member variable called "selected". For this the nodes
                         *   should be in the exact same order for both classes, so we can index them
                         * - Replacing the SPPath being used here by the NodePath::SubPath class; but how?
                         */
                    }

                    Geom::Point const sp_dt = dt->doc2dt(sp_doc);
                    if (!being_edited || (c1 && c2)) {
                        Geom::Coord dist = Geom::distance(sp_doc, p_doc);
                        // std::cout << "  dist -> " << dist << std::endl;
                        if (dist < getSnapperTolerance()) {
                            // Add the curve we have snapped to
                            Geom::Point sp_tangent_dt = Geom::Point(0,0);
                            if (p.getSourceType() == Inkscape::SNAPSOURCE_GUIDE_ORIGIN) {
                                // We currently only use the tangent when snapping guides, so only in this case we will
                                // actually calculate the tangent to avoid wasting CPU cycles
                                Geom::Point sp_tangent_doc = curve->unitTangentAt(*np);
                                sp_tangent_dt = dt->doc2dt(sp_tangent_doc) - dt->doc2dt(Geom::Point(0,0));
                            }
                            isr.curves.emplace_back(sp_dt, sp_tangent_dt, num_path, index, dist, getSnapperTolerance(), getSnapperAlwaysSnap(), false, curve, p.getSourceType(), p.getSourceNum(), it_p.target_type, it_p.target_bbox);
                            if (snap_tang || snap_perp) {
                                // For each curve that's within snapping range, we will now also search for tangential and perpendicular snaps
                                _snapPathsTangPerp(snap_tang, snap_perp, isr, p, curve, dt);
                            }
                        }
                    }
                }
                num_path++;
            } // End of: for (Geom::PathVector::iterator ....)
        }
    }
}

/* Returns true if point is coincident with one of the unselected nodes */
bool Inkscape::ObjectSnapper::isUnselectedNode(Geom::Point const &point, std::vector<SnapCandidatePoint> const *unselected_nodes) const
{
    if (unselected_nodes == nullptr) {
        return false;
    }

    if (unselected_nodes->size() == 0) {
        return false;
    }

    for (const auto & unselected_node : *unselected_nodes) {
        if (Geom::L2(point - unselected_node.getPoint()) < 1e-4) {
            return true;
        }
    }

    return false;
}

void Inkscape::ObjectSnapper::_snapPathsConstrained(IntermSnapResults &isr,
                                     SnapCandidatePoint const &p,
                                     SnapConstraint const &c,
                                     Geom::Point const &p_proj_on_constraint) const
{

    _collectPaths(p_proj_on_constraint, p.getSourceType(), p.getSourceNum() <= 0);

    // Now we can finally do the real snapping, using the paths collected above

    SPDesktop const *dt = _snapmanager->getDesktop();
    g_assert(dt != nullptr);

    Geom::Point direction_vector = c.getDirection();
    if (!is_zero(direction_vector)) {
        direction_vector = Geom::unit_vector(direction_vector);
    }

    // The intersection point of the constraint line with any path, must lie within two points on the
    // SnapConstraint: p_min_on_cl and p_max_on_cl. The distance between those points is twice the snapping tolerance
    Geom::Point const p_min_on_cl = dt->dt2doc(p_proj_on_constraint - getSnapperTolerance() * direction_vector);
    Geom::Point const p_max_on_cl = dt->dt2doc(p_proj_on_constraint + getSnapperTolerance() * direction_vector);
    Geom::Coord tolerance = getSnapperTolerance();

    // PS: Because the paths we're about to snap to are all expressed relative to document coordinate system, we will have
    // to convert the snapper coordinates from the desktop coordinates to document coordinates

    Geom::PathVector constraint_path;
    if (c.isCircular()) {
        Geom::Circle constraint_circle(dt->dt2doc(c.getPoint()), c.getRadius());
        Geom::PathBuilder pb;
        pb.feed(constraint_circle);
        pb.flush();
        constraint_path = pb.peek();
    } else {
        Geom::Path constraint_line;
        constraint_line.start(p_min_on_cl);
        constraint_line.appendNew<Geom::LineSegment>(p_max_on_cl);
        constraint_path.push_back(constraint_line);
    }

    bool strict_snapping = _snapmanager->snapprefs.getStrictSnapping();

    // Find all intersections of the constrained path with the snap target candidates
    for (const auto & k : *_paths_to_snap_to) {
        if (k.path_vector && _allowSourceToSnapToTarget(p.getSourceType(), k.target_type, strict_snapping)) {
            // Do the intersection math
            std::vector<Geom::PVIntersection> inters = constraint_path.intersect(*(k.path_vector));

            // Convert the collected intersections to snapped points
            for (const auto & inter : inters) {
                // Convert to desktop coordinates
                Geom::Point p_inters = dt->doc2dt(inter.point());
                // Construct a snapped point
                Geom::Coord dist = Geom::L2(p.getPoint() - p_inters);
                SnappedPoint s = SnappedPoint(p_inters, p.getSourceType(), p.getSourceNum(), k.target_type, dist, getSnapperTolerance(), getSnapperAlwaysSnap(), true, false, k.target_bbox);
                // Store the snapped point
                if (dist <= tolerance) { // If the intersection is within snapping range, then we might snap to it
                    isr.points.push_back(s);
                }
            }
        }
    }
}


void Inkscape::ObjectSnapper::freeSnap(IntermSnapResults &isr,
                                            SnapCandidatePoint const &p,
                                            Geom::OptRect const &bbox_to_snap,
                                            std::vector<SPItem const *> const *it,
                                            std::vector<SnapCandidatePoint> *unselected_nodes) const
{
    if (_snap_enabled == false || _snapmanager->snapprefs.isSourceSnappable(p.getSourceType()) == false || ThisSnapperMightSnap() == false) {
        return;
    }

    /* Get a list of all the SPItems that we will try to snap to */
    if (p.getSourceNum() <= 0) {
        Geom::Rect const local_bbox_to_snap = bbox_to_snap ? *bbox_to_snap : Geom::Rect(p.getPoint(), p.getPoint());
        _findCandidates(_snapmanager->getDocument()->getRoot(), it, p.getSourceNum() <= 0, local_bbox_to_snap, false, Geom::identity());
    }

    _snapNodes(isr, p, unselected_nodes);

    if (_snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_PATH, SNAPTARGET_PATH_INTERSECTION, SNAPTARGET_BBOX_EDGE, SNAPTARGET_PAGE_BORDER, SNAPTARGET_TEXT_BASELINE)) {
        unsigned n = (unselected_nodes == nullptr) ? 0 : unselected_nodes->size();
        if (n > 0) {
            /* While editing a path in the node tool, findCandidates must ignore that path because
             * of the node snapping requirements (i.e. only unselected nodes must be snapable).
             * That path must not be ignored however when snapping to the paths, so we add it here
             * manually when applicable
             */
            SPPath const *path = nullptr;
            if (it != nullptr) {
                SPPath const *tmpPath = dynamic_cast<SPPath const *>(*it->begin());
                if ((it->size() == 1) && tmpPath) {
                    path = tmpPath;
                } // else: *it->begin() might be a SPGroup, e.g. when editing a LPE of text that has been converted to a group of paths
                // as reported in bug #356743. In that case we can just ignore it, i.e. not snap to this item
            }
            _snapPaths(isr, p, unselected_nodes, path);
        } else {
            _snapPaths(isr, p, nullptr, nullptr);
        }
    }
}

void Inkscape::ObjectSnapper::constrainedSnap( IntermSnapResults &isr,
                                                  SnapCandidatePoint const &p,
                                                  Geom::OptRect const &bbox_to_snap,
                                                  SnapConstraint const &c,
                                                  std::vector<SPItem const *> const *it,
                                                  std::vector<SnapCandidatePoint> *unselected_nodes) const
{
    if (_snap_enabled == false || _snapmanager->snapprefs.isSourceSnappable(p.getSourceType()) == false || ThisSnapperMightSnap() == false) {
        return;
    }

    // project the mouse pointer onto the constraint. Only the projected point will be considered for snapping
    Geom::Point pp = c.projection(p.getPoint());

    /* Get a list of all the SPItems that we will try to snap to */
    if (p.getSourceNum() <= 0) {
        Geom::Rect const local_bbox_to_snap = bbox_to_snap ? *bbox_to_snap : Geom::Rect(pp, pp);
        _findCandidates(_snapmanager->getDocument()->getRoot(), it, p.getSourceNum() <= 0, local_bbox_to_snap, false, Geom::identity());
    }

    // A constrained snap, is a snap in only one degree of freedom (specified by the constraint line).
    // This is useful for example when scaling an object while maintaining a fixed aspect ratio. It's
    // nodes are only allowed to move in one direction (i.e. in one degree of freedom).

    _snapNodes(isr, p, unselected_nodes, c, pp);

    if (_snapmanager->snapprefs.isTargetSnappable(SNAPTARGET_PATH, SNAPTARGET_PATH_INTERSECTION, SNAPTARGET_BBOX_EDGE, SNAPTARGET_PAGE_BORDER, SNAPTARGET_TEXT_BASELINE)) {
        _snapPathsConstrained(isr, p, c, pp);
    }
}

bool Inkscape::ObjectSnapper::ThisSnapperMightSnap() const
{
    return true;
}

void Inkscape::ObjectSnapper::_clear_paths() const
{
    for (const auto & k : *_paths_to_snap_to) {
        delete k.path_vector;
    }
    _paths_to_snap_to->clear();
}

Geom::PathVector* Inkscape::ObjectSnapper::_getBorderPathv() const
{
    Geom::Rect const border_rect = Geom::Rect(Geom::Point(0,0), Geom::Point((_snapmanager->getDocument())->getWidth().value("px"),(_snapmanager->getDocument())->getHeight().value("px")));
    return _getPathvFromRect(border_rect);
}

Geom::PathVector* Inkscape::ObjectSnapper::_getPathvFromRect(Geom::Rect const rect) const
{
    SPCurve const *border_curve = SPCurve::new_from_rect(rect, true);
    if (border_curve) {
        Geom::PathVector *dummy = new Geom::PathVector(border_curve->get_pathvector());
        return dummy;
    } else {
        return nullptr;
    }
}

void Inkscape::ObjectSnapper::_getBorderNodes(std::vector<SnapCandidatePoint> *points) const
{
    Geom::Coord w = (_snapmanager->getDocument())->getWidth().value("px");
    Geom::Coord h = (_snapmanager->getDocument())->getHeight().value("px");
    points->push_back(SnapCandidatePoint(Geom::Point(0,0), SNAPSOURCE_UNDEFINED, SNAPTARGET_PAGE_CORNER));
    points->push_back(SnapCandidatePoint(Geom::Point(0,h), SNAPSOURCE_UNDEFINED, SNAPTARGET_PAGE_CORNER));
    points->push_back(SnapCandidatePoint(Geom::Point(w,h), SNAPSOURCE_UNDEFINED, SNAPTARGET_PAGE_CORNER));
    points->push_back(SnapCandidatePoint(Geom::Point(w,0), SNAPSOURCE_UNDEFINED, SNAPTARGET_PAGE_CORNER));
}

void Inkscape::getBBoxPoints(Geom::OptRect const bbox,
                             std::vector<SnapCandidatePoint> *points,
                             bool const /*isTarget*/,
                             bool const includeCorners,
                             bool const includeLineMidpoints,
                             bool const includeObjectMidpoints)
{
    if (bbox) {
        // collect the corners of the bounding box
        for ( unsigned k = 0 ; k < 4 ; k++ ) {
            if (includeCorners) {
                points->push_back(SnapCandidatePoint(bbox->corner(k), SNAPSOURCE_BBOX_CORNER, -1, SNAPTARGET_BBOX_CORNER, *bbox));
            }
            // optionally, collect the midpoints of the bounding box's edges too
            if (includeLineMidpoints) {
                points->push_back(SnapCandidatePoint((bbox->corner(k) + bbox->corner((k+1) % 4))/2, SNAPSOURCE_BBOX_EDGE_MIDPOINT, -1, SNAPTARGET_BBOX_EDGE_MIDPOINT, *bbox));
            }
        }
        if (includeObjectMidpoints) {
            points->push_back(SnapCandidatePoint(bbox->midpoint(), SNAPSOURCE_BBOX_MIDPOINT, -1, SNAPTARGET_BBOX_MIDPOINT, *bbox));
        }
    }
}

bool Inkscape::ObjectSnapper::_allowSourceToSnapToTarget(SnapSourceType source, SnapTargetType target, bool strict_snapping) const
{
    bool allow_this_pair_to_snap = true;

    if (strict_snapping) { // bounding boxes will not snap to nodes/paths and vice versa
        if (((source & SNAPSOURCE_BBOX_CATEGORY) && (target & SNAPTARGET_NODE_CATEGORY)) ||
            ((source & SNAPSOURCE_NODE_CATEGORY) && (target & SNAPTARGET_BBOX_CATEGORY))) {
            allow_this_pair_to_snap = false;
        }
    }

    return allow_this_pair_to_snap;
}

void Inkscape::ObjectSnapper::_snapPathsTangPerp(bool snap_tang, bool snap_perp, IntermSnapResults &isr, SnapCandidatePoint const &p, Geom::Curve const *curve, SPDesktop const *dt) const
{
    // Here we will try to snap either tangentially or perpendicularly to a single path; for this we need to know where the origin is located of the line that is currently being rotated,
    // or we need to know the vector of the guide which is currently being translated
    std::vector<std::pair<Geom::Point, bool> > const origins_and_vectors = p.getOriginsAndVectors();
    // Now we will iterate over all the origins and vectors and see which of these will get use a tangential or perpendicular snap
    for (const auto & origins_and_vector : origins_and_vectors) {
        Geom::Point origin_or_vector_doc = dt->dt2doc(origins_and_vector.first); // "first" contains a Geom::Point, denoting either a point or vector
        if (origins_and_vector.second) { // if "second" is true then "first" is a vector, otherwise it's a point
            // So we have a vector, which tells us what tangential or perpendicular direction we're looking for
            if (curve->degreesOfFreedom() <= 2) { // A LineSegment has order one, and therefore 2 DOF
                // When snapping to a point of a line segment that has a specific tangential or normal vector, then either all point
                // along that line will be snapped to or no points at all will be snapped to. This is not very useful, so let's skip
                // any line segments and lets only snap to higher order curves
                continue;
            }
            // The vector is being treated as a point (relative to the origin), and has been translated to document coordinates accordingly
            // We need however to make it a vector again, because also the origin has been transformed
            origin_or_vector_doc -= dt->dt2doc(Geom::Point(0,0));
        }

        Geom::Point point_dt;
        Geom::Coord dist;
        std::vector<double> ts;

        if (snap_tang) { // Find all points that lead to a tangential snap
            if (origins_and_vector.second) { // if "second" is true then "first" is a vector, otherwise it's a point
                ts = find_tangents_by_vector(origin_or_vector_doc, curve->toSBasis());
            } else {
                ts = find_tangents(origin_or_vector_doc, curve->toSBasis());
            }
            for (double t : ts) {
                point_dt = dt->doc2dt(curve->pointAt(t));
                dist = Geom::distance(point_dt, p.getPoint());
                isr.points.emplace_back(point_dt, p.getSourceType(), p.getSourceNum(), SNAPTARGET_PATH_TANGENTIAL, dist, getSnapperTolerance(), getSnapperAlwaysSnap(), false, true);
            }
        }

        if (snap_perp) { // Find all points that lead to a perpendicular snap
            if (origins_and_vector.second) {
                ts = find_normals_by_vector(origin_or_vector_doc, curve->toSBasis());
            } else {
                ts = find_normals(origin_or_vector_doc, curve->toSBasis());
            }
            for (double t : ts) {
                point_dt = dt->doc2dt(curve->pointAt(t));
                dist = Geom::distance(point_dt, p.getPoint());
                isr.points.emplace_back(point_dt, p.getSourceType(), p.getSourceNum(), SNAPTARGET_PATH_PERPENDICULAR, dist, getSnapperTolerance(), getSnapperAlwaysSnap(), false, true);
            }
        }
    }
}

/*
  Local Variables:
  mode:c++
  c-file-style:"stroustrup"
  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
  indent-tabs-mode:nil
  fill-column:99
  End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :