Hey all, I’m looking for a library that can adaptively sample parametric plots (for reasonably well-behaved functions). I’m on the verge of writing a little library here but it seems like so many people would want this that I feel it “should” already exist. Does anyone have a pointer?
Problem description
Say I have two functions f, g :: Float64 -> Float64 and I want to plot the parametric plot of the [(f(t), g(t)) for t in T] and the task is to choose T such that the resulting plot shows a decent level of detail in some given interval of f(t) values.
This problem is nontrivial for two reasons:
f is not linear in my case, so I shouldn’t choose T uniformly spaced: this would run the risk of giving me inefficiently many samples in some subset of the f(t) points and too few samples in some other subset, hiding detail.
And then g(t) is of course not necessarily linear in f(t), so ideally I’ll want more samples where it has higher curvature.
Problem 1. is more severe for my specific use case because there’s a high risk of just going “blind”.
An obvious special case of this is non-parametric adaptive plots, i.e., f = identity.
Approach
In my case, f and g are reasonably well-behaved: they’re both differentiable with derivatives computable via ForwardDiff, f is even monotonic, etc.
The algorithm itself is not super complicated: successive bipartition and checking the derivative (or honestly just checking the function value against linear approximation) should do the trick. And then I want some safeguards against too many samples, error threshold, etc.
Some libraries that don’t seem to do the trick
AdaptiveSampling.jl seems to be more about compressing oversampled signals than what I wanna do.
Someone suggested Mamba could do something clever, but I don’t know and it’s 5 years out of date and incompatible with everything else I’m using by now.
One might be able to do something with ApproxFun but I don’t really need global approximation.
I see you created ParametricAdaptiveSampling.jl. Since you mention Meshes.jl in your README, I am wondering whether you saw that Meshes.jl already supports parametrized curves. It also already has different sampling methods, which work with the ParametrizedCurve type. I guess your specific implementation of an adaptive sampling you implemented in ParametricAdaptiveSampling.jl is not yet supported (I haven’t looked at your algorithm in detail), but maybe it would make sense to think about adding this sampling method to the set of continuous sampling method. The benefit of this would be that you or any user of the adaptive sampling could use all of the machinery of Meshes.jl and that Meshes.jl already provides some useful helpers that you can probably reuse in your implementation. It would also probably lead to a higher visibility. Another benefit can be that it probably very well generalizes to other types of curves, such as BezierCurve, for which a parametrization is already defined in Meshes.jl. Pinging @juliohm since he might me interested and can also provide better guidance than me if you indeed consider adding this (really nice!) functionality to Meshes.jl.
Thank you for the ping @JoshuaLampert ! I fully agree with your comment and suggestions. IMHO, the Julia community is too tiny to afford isolated efforts.
I couldn’t find the ParametricAdaptiveSampling.jl repository though. The Discourse link is redirecting me to a “Page not found”. What is the full URL?
Oooh! Well looks like I was right, it is related! Thanks a lot for the ping! I’ll cancel my registry inclusion request (in time lock right now) for now and check if this can be leveleraged or maybe become a simple wrapper, or just evaporate tbh. Fully agree on isolated efforts.
@JoshuaLampert making progress at the speed of a sand dune here, but making some progress at least. I’m trying to make some comparisons vs the methods already in Meshes.jl. Could you answer a few questions:
Do I understand correctly that sample() has no interface to get the parameter values (t)? I have this in my code and while I don’t use it a lot, it could be useful in some situations where the parameter values are meaningful.
Can you give some pointers for the structure of Meshes to write algorithms? This is mainly towards generalizing the algorithm to n parameter dimensions. E.g., how would I start with some initial set of points (probably a square) and successively split it into triangles according to some rule?
Maybe a good entry point is: can you represent iso surfaces or functions on n-dimensional domains currently?
I believe that is true. I agree that in some cases it would make sense to have access to the parameter values. It would be cool to extend the interface to also allow sample to return the parameter values in addition to the sampled points. The details of how that would be implemented need to be discussed. What is your opinion on that, @juliohm?
Probably @juliohm can give the best guidance here as he has a better overview of the algorithms. Maybe as a first step, one could restrict the method to only one-dimensional ParametrizedCurves (and probably also other 1D curve types like BezierCurve, which should be able to simply reuse the same code) to have a starting point and make implementation and review easier. This could be extended in a later step to more general geometries in higher parameter dimensions. This could be done by creating a method for sample like sample(::AbstractRNG, geom::ParametrizedCurve, method::AdaptiveSampling).
Do you mean something like ParametrizedCurve for n parameters? Currently, this is not available in Meshes.jl. There is quite some discussion about this starting at Add `ParametrizedCurve` by JoshuaLampert · Pull Request #1093 · JuliaGeometry/Meshes.jl · GitHub and the following comments on this PR. I always wanted to add parametrized geometries in higher dimensions, but didn’t find the time yet (and probably won’t find it soon).
Generally, I would recommend to split this up into some smaller PRs rather than trying to put everything in one PR. For easier communication, you can also join the #meshes.jl channel on Zulip. Thanks a lot for considering a contribution!
Thank you @srs for considering the contribution! and @JoshuaLampert for leading the discussion!
Could you give an example of these situations where the parameter values are meaningful?
As @JoshuaLampert already explained, we follow the same code pattern in the entire Meshes.jl codebase where we define method types like AdaptiveSampling, holding parameters, and then have a single verb like sample(::AbstractRNG, geom, method::AdaptiveSampling) to represent the operation. You can find all the sampling methods in the sampling folder:
From what I recall, you are only interested in ContinuousSamplingMethod subtypes.
I couldn’t share a better recommendation! Please join us in our Zulip channel if you can. There we can interact very quickly to polish ideas and design.
Thanks a lot for the ping! I’ll cancel my registry inclusion request (in time lock right now) for now and check if this can be leveleraged or maybe become a simple wrapper, or just evaporate tbh. Fully agree on isolated efforts.