Bordering on the Insane — A Story of a Near Collapse

You’ll have to excuse the witty title, but I’ve been working on table borders. Specifically collapsed multi-line borders, properly joined at intersections. It is hard work I tell you. No, really, it’s downright ridiculous.

Some Background

Since a table cell may span multiple rows or columns, along each side of the cell, it may share its border on that side with N neighboring cells, or with the table border. Along each such shared border segment, the neighboring border along that segment must be identified and collapsed with the cell border according to certain rules. The most commonly used rules are those specified in the CSS collapsing border model, sometimes with slight modifications. This is also what I’m aiming for in my implementation.

Lines in Scribus can traditionally be represented by an arbitrary number of lines, each with its own color, width and style, drawn on top of each other, thin over thick. Like this:

A multi-line in Scribus
A multi-line in Scribus

In trying to keep in style, I’d of course like to support these types of lines in my implementation of table borders. This is also supported by competing products such as InDesign.

Borders from different cells, or from the table itself, meeting at an intersection in the table should optionally be joined. Joining is the process of adjusting the start and end points of the border, as well as adjusting the start and end points of the individual lines constituting the border, in order to make a “best effort” join with any other borders meeting at the intersection.

This is where the fun begins. I’ve identified at least these 41 possible cases of joins:

Table Border Join Cases
Table Border Join Cases

The Past ~Two Weeks

In the past two weeks most of my work has been trying to find a joining/painting algorithm that correctly identifies all the cases above and performs the necessary adjustments.

To paint an entire table, the painting algorithm must iterate over all cell edges in the table, and for each edge, iterate over all shared border segments. For each segment, the segment is collapsed with the correct neighboring border. Next, each of the, possibly six, other border segments meeting the segment at its start and end point must also be identified. This means identifying all the cells surrounding the segment and collapsing the appropriate shared border segments between them.

Let’s take a simple case as an example. In the example below we want to paint the top border of the green-tinted cell, which spans two columns. The thin red dotted line represents the underlying table grid.

Painting a Top Border
Painting a Top Border

In the first iteration above, in addition to collapsing the shared border segment between the cell itself and the cell above it, the five border segments coming in to meet it at the two intersections must be identified and collapsed correctly. After that, adjustments for joining can be made to the segment start and end, before the segment is finally painted.

Similarly, in the second iteration, there are four additional collapses that needs to be done before joining adjustments and finally painting can be done.

Needless to say, it’s been quite a chore trying to get this to work. Especially the joining algorithm has been a tough nut to crack. I’ve used up numerous sketch pads trying to figure it out. When working on something like this, pen and paper is invaluable. But, although there are some cases it can’t quite handle in a pleasing way, I think I finally have an approach that will work. I’ve intentionally made the code for collapsing and joining strictly separated from the rest of the code, to ease unit testing.

To not get too complicated the algorithm I’ve settled on imposes a strict painting order — horizontal borders must be painted on top of vertical ones. This means two iteration across the table. Iteration is quite fast though, and besides, I’d rather spend my time optimizing cell accesses on the table than convoluting the joining algorithm with added complexity.

So without further ado, here’s a screenshot of some collapsed joined and non-joined borders on a table in Scribus:

Joined Borders in Scribus
Joined Borders in Scribus

Although there are some bugs in there, I have other fish to fry at the moment, so I’m going to leave painting for a while. And if there’s anyone out there who, after looking at that picture with the 41 join cases I’ve identified, get a brilliant idea for an algorithm that covers them all with a minimal amount of code, then contact me! Please!

That’s all for now. Bye ’til next time!

11 thoughts on “Bordering on the Insane — A Story of a Near Collapse

    1. Case X would just be Case 11 again. The cases all seem to give priority to horizontal lines, so there would be no way to distinguish X from 11.

      1. Right. The approach I’ve taken enforces a strict painting order; horizontal on top of vertical. It simplifies the code a lot. In fact, I’m unsure if it’s even possible without doing so :)

        For those interested. The code that handles these cases are in tableutils.cpp, in the joinHorizontal(…) and joinVertical(…) functions. I had actually forgot two cases. The full list of cases is here.

  1. @Aaron: Hi. I’m glad you’re taking an interest in the project.

    Regarding that approach to joining; it certainly would eliminate a lot of cases, but unfortunately it’s not a proper join.

    Imagine a user wanting to highlight a cell by giving it a thicker border than the surrounding cells. I doubt he/she would want to get a beveled join like that shown in your picture. The cell should stay rectangular.

    But bonus point to you for trying to find ways to cut corners! (no pun intended :)

    Cheers.

Leave a Reply

Your email address will not be published. Required fields are marked *