Drawing a Tree on Canvas with XY Coordinates
A detailed design, development, and recursion analysis to draw a tree data structure with HTML Canvas and TypeScript are given from the solution tree feature implemented into the 2DP Repsymo Solver for the machine replacement model from the operations research field.
The result is a web app that renders an MRM solution tree within 2D coordinates.
Original MRM Problem
The Machine Replacement Model (MRM) is a deterministic dynamic programming model from operations research. It states that we have a machine with an initial age. We have a number of decision years to know what to do with that machine. Then, for each decision year, there are two options: keep the machine and pay maintenance (K), or replace the machine with a new one (R). All the possible outcomes starting from the first decision year can be visually represented as a tree that grows on the horizontal axis or the same, the independent variable (decision year).
The first solution tree version depicted below was made with HTML, CSS, and
the DOM API (
div elements). That version can be found at
It’s recommended to check it out to understand the problem better and get
textbook references. It’s also advisable to review the
Repsymo Solver for a complete insight into this model
Chances are obviously limited and the connecting lines from a node to its next nodes are missing (hence the pairs \((K, R)\) as labels). The other problem is that the data structure was a two-dimensional array but the underlying model corresponds to a tree. This solution was a very good fit back in the day for moving forward faster with the development.
The problem consists of populating the binary tree data structure onto a canvas and also the XY-axes to establish each node’s position.
A browser canvas2 (or canvas in general) is not the best performant solution3 but is a great step for this problem in terms of rendering and correctness.
Other Kinds of Trees
Another more common tree data structure is a file explorer which loads your directories and files from your disk. For working with trees we natively implement recursion as the natural or mathematical definition of the problem. Here is another project showing some recursion and designed to work with file systems CP: Distributed Text File System where its left panel with a populated-root-directory is also a tree.
Tree Data Structure
As said above, the nature of many problems is recursive.
There are many ways of representing trees, and one of them is the underlying topic of this article: the solution tree of the MRM. Others are file systems, and so on.
When a wrong data structure is applied (due to engineering constraints) like two-dimensional arrays (cartesian coordinates) to model what actually is a tree (recursive) in this case, algorithms arise, and they’re limited, convoluted, and prone to errors.
Applying the right data structure to a model has more engineering efforts, but it homogenizes the problem down to a simple model that is elegant and correct, in other words, the model matches4 the representation.
EP: MRM Solution Tree
Two elements are required to draw on the canvas: the 2D axis and the tree that grows horizontally. These two elements are what the solution tree application to render consists of.
Create into your HTML a
div containing the
canvas in which we are going to
Some styles can be added.
Now everything will be programmatically developed.
Create the module
mrm-canvas that is going to be developed. It’s going to
contain the following specification that is going to be detailed along with this
This function is going to help with some calculations:
- root-node.json: sample tree object to render.
- mrm.ts: assumed data model.
- mrm-canvas.ts: underlying module.
- gh-pr: pull request containing the initial step-by-step development.
- triangle.py: generates the rectangle triangles figure.
The solution tree for the machine replacement model consists of the following data type:
It follows that the independent variable \(x\) is going to be the
attribute and the dependent variable \(y\) the
machineAge. The tree is binary
so can have two children:
Thus, we have a binary tree to draw on an XY-plane.
This data structure is an external given model, so it should be added, say,
The following base class is going to manage the canvases. It has the
HTMLCanvasElement (with its respective context) member so the drawing is
performed on that canvas element. The init method sets the canvas element and
its size according to its parent element. The render method runs a standard game
loop operation when the model is updated and then the drawing is performed with
the new model values computed. That means the tree can be re-rendered in
different states if the
render method is called.
Drawing the Axes
First, the axes lines are easily drawn:
To draw the \(X\) axis labels, set the text-align center and draw the abscissa
value from \(0\) until a maximum set value. There is a variable
that tells the width and height of each cell in the XY-plane (first quadrant).
For drawing the \(Y\) axis labels some minor considerations are taken into account to draw it properly.
These results are compiled into the
Drawing the Tree
The tree canvas is quite more complicated. The class consists of the following structure:
Notice we have:
- An axes canvas: To draw the axes.
- The root node: The tree data structure that is going to be drawn.
- A radius: A computed value for a node’s radius.
- Memoization: To avoid drawing nodes that have already been drawn due to the recursive algorithm.
Finally, yes, the
drawNode method is going to be the recursive function. You
can start noticing it is called to draw the root node, so it ends up drawing all
the children recursively.
Regarding the helper method
getNodeCP we have the following code to get the
center point of the given
Drawing a Node
This is the recursive function to populate the whole tree from the root node. We take care of memoization to dynamically store the drawn nodes. For correctness effects, we always render the node circle and its content but the node lines and labels (which are visually significant if rendered more than once) are only rendered once.
So, it takes three steps:
- Draw the outgoing lines with their corresponding labels.
- Draw the circle with a background and border.
- Draw the node content consisting of its
drawNodeLines calls back to this method so initiates the recursion
process. That one is left to the end as it’s the harder.
Node Circle and Content
These are pretty straightforward.
To draw the circle:
To draw the content inside the node:
Notice in the call to
measureText, we use an advanced Canvas API to get the
text height and be able to center it vertically. It is horizontally centered
ctx.textAlign = 'center'.
By running at this stage we obtain the first node drawn representing the initial decision year:
Line with Labels from Node-to-Node
First, we need some definitions to address this challenge:
The \((x, y)\) coordinates are the center of the node (Center Point). The arrows tell us if the next node is just to the right of the current node (iff both nodes’ ordinates are the same and equal to \(1\) for this problem).
Drawing the line is straightforward:
The rectangle triangle defined by the two-node points is going to be useful for computing the directions for the outgoing lines from the current node to the next one. We simply use similar triangles to obtain the requesting points.
With that information we can draw the lines according to the corresponding quadrant: up, straight or right, down. The next node is always to the right as the decision year always increases.
Then just call one of these functions to draw the appropriate line:
Finally, to implement the method
drawNodeLines we draw the line to the
“Keep” node and to the “Replace” node by making use of recursion:
The initial method
drawNode is called recursively (recall that
the caller and
drawNodeLines is the callee) and the
set is carried to the method call.
Enhancing Rendering Sizes
For managing more proper rendering sizes this may be an idea.
Another option is to call the method
init on window size changed, adding
scroll, etc. Performance should be considered here.
By importing the developed module, the API is then consumed as follows:
By running now, we get the desired result:
The result is deployed to the example project app.
Analysis on correctness and performance is detailed.
If we remove the memoization, nodes will be rendered more than once which is not acceptable. The results are shown below. Recall that we still render the node circle and content to fix incorrectness but the lines and labels must not be drawn more than once. Excluding the lines (and labels) drawing is a partial drawing, so we only draw the circle and content.
The tree is binary, contains \(15\) nodes, and we get the following number of renderings:
|With Memoization (partial drawings)||15|
|With Memoization (whole and partial drawings)||21|
drawNode function is called \(21\) times to render the whole
tree but just \(15\) of those are full rendering.
With memoization off is visually clear that nodes are being rendered on top of themselves, so it’s easy to spot that flaw (notice node \((4, 1)\) for instance):
The problem, if we use full memoization, is as said before, correctness:
The optimization can be addressed by computing a more accurate model and just drawing the exact required line tangent to the nodes, so they don’t overlap with the other content.
Order of Rendering
By counting the time a node was drawn with full memoization and drawing that position on top of the node as a blue/purple counter we can easily debug or follow the recursion process.
Recall that, as said above, the last nodes from the bottom are partially drawn more times later.
From the equipment replacement problem, we have one or more solutions that tell us what to do with the machine from the first decision year (result chains). For a given year, it might turn out that both options, keep and replace, yield the exact same effect, hence we have a bifurcation or fork: we have to follow two branches if we keep and if we replace. This produces a directed graph structure that looks similar to the tree that was developed.
Result Chains: Replace the first year and then, two ways can be taken for the next year.
Since the solution tree is the set of all possible solutions to the problem, and particularly, the model solution belongs to the tree which, with more clever work can be traced onto the same solution tree:
Traced Solution Tree: The model solution can be drawn into the tree.
Check out Pull Request: Implement solution tracing on mrm solutions-tree to learn more about it.
Caveats on Recursion
Many design and performance issues should be deeply addressed but that’s another topic. The problem is that languages like TS/JS and platforms like web browser runtimes are not good for these problems.
Recall that, just functional languages implement TCE and TCO at first class so the engineer or mathematician must be careful when using recursion. For mainstream languages, imperative loops are to be used instead.
When it comes to mathematical models it’s key to design declarative systems but general-purpose computers don’t support many abstractions and unfortunately, recursion is not so widely used due to the hardware being imperative as an obstacle.
In other words, be careful when using recursion. Recursion is key for defining mathematical models but computers don’t understand math really well and imperative loops are preferred for most implementations unless you know what you’re doing.
That is not a problem of recursion as is, but a problem of computers, so use recursion as a mathematician but think about it when engineering.
Solution Tree Feature
This case study for the feature
Solution Tree | MRM | 2DP Repsymo Solver
is taken to obtain insight and then employ the machine replacement model and
the HTML5 Canvas API to address the modeling and design of this feature into a
typescript module providing rendering for XY-axis and the solution tree.
Basic trigonometry is needed to render some elements, like similar triangles which are useful to position the node labels.
Standard memoization with a
Set helps to fix and optimize the recursive tree
traversal rendering and detailed analysis on the recursion used as well as
further insight on how this feature is evolving in the Repsymo Solver
complements the understanding of this topic.
Example Project: Machine Replacement Model was the first and main OR project devised and developed by Tobias Briones to solve and be able to explain the MRM to eventually end up building the 2DP Repsymo Solver ↩
A Canvas is a popular, more flexible, and performant tool for specific graphics than a user GUI library like for example the HTML DOM API or Android Views, but it’s a lower-level API, so it requires more work and design which is probably what we’re looking for ↩
A Canvas is a lower-level tool than a GUI toolkit, but it’s far from the advanced top-performant techniques ↩
Notice FP pattern matching ↩