Tuesday 25 December 2012

JTS 1.13 Released

I'm to announce that JTS 1.13 has been released.  It's available for download from SourceForge.

There is a long list of new features, enhancements and bug fixes in this release:

Functionality Improvements

  • Changed GeometryFactory.createGeometry() to make a deep copy of the argument Geometry, using the CoordinateSequenceFactory of the factory
  • Added ability to specify a dimension in CoordinateArraySequence
  • Changed Geometry.getEnvelopeInternal() to return a copy of the cached envelope, to prevent modification
  • Added GeometryEditor.CoordinateSequenceOperation to allow easy editing of constituent CoordinateSequences
  • Added GeometryFactory.createPolygon convenience methods which do not require holes to be specified
  • Geometry overlay methods now return empty results as atomic types of appropriate dimension
  • Added RectangleLineIntersector to provide efficient rectangle-line intersection testing
  • Added getOrdinate and setOrdinate to Coordinate
  • Quadtree is Serializable
  • STRtree is Serializable
  • Added max, average and wrap functions to MathUtil
  • Improved WKTReader parse error reporting to report input line of error
  • Improved WKBReader to repair structurally-invalid input
  • Made TopologyPreservingSimplifier thread-safe
  • Added AbstractSTRtree.isEmpty() method
  • Added QuadTree.isEmpty() method
  • Added KdTree.isEmpty() method
  • Added decimation and duplicate point removal to ShapeWriter.
  • ScaledNoder now preserves Z values of input
  • Added instance methods for all Triangle static methods
  • Added CGAlgorithmsDD containing high-precision versions of some basic CG algorithms
  • Added IntersectionMatrix.isTrue() method for testing IM pattern matches
  • Added getRawCoordinates methods to PackedCoordinateSequence concrete classes
  • Modified Geometry.isSimple() to explicity check for simplicity for all types, and support GeometryCollections
  • Improved MCIndexSnapRounder to add nodes only where they are necessary
  • Added CoordinateArrays.removeNull() method
  • Enhanced GeometryEditor to handle null geometries returned from operation
  • Added WKBHExFileReader
  • Added Distance3D operation

Performance Improvements

  • Simplified & improved performance of RectangleIntersects by using new RectangleLineIntersector
  • In RandomPointsInGridBuilder eliminated redundant ArrayList usage
  • In PreparedPolygonIntersects and PreparedLineStringIntersects added check to avoid creating segment index if all test inputs are points
  • In AbstractSTRtree switched to using indexed list access for better performance than using iterators
  • In AbstractSTRtree freed inserted item array after index is built
  • Improved performance of Polygonizer for cases with many potential holes
  • Improved performance for some DD methods by making them final
  • Added fast filter for CGAlgorithmsDD.orientationIndex, and switched to self-operations for DD determinant
  • Changed STRtree.createNode() to use a static class for nodes
  • Changed QuadTree Node to use scalar x and y variables rather than a Coordinate to reduce memory allocation
  • Fixed PreparedGeometry concrete classes to be thread-safe.
  • Fixed SortedPackedIntervalRTree so that it is thread-safe.

Robustness Improvements

  • Switched to using DD extended-precision arithmetic to compute orientation predicate
  • CGAlgorithms.distanceLineLine() improved to be more robust and performant
  • Fixed robustness issue causing Empty Stack failure in ConvexHull for some nearly collinear inputs
  • CGAlgorithms.signedArea() uses a more accurate algorithm

Bug Fixes

  • Fixed Geometry.equalsExact() to avoid NPE when comparing empty and non-empty Points
  • Fixed CascadedPolygonUnion to discard non-polygonal components created during unioning, to avoid failures and provide more desirable behaviour
  • Fixed CentralEndpointIntersector to initialize result correctly
  • Fixed DelaunayTriangulationBuilder.extractUniqueCoordinates(Geometry) to avoid mutating the vertex order of the input Geometry
  • Fixed ConformingDelaunayTriangulationBuilder to allow non-disjoint site and constraint vertex sets
  • Fixed RandomPointsInGridBuilder point generation to use circle constraint correctly
  • Fixed Linear Referencing API to handle MultiLineStrings consistently, by always using the lowest possible index value, and by trimming zero-length components from results
  • Fixed bug in LocationIndexedLine and LengthIndexLine which was causing an assertion failure when the indexOfAfter() method was called with a constraint location which is at the end of the line
  • Fixed bug in STRtree.query(Envelope, ItemVisitor) causing an NPE when tree is empty
  • Fixed issue with creating zero-length edges during buffer topology building under fixed precision, by: adding filter to remove zero-length edges; using a better estimate of scale factor for reducing to fixed precision after initial failure.
  • Fixed TopologyPreservingSimplifier to return a valid result for closed LineStrings with large distance tolerances
  • Fixed TopologyPreservingSimplifier to return an empty result for an empty input
  • Fixed DouglasPeuckerSimplifier to return an empty result for an empty input
  • Fixed MinimumBoundingCircle to correctly compute circle for obtuse triangles.
  • Fixd GeometryPrecisionReducer to use input GeometryFactory when polygon topology is fixed
  • Fixed GeometryNoder bug that was failing to snap to end vertices of lines
  • Fixed Geometry.getCentroid() and Geometry.getInteriorPoint() to return POINT EMPTY for empty inputs
  • Fixed DelaunayTriangulationBuilder to correctly extract unique points
  • Fixed KdTree to correctly handle inserting duplicate points into an empty tree
  • Fixed LineSegment.projectionFactor() to handle zero-length lines (by returning Double.POSITIVE_INFINITY)
  • Fixed LocationIndexedLine to handle locations on zero-length lines
  • Fixed LengthIndexedLine and LocationIndexedLine to handle indexOfAfter() correctly
  • Fixed WKBReader to handle successive geometrys with different endianness
  • Fixed GeometricShapeFactory to correctly handle setting the centre point
  • Fixed GeometryFactory.createMultiPoint(CoordinateSequence) to handle sequences of dimension > 3

API Changes

  • Changed visibility of TaggedLineStringSimplifier back to public due to user demand


  • Added Performance Testing framework (PerformanceTestRunner and PerformanceTestCase)
  • Added named predicate tests to all Relate test cases

JTS TestBuilder

Functionality Improvements

  • Added segment index visualization styling
  • Improved Geometry Inspector
  • Added stream digitizing for Polygon and LineString tools
  • Added output of Test Case XML with WKB
  • Added Extract Component tool
  • Added Delete Vertices Or Components tool
  • Added Geometry Edit Panel pop-up menu, with operations
  • Added Halton sequence functions
  • Added sorting functions
  • Added function for selection of first N components
  • Added CGAlgorithms functions
  • Added ability to paste and load multiple WKBHex geometries

Performance Improvements

  • Using decimation substantially improves rendering time for large geometries.

Bug Fixes

  • Fixed bug in saving XML test files

Thursday 20 December 2012

Convenience trumps all

The always-readable Stephen O'Grady has an insightful post titled Do Not Underestimate the Power of Convenience.  He proposes that an increasingly important factor driving the uptake of software is the developer's drive for convenience.  "Convenience" is an, er, convenient term for things like ease-of-use, power, portability and low barrier to entry.  In the case of software the lowest possible barrier is provided by free open source software, but the principle applies to infrastructure as well (reflected by the rapid uptake of things like cloud computing and BYOD).  As evidence he lists a set of technologies whose prevalence has been driven bottom-up by developers, rather than top-down by corporate fiat.  It reads like the bill-of-materials for IT infrastructure in a start-up: AWS, Linux, dynamic languages, Git, Eclipse, etc.

One reason he gives for this situation is the pleasing (to my ears) observation that "Developers are the new Kingmakers" (which he discusses in detail in another post).  I suspect that these are mutually-reinforcing phenomena.  Developer's drive for convenience has led to the rapid evolution of open source software (and not coincidentally the improvement of the tools which enable its development).  This has led to the current situation where in many cases OSS surpasses commercial offerings, or at least is "good enough" to be used in demanding production environments.  Since the developers are the ones making the software, or at least are the ones who understand it, they need to be involved in the decisions to adopt it (if they aren't spearheading the adoption themselves). (And especially since there are usually no marketing people in sight...)

In fact, I contend that the drive for convenience is the motivation for many of the advances in software and computation.  A classic example is the ongoing quest to increase the concision of computer languages, by making them more expressive and provide a richer computation model.   Another is the evolution of systems which can easily automate mundane tasks (with examples including the rich shell and command-line capabilities of *nix and the increasingly powerful array of build tools - the best of which of course are free and open source.)  Developer's preference for software which is portable and standard is also driven by convenience - everyone wants their current favourite set of software available wherever they happen to be are working (and as expected, open source software typically exhibits the highest degree of portability).

As Larry Wall said, laziness and impatience are virtues for a programmer.

Lazy programmers avoid yak shaving

Taken to the extreme, the drive for convenience is simply another way of stating the ultimate goal of all compute science - to free computation from any limitations of space, time, money and power.  Put this way, O'Grady's thesis is almost a tautology.  But it's a valuable reminder of the constant need to push against the strong opposing forces of commercial interest and bureaucratic inertia.