The project would attempt to automate the generation of the http://xkcd.com/657/ visualization:
In particular I will try to implement an automated way to parse character interaction instructions (or, perhaps, a raw movie script) and generate an ‘action line’ for each character in a way that codes interaction with spatial proximity.
My main goal is to implement an efficient and effective layout algorithm that, with the users help, would generate results similar to the hand crafted images shown above. The layout algorithm will use combinations of genetic algorithms and simulated annealing to achieve the goal.
Above and Beyond
Depending on the ease of implementing the layout algorithm I would also like to consider these extensions:
- Effective label placement – how do we label the lines in an aesthetic and uncluttered way?
- Movie script parsing – can we automatically parse a movie script and, perhaps with some minimal help form the user, determine how to visualize it?
- Temporal manipulation – can we automatically determine how to stretch and compress the x-axis to achieve the most clarity by giving lots of space to complicated time periods and little space to simpler time periods?
- Important character encoding – can we have the layout ‘flow’ around some pivotal character? (e.g. how do all the characters in Star Wars interact with Luke?)
MatrimonialPathFinder* (still unpublished work within the Stanford Visualization department)
http://xkcd.com/657/ (show above)
Edge crossing minimization algorithm for hierarchical graphs based on Genetic Algorithms (Shen Wei-xiang, Huang Jing-wei): link
Differential evolution for small TSPs with constraints (Štefan Peško): [link: http://frcatel.fri.uniza.sk/users/pesko/publ/DeTSP.pdf]
Differential evolution - A Simple and Efficient Heuristic Strategy for Global Optimisation over Continuous Spaces (Rainer Storn, Kenneth Price): link
*Not the actual project name
**Not for grading – updated after submission deadline