Implementation details


The data in a line gadget should be sorted by non-descending x coordinate. In a large data set this allows to quickly find the left and right intersection points with the viewport using binary search and remove the irrelevant data from further processing: clip-by-x. If the resulting sequence is empty (i.e. the entire data set is completely to the left or to the right of the viewport), nothing is drawn (x-in-bounds?).

If there are several points with the same x coordinate matching xmin, the leftmost of those is found and included in the resulting set (adjusted-head-slice). The same adjustment is done for the right point if it matches xmax, only this time the rightmost is searched for (adjusted-tail-slice).

If there are no points with either the xmin or the xmax coordinate, and the line spans beyond the viewport in either of those directions, the corresponding points are calculated and added to the data set (min-max-cut).

After we've got a subset of data that's completely within the [xmin,xmax] bounds, we check if the resulting data are completely above or completely below the viewport (y-in-bounds?), and if so, nothing is drawn. This involves finding the minimum and maximum y values by traversing the remaining data, which is why it's important to cut away the irrelevant data first and to make sure the y coordinates for the points at xmin and xmax are in the data set. All of the above is done by clip-data.

At this point either the data set is empty, or there is at least some intersection between the data and the viewport. The task of the next step is to produce a sequence of lines that can be drawn on the viewport. The drawable-chunks word cuts away all the data outside the viewport, adding the intersection points where necessary. It does so by first grouping the data points into subsequences (chunks), in which all points are either above, below or within the [ymin,ymax] limits (monotonic-split-slice using between<=>).

Those chunks are then examined pairwise by (drawable-chunks) and edge points are calculated and added where necessary by (make-pair). For example, if a chunk is within the viewport, and the next one is above the viewport, then a point should be added to the end of the first chunk, connecting its last point to the point of the viewport boundary intersection (fix-left-chunk, and fix-right-chunk for the opposite case). If a chunk is below the viewport, and the next one is above the viewport (or vice versa), then a new 2-point chunk should be created so that the intersecting line would be drawn within the viewport boundaries (2-point-chunk).

The data are now filtered down to contain only the subset that is relevant to the currently chosen visible range, and is split into chunks that can each be drawn in a single contuguous stroke.

Since the display uses inverted coordinate system, with y = 0 at the top of the screen, and growing downwards, we need to flip the data along the horizontal center line (flip-y-axis).

Finally, the data needs to be scaled so that its coordinates are mapped to the screen coordinates (scale-chunks). This last step could probably be combined with flipping the y coordinate for extra performance.

The resulting chunks are displayed with a call to draw-line each.