Arc Parameterization, Length & Error

[tatarize]

    def test_point_in_arc(self):
        """Use known circle elements to test approximate arc values."""
        from math import cos, sin, pi
        tau = 2 * pi
        for angle in range(-180, 180, 1):
            arc = Arc(0 + 25j, 25 + 25j, angle, 0, 0, 0 - 25j)
            path = Path(arc)
            for i in range(100):
                x = sin(i * tau / 200) * 25
                y = cos(i * tau / 200) * 25
                p = i / 100.0
                point = path.point(p)
                self.assertAlmostEqual(point.real, x, places=5)  #6th wrong for some.
                self.assertAlmostEqual(point.imag, y, places=5)
                self.assertEqual(arc.point(p), point)
            error = path.length() - (tau / 2.0) * 25.0
            print("%.12f error at angle %d" % (error, angle))
            self.assertAlmostEqual((tau / 2.0) * 25.0, path.length(), places=5)  # 6th place wrong

Some of these errors are pretty large and all of them are negative since number of straight lines being used to approximate a circle will always be inside the circle. And the error check it was supposed to use was 1e-12 there. But, the factor there isn't whether the value is known to less than that value, you can do that but it takes subscribing and superscribing the arc.

However this method for approximating a circle has diminishing returns on the order of the square of the number of points. It's really hard and prohibitively expensive to eek out more correctness through this means.

Side note, in my test there, (feel free to use it), I'm pointlessly rotating the circle because that's where my code is breaking in my parameterizations.

-0.000000007520 error at angle -180
-0.000000007520 error at angle -147
-0.000000534356 error at angle -114
-0.000000652759 error at angle -81
-0.000000534356 error at angle -48
-0.000000534356 error at angle -15
-0.000000534356 error at angle 18
-0.000000007520 error at angle 51
-0.000000007520 error at angle 84
-0.000000534356 error at angle 117
-0.000000007520 error at angle 150

Note that the point value there has itself error up to the 6th order. And you use the point value to get get the position at some value pos so even if your lengths were somehow perfect we'd still get 6th order error. Maybe there's something about the function itself that is introducing a lot more error than it needs. Like floats work better if you keep them between 0 and 1. Since you get denormal calculations. But, asking for 12th order error when you can only have 6th order possible seems like it's a big time suck for no results.

Also, you might want to strongly consider cheating for the special case of circular. It's downright common that we actually have circles, and the equations are easy given tau is already calculated for us.

[tatarize]

There's also some issues with parameterizing the arcs with regard to matrix values and svg values. The SVG standard says we increase the size of our radius if there is no solution that can work. Okay. Done. But, your tests specifically generation for 'M 600,350 L 650,325 A 25,25 -30 0,1 700,300 L 750,275', says I should return 25,25 again when distance from (650,325) to (700,300) is ~55.9 which needs to scale up. to ~27.95 and if I do that. My actual points are that far apart. The code seems to demand I store the too small radius again to reproduce the same code rather than code that will correctly radius check, corresponds to the same shape.

Unlike the other shapes which store all the information needed to use and manipulate them. Arcs store the svg parameters in order to regurgitate them.

[tatarize]

Actually that's not really your test it's actually code.

    def test_issue_47(self):
        arc_path_declared = Path(Move(0 + 25j), Arc(0 + 25j, 25 + 25j, 0.0, 0, 0, 0 - 25j))
        arc_path_parsed = parse_path('M 0 25 A25,25 0.0 0 0 0,-25')
        arc_path_parsed_scaled = parse_path('M 0 25 A1,1 0.0 0 0 0,-25')
        self.assertEqual(arc_path_declared, arc_path_parsed)
        self.assertEqual(arc_path_parsed_scaled, arc_path_declared)

Which you can tell from the svg spec is actually correct. However svg.path causes:

Path(Move(to=25j), Arc(start=25j, radius=(25+25j), rotation=0.0, arc=False, sweep=False, end=-25j), closed=False) != Path(Move(to=25j), Arc(start=25j, radius=(1+1j), rotation=0.0, arc=False, sweep=False, end=-25j), closed=False)

Expected :Path(Move(to=25j), Arc(start=25j, radius=(1+1j), rotation=0.0, arc=False, sweep=False, end=-25j), closed=False)
Actual :Path(Move(to=25j), Arc(start=25j, radius=(25+25j), rotation=0.0, arc=False, sweep=False, end=-25j), closed=False)

To correct this, the last line in _parameterize should be:

self.radius = rx + ry * 1j # This could be scaled by the radii check.

Which will use the scaled radii. However this will cause several other checks to fail. Namely the svg parsing back and forth of the above code and a length check which was checked against non-scaled radii lengths.

https://www.w3.org/TR/SVG/implnote.html#ArcImplementationNotes

If the result of the above equation is less than or equal to 1, then no further change need be made to rx and ry. If the result of the above equation is greater than 1, then make the replacements

---

Trying to make my library which has a bunch of different code still backwards compatible and bug checking with your awesome test code. It's found a few things that are important and a couple that aren't as much. But, this one kept popping out one way when I fixed it and the other when I broke it again. Traced it down to your test code is broken because the code it's testing is also kinda off spec.

[tatarize]

Beyond the implementation flaw there's also problem with the parameterization with regard to scaling.

My pull request #46 to fix #36 #16 etc, generally had serious problems with the arc parameterization. You take in and save the SVG parameters and convert to circle based parameterization. However, neither of these are able to be transformed. They are static values.

I could code up a functional matrix that could work with complex numbers but you'd still hit a wall at Arc. Even when I break the real and complex parts apart, and then perform the matrix multiplication stuff, applying that to Arc would still be broken because what a matrix does to the parameters differs greatly by the parameters and the operation invoked.

Without arc, you could just multiply all the points by a real number and that would natively scale it. However, it would not properly scale the arcs. It would give them correct start and end points, but the ellipse used between the points would be unscaled. And the parameters would be screwy.

[regebro]

You are talking about a whole bunch of different issues here, and in none of the cases do I really follow what the actual problem is.

I think you are saying in the first comments that the length calculations of arcs isn't accurate enough?

Your second comment is entirely beyond me. I can't find any place the SVG specs talk about increasing any radius. And:

"Unlike the other shapes which store all the information needed to use and manipulate them. Arcs store the svg parameters in order to regurgitate them."

Arcs also store the information needed to use them, which is the parameterization used to calculate the length(). I fail to see how it is a problem that the results of the parameterization is stored so it doesn't have to be redone for each length() or point() calculation.

In your third comment you seem to claim that parse_path('M 0 25 A25,25 0.0 0 0 0,-25') and parse_path('M 0 25 A1,1 0.0 0 0 0,-25') should return equivalent objects, which is clearly false, so I don't know why you would say that.

"You take in and save the SVG parameters and convert to circle based parameterization. However, neither of these are able to be transformed."

If it was true, transforming arcs would be entirely impossible, which of course, is not the case, so yet again I have no idea what you are trying to say.

[regebro]

Although shortcutting the arc calculations when it's actually a circle is a good idea, I might do that.

[tatarize]

TL;DR versions.

1. The error value is not within 1e12 but rather the improvement step is less than 1e12 closer. The series here is drops at the square of the number of points. So it converges very slowly. So you'll reach steps less than 1e12 while there is still a very large error.

2. https://www.w3.org/TR/SVG11/implnote.html#ArcImplementationNotes
   F.6.2 Out-of-range parameters
   "If rx, ry and φ are such that there is no solution (basically, the ellipse is not big enough to reach from (x1, y1) to (x2, y2)) then the ellipse is scaled up uniformly until there is exactly one solution (until the ellipse is just big enough)."
   The 2.0 spec gives the implementation notes that specifically says you replace the old rx, ry with the new values.

3. "In your third comment you seem to claim that parse_path('M 0 25 A25,25 0.0 0 0 0,-25') and parse_path('M 0 25 A1,1 0.0 0 0 0,-25') should return equivalent objects, which is clearly false, so I don't know why you would say that."

It's true.

<svg xmlns="http://www.w3.org/2000/svg" width="200" height="100" version="1.1" viewport="-25 -25, 100 100">
<g transform="translate(50,50)">
   <path d="M 0 25 A25,25 0.0 0 0 0,-25" fill="red">
</g>
<g transform="translate(75,50)">
   <path d="M 0 25 A1,1 0.0 0 0 0,-25" fill="blue">
</g>
</svg>

4. I'm trying to say parameterizations you are using makes doing transforms a non-starter currently. The arcs need to have a different internal parameterization to make that possible. There's a couple that would work, but it's currently two different static forms and isn't workable. My code in svg.elements works for that as an example. But, I basically have to store all the properties as points and recalculate them when queried.

[regebro]

1. OK, I see.

2. Ahh, interesting. Yeah, that's a tricky one.

3. Yeah, those objects will not and should not test as equal, just because the scaling rule means they would be drawn the same. Likewise, would we implement a library with support for the other SVG shapes, a circle drawn with a circle object will not be equal to a circle drawn with an arc. We are not going to sit and figure out if two paths would be drawn exactly the same. The will be equal if they have the same parameters and not in any other case.

4. The internal parameterizations are there for the point() and length() calculations. There are exactly zero ways they possibly can stop transformations. Maybe you are saying that you don't know how to transform them? Then don't.

"But, I basically have to store all the properties as points and recalculate them when queried."

Queried? Nothing is being queried...

[tatarize]

3. I used your test suite with svg.elements after I had most of it done. For 3 it actually does matter even in your code. One of the tests that suffers from that bug. It's calculating the length of a large path, one element of which is an arc and it didn't scale up the arc, so the length was wrong. When I fixed it in my code it actually threw an error in two places. One was rewriting the same path which it couldn't do if you replaced the values for rx and ry, the other was a wrong length value that no longer matched the static expected result.

For 3 you can just replace the value with the scaled up value, it's what the SVG 2.0 documentation now says should be done. And you calculated them already in the _parameterize function. Just overwrite the values, it's two lines.

4. I know how to do it, but, basically it would involve creating a lot of different points around the circle that exemplify the arc values and then transforming them. You'd have center, start and end. But, it would also need to transform rx as a point in space and ry as a point in space. Both of which are fairly easy to do, and reversing the sweep angle if the sx or sy signs are not equal. That can all be done.

The problem here is there's a bunch of values attached to the arc which are now invalid. It might have switched the sweep boolean or changed the sweep angle, changed the rx or ry and even made previously equal rx and ry non-uniform etc.

The concrete suggestion I'd have on that is to simply store the internal values for the arc as points to begin with. Having rx and ry a real position in euclidean space (which you pretend is complex space). Then rather than calling them as variables you make them @Property functions that recalculate that. For rx and ry you're adding in a euclidean distance function (though with complex numbers you can do that with abs())

The other option is only allow methods that directly call the Arc convert those properties to points, transform them, and then recalculate the properties in question. Though for this case you'll need to calculate the methods for both stored parameterizations which was my original problem there, a lot of those parameters are redundant information since if you have one you can calculate the other. And you'll refigure a lot of data that you might not need.

This is why in svg.elements I opted to store the arcs as 5 points. Since I could transform that without any issue and calculate any needed value from those points. 4 is largely concerned with fundamental principles methodology and I'm just not sure which way you'd want to go there.

Should it do the transforms in a 3rd parameterization and then convert that into the other two parameterizations. Or should it just use 1 parameterization and then calculate relevant data about those parameterizations on the fly? Or should any attempt at transforms be skipped to avoid messing up a reasonable enough project with features that might require fundamental changes. I mean I already needed to solve this stuff for svg.elements and with a bit more work it could be pretty robust.

PS. best thing I ever did was merge the parser with the Geometric objects. Path('m0,0 L5,5') * Matrix('translate(50,50)') is super awesome.

[regebro]

"Just overwrite the values, it's two lines."

No, that defeats the purpose of the library.

"The problem here is there's a bunch of values attached to the arc which are now invalid."

Which is easily solved by running the parameterizing again, but anyway, that's an entirely moot point as the transform should return a new Arc object, not change the existing one.

"The concrete suggestion I'd have on that is to simply store the internal values for the arc as points to begin with."

But that's what I do!?

"which you pretend is complex space"

There is no pretending.

"Then rather than calling them as variables you make them @Property functions that recalculate that."

Recalculate what?

I'm sorry, but this conversation isn't going any further. I can't see that any of the issues you point out are real issues.

[tatarize]

@regebro Surely the fact that failing to expand the radii causes the length calculation to be wrong is an issue. You calculate the length of an arc with a tiny radius but it should have a much larger one.

[regebro]

@regebro Surely the fact that failing to expand the radii causes the length calculation to be wrong is an issue. You calculate the length of an arc with a tiny radius but it should have a much larger one.

Well, you didn't say that, so if that is an issue, you did not point that out before. Also, I quote: "And you calculated them already in the _parameterize function." In that case, the radius IS expanded. But I haven't verified that. I'll look into it.

[tatarize]

"For 3 it actually does matter even in your code. One of the tests that suffers from that bug. It's calculating the length of a large path, one element of which is an arc and it didn't scale up the arc, so the length was wrong. When I fixed it in my code it actually threw an error in two places. One was rewriting the same path which it couldn't do if you replaced the values for rx and ry, the other was a wrong length value that no longer matched the static expected result."

The two lines I'm talking about are setting the values in the bit in _parameterize() which is called ` # Correct out of range radii`` -- Which you check against but you never actually save. It updates the rx ry value as passed to the function, but then loses those at the end.

To correct this, the last line in _parameterize should be:

self.radius = rx + ry * 1j # This could be scaled by the radii check.

Though getting lost is pretty easy since the topic has like 6 topics and like 4 don't really matter.

[regebro]

OK, I need to store the radius scale as well and use that in the point calculations then.
Thanks for that!