TG is a geometry library for C that is small, fast, and easy to use. I designed it for programs that need real-time geospatial, such as geofencing, monitoring, and streaming analysis.
Features
- Implements OGC Simple Features including Point, LineString, Polygon, MultiPoint, MultiLineString, MultiPolygon, GeometryCollection.
- Optimized polygon indexing that introduces two new structures.
- Reads and writes WKT, WKB, and GeoJSON.
- Provides a purely functional API that is reentrant and thread-safe.
- Spatial predicates including "intersects", "covers", "touches", "equals", etc.
- Test suite with 100% coverage using sanitizers and Valgrind.
- Self-contained library that is encapsulated in the single tg.c source file.
- Pretty darn good performance. ๐ [benchmarks]
Goals
The main goal of TG is to provide the fastest, most memory efficent geometry library for the purpose of monitoring spatial relationships, specifically operations like point-in-polygon and geometry intersect.
It's a non-goal for TG to be a full GIS library. Consider GEOS if you need GIS algorithms like generating a convex hull or voronoi diagram.
Performance
TG uses entirely new indexing structures that speed up geometry predicates. It can index more than 10GB per second of point data on modern hardware, while using less than 7% of additional memory, and can perform over 10 million point-in-polygon operations per second, even when using large polygons with over 10K points.
The following benchmark provides an example of the point-in-polygon performance of TG when using a large polygon. In this case of Brazil, which has 39K points.
Brazil ops/sec ns/op points hits built bytes tg/none 96,944 10315 39914 3257 46.73 ยตs 638,720 tg/natural 10,143,419 99 39914 3257 53.17 ยตs 681,360 tg/ystripes 15,174,761 66 39914 3257 884.06 ยตs 1,059,548 geos/none 29,708 33661 39914 3257 135.18 ยตs 958,104 geos/prepared 7,885,512 127 39914 3257 2059.94 ยตs 3,055,496
- "built": Column showing how much time the polygon and index took to construct.
- "bytes": Column showing the final in-memory size of the polygon and index.
- "none": No indexing was used.
- "natural": Using TG Natural indexing
- "ystripes": Using TG YStripes indexing
- "prepared": Using a GEOS PreparedGeometry
See all benchmarks for more information.
Using
Just drop the "tg.c" and "tg.h" files into your project. Uses standard C11 so most modern C compilers should work.
$ cc -c tg.cProgrammer notes
Check out the complete API for detailed information.
Pure functions
TG library functions are thread-safe, reentrant, and (mostly) without side effects. The exception being with the use of malloc by some functions like geometry constructors. In those cases, it's the programmer's responsibiilty to check the return value before continuing.
struct tg_geom *geom = tg_geom_new_point(-112, 33);
if (!geom) {
// System is out of memory.
}Fast cloning
The cloning of geometries, as with tg_geom_clone(), are O(1) operations that use implicit sharing through an atomic reference counter. Geometry constructors like tg_geom_new_polygon() will use this method under the hood to maintain references of its inputs.
While this may only be an implementation detail, it's important for the programmer to understand how TG uses memory and object references.
For example:
struct tg_geom *geom = tg_geom_new_polygon(exterior, holes, nholes);Above, a new geometry "geom" was created and includes a cloned reference to the tg_ring "exterior" and all of the holes.
Providing TG_NOATOMICS to the compiler will disable the use of atomics and
instead use non-atomic reference counters.
cc -DTG_NOATOMICS tg.c ...
Alternatively, the tg_geom_copy() method is available to perform a deep copy of the geometry.
Avoid memory leaks
To avoid memory leaks, call tg_geom_free() on geometries created from geometry constructors, geometry parsers, tg_geom_clone(), and tg_geom_copy()
In other words, for every tg_geom_new_*(), tg_geom_parse_*(),
tg_geom_clone(), and tg_geom_copy() there should be (eventually and exactly)
one tg_geom_free().
Upcasting
The TG object types tg_line, tg_ring, and tg_poly can be safely upcasted to a tg_geom with no cost at runtime.
struct tg_geom *geom1 = (struct tg_geom*)line; // Cast tg_line to tg_geom
struct tg_geom *geom2 = (struct tg_geom*)ring; // Cast tg_ring to tg_geom
struct tg_geom *geom3 = (struct tg_geom*)poly; // Cast tg_poly to tg_geomThis allows for exposing all tg_geom functions to the other object types.
In addition, the tg_ring type can also cast to a tg_poly.
struct tg_poly *poly = (struct tg_poly*)ring; // Cast tg_ring to tg_polyDo not downcast. It's not generally safe to cast from a tg_geom to other types.
Example
Create a program that tests if two geometries intersect using WKT as inputs.
#include <stdio.h>
#include <tg.h>
int main(int argc, char **argv) {
if (argc != 3) {
fprintf(stderr, "Usage: %s <geom-a> <geom-b>\n", argv[0]);
return 1;
}
// Parse the input geometries and check for errors.
struct tg_geom *a = tg_parse_wkt(argv[1]);
if (tg_geom_error(a)) {
fprintf(stderr, "%s\n", tg_geom_error(a));
return 1;
}
struct tg_geom *b = tg_parse_wkt(argv[2]);
if (tg_geom_error(b)) {
fprintf(stderr, "%s\n", tg_geom_error(b));
return 1;
}
// Execute the "intersects" predicate to test if both geometries intersect.
if (tg_geom_intersects(a, b)) {
printf("yes\n");
} else {
printf("no\n");
}
// Free geometries when done.
tg_geom_free(a);
tg_geom_free(b);
return 0;
}Build and run the example:
$ cc -I. examples/intersects.c tg.c
$ ./a.out 'POINT(15 15)' 'POLYGON((10 10,20 10,20 20,10 20,10 10))'License
TG source code is available under the MIT License.