The SFCurve library was conceived as part of a collaborative effort between two LocationTech projects, GeoTrellis and GeoMesa. Each project had developed Scala code to facilitate the creation and manipulation of Z-order curve indices based on spatial or spatiotemporal properties of data. In GeoTrellis, the Z-order curve functionality allows for raster tiles to be indexed such that the execution of large range queries and distributed raster operations is optimized. GeoMesa has analogous code to construct a GeoHash that serves a similar purpose for processing vector data.
The GeoTrellis and GeoMesa teams recognized that the similar code they had developed in each independent project was essentially solving the same problems, and the decision was made to collaborate on a common library for solving this set of problems. SFCurve is that library.
SFCurve solely deals with space-filling curves, and their application to indexing N-dimensional data, with a focus on 2- and 3-dimensional spaces. This includes functionality to perform bidirectional transformations between the 1-dimensional space of the index and the N-dimensional space of the data, for a single index or a range of indices.
The SFCurve library will support a clean API to its interface that is idiomatic to the Scala language. In addition, a Java API will be developed so that Java applications will be fully supported in their use of SFCurve. Other APIs for JVM-based languages may be developed.
The intention is to limit the scope of the SFCurve library, for two reasons. The first is to allow the library to concentrate on becoming a robust and optimized set of space filling curve implementations, so that extraneous code and extra features that belong in other libraries do not detract from a focused effort. The second is to minimize the external dependencies of this library. Any developer interested in using this library should be able to do so without importing a set of unwanted functionality and external dependencies. The modular nature of this library will mean that more projects will be able to use it to solve the specific problems of indexing against a space filling curve. Another benefit of minimizing dependencies is that less code and dependencies means less IP concerns.
The SFCurve library is a Scala library for the creation, transformation, and querying of space-filling curves (http://en.wikipedia.org/wiki/Space-filling_curve).
It is a common requirement for software dealing with spatial or spatiotemporal data (2- or 3-dimensional data) to store that data based on a 1-dimensional index. For instance, say I wanted to query a set of spatiotemporal data, and I only wanted to retrieve information between the years 2014 and 2015, within the state of Pennsylvania. Software could translate the 3-dimensional query parameters (one dimension being the time, and two dimensions being the longitude and latitude properties of the geographical boundary) into a set of 1-dimensional ranges. The start and end of these ranges would correspond to indices that were derived by a space-filling curve. If the set of spatiotemporal data was indexed by the same space filling curve, the 1-dimensional ranges could be used to retrieve the appropriate data. In many systems, including the ones that GeoTrellis and GeoMesa operate on, this method of querying spatiotemporal data is significantly faster than retrieving the data based directly on its 3-dimensional properties.
SFCurve provides (or will provide) Scala and Java APIs for functionality dealing with space filling curves. This includes a set of interfaces that provide a common and well-defined way for dealing with space filling curve implementations, as well as implementations of curves such as the Z-order curve and Hilbert curve.
SFCurve was originally conceived and developed by two LocationTech projects, so contributing this code to our community makes the most sense. The LocationTech community has fostered our two projects thus far, and we appreciate the project management infrastructure, the deployment architecture, the legal review process and the overall community support that being a project at LocationTech will afford the SFCurve.
There has also been interest in a JVM-based library for space-filling curves outside of the two LocationTech projects mentioned. Being part of LocationTech gives this project clear visibility and a community around this code, so that it will be as easy as possible for anyone who requires this sort of functionality to find and use this library.
All source code of the initial contribution was written by committers of LocationTech. There are no dependencies of the initial contribution besides the Scala language itself and the code required to build and test the project. As mentioned in the above Scope section, a project goal is to minimize taking on dependencies, which will minimize future legal issues.
The initial contribution will be immediately ready, as will the dependencies for IP review. Since the GeoTrellis and GeoMesa projects are already in incubation, the stewards of SFCurve are familiar with the submission process and so the incubation steps for SFCurve can be streamlined. Because there are minimal dependencies in the SFCurve codebase, the IP review should be quick and painless.
An initial 0.1.0 release will be release as soon as the IP review and other incubation steps are complete. This will allow the GeoTrellis codebase can replace it’s current Z-order curve implementation with the SFCurve implementation in development and future releases.
In parallel to the incubation process, development will begin on integrating the GeoMesa space filling curve implementations. Implementations will be thoroughly tested and benchmarked. Where appropriate, implementations will be merged in order to create the most correct and performant versions of each space filling curve implementation. GeoMesa will move from using its own internal implementation of space filling curves to the SFCurve library implementations.
Other space filling curves, such as the Hilbert Curve, will be implemented.
The Scala and Java API’s will be iterated on and solidified based on community feedback and to allow for a range of space filling curve implementations and functionality.
Future releases will be based off of milestones achieved in the SFCurve project, as well as in service to the release schedule of the broader community of projects using SFCurve.
The initial contribution will be the source code currently residing at https://github.com/geotrellis/curve.
The initial contribution contains only the GeoTrellis implementation of the Z-order curve for 2-dimensional and 3-dimensional spaces. This will serve as the groundwork for the robust SFCurve library, which will be collaboratively developed between committers on the GeoTrellis and GeoMesa projects, as well as any other collaborators willing to participate.