Finding the best spot to put a label in a graph

johnnywang has asked for the wisdom of the Perl Monks concerning the following question:

In solving the problem I posed in perl for graphing Euclidean geometry, I came across the following problem.

When you draw a graph, say, even a simple one like a triangle, if you want to label the vertices, it's not straight forward to decide where to put the labels so as not to intersect with the lines. In this particular case, it's not that hard to find a half plane at a vertex that has no lines in it, one can then get a nice box for the label. For a more complicated graph with more than a couple of lines and vertices, is there a good algorithm for finding the right location for a label? I guess there can't be a complete solution, after all, there can be so many lines at a point where it just doesn't leave any space big enough for a label. But are there solutions that work in most of cases? Thanks.

Comment on Finding the best spot to put a label in a graph

Replies are listed 'Best First'.
Re: Finding the best spot to put a label in a graph by SciDude (Friar) on Aug 15, 2004 at 00:39 UTC
The best solution may be no labels at all! Although more of a design question than a perl question, consider study of Edward Tufte. There are quite a few "Tufte Representations" contained in his books and classes that may help you. Tufte also sponsors a forum for such topics that cover many similiar issues, such as label alignment. For multiple triangles I would consider the "mini multiples" approach. In short, you draw one representative triangle with clear labels and then leave the labels off of all other similar items on the page. You will find the approach clear and avoids "graph clutter/chart junk." Tufte has applied this approach to display of medical status (one example.) For somewhat more complex data you may find the Knight's Tour approch interesting. A group of semimagic solutions can be seen as small multiples. I would love to see more of your code! SciDude The first dog barks... all other dogs bark at the first dog.	[reply]
Re: Finding the best spot to put a label in a graph by kvale (Monsignor) on Aug 15, 2004 at 01:42 UTC
Label placement can be viewed as a problem in computational geometry. Text is usually considered as being enclosed in a bounding box (rectangle). So your task is to pick some aesthetically beautiful locations to try, and test if any of the lines or arcs in your diagram intersect the bounding box. As you say, aesthetic locations may not always work. As a first try after that failure, I would identify the set of lines coming into a vertex, compute the angles between neigboring lines, and pick the neighboring lines with the largest angle between them to nestle the label into. Given the angle and the size of the bounding box, it is a simple matter of geometry to determine how far away the bounding box should be from the vertex so that it does not intersect each line. I'd expect the center of the bounding box would lie close to the bisector of the two lines. -Mark	[reply]
Re: Finding the best spot to put a label in a graph by gaal (Parson) on Aug 15, 2004 at 06:01 UTC
tomsawyer.com make a good commercial product that lays out graphs automatically and incidentally deals with labels. Probably doesn't help you with your current problem <g>, but their image gallery is tooo cool to pass mentioning :)	[reply]