Attempting to SVG some ASCII art diagrams

ZkAWHR

I made thing for this website/Glorpdown a little while ago. Thing that lets me render a diagram made with ASCII art as SVG on a webpage. So I can do:

``` drawing
.-------.   .-------.
| hello +-->| world |
'-------'   '-------'
```

And get:

(I kind of like that the diagrams are there when viewing the plaintexty Glorpdown and not just when viewing the rendered HTML.)

I looked a bit around before I made it. I tend to look for something like, some ways of thinking about the problem and maybe dividing it into subproblems, different approaches, tradeoffs, maybe some "patterns." I don't usually find what I'm looking for though. Found some existing solutions, but couldn't be bothered digging into them and figuring out what the important ideas were etc. So I just ended up doing something:

Line segments and shapes

One thought I had was something like: If you draw a rectangle with ASCII art, maybe the thing should figure out that it's a rectangle and make an SVG <rect>, and so on. The alternative seemed to be to process one character at a time: If the character's a hyphen, we make a little horizontal SVG <line>, and so forth. I think it sounds nice to have an SVG with reasonably few, uh, "appropriate" SVG shapes in it. And less nice to have one with a ton of tiny lines that happen to form shapes.

So I had some thoughts like, if I find a hyphen, should I like try to follow along that line to see what shape it makes? And then, how do I deal with this-or-that? Should I "consume" a character once I've processed it as part of a shape? What if it's part of another shape as well? How do I know e.g. which way to follow it at the plus sign on the hello box there? Bunch of stuff that sounded like stuff that I didn't want to deal with.

So eh. Decided to do the one character at a time thing. If I did that and also had some "line joining" machinery, then I could probably keep things fairly simple in my head and also keep the SVG from getting too bad.

Like if you added a line from (1, 1) to (2, 2) and then a line from (2, 2) to (2, 1), the machinery would join those together. If you then added a line from (3, 3) to (4, 4), that would not connect to any existing (poly)line, so you'd end up with two "shapes:" One polyline from (1, 1) to (2, 2) to (2, 1), and one line from (3, 3) to (4, 4).

Anyway. The following is a somewhat minimal example. The version I'm using for the website has more stuff. It makes lines out of more characters, it does some SVG <text> for regular text, handles Unicode stuff a little. But like the important ideas or the fundamentals or something should be in the example.

We'll only do vertical and horizontal lines (hyphens and pipes) and plus signs that can connect in all 4 direction. And we'll try to turn something like this:

+----------+
| +--+ +-+ |
| |  | +-+ |
| |  +-----+
+-+--+     |
+----------+

Into something like this:

So we'll be using this as a test string:

teststring = [[
+----------+
| +--+ +-+ |
| |  | +-+ |
| |  +-----+
+-+--+     |
+----------+
]]

Drawing some stuff

We wanna draw some SVG stuff. We need points:

Point = {}
allpoints = setmetatable({}, { __mode = "kv" })
function point(x, y)
  local key = x .. "," .. y
  local res = allpoints[key]
  if res then return res end
  res = setmetatable({ x = x, y = y }, Point)
  allpoints[key] = res
  return res
end

function Point:__add(other)
  return point(self.x + other.x, self.y + other.y)
end

function Point:__tostring()
  return "(" .. self.x .. ", " .. self.y .. ")"
end

U, R, D, L = point(0, -1), point(1, 0), point(0, 1), point(-1, 0)

Testing:

print(D + R + R)
print(D + R + R == point(2, 1))
print(D + R + R == R + R + D)
print(D + R + R == R + R + R)

We make sure that for any x/y-combination, there only exists one instance of a point. That's nice if we want to compare points with == or use them as keys in tables. It's like generally pretty convenient.

We'll make SVG. Here's SVG functions:

xscale, yscale = 8, 8

function svgopen(w, h)
  return '<svg width="' .. w * xscale .. '" height="' .. h * yscale ..' ">'
