Question: linear programming solver and contouring

[tmbb]

I'd like to discuss two features which are probably not realistically possible to implement in Typst itself but which may be possible with some kind of rust bindings (which I believe are impossible with Typsts the way it works now).

Countours of surfaces

While I was implementing my own (very simple and totally not extensible) plotting library in Typst, I noticed that most things were very easy as long as I restricted myself to basic shapes, such as circles, rectangles and paths. This allows one to build plots such as pie charts, bar charts, boxplots, filled plots, Kaplan-Meier survival curves, etc. However, sometimes one might want to represent a smothed version of a 3D surface projected into 2D or a density plot, such as this (taken from the Matplotlib docs):

The colors themselves can be either discrete (using contours) or smooth (with some kind of linear interpolation between contours). The main algorithm used for those contours is the marching squares algorithm, which is slow and hard to implement in a scripting language like Typst. Fortunately, there seem to be very good implementations in rust for contour drawing.

Linear Programming

Something else which is kinda hard to do and which causes problems in many plotting libraries such as Matplotlib is mixing variable and fixed lengths. For examle, suppose you have a boxplot annotated with p values from comparisons beween groups (drawn in matplotlib):

Because matplotlib doesn't handle fixed and variable dimensions inside plots very well, I've had to fix the limits through trial and error. Solving linear constraints for placement of items inside the plot is actually very easy, and doesn't require a real linear programming solver such as the simplex algorithm. However, if you want to take into accound the labels, I believe (but I haven't proved) that you start having to solve general linear programming for it to work. The asymptote library (a [C++ program]() to draw graphics which uses TeX for text rendering actually implements the simplex method to handle these constraints). I believe (but again, I haven't proved) that solving "general" linear programming is required to determine the margins of a plot in more complex layouts such as these:

There exists at least one pure rust implementation of the simplex algorithm for linear programming on any number of variables and constraints, and for the layout problem above, in which wahst is needed is a way to determine the margins of the plot, one can get by with only two variables (one can solve for the left and right margin in each axis independently of the other axes, assuming that the total size of the plot is constant, which it often is). The number of constraints is expectedd to be low because even plot with hundreds or thousands of datapoints only contain a couple elements such as legends and annotations which require solving a linear program. I don't know how feasible it would be to implement the simplex algorithm in typst and how performant it would be for small problems such as these.

Given that someone has implemented the simplex algorithm in pure python (https://github.com/dmishin/pylinprog/blob/master/linprog.py) in a very short file, I think that it shouldn't be too hard to implement in typst (everything that can be done with a python class can be done with a typst dictionary).

3D plotting

Plotting smooth 3D surfaces also seems pretty hard for typst, as it requires handling the way light would reflect on general surfaces or at least fine meshes. While this seems easy with a linear algebra package, such linear algebra would have to be performed in rust.

Conclusions

Currently, I believe there is no way of adding rust bindings to a typst package (and rightly so), so if one wants to be able to draw contours efficiently, such functionality would have to be added to typst itself, right? I don't believe that an interpreted language such as typst would be able to draw contours efficiently for a realistic number of points with the marching squares algorithm.

Regarding 3D plotting, it would require bindings to at least a matrix multiplication library and some vectorized functions optimized to work on large multidimensional arrays or at least matrices. This could have to be implemented in typst and not in a package.

Regaring linear programming, I believe it might be possible to implement the simplex algorithm in typst itself, and that may allow us to have more sophisticated layout algotithms and better automated positioning of graphical elements.

I don't know if this is in scope for this library, but these are ideas I'd like to leave here for discussion.

[johannes-wolf]

Re: Linear Programming You want to auto grow the plot-range with not only plotting data but also manually added annotations/drawings, right? So that axes have margins, that can auto-grow if annotations are outsides the "data area".

[johannes-wolf]

Re: 3D Plotting/Smooth Areas One would need to be able to program a pixel shader. Technically that should be possible with the new image.decode but maybe a bit slow.

It would be really nice if typst had native types for vectors and matrices.

[tmbb]

You want to auto grow the plot-range with not only plotting data but also manually added annotations/drawings, right? So that axes have margins, that can auto-grow if annotations are outsides the "data area"

Yes, you can make the margins grow, but in the most common case I believe you'd have some constraints on the total dimensions of the figure/plot. This means you can't make the margins grow arbitratily. Say you want your plot to occupy an area of 6x4cm. You want your data area to be as big as possible inside the 6x4cm rectangle. The maximum size for the data area will be constrained by the axis labels and such on the outside, and by the annotations on the inside. If the axis labels and such don't depend on the data, then they will be fixed, and we only have to care about the annotations and the margins. But even so, I think that to get the minimum size for the margins one has to find a maximum on a system of inequalities with N inequalities and 2 unknowns. To do that, one must implement something like the simplex method for two variables.

[johannes-wolf]

I first implementation of contouring is here: cetz-package/cetz#243. It is a bit slow, but should work well if the sample size is small. Do you have any realistic functions to measure it with?

[astrale-sharp]

Currently, I believe there is no way of adding rust bindings to a typst package (and rightly so),

There are typst plugins tho that you can write in rust and package as webassembly