path simplification can decrease the smoothness of data plots

Michael Droettboom <mdroe@...552...> writes:

I've checked this change into SVN so others can test it out.

Assuming we don't discover any cases where this is clearly inferior, it
should make it into the next major release.

Mike

Hi,

This change looks good- it has the advantage of choosing points that actually
lie on the curve, which is better visually, and would seem to be a better
solution for publication quality plots.

The method for simplifying the paths is quite simple and effective, but a bit
crude- there are other algorithms you might look into for simplifying lines:

  http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm

This one is fairly simple to implement and has the advantage that you have some
control over the errors- the deviation from your simplified path and the actual
path.

Also, you might consider to make the path simplification tolerance (perdNorm2)
an adjustable parameter in the matplotlibrc file:

  #src/agg_py_path_iterator.h

    //if the perp vector is less than some number of (squared)
    //pixels in size, then merge the current vector
    if (perpdNorm2 < (1.0 / 9.0))

kind regards,

a

a wrote:

Michael Droettboom <mdroe@...552...> writes:

I've checked this change into SVN so others can test it out.

Assuming we don't discover any cases where this is clearly inferior, it should make it into the next major release.

Mike

Hi,

This change looks good- it has the advantage of choosing points that actually
lie on the curve, which is better visually, and would seem to be a better
solution for publication quality plots.

The method for simplifying the paths is quite simple and effective, but a bit
crude- there are other algorithms you might look into for simplifying lines:

  http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm

This one is fairly simple to implement and has the advantage that you have some
control over the errors- the deviation from your simplified path and the actual
path.
  

Thanks for the pointers.

The original simplification code was written by John Hunter (I believe), and I don't know if it was designed by him also or is a replication of something published elsewhere. So I take no credit for and have little knowledge of its original goals.

However, IMHO the primary purpose of the path simplification in matplotlib is to improve interactive performance (and smaller file size is just an convenient side effect of that), I would hesitate to use an algorithm that is any worse than O(n), since it must be recalculated on every pan or zoom since the simplification is related to *pixels* not data units. Even on modern hardware, it is a constant battle keeping the inner drawing loop fast enough. We could, of course, make the choice of algorithm user-configurable, or use something more precise when using a non-interactive backend, but then we would have two separate code paths to keep in sync and bug free --- not a choice I take lightly.

The trick with the present algorithm is to keep the error rate at the subpixel level through the correct selection of perpdNorm. It seems to me that the more advanced simplification algorithm is only necessary when you want to simplify more aggressively than the pixel level. But what hasn't been done is a proper study of the error rate along the simplified path of the current approach vs. other possible approaches. Even this latest change was verified by just looking at the results which seemingly are better on the data I looked at. So I'm mostly speaking from my gut rather than evidence here.

Also, you might consider to make the path simplification tolerance (perdNorm2)
an adjustable parameter in the matplotlibrc file:

  #src/agg_py_path_iterator.h

    //if the perp vector is less than some number of (squared)
    //pixels in size, then merge the current vector
    if (perpdNorm2 < (1.0 / 9.0))
  

That sounds like a good idea. I'll have a look at doing that.

Mike

···

--
Michael Droettboom
Science Software Branch
Operations and Engineering Division
Space Telescope Science Institute
Operated by AURA for NASA