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.