https://github.com/tidwall/tg Skip to content Toggle navigation Sign up * Product + Actions Automate any workflow + Packages Host and manage packages + Security Find and fix vulnerabilities + Codespaces Instant dev environments + Copilot Write better code with AI + Code review Manage code changes + Issues Plan and track work + Discussions Collaborate outside of code Explore + All features + Documentation + GitHub Skills + Blog * Solutions For + Enterprise + Teams + Startups + Education By Solution + CI/CD & Automation + DevOps + DevSecOps Resources + Learning Pathways + White papers, Ebooks, Webinars + Customer Stories + Partners * Open Source + GitHub Sponsors Fund open source developers + The ReadME Project GitHub community articles Repositories + Topics + Trending + Collections * Pricing Search or jump to... Search code, repositories, users, issues, pull requests... Search [ ] Clear Search syntax tips Provide feedback We read every piece of feedback, and take your input very seriously. [ ] [ ] Include my email address so I can be contacted Cancel Submit feedback Saved searches Use saved searches to filter your results more quickly Name [ ] Query [ ] To see all available qualifiers, see our documentation. Cancel Create saved search Sign in Sign up You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert {{ message }} tidwall / tg Public * Notifications * Fork 7 * Star 252 Geometry library for C - Fast point-in-polygon License MIT license 252 stars 7 forks Activity Star Notifications * Code * Issues 1 * Pull requests 0 * Actions * Projects 0 * Security * Insights More * Code * Issues * Pull requests * Actions * Projects * Security * Insights tidwall/tg This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. main Switch branches/tags [ ] Branches Tags Could not load branches Nothing to show {{ refName }} default View all branches Could not load tags Nothing to show {{ refName }} default View all tags Name already in use A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch? Cancel Create 1 branch 1 tag Code * Local * Codespaces * Clone HTTPS GitHub CLI [https://github.com/t] Use Git or checkout with SVN using the web URL. [gh repo clone tidwal] Work fast with our official CLI. Learn more about the CLI. * Open with GitHub Desktop * Download ZIP Sign In Required Please sign in to use Codespaces. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching Xcode If nothing happens, download Xcode and try again. Launching Visual Studio Code Your codespace will open once ready. There was a problem preparing your codespace, please try again. Latest commit @tidwall tidwall Update README.md ... 25a85a6 Sep 23, 2023 Update README.md 25a85a6 Git stats * 4 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time .github/workflows First commit September 22, 2023 16:18 deps First commit September 22, 2023 16:18 docs First commit September 22, 2023 16:18 examples First commit September 22, 2023 16:18 tests First commit September 22, 2023 16:18 .gitignore First commit September 22, 2023 16:18 .package First commit September 22, 2023 16:18 LICENSE First commit September 22, 2023 16:18 README.md Update README.md September 22, 2023 18:58 tg.c First commit September 22, 2023 16:18 tg.h First commit September 22, 2023 16:18 View code [ ] Features Goals Performance Using Programmer notes Pure functions Fast cloning Avoid memory leaks Upcasting Example Contact License README.md TG 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 memory sanitizer 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, 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 us 638,720 tg/natural 10,143,419 99 39914 3257 53.17 us 681,360 tg/ystripes 15,174,761 66 39914 3257 884.06 us 1,059,548 geos/none 29,708 33661 39914 3257 135.18 us 958,104 geos/prepared 7,885,512 127 39914 3257 2059.94 us 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.c Programmer 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_geom This 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_poly Do 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 #include int main(int argc, char **argv) { if (argc != 3) { fprintf(stderr, "Usage: %s \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))' Contact Josh Baker on Mastodon @tidwall@mastodon.social or (less) on Twitter @tidwall. License TG source code is available under the MIT License. About Geometry library for C - Fast point-in-polygon Resources Readme License MIT license Activity Stars 252 stars Watchers 7 watching Forks 7 forks Report repository Releases 1 tags Packages 0 No packages published Languages * C 99.3% * Other 0.7% Footer (c) 2023 GitHub, Inc. Footer navigation * Terms * Privacy * Security * Status * Docs * Contact GitHub * Pricing * API * Training * Blog * About You can't perform that action at this time.