create a quadtree implementation adapted for svg paths and segments

[Esser50K]

I've been working on a project that heavily relies on the use of the intersection calculation capabilities of this lib. However I noticed it being too slow when I loaded it with larger svgs, essentially this is because for every path it goes through every segment every single time.

I experimented with loading the segments into a quadtree so they wold be quicker too look up and it works quite well, especially for svgs with a lot of paths and paths with a lot of segments.

I know this doesn't make the cut according to contribution guidelines but I'm happy to make the changes if there is actual interest for this.

[Esser50K]

I was thinking and I could also extend this in a way that Path objects actually hold their own Quadtree. So that one could simply call .intersect on it and get the automatic performance boost whilst using the same API.

[mathandy]

Hi @Esser50K, thanks for the suggestion and PR. If there's a significant speedup, yeah, that sounds great. I think there's pretty good test coverage for intersections, so we could even set your method as the default.

[Esser50K]

Alright I moved the Quadtree inside the Path. I've added some tests just to check if the Quadtree behaves as expected. I think that the intersection part is already covered by the other tests so not sure if you'd like something specific for Quadtrees.

I guess a performance test would make sense. The quadtree only gives marginal improvements for small SVGs with a low amount of paths, however when the number of paths is large (and the paths have many segments) this method is a lot faster.

In theory the performance of the other intersection was simply quadratic O(n^2) and now it is O(n * log(n)) (I think).

[tatarize]

I don't like the idea of always storing QuadTree inside Path. You can have a lot of paths and now all implementations would have a QuadTree object in them. Not only that they build the quadtree when it's created, for a function that might not be called. That seems like a lot of overhead in the generic case. It would seem that, at worst, you should build a quadtree cache and reset it in the same cases where .lengths get reset.

---

The actual methodology for doing this faster would be to use the Bentley Ottmann (https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm) algorithm for finding line intersections. ( https://www.youtube.com/watch?v=qkhUNzCGDt0). Given the bezier curves you might need to do some weird things with creating rational bezier curves (or segmenting them) etc.

---

The time complexity here is actually the same as it ever was. You're still dealing with O(N²) the difference is you're not doing a brute force N² testing everything but you're actually only testing those segments with overlapping bounding boxes. In worst case you built a quadtree and then did all the same intersection checks you did before. In best case you did no intersection checks since nothing overlapped at all. Time complexities for acceleration structures are a bit weird but it speeds up the average case. Here you're doing fast hit testing, if the bounding boxes of the two segments do not overlap they cannot intersect. This means most of the time you skip all most of potential intersections.

Bounding box checks on bezier curves are a bit hefty. There's actually a note that "Warning: For the non-cubic case this is not particularly efficient." in the case of a Bezier segment you can actually do the axis aligned bounding box (AABB) of the all the control points. This is not the bounding box but, by definition, a bezier curve fits into convex hull of the endpoints and control points (though you usually just do min-x, min-y, max-x max-y since that's always going to contain the convex hull, and is way easier to calculate.

---

There's probably a couple shorter methods too rather than calculating the denom and t1 t2 for intersections you could probably check if these overlap and get a pretty marked speed improvement. The intersect routines seem to run a bunch of math without bothering to see if the quick bounding boxes even overlap. For the heftier checks this is low hanging fruit. You might be able to beat the speed improvement for building the quad-tree simply by implementing fast-fails for quick-bounds intersection tests. If we know the AABB of the points in a line and a points in a bezier curve and these do not intersect, then the curves don't intersect... stop working. All cases we're still doing O(N²), but rather than skipping the non-overlapping tests we could fail a lot more quickly.

For example if we're looking for a line-cubicbezier intersection.

if min(other_seg.start.real, other_seg.end.real) > max(self.start.real, self.control1.real, control2.real, self.end.real):
     return None
if max(other_seg.start.real, other_seg.end.real) < min(self.start.real, self.control1.real, control2.real, self.end.real):
     return None
if min(other_seg.start.imag, other_seg.end.imag) > max(self.start.imag, self.control1.imag, control2.imag, self.end.imag):
     return None
if max(other_seg.start.imag, other_seg.end.imag) < min(self.start.imag, self.control1.imag, control2.imag, self.end.imag):
     return None

These checks are going to be quite fast compared to the other checks. So really a check for the performance should be matched against this sort of added fast fail routine which should speed the whole thing up quite considerably anyway.

[tatarize]

        if isinstance(other_seg, (Line, QuadraticBezier, CubicBezier)):
            ob = [e.real for e in other_seg.bpoints()]
            sb = [e.real for e in self.bpoints()]
            if min(ob) > max(sb):
                return []
            if max(ob) < min(sb):
                return []
            ob = [e.imag for e in other_seg.bpoints()]
            sb = [e.imag for e in self.bpoints()]
            if min(ob) > max(sb):
                return []
            if max(ob) < min(sb):
                return []

Is probably about right. Might be faster to hardcode it rather than doing the list comprehension but adding that as the first value in intersect for Line, CubicBezier and QuadraticBezier would actually suffice to check the performance boost against a fast failing analog.

[tatarize]

Here's a somewhat fair test for random intersections:

    def test_random_intersections(self):
        from random import Random
        r = Random()
        distance = 100
        distribution = 10000
        count = 500

        def random_complex(offset_x=0.0, offset_y=0.0):
            return complex(r.random() * distance + offset_x, r.random() * distance + offset_y)

        def random_line():
            offset_x = r.random() * distribution
            offset_y = r.random() * distribution
            return Line(random_complex(offset_x, offset_y), random_complex(offset_x, offset_y))

        def random_quad():
            offset_x = r.random() * distribution
            offset_y = r.random() * distribution
            return QuadraticBezier(random_complex(offset_x, offset_y), random_complex(offset_x, offset_y), random_complex(offset_x, offset_y))

        def random_cubic():
            offset_x = r.random() * distribution
            offset_y = r.random() * distribution
            return CubicBezier(random_complex(offset_x, offset_y), random_complex(offset_x, offset_y), random_complex(offset_x, offset_y), random_complex(offset_x, offset_y))

        def random_path():
            path = Path()
            for i in range(count):
                type_segment = random.randint(0, 3)
                if type_segment == 0:
                    path.append(random_line())
                if type_segment == 1:
                    path.append(random_quad())
                if type_segment == 2:
                    path.append(random_cubic())
            return path

        path1 = random_path()
        path2 = random_path()
        t = time.time()
        path1.intersect(path2)
        print(f"\nIntersection calculation took {time.time() - t} seconds.\n")

This goes from 47 seconds to 1.5 seconds with a the given distribution, with fast failing turned on.

[Esser50K]

@tatarize can you confirm these are your suggestions in summary:

• make quadtree not build itself by default
• make it python2.7 compatible
• maybe rebase on top of the tatarize:fastfail-intersection so I include the test and compare against it?

Or do you think using a quadtree for accelerating intersections is incorrect altogether and one should use the Bentley Ottoman algorithm for it? (although it looks like that would require linearizing paths which I think will be a bit inefficient. I did try linearizing the paths instead of passing in the segments to the quadtree but that essentially made the building of the quadtree much slower)

[mathandy]

Do you have any examples to demonstrate the speedup @Esser50K ? Running python -m unittest test.test_path.Test_intersect shows no significant improvement.

I'm tempted to drop 2.7 support just to have type annotations.

[mathandy]

Thanks to some great work by @tatarize , you can now run python -m unittest test.test_path.Test_intersect.test_random_intersections to test how fast intersections are found. By adjusting the count variable you can increase or decrease the number of intersections that will be present in the randomly generated paths. E.g. with count = 100 it seems unlikely that any intersections will be present.

This also currently produces a AttributeError: 'list' object has no attribute 'union' error when using your code at out = out.union(self._subtreeNE._get_segments_in_area(area, out))

[Esser50K]

Nice to see an update here. Yeah I think I messed some things up when I refactored the code. I think the changes from @tatarize go a long way. I will clean this up and run some tests to see if this is still worth it or not.

[Esser50K]

I believe that the fast-fail code from @tatarize is doing something very similar to the quadtree (in the sense that is looking at the bounds and checking if they overlap at all). This way when the quadtree runs it is mostly just doing duplicate work. I changed the test slightly just to compare both but one can see that the quadtree does not give any improvements with the new fast-fail code.

Test output logs:

Found 68 intersections in 2.938478946685791 seconds.
Found 68 intersections in 2.836733818054199 seconds without quadtree.

Found 80 intersections in 2.836812973022461 seconds.
Found 80 intersections in 2.8853371143341064 seconds without quadtree.

Found 77 intersections in 3.0371289253234863 seconds.
Found 77 intersections in 2.925523042678833 seconds without quadtree.

Found 69 intersections in 2.9582250118255615 seconds.
Found 69 intersections in 2.914271116256714 seconds without quadtree.

Found 66 intersections in 2.9921112060546875 seconds.
Found 66 intersections in 2.889678716659546 seconds without quadtree.

Found 86 intersections in 3.080353021621704 seconds.
Found 86 intersections in 3.037317991256714 seconds without quadtree.

@mathandy feel free to close this PR in that case

[tatarize]

The massive increase from the quadtree was actually because it did fast fail. The actual datastructure itself wasn't speeding things up much if at all. Basically if the AABB (axis aligned bounding boxes) of the curves do not overlap then they can't intersect so we can do some very basic subtraction and rule out something like 95% (varies a lot) of possible intersections. Fast fail just does a very tiny amount of subtraction to see if intersection is even possible.

It's like 4 subtractions and a compare which shouldn't add much overhead at all. In fact, if there's no overlap across the x-axis it doesn't even check the y-axis at all.

I also submitted: https://github.com/mathandy/svgpathtools/issues/192 for some review.

While it's technically imprecise and can fail in some edge cases it's also 50x faster (and much more exact for where the intersection occurs) and works for all curves including arcs. So if finding intersections was mission critical it can be sped up still. It would be possible to change that code perform AABB overlap checks to actually exactly solve the intersections, or at least show that an extremely small region of space still contains both curves (without knowing if they necessarily overlap).

[mathandy]

Regardless, thanks for your work on it. You are appreciated!