Friday, May 15, 2009

UML Sequence Diagrams on the Web

I find the sequence diagram to be one of the most useful UML diagrams - but it's also one of the most fiddly & annoying to generate in a diagramming tool. There's a few reasons for that:
  • there's a large amount of implicit structure which is tedious to maintain
  • sequence diagrams quickly get complex for processes with lots of actors and/or actions
  • I can never remember all the conventions for representing concepts like alternation, loops and nesting
Luckily, the web to the rescue! The websequencediagrams website has a on-line diagram generator which uses a simple language to describe the diagram. This works well precisely because of the structure in sequence diagrams. Because they are inherently linear in structure, they are more constrained than other UML diagrams.

The language supports just about everything you might want - signal types, groups, nesting, notes, lifelines, etc. It outputs in images or as PDF - and it even has cool styles! Here's the idea:
loop 1000 times
Me->Visio: draw sequence diagram
Visio->Me: frustration
Me->Google: search for better way
Google->Me: find websequencediagram tool
Me->WebSequenceDiagram: draw sequence diagram
WebSequenceDiagram->Me: happiness!


I've blogged about the appeal of specifying UML diagrams using code before. I'm not sure how much traction TextUML is getting - but it's hard to resist the appeal of a web interface, a simple language, and sexy ouput.

Now, if only someone would develop a force-directed web-based state diagram engine...

Note: there's some other alternatives to the websequencediagram tool - the author blogs about them here. The most interesting from my point of view is sdedit, which is open-source and Java-based. It's more powerful, but the language looks a mite complex. (Too bad there's no standard language for describing UML - maybe the Three Amigos should skip a siesta and whip one up.)

Monday, May 4, 2009

Voronoi Diagrams in JTS 1.11

As is well-known, the Voronoi diagram (or tesselation) is the dual of the Delaunay triangulation. So the new Delaunay Triangulation code in JTS has a natural extension to computing Voronoi diagrams. Thanks to the quad-edge data structure underlying the Delaunay algorithm this was relatively trivial to implement, after a few design issues were sorted out (such as:
  • efficiently enumerating all vertices in the QuadEdge data structure which provides the basis for Delaunay computation
  • computing the circumcentre of all Delaunay triangles in a consistent way
  • clipping the generated Voronoi cell polygons to a reasonable bounding area)
Some examples on randomly-generated point sets:

Delaunay and Voronoi diagrams of 20 points (15 ms)

Voronoi diagram of 100 points (63 ms)

Voronoi diagram of 100,000 points (7.3 sec)

The JTS implementation scales very well - a Delaunay/Voronoi diagram of 1 million points computes in under 5 minutes. The one downside is memory usage. As usual, Java is quite memory-hungry - a 1 M point Delaunay takes around 700 MB. This seems excessive, even for Java. Hopefully some memory profiling may reveal that this can be reduced by some tuning of the class structures involved.

Even better, the Delaunay/Voronoi algorithm seems to be quite robust, even though no special attempt has been made to provide high-precision or otherwise robust implementations of some of the key predicates (inCircle and orientation). This may yet prove to be an issue for some inputs, but at this point it seems possible to claim that for non-pathological inputs the algorithms execute correctly.