search

mathandy / svgpathtools

A collection of tools for manipulating and analyzing SVG Path objects and Bezier curves.
MIT License
551 stars 139 forks source link

Approximate cubic Bézie using line segments #28

Closed majdal closed 6 years ago

majdal commented 7 years ago

Hi folks - thanks for the great library.

I'm not sure if this functionality is within the scope of this library, but I'm going to put it up for discussion here anyway.

I'd like to approximate a CubicBezier with a series of Line objects. This has many applications, for example in drawing SVGs using an XY plotter (which is my specific need).

The trivial way to do this is to divide the curve into an equal number of points and create Line objects connecting each new segment along the path. This however is not guaranteed to give a good representation of the curve, and is likely to contain an excessive number of points.

A good way to make this approximation is to do it in an adaptive way. Break the curve into smaller curves (CubicBezier.split()) until a certain flatness criterion is met. After doing a bit of research, this seems to be the most referneced article on the subject. The method is critiqued here, especially for not having consulted prior academic research on the subject.

I'd like to implement something like this, and possibly contribute it to this library if you see that it would fit. But before I do so, I'd like to get your recommendations on what algorithm would be appropriate for this purpose.

The antigrain algorithm is one possibility, and in the google groups thread there's another interesting suggestion:

A well-known flatness test is both cheaper and more reliable than the ones you have tried. The essential observation is that when the curve is a uniform speed straight line from end to end, the control points are evenly spaced from beginning to end. Therefore, our measure of how far we deviate from that ideal uses distance of the middle controls, not from the line itself, but from their ideal arrangement. Point 2 should be half-way between points 1 and 3; point 3 should be half-way between points 2 and 4. This, too, can be improved. Yes, we can eliminate the square roots in the distance tests, retaining the Euclidean metric; but the taxicab metric is faster, and also safe. The length of displacement (x,y) in this metric is |x|+|y|.

What do you suggest as a good algorithm to implement in this case? Would love some feedback.

majdal commented 7 years ago

I found this very nicely written article with an elegant and clearly derived flatness test.

mathandy commented 7 years ago

Hi @majdal, this would be great functionality for svgpathtools to have. If you want to contribute a stand-alone function to do this, please do so. I'm busy with other projects and couldn't offer any significant help though. If you decide to do this, please take a look at the svgpathtools Contributor Guidelines.

I'll leave this issue for now as it may provide valuable information to someone or lead to further discussion.

mathandy commented 6 years ago

Further information and a simple solution to this is posted in issue #61