Tektosyne 6.1.0 Released

Tektosyne 6.1.0 is now available for download. This is a fairly substantial bugfix release, with a number of specific changes beyond those described in my overview post, Moving Projects to Java 9. You can find a summary in the What’s New file.

First, a clarification. While the JavaFX demo application and IntelliJ IDEA project files in the source package now require Java SE 9.0.4, the library itself continues to target Java SE 8. Tektosyne requires no Java 9 features, and this way developers still on Java 8 won’t be forced to rebuild the JAR just to use the library.

I also split the download into a binary and a source code package, same as with my other projects. The only difference is that the binary package also contains the prebuilt Javadoc class reference. So you only need the binary package to use the library.

Float/Double.MIN_VALUE

Aside from the minor bugs listed in the What’s New file, the major issues fixed in this release were brought to my attention by an astute Github user of Tektosyne, going by the alias of Mushrooms (sf17k).

The first was surprising enough that I already wrote a dedicated post on the subject, Beware of Java’s inconsistent MIN_VALUE. In short, a number of basic algorithms were broken because I assumed the floating-point versions of MIN_VALUE had the same meaning as the integral versions, when in fact they are quite different. See the linked post for details.

Voronoi Diagrams, Part 1

Several more subtle errors surfaced in various Voronoi algorithms when tested with unusual sets of generator sites. One affected the core sweep line algorithm. When all generator sites are exactly aligned, the Voronoi edges separating them will be exactly parallel. That means there will be no “natural” Voronoi vertices, only the pseudo-vertices where those parallel edges intersect the rectangular clipping bounds.

The sweep line algorithm got confused by this. It relies on a priority queue to correctly retire the temporary half-edges generated for each pair of sites, and that priority queue operates only on natural vertices. In the absence of natural vertices, the final clean-up loop for non-retired edges was presented with double sets of half-edges, so each final Voronoi edge was output twice.

As far as I can tell, this is actually a bug in the original C code by Steven J. Fortune on which I based my C# and Java versions. I saw no obvious fix in the algorithm itself, so I brute-forced a solution with a hash set in the clean-up loop to check for edges that had already been output. Performance impact should be small.

Voronoi Diagrams, Part 2

Two more failure cases concerned the generation of Voronoi regions, which Tektosyne implements as a separate algorithm in class VoronoiResults. Both failures affected regions that are open towards two or more corners of the clipping bounds, and so must be closed over the clipping bounds with additional pseudo-vertices and pseudo-edges.

First, when Voronoi edges are exactly horizontal or vertical the closing algorithm failed to detect any open regions and did not close them at all. Second, when a Voronoi region was open to three corners of the clipping bounds, the region was closed over the one remaining corner instead. These were clearly my fault, as my closing algorithm had been a bit quick-and-dirty. The new version has a lot more ifs and is hopefully robust for all cases now.

Leave a Reply