Monday, January 16, 2012

Thinking about Diagrams and Figures with Constraints

I have a small website for teaching kids to program, and I've long wanted to translate it into French and other languages. Being a website geared towards kids, the website has lots of diagrams and figures. Many of these diagrams contain text, so I would need to new versions of about 100 diagrams for each additional language I wanted to support with my website. Obviously, sitting around redrawing the diagrams for each new language would be impractical, especially for languages that I'm personally not familiar with. So I need some system that will let me define my diagrams in a generic way, substitute in different translations for the text, and then generate different versions of the diagrams for different languages.

The crux of the problem is that text might be different sizes in different languages. In English, you might use one word to describe something, but another language might use 5 words to describe the same thing. As a result, the diagrams need to lay themselves out differently depending on the size of the text. I've been trying to find a tool to do that, but I've been having problems figuring out what terms to use in the search. Right now, I'm just trying to understand what sort of tools are available in the space or, given that I probably have to write a chunk of code to substitute in the text translations anyway, how hard it would be to write a simple one from scratch.

Internationalization is a common problem in user interfaces, so coders commonly use a constraint-based layout scheme for their user interfaces in order to avoid this problem. Basically, you have some simple patterns or templates that define how UI elements should be arranged with respect to one another, and then you stick UI widgets into those templates. So you might have a row of widgets, or a grid of widgets, etc. This doesn't necessarily work too well for diagrams because the layouts tend not to be as rigid as in UIs. I was thinking that I could build a more complex version of the system where the diagram designer simply inputs arbitrary layout constraints (e.g. the right side of this element should touch the left side of this other element), and then everything would be fed into a solver of a linear system of equations to get the final layout.

I'm a little concerned though that it might get tedious describing all of the constraints needed to solve a full system. Plus, these constraints might be too rigid in that you can't say, "I need a circle as big as possible to fill that space between the elements" or "make the font size as big as possible as long as the width isn't too big." Of course, doing something like that might require a system that uses linear programming or some other mathematical optimization technique underneath, and it might be tricky to translate constraints from a diagram design into the proper set of inequalities and objective functions without totally confusing the diagram designer.

There are various "constraint-based diagram editors" available, but most of these tools are designed from drawing large graphs (e.g. org charts). Given a bunch of inter-connected diagram elements, these tools will use spring systems or other techniques to find a good planar embedding of the graph. Some of my diagrams could be laid out this way, but I'm not sure if this approach is simultaneously too heavy and too underpowered for the types of diagrams I want. My diagrams don't really fit into those graph models, so I'd be worried that the mismatch of diagram types would make it difficult to get the results I wanted.

I also looked at some constraint solver systems that I could maybe build up into a diagram tool since that would give me the most flexibility in terms of how constraints could be expressed. Unfortunately, constraint solvers are actually a technical term used to refer to specific AI-like problems like SAT, etc. They specialize in solving binary constraints. Although they can also work with real numbers, it seems that some of them solve the problem by discretizing the real number line and then using standard binary constraints to solve things.

Perhaps what I need is some sort of symbolic computation engine that can work with intervals. Does that even exist? Perhaps I'm going overboard with this whole diagramming thing.

No comments:

Post a Comment