Path.simplify() sometimes results in control points that are nowhere near the line

[calamitas]

The sketch below shows this behavior. The lower line shows the simplified path where one control points sticks out below. Increasing the tolerance to 10 seems to fix the problem.

We see this issue a lot in our application, especially when we use Path.simplify while drawing live; sometimes the line jumps to the edge of the screen and then goes back.

Simply changing the tolerance doesn't fix it completely as things can still go wrong (see second sketch below).

Any ideas on how to fix this? The path simplifying in paper.js is great except that it sometimes gives these weird artefacts.

http://sketch.paperjs.org/#S/lVVdc6IwFP0rGV5qR5YJNx8E3X3aP9CZPooPVGJ1RHCQbus4/vdGbKIEiG5exMu5X+feQ45ekW6lN/FeN7JerDzfW5TZ+f+/tEK7cl3Ue/QHzZICqXNMvK/Em0BI/cQ7qCdKaMBvTnTybWTrPecPO4pHkQRfkfY7bt4BOKOQMArI7fnxI7GwkSLuR3I7O40GYkLYtlt+jLUzaLJBgIXkmPUjGXd2y4lmF4iwBmRD6UAxhLSbsLvnhnuAezl4u1xuHON7OchAcd02BpCsXVuHqRA0Mlbs6wlZk9XRuhUyCr2tkcg9IRbebK7JS4VRBbN3gXJLJxop3PqhTFfPMHYjqTBIWxXU4lfvOrN01dEI7dcICzsZDHcM3+EOh70xaUc/jOnpUnpHMfYOm+8DcWqZR9h8H5gTGQGYLXLPIYquO2mzJHD/vkEUO7MLGNAHd+tDkH4lALe5FnRYc0kxnyZFc+Ok9SpUF04hP9GLeh4dkyKp9/J9K9VNNEGzud8Y6qrcyL9lXlYT9PSWp4vNU1Kcnm+iwP9GqWSmYyzLCo2aQCoInqqf3z93YZDL4r1eKdN4/Kxaazpsig7SLBtdQLPdPPhCv1DIsI+upsPFdE6gveARrzEC3Hgpni5O+/V2l6+Xh9HZejEtP/L88Cpzuahlpqquqw859U7f

http://sketch.paperjs.org/#S/lVbLctowFP0VjTchA/VIV0+TdtUf6EyXmIULTmAAmzGeNgzDv1cxsSQb3aTVBvtyztHVfcmXpCoOZTJPfu7KdrVJZsmqXr+9/y4acqy3VXsi38jikieveTIHqWZ5crZPnJnrzFlNqoKlHUamPFyeoVScQUdKjsGZeMeAFhjGZMP9ekbgqxBxX5lWHqOhtyo6QCsPkpRHN2NidGjhKUw5kEB1gfYgqTCQ0MhJAfWXZ4CEXESCzPUoQUGyR+fuKYKjFG56jMRyBzDMi+pDJVRQaNxbNVZaWTwvAoIigN4hzjEdm6w05g8YjjEkG/zjClaBxyhE9S6qnjLKtZMVQdFk1FkZKoTtrajH8L70IRuWkv40MpwGDrER240ENHpIP3HASkaCjgbmA4YetcenXinfERQQVcXjeeeUYaqSOgwNrCbuXdChiiFn5mhchdMxmD+SxXcWFK0BKuNdxrAoCeOGAMdUBTLABccuEiyjgvqe09RFG7DrRWdIkwUT1LgxBsJnzUiHvRthHqQcdRzqAIQ1OkOHutHDcLuWZuHebjbA3ZBZPuVVd9MX7YbZi74q/5Af9nlyyau8PZUvh9J+AczJYjnrDG1T78rv9b5u5uTh175Y7R7y6voYqMD/qjTlutd4rhsy6YSsCH2yP1/fv0HSfVm9tBtrmk4fiZUldnVOp8V6PbmBFsdl+kq+EGbbi3jT+WZ626Bnwb+wpgRox7rm1Y102h6O++3zecI6e3L9Cw==

[calamitas]

After looking at the PathFitter code, it's obvious that the least squares method doesn't care whether or not the curve contains any of these big jumps as long as the total error is minimal. I fixed it in our code for now by checking if either of the alphas is too large and reverting to the 1/3 rule in that case (same as for alphas that are too small). At the moment, I check if either alpha is larger than segLength, but this can be refined to check for control points that are 'out of order'.

A second possible issue from an inspection of the code is that reparameterize can generate values for u that are out of order. As you know, Newton-Raphson can overshoot the root, sometimes by a lot, and this causes a later u value to become smaller than an earlier one. I checked and this actually happens for almost any line I draw as long as it is not too straight. Although I haven't found a case where it happens, it is at least theoretically possible that a Bezier can be fitted for this new parameterization. The resulting curve would then hit (or nearly hit) the points in the wrong order.

[calamitas]

Note also that when reparameterize generates u values outside of the range 0 to 1 for some points, the resulting curve segment won't even hit those points.

[lehni]

Great, thanks for looking into this! The code was ported over from Graphic Gems (http://iut-arles.univ-provence.fr/web/romain-raffin/sites/romain-raffin/IMG/pdf/PSchndeider_An_Algorithm_for_automatically_fitting_digitized_curves.pdf)

Would you like to try and fix these errors?

[lehni]

@calamitas would you be willing to share your changes to the code? I'd be happy to accept a pull request.

[calamitas]

Sorry, totally forgot about this.

We used this for a client and I'd have to check with said client to see if we can share the code. If not, I'll recode it in my spare time. I don't know when I'll get around to it as I have little free time for the moment due to a 4 month old baby requiring attention.

[lehni]

Good to hear. I hope the client is happy to give something back, given the fact they're building on a lot of work that we happily contribute.

[calamitas]

Well, we never got an answer from the client, so I suppose the answer is no.

At someone else's request, I redid the fix. You can find the commit here: calamitas@d5c25db .

If you want a test written for the fix, I'll be glad to do so when I find the time. Then I'll send you a pull request.

[lehni]

This is great, thanks a lot! I'll review and merge this in now. Apologies for taking so long to respond.

[lehni]

Fixed in faecea3