Feature Request: Possibility to calculate intersections between paths

[Esser50K]

I'm working on something that heavily relies on intersection calculation. I was doing it by hand because I didn't find anything in this library. Then I found the svgpathtools library which seems to support exactly this (and this lib is also inspired by it as far as I see).

Could that code be ported here as well?

[tatarize]

Probably. I personally want normal and tangent vector code from the library but there's a few of the functions that don't easily have a home. Some of them seem a bit complex there. One could likely find the intersections by linearizing the paths. There are some really nice bits of intersection code, but some bits were seemingly missing like some arc intersection bits.

I've no qualms porting stuff from mathandy's work. But, I think I grabbed everything that was easy and highly understandable work. I mostly focused on getting svg parsing as near to perfect as I could. So I used svg.path code initially and patched in svgpathtools code into that. I'll check what's needed.

[Esser50K]

Great! Yeah I'm using the linearizing the path route but it's incredibly inefficient (compared to using math)

[tatarize]

svgelements thanks to abey79 has numpy linearization algorithms to do the linearization paths with the npoint function. This is the fastest set of methods to linearize the path data. If you are looking for the intersection of two different shapes stored as numpy arrays I would venture a guess that you could absolutely perform the regular line intersection formula to get an NxM matrix of values t0 and t1 where N is the number of line segments in the first shape and M is the number of line segments in the second shape and t0 is the value between t value where the line in M intersects the line in N. If the values for t0 and t1 are between 0 and 1 then you have a an intersection of those two line segments.

This would basically be what you're already doing but with numpy you could do this for all your line segments in a large bulk event. My numpy magic is weak but I generally see that the formula for finding line intersections could be accessed in a highly parallel fashion.

[tatarize]

import numpy as np

T = np.array([[0, -1], [1, 0]])
def line_intersect(a1, a2, b1, b2):
    da = np.atleast_2d(a2 - a1)
    db = np.atleast_2d(b2 - b1)
    dp = np.atleast_2d(a1 - b1)
    dap = np.dot(da, T)
    denom = np.sum(dap * db, axis=1)
    num = np.sum(dap * dp, axis=1)
    return np.atleast_2d(num / denom).T * db + b1

import svgelements as svge
from random import random

j = svge.Path(svge.Circle(cx=random() * 5, cy = random() * 5, r=random() * 5)).npoint(np.arange(0, 1, 0.001))
k = svge.Path(svge.Circle(cx=random() * 5, cy=random() * 5, r=random() * 5)).npoint(np.arange(0, 1, 0.001))
mesh = np.meshgrid(np.arange(0, len(j)), np.arange(0, len(k)))
a1 = j[mesh[0]]
a2 = j[mesh[1]]
k1 = k[mesh[0]]
k2 = k[mesh[1]]
print(line_intersect(j[:-1], j[1:], k[1:], k[:-1]))

I gave it a shot, but I need something for segments since the intersections exist for any lines (other than parallel lines within Euclidean Geometry) and the code I grabbed from SO for line intersection doesn't check whether T is between 0 and 1. Might have a bunch of other bugs too.

[tatarize]

This was actually added. In part due to your notes in svgpathtools looking for this more effectively. We added segment.intersect(other) as a quite fast version in here. There might be some additional things needed like quadtrees to avoid checking wouldbe overlapping bounding boxes but this is added. Also I opened an Issue on svgpathtools with my solution there as well.