end

function svgline(tag, color, points)
  local res = { '<', tag, ' stroke="', color, '" points="' }
  for p in points do
    table.insert(res, p.x * xscale .. "," .. p.y * yscale)
    table.insert(res, " ")
  end
  res[#res] = '" />'
  return table.concat(res)
end

Because reasons, svgline takes an iterator function as its points argument, instead of e.g. a table/array. We'll make a helper function for testing:

function it(list)
  local i = 0
  return function()
    i = i + 1
    return list[i]
  end
end

Can make a drawing now:

local list1 = { point(1, 1), point(11, 1), point(11, 11) }
local list2 = { point(1, 1), point(1, 11), point(11, 11) }
local list3 = { point(3, 3), point(10, 6), point(2, 9) }
web.html(
  svgopen(12, 12) ..
  svgline("polyline", "white", it(list1)) ..
  svgline("polyline", "pink", it(list2)) ..
  svgline("polygon", "yellow", it(list3)) ..
  '</svg>'
)

Great.

Map of chars

We wanna turn a string into a data structure that lets us treat things as kind of a 2D map. The details aren't terribly important, but here's some thing:

function mapfrom(str)
  local chars = {}
  local res = { w = 0, h = 0, chars = chars }
  local x, y = 0, 0
  for c in str:gmatch(".") do
    if c == "\n" then
      y = y + 1
      x = 0
    else
      chars[point(x, y)] = c
      x = x + 1
      res.w = math.max(res.w, x)
    end
  end
  res.h = y
  function res.at(p)
    return chars[p]
  end
  return res
end

We'll test it a little:

print(teststring)
local map = mapfrom(teststring)

local function str(x, y)
  return '"' .. map.at(point(x, y)) .. '"'
end
print(str(0, 0), str(1, 0), str(0, 1), str(1, 1), "\n")

for y = 0, map.h do
  local str = {}
  for x = 0, map.w do
    table.insert(str, map.at(point(x, y)))
  end
  print(table.concat(str))
end

Seems fine.

Processing chars

We'll deal with the line joining machinery later. In order to have something to program against, we'll make something that doesn't actually join any lines:

function nojoining()
  local res = {}
  function res.add(from, to)
    table.insert( res, { points = function() return it({ from, to }) end })
  end
  return res
end

Okay. I dunno. I like to think of each character as occupying some space within the larger map, but kind of having its own local coordinates. Characters are often roughly twice as tall as they are wide, particularly in monospacey ASCII art stuff, so e.g. 4 by 8:

So then we can think of the top left of the character as (0, 0), the middle as (2, 4), the bottom right as (4, 8), and so on.

Characters that are next to each other mildly overlap:

(4, 0) of one character is the same point as (0, 0) of the character to its right, etc.

When we're processing a character, we can have a helper function that translates coordinates like those into global coordinates. We'll make a helper function function:

function halphalp(lines, p)
  local off = point(p.x * 4, p.y * 8)
  return function(from, to)
    lines.add(off + from, off + to)
  end
end

Let's turn some characters into lines. We turn hyphens and pipes into horizontal and vertical lines. Plusses add lines connecting to neighbours, if there are any neighbour characters of the right kinds. We could image expanding this a lot, but like the essence is probably there: Adding lines, possibly depending on neighbours.

function makelines(map)
  local res = lines()
  for p, c in pairs(map.chars) do
    local add = halphalp(res, p)
    if c == "|" then
      add(point(2, 0), point(2, 8))
    elseif c == "-" then
      add(point(0, 4), point(4, 4))
    elseif c == "+" then
      local l = map.at(p + L)
      local r = map.at(p + R)
      local u = map.at(p + U)
      local d = map.at(p + D)

      if l == "-" or l == "+" then
        add(point(0, 4), point(2, 4))
      end
      if r == "-" or r == "+" then
        add(point(2, 4), point(4, 4))
      end
      if u == "|" or u == "+" then
        add(point(2, 0), point(2, 4))
      end
      if d == "|" or d == "+" then
        add(point(2, 4), point(2, 8))
      end
    end
  end
  return res
end

We're only adding line to the space occupied by the current characters. In my head I kind of organize the different characters as:

Line characters: Just add a line without caring about any context or circumstances.
Connector characters: Add connections to neighbours.

It seems maybe disciplined or something to me, but I'm sure we could have made the line characters look for neighbouring connectors instead.

Also: When looking at neighbours we kind of know about the different characters and what they mean. We could almost imagine looking at the points in the "linespace" or something instead. Like "if there's something at my (4, 4), draw a line connecting to it." But it sounds like it'd get messy trying to deal with "there's nothing at my (4, 4), but maybe there's going to be" stuff...

Eh. When we got lines, we can make SVG:

function makeSvg(map)
  local lines = makelines(map)
  local w = (map.w + 1) * 4
  local h = (map.h + 1) * 8
  local res = { svgopen(w, h) }
  for _, l in ipairs(lines) do
     if l.points then
       local tag = l.closed and "polygon" or "polyline"
       table.insert(res, "\n  ")
       table.insert(res, svgline(tag, color(), l.points()))
     end
  end
  table.insert(res, '\n</svg>')
  return table.concat(res)
end

Test:

print(teststring)
lines = nojoining
function color() return "white" end
web.html(makeSvg(mapfrom(teststring)))

Looks okay.

Lots of tiny lines

Okay so just to illustrate that we're drawing very many tiny lines this way, we'll mess with the colours:

coloridx = 0
colors = { "white", "red", "yellow" }
function colorcycler()
  coloridx = coloridx + 1
  local res = colors[coloridx]
  if coloridx == #colors then coloridx = 0 end
  return res
end

lines = nojoining
color = colorcycler
web.html(makeSvg(mapfrom(teststring)))

Those are several.

Lines that can be extended

A few things:

Want lines that can be extended in either direction
When we add a line, we must be able to figure out what to do: Add a new line, extend an existing, join two lines, or join a line to itself (close it and make a polygon instead of a polyline)
Also also like, when we figure out what to do we wanna like, do that thing

For the extending in either direction part: One way to do it is to just have two array-like tables. Like a polyline with six points could look like this:

Like, if a polyline consists of one 2-element array (first) and one 4-element array (last), the full polyline would go like:

first[2], first[1], last[1], last[2], last[3], last[4]
Or, in the other direction: last[4], last[3], last[2], last[1], first[1], first[2]

So you kind of count down in one array and then up in the other one in order to get all the points in a reasonable order. Makes it so you can always add new points to the end of one of the arrays in order to extend the polyline.

Some supporty helpy stuff. If a "half" of a polyline is an array connected to the other half, we can make an iterator function that counts down through the half we start with and then up through the one that it's connected to:

function halfandhalf(first)
  local last = first.other
  local current
  local i = #first
  local function lastpoints()
    local res = last[i]
    i = i + 1
    if i > #last then current = nil end
    return res
  end
  local function firstpoints()
    local res = first[i]
    if i == 1 then current = lastpoints
    else i = i - 1
    end
    return res
  end
  current = firstpoints
  return function()
    return current and current()
  end
end

An test:

local last = { "c", "d", "e", "f" }
local first = { "b", "a", other = last }
last.other = first
print("from one side:")
for c in halfandhalf(first) do print(c) end
print("\nfrom the other:")
for c in halfandhalf(last) do print(c) end

Later on, if we're extending a line and we're not changing direction, we can move the end of the line instead of adding a new point to it. Some direction helper stuff:

function dir(from, to)
  return point(to.x - from.x, to.y - from.y)
end

function samedir(a, b)
  if a.x == b.x and a.y == b.y then
    return true
  elseif a.x == 0 and b.x == 0 then
    return (a.y > 0 and b.y > 0) or (a.y < 0 and b.y < 0)
  elseif a.y == 0 and b.y == 0 then
    return (a.x > 0 and b.x > 0) or (a.x < 0 and b.x < 0)
  else
    return false
  end
end

Those functions are not very smart. People with smart could make better versions of those. But they're fine for our use.

Line joining machinery

So uh, the actual joining machinery then. Same interface as nojoining. We want to create something that has an add function that takes two points. And after adding a bunch of stuff, we want the thing to be an array with a bunch of stuff. If an element in the array has a points function, then we can call that to get an iterator function for the points in a polyline/polygon.

Internally, it will also keep track of where lines end and can be extended. Whenever something is added (lines.add below), the two points are looked up in extendible. The lookup returns the "half" that can be extended, if any.

If neither points is extendible, a new polyline is added with line
If one point is extendible, then the half we found is extended wiht extend
If both points are extendible, the two things we found are joined

A polyline is joined to itself (if the two halves we found are each others others) by closing it (turning it into a polygon). A polyline is is joined to another one by removing the one with the fewest points and axtending the one we're keeping with all the points from the one we're removing. (With a different data structure for the polylines, we could have made polylines consist of more than two arrays when joining instead I guess. Not something I've bothered with but I dunno, might be fun.)

And we modify extendible as we go: When we add new lines we add two extension points, one for each half. When we extend a half, we move (remove and add) its extension point. And when we join things we remove two extension points.

A function with a bunch of functions in it. The lines are very managed by the joining machinery, so I just put all of the stuff inside it. I dunno, I'm sure some stuff could be extracted, like maybe the extendible stuff could exist as more its own thing, but I haven't really felt like it...

function joining()

  local lines = {}
  local extendible = {}

  local function line(from, to)
    local lineinfo = {}
    local half = { from, dir = dir(to, from), info = lineinfo }
    local other = { to, other = half, dir = dir(from, to), info = lineinfo }
    half.other = other
    function lineinfo.points() return halfandhalf(half) end
    table.insert(lines, lineinfo)
    extendible[from] = half
    extendible[to] = other
  end

  local function extend(half, point)
    local i = #half
    local prev = half[i]
    extendible[prev] = nil
    extendible[point] = half
    local newdir = dir(prev, point)
    if not samedir(newdir, half.dir) then
      i = i + 1
    end
    half[i] = point
    half.dir = newdir
  end

  local function unstend(half)
    extendible[half[#half]] = nil
  end

  local function join(first, last)
    if first == last then
      error("oh no")
    elseif first.other == last then
      first.info.closed = true
      unstend(first)
      unstend(last)
      return
    else
      local flen = #first + #first.other
      local llen = #last + #last.other
      local keep, remove
      if flen >= llen then keep, remove = first, last
      else keep, remove = last, first end
      unstend(remove)
      unstend(remove.other)
      remove.info.points = nil
      for p in halfandhalf(remove) do
        extend(keep, p)
      end
    end
  end

  function lines.add(from, to)
    local first = extendible[from]
    local last = extendible[to]
    if first and last then
      join(first, last)
    elseif first then
      extend(first, to)
    elseif last then
      extend(last, from)
    else
      line(from, to)
    end
  end
  return lines
end

Let's test:

lines = joining
color = colorcycler
web.html(makeSvg(mapfrom(teststring)))

Fewer line elements :)

We can also see what the SVG looks like as text, and like confirm that there's a polygon in there and stuff:

lines = joining
color = colorcycler
print(makeSvg(mapfrom(teststring)))

Let's draw something else just because why not:

lines = joining
function color() return "white" end
web.html(makeSvg(mapfrom([[
+---+
| + |
| | |
| +-+-------+
|   | +++++ |
+---+ +++++ |
    | ++ ++ |
    +-------+
]])))

Okay.