Meme of the Month

Well, it's obvious, innit?


You can be the first to write the Wikipedia article!

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
end
Me->Google: search for better way
Google->Me: find websequencediagram tool
Me->WebSequenceDiagram: draw sequence diagram
WebSequenceDiagram->Me: happiness!

produces


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.)

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.

Delaunay Triangulation in JTS 1.11

The next version of JTS (1.11) will include an API for creating Delaunay triangulations and Conforming Delaunay triangulations. For a thorough explanation of the differences between Delaunay, Conforming Delaunay, and Constrained Delaunay, and why they are actually quite difficult to compute, see Jonathan Shewchuk's wonderful web site. [Side note - yet another B.C.-grown spatial dude - must be something in the water up here!]

This Delaunay implementation arose out of the work I did on automated watershed extraction using a system called WaterBuG a while back. It's taken a while to make its way into JTS because there's quite a bit of work involved in turning a codebase targeted at a very specific project into a clean, user-friendly API. Not to mention writing documentation...

But it's there now, and I'll be interested to see if it's of use to JTSer's. There seems to be a sudden surfeit of Delaunay and CDT Java libraries (see here, here, here, here and here), so I make no claims that the JTS one is best-of-breed. But hopefully having a decent implementation easily accessible and embedded in a general-purpose library will meet some needs. Also, my hope is that it will serve as the basis for further algorithms in JTS (such as the much-sought-after Concave Hull!).

Here's some screenshots showing the triangulation API at work:

The input points and constraint segments:
The Delaunay triangulation (notice that triangle edges cross some of the longer constraint edges):
A conforming Delaunay triangulation (the triangulation edges are now faithful to the constraint edges):

Web Monkeys with Laserbeams like JTS

...As they explain in this blog post about using JTS to simplify a polygonal coverage.

The really sweet thing is that not only do the Web Monkeys have laser beams, but also honkin' big computers as well. The post states that they use 7 GB of memory to process 41,000 polygons in a single batch (as is required for the simplification algorithm that they're using). I inquired and found out that they're using:

java version "1.6.0_11"
Java(TM) SE Runtime Environment (build 1.6.0_11-b03)
Java HotSpot(TM) 64-Bit Server VM (build 11.0-b16, mixed mode)

Niice... I've always wanted to experiment with large memory space for JTS processing, for things like large overlays, large TIN building, etc. So far I haven't had a machine large enough to let me try. But it sounds like 64-bit Java "just works", as expected. Another great reason for coding to a JVM - 64-bit memory space support with no recompilation!

GM and VE side-by-side and head-to-head

Here's a nifty page which shows GM and VE side-by-side, with slaved navigation. It's quite handy for seeing differences in map rendering and imagery.


For my area of interest (Victoria B.C.) my 20-second appraisal is that they both have aspects of their rendering which are better than the other; and VE's imagery coverage is more limited than GM's (probably due to this deal).

More on Database Thawing

I just saw this blog post in rebuttal to Martin Fowler's DatabaseThaw article. It's a typically well-thought out response from Typical Programmer. The short summary is that he rejects Fowler's criticism of using RDB's as the mechanism for application integration. (And don't dismiss him as simply a RDB bigot - he's not shy about nailing relational gurus, as in Relational Database Experts Jump The MapReduce Shark).

TP's arguments ring true to me, although in my experience it takes a very concientious DB shop to fully maintain the "encapsulation of data and operations" across many applications, many custodians, and many developers.

It would be great if Fowler's vision of the integration point being HTTP rather than SQL solved all our problems. Loose coupling is a wonderful thing to have. But so far I'm not seeing how this provides equivalent performance for all cases, and how it avoids the problem of data model mismatch.

Is Global Database Warming happening?

Martin Fowler has a great bliki^TM post on DatabaseThaw. The soundbite is something like "What happens after relational DBs?". He has some interesting links to things like Drizzle.

His opinon of relational DBs is that

their dominance is due less to their role in data management than their role in integration

This makes sense, but I think they also have offered the benefit of providing a fairly powerful, standard way of modelling and querying data. Over the lifetime of this technology this has fought off some powerful challengers, notably object-oriented data modelling. (Although perhaps this battle was only won by becoming more like the "loser"). The latest challenger is semantic data modelling (RDF, SPARQL, etc). Perhaps the world is ready to make this transition - although I'm not rushing to sell my Oracle stock.

He also makes a good point that the focus of integration is shifting from the DB to the Web. Hard to argue with this... the clouds are moving in!

Computing Geometric Similarity

The GEOS team is working on porting the JTS CascadedPolygonUnion algorithm. Reasonably enough they asked whether there were unit tests that they could use to check the correctness of their code. I was a bit dismayed to realize that in fact there weren't any unit tests for this class (although having used the code extensively I'm pretty confident that it's correct.)

So fine, some unit tests are needed. This should be easy, right? Just create or obtain some polygonal datasets, union them using both CascadedPolygonUnion (fast) and Geometry.union (slow), and compare the results.

But there's a catch (in geometric processing there usually is). Due to rounding effects, there's no guarantee that the results of the two algorithms will be vertex-by-vertex identical. Of course, they should be very, very similar... but how to check this?

In geometry processing it's usually much harder to test "similar" than it is to test "exact", and this case is no exception. In fact, there's many different tests that could be used, depending on how you want to define "similar". In the context of unit tests, similarity testing is essentially checking for discrepancies which might be introduced into a theoretically correct result. So the tests to use may depend on the operation(s) that are being performed, since different kinds of algorithms can produce different kinds of discrepancies. A further issue which needs to be considered is to detect gross differences which might result from catastrophic algorithm failure.

So now the task is to write a SimilarityValidator for geometries. For polygons there's various characteristics which can be compared:

• A simple thing to do is to compare basic quantities like the area and perimeter length of the polygons. Paradoxically, these are good for detecting small discrepancies, but not for detecting gross ones (e.g. two identical rectangles which are offset by a large distance)
  
• One obvious thing to do is to compute the symmetricDifference of the polygons and inspect the area of the result. This has a couple of issues. One is what area tolerance to use? A more serious issue is that the symmetric difference operation is itself an approximation to an exact answer. This is especially true in situations where the inputs are very close - which is exactly the situation we are trying to check! So there may be a certain lack of confidence that this is detecting all discrepancies
• A more robust test is to compute the Hausdorff distance between the rings of the polygons. This allows expressing the tolerance in terms of distance, which is more intuitive. It's also fairly robust and easy to confirm the answer. There's a challenge in developing an efficient Hausdorff algorithm - but that's a topic for another blog post.
• Other tests might include comparing structural things like comparing the number of rings in the polygons.
  

Hausdorff Distance between two polygons

With this validator written and some test datasets run I can finally confirm that CascadedPolygonUnion actually works!

JTS Version 1.10 released

I'm happy to announce that after a long gestation JTS 1.10 has been released. (This is my contribution to help fulfill James Fee's prediction 8^)

The package is available on SourceForge here.

There are numerous enhancements in this version. The highlights are:

• Dramatic improvements to buffer performance, robustness and quality
• Moving the GML I/O classes into the core library, and provided more control over the emitted GML
  
• numerous bug fixes and performance improvements.

The full list of changes is:

Functionality Improvements

• Added Geometry.reverse() method for all geometry types
• Added setSrsName, setNamespace, setCustomRootElements methods to GMLWriter
• Added Envelope.getArea method
• Added copy, copyCoord methods to CoordinateSequences
• Added area method to Envelope
• Added extractPoint(pt, offset) methods to LengthIndexedLine and LocationIndexedLine
• Added CoordinatePrecisionReducerFilter
• Added UnaryUnionOp(Collection, GeometryFactory) constructor to handle empty inputs more automatically
• Added DiscreteHausdorffDistance class
• Made LineMerger able to be called incrementally
• Added GeometricShapeFactory.createArcPolygon to create a polygonal arc
• Enhanced Geometry.buffer() to preserve SRID

Performance Improvements

• Improved performance for EdgeList (by using a more efficient technique for detecting duplicate edges)
• Improved performance for ByteArrayInStream (by avoiding use of java.io.ByteArrayInputStream)
• Unrolled intersection computation in HCoordinate to avoid object allocation
• Improved performance for buffering via better offset curve generation and simplification.
• Improved performance for IsValipOp by switching to use STRtree for nested hole checking

Bug Fixes

• Fixed Geometry.getClassSortIndex() to lazily initialize the sorted class list. This fixes a threading bug.
• Fixed RectangleContains to return correct result for points on the boundary of the rectangle
• Fixed error in com.vividsolutions.jts.simplify.LineSegmentIndex which caused polygons simplified using TopologyPreservingSimplifier to be invalid in certain situations
• Fixed error in DouglasPeuckerSimplifier which caused empty polygons to be returned when they contained a very small hole
• Fixed PackedCoordinateSequence to return NaN for null ordinate values
• Fixed Geometry.centroid() (CentroidArea) so that it handles degenerate (zero-area) polygons
• Fixed Geometry.buffer() (OffsetCurveBuilder) so that it handles JOIN_MITRE cases with nearly collinear lines correctly
• Fixed GeometryFactory.toGeometry(Envelope) to return a CW polygon
• Fixed UnaryUnionOp to correctly handle heterogeneous inputs with P/L/A components
• Fixed UnaryUnionOp to accept LINEARRINGs
• Fixed CentroidArea to handle zero-area polygons correctly
• Fixed WKBWriter to always output 3D when requested, and to handle 2D PackedCoordinateSequences correctly in this case
• Fixed NodedSegmentString to handle zero-length line segments correctly (via safeOctant)
• Cleaned up code to remove unneeded CGAlgorithms objects
• Fixed GeometricShapeFactory.createArc to ensure arc has requested number of vertices

API Changes

• Moved GML I/O classes into core JTS codebase
• Changed GMLWriter to not write the srsName attribute by default
• In DistanceOp switched to using nearestPoints method names
• Exposed STRtree.getRoot() method

---

JTS TestBuilder

UI Improvements

• Added ability to read GML from input panel
• Added GML output to View dialog
• Added file drag'n'drop to Geometry Input text areas
• Add display of computation time
• Added Stats panel
• Added Scalar functions panel, with extensible function list
• Added Save as PNG...

---

JTS TestRunner

Functionality Improvements

• Added -testCaseIndex command-line option

OGRS 2009: International Opensource Geospatial Research Symposium

Via the OpenJUMP list comes this notice of the OGRS 2009: International Opensource Geospatial Research Symposium conference in Nantes, France.

France and Australia in one year sounds like a pretty good training plan to me!

KML Pie Charts in JEQL

Pie Charts are a nice way of displaying thematic visualization in Google Earth. They're also a good test of the chops of a KML generator. So naturally I was keen to see how to produce pie charts with JEQL.

For simplicity I decided to make my test statistic an orthographic comparison of the names of countries, showing the relative length of the country names and their vowel/consonant distribution. (This wasn't because this is a particularly interesting statistic, but it uses easily available data and exercises some of the data processing capabilities of JEQL).

The solution ended up using lots of existing capabilities, such as splitting multigeometries, regular expressions, JTS functions such as interior point, boundary and distance, and of course generating KML with extrusions and styling. The only new function I had to add was one to generate elliptical arc polygons - which is a good thing to have.

The results look pretty snazzy, I think - and would be even better with more meaningful data!

Wordlicious

After seeing this post on Wordle, I had to try it....


and there's no stopping at just one...

Nostalgic Trivia

When I was but a wee nerdling, I took a course taught by a grizzled veteran of the computer industry. I can no longer remember the subject matter of the course, but I do remember that at one point he referred to the main players in the computer business as "IBM and D'BUNCH". D'BUNCH were DEC, Burroughs, Univac, NCR, Control Data, and Honeywell. (And yes, I had to resort to Wikipedia to remember all these names.)


The moral of the story? Computer manufacturers come and go, but IBM remaineth eternal, apparently.

Dating myself even more, in the early part of my career I used machines made by the first 3 of these. The Univac had the distinction of having the most obtuse, unwieldy, difficult-to-use OS I have ever encountered. DEC, in contrast, had the best OS (of proprietary ones, that is - *nix blows 'em all away).

Untangling REST

Thanks to Sean I just learned about Roy Fielding's blog.



I don't know why it never occurred to me that Roy Fielding would have a blog, and it would likely to be a good source of commentary on the evolving philosophy of the Web, but it didn't. He does, and sure enough it's chock full o' goodness.

Highlights include this post about how to efficiently build a RESTful Internet-scale event notification system for querying Flickr photo update events - using images as bitmap indexes of event timeslices! Or the post which Sean noted, along with this one - both cri-de-coeurs about the pain of seing the clean concept of REST muddied to the point of meaningless.

Anyone confused about REST would do well to avoid inhaling too much smoke and get a dose of fresh air from the source...

Improvements to JTS buffering

By far the most difficult code in JTS to develop has been the buffer algorithm. It took a lot of hard graft of thinking, coding and testing to achieve a solid level of robustness and functionality. There have been a couple of iterations of improvements since the first version shipped, but the main features of the algorithm have been pretty stable.

However, it was always clear that the performance and memory-usage characteristics left something to be desired. This is particularly evident in cases which involve large buffer distances and/or complex geometry. These shortcomings are even more apparent in GEOS, which is less efficient at computation involving large amounts of memory allocation.

I'm pleased to say that after a few years of gestating ideas (really! - at least on and off) about how to improve the buffer algorithm, I've finally been able to implement some enhancements which address these problems. In fact, they provide dramatically better performance in the above situations. As an example, here are timing comparisons between JTS 1.9 and the new code (the input data is 50 polygons for African countries, in lat-long):

Buffer
Distance     JTS 1.9    JTS 1.10

0.01        359 ms     406 ms
0.1        1094 ms     594 ms
1.0      16.453 s     2484 ms
10.0     217.578 s     3656 ms
100.0     728.297 s      250 ms
1000.0    1661.109 s      313 ms

Another tester reports that a buffering task which took 83 sec with JTS 1.9 now takes 2 sec with the new code.

But wait, there's more! In addition to the much better performance of the new algorithm, the timings reveal a further benefit - once the buffer distance gets over a certain size (relative to the input), the execution time actually gets faster. (In fact, this is as it should be - as buffer distances get very large, the shape of the input geometry has less and less effect on the shape of the buffer curve.)

The algorithm improvements which have made such a difference are:

• Improved offset curve geometry - to avoid some nasty issues arising from arc discretization, the original buffer code used some fairly conservative heuristics. These have been fine-tuned to produce a curve which allows more efficent computation, while still maintaining fidelity of the buffer result
  
• Simplification of input - for large buffer distances, small concavities in the input geometry don't affect the resulting buffer to a significant degree. Removing these in a way which preserves buffer distance accuracy (within tolerance) gives a big improvement in performance.

A nice side effect of this work is the development of a solid methodology for validating buffers, and a thorough test suite for correctness, robustness, and performance.

This code will appear in JTS 1.10 Real Soon Now.

Java Power Tools cuts straight and true

Part of my summer holiday reading is the book Java Power Tools, by John Ferguson Smart.

I count a computer book a good buy if I get one new idea from it; two is stellar; and three or more goes on my "Recommend to Colleagues" list. This one is on the list... Ideas I`ve picked up include:

• the XMLTask extension for Ant, that provides easy and powerful editing of XML files. This should make configuring things like web.xml and struts-config.xml a lot easier. It even provides a way to uncomment blocks of XML markup.


• SchemaSpy, which generates database documentation (including ER diagrams!) from JDBC metadata. The tool also also comes with profiles for interpreting some vendor-specific metadata. It will be interesting to see how it handles spatial datatypes in Oracle and PostGIS...


• using Doxygen to generate documentation for Java source. Doxygen provides more capabilities than Javadoc, including UML diagrams and a variety of output document formats.


• UMLGraph also allows generating UML diagrams from Java source, and embedding them directly in Javadoc.

For graph visualization, SchemaSpy, Doxygen and UMLGraph all use the GraphViz application. This looks like a great tool in its own right. It provides a DSL for specifying graph structures and node and edge symbology, along with a layout and rendering engine which outputs to numerous different formats.

JPT of course covers all the better-known tools such as Ant, Maven, CVS, SVN, JUnit, Bugzilla, Trac, and many others. It doesn`t replace the documentation for these tools, but it does give a good comparative overview and enough details to help you decide which ones you`re going to strap around your waist for the next project.

Be the most popular tile on your block

You might think that the image below is a map of North America population density. You'd be off by one level of indirection...

In fact it's a heat map of the access frequency for Virtual Earth map tiles.

So really it's not an image of where people are, but where they want to be...

The image comes from a paper out of Microsoft Research: How We Watch the City: Popularity and Online Maps, by Danyel Fisher.

Makes me wonder if there are tiles that have never been accessed. Like perhaps this one? (It took a looong time to render....)


And what is the most-accessed tile? This one, perhaps?

Revolution is Happening Now

This great graph shows why we're all going to wrassling with parellelization for the rest of our coding lives:

Source: Challenges and Strategies for High End Computing, Kathy Yelick

Also see this course outline for an sobering/inspiring view of where computation is headed.

Krusty kurmudgeon Knuth kans kores & kommon kode

Andrew Binstock has an interesting interview with Don Knuth.



Professor Knuth makes a few surprising comments, including a low opinion of the current trend towards multicore architectures. Knuth says:

To me, it looks more or less like the hardware designers have run out of ideas, and that they’re trying to pass the blame for the future demise of Moore’s Law to the software writers...

But then he goes on to admit:

I haven’t got many bright ideas about what I wish hardware designers would provide instead of multicores...

Which seems to me to make his complaint irrelevant, at best. (Not that I don't sympathize with his frustration about banging our heads against the ceiling of sequential processing speed. And as the sage of combinatorial algorithms he must be more aware than most of us about the difficulties of taking advantage of concurrency.)

Another egregious Knutherly opinion is that he is "biased against the current fashion for reusable code". He prefers what he calls "re-editable code". My thought is that open source gives you both options, and personally I am quite happy to reuse, say, the Java API rather than rewriting it. But I guess when most of your code is developed in your own personal machine architecture (Knuth's MIX) then it's a good thing to enjoy rewriting code!

In the end, however, I have to respect the opinions of a man who has written more lines of code and analyzed more algorithms than most of us have had hot dinners. And I still place him in the upper levels of the pantheon of computer science, whose books all programmers would like to have seen gracing their shelves - even if most of us will never read them!

And yes, this post is mostly an excuse for some korny alliteration - but the interview is still worth a read. (Binstock's blog is worth scanning too - he has some very useful posts on aspects of Java development.)