Arc line intersect fix

[SebKuzminsky]

This PR supersedes #36 and #38. It provides a new implementation of Arc.intersect(Line) which fixes the problems highlighted by those PRs. All the Arc/Line tests from those PRs are included in this PR, plus a whole bunch of additional test cases.

This new implementation only deals with non-rotated Arcs intersecting with (arbitrary) Lines. Rotated Arcs, and Arcs intersecting with non-Line objects are still handled by the untouched original code.

[mathandy]

Hey, thanks @CatherineH and @SebKuzminsky!

I like the name point_to_t. Is there a reason you're not using the (admittedly poorly named) radial_range method?

I haven't looked much at your code yet -- just wanted to point out such a function exists. I'm not at all opposed to adding a point_to_t method actually. In my opinion, we should try to avoid adding redundant code though.

[SebKuzminsky]

radialrange() says it finds the values of t where the segment has the minimum and maximum distance from the origin. point_to_t() takes a (x+yj) point and returns the t-value of that point. It is the inverse of point(). Ie, for all points in seg:

point == seg.point(seg.point_to_t(point))

What am I missing regarding the overlap in functionality between these two functions?

[SebKuzminsky]

I should make explicit: it's certainly not my intention to add redundant code, and I welcome education here.

[mathandy]

The names origin and radialrange come together nicely to make for an exceptionally confusing naming choice. ... My fault. I added the closest_point_in_path function in an attempt to remedy this. A method named point_to_t that calls (where appropriate) radialrange would have been a better choice.

from svgpathtools import *
seg = Line(0, 4+4j)  # an arbitrary path segment
pt = 3+3j  # an arbitrary point on that path segment

# find the `t` s.t. `seg.point(t) == pt`
t = seg.radialrange(pt)[0][1]

# check
print(seg.point(t) == pt)

[SebKuzminsky]

Ah, I see how that works, thanks. closest_point_in_path() operates on a path, not a segment, so it's not quite what I needed for these changes to intersect().

I can imagine a couple of ways forward here.

1. Keep Arc.point_to_t() and Line.point_to_t() but rewrite them to call radialrange().
2. Get rid of point_to_t() and rewrite Arc.intersect(Line) to call radialrange() directly instead.

I'm happy to rework this PR in either way, or some other way if you prefer. Let me know what you think would be best.

[mathandy]

Assuming the first idea isn't difficult, let's go with that one. Thanks @SebKuzminsky!

[SebKuzminsky]

I replaced the guts of Line.point_to_t() with a call to radialrange(), but that idea failed for Arc:

>       raise _NotImplemented4ArcException
E       Exception: This method has not yet been implemented for Arc objects.

[SebKuzminsky]

Hmm, there's a slight problem with using radialrange() in Line.point_to_t(): performance.

The original "by-hand" implementation takes ~75 microseconds per call in my test (on my hardware), the updated implementation that calls radialrange() takes ~315 microseconds. I guess this is not surprising since radialrange() answers a much more general, more complicated question than what point_to_t() really needs.

Here's my test script:

#!/usr/bin/env python2

import svgpathtools
import random
import resource

num_points = 30000
l = svgpathtools.path.Line(start=(0+0j), end=(10+10j))

random.seed(0)
test_points = [complex(random.uniform(-5, 15), random.uniform(-5, 15)) for i in range(num_points)]

start = resource.getrusage(resource.RUSAGE_SELF)
for p in test_points:
    l.point_to_t(p)
end = resource.getrusage(resource.RUSAGE_SELF)

total = (end.ru_utime + end.ru_stime) - (start.ru_utime + start.ru_stime)
print("%.6f seconds/point" % (total/num_points))

[SebKuzminsky]

I'm closing this PR and offering instead a cleaned up version. This PR has a couple of problems that I've addressed in the new PR:

• The initial branch in this PR had some bugs that I fixed in later commits. The new PR has these bugfixes squashed into the commits that they fix.
• The suggestion to use radialrange() in Arc.point_to_t() and Line.point_to_t() didn't work out. Arc has no radialrange(), and Line's radialrange() is several times slower than the "by-hand" implemetation in my original Line.point_to_t(). So the new PR does not use radialrange() at all.
• This PR is old enough that master has moved ahead, and this PR no longer merges cleanly. I rebased the branch onto the current master branch and resolved all the merge conflicts.