Howdy, I work on S2 [1] so I have questions! How do you deal with polygons that cross the antimeridian?<p>The indexing structure you've come up with seems very interesting. In spherical coordinates line sweep algorithms like that are a little less intuitive because there's not really a min and max y value to work with. Does your index support multiple polygons indexed together?<p>The lack of exact predicates worries me a little bit. It's tricky because it will work right until it doesn't for mysterious reasons, and it's very hard to test for if you haven't built it on a foundation of exact predicates. You'll periodically fall into the fractal foam around edges when testing if you cross them or not ([2] has some good pictures). We do this in S2 by relying on a set of predicates [3] that fall all the way back to symbolic perturbation if they have to. We simply don't have to think about colinear points in S2 for that reason.<p>[1] <a href="https://s2geometry.io/" rel="nofollow noreferrer">https://s2geometry.io/</a>
[2] <a href="https://github.com/mourner/robust-predicates">https://github.com/mourner/robust-predicates</a>
[3] <a href="https://github.com/google/s2geometry/blob/master/src/s2/s2predicates.h">https://github.com/google/s2geometry/blob/master/src/s2/s2pr...</a>
Nice library. +1 for the excellent visualizations [1]. Will you keep it focused on intersections or might you dabble with triangulation?<p>[1] <a href="https://github.com/tidwall/tg/blob/main/docs/POLYGON_INDEXING.md">https://github.com/tidwall/tg/blob/main/docs/POLYGON_INDEXIN...</a>
Rather than creating new geometric primitives on the heap, wouldn't it be more flexible if the caller can provide the memory to initialize the structure in?<p>Then instead of<p><pre><code> struct tg_geom *geom = tg_geom_new_point(-112, 33);
if (!geom) {
// System is out of memory.
}
</code></pre>
you could do<p><pre><code> struct tg_geom geom;
tg_geom_init_point(&geom, -112, 33);
</code></pre>
without need for error checking or cleanup. You can still allocate on the heap if you want but you wouldn't have to.
Hey, this looks really great, but I couldn't really see anything in the docs about robustness (how you handle floating point inaccuracy, etc) - what approach did you use?
This looks really interesting. It implements pretty much the exact subset of geospatial stuff that I care about, in a single C file (an amalgamation that includes its dependencies).<p>This could make for a really neat SQLite extension, as a much lighter alternative to SpatiaLite.
This is awesome! I wonder how feasible is it to include TG in Apache Sedona (<a href="https://github.com/apache/sedona">https://github.com/apache/sedona</a>)<p>Although Sedona runs as a distributed system, but TG may speed local in-memory geometrical computation for each worker node. Let me know your thoughts!
Very nice! I wonder if I can compile this to wasm. I’ve been badly needing spatial predicates in a web environment that are faster and less clunky than JSTS.<p>Does it assume a flat Cartesian world or does it handle ellipsoids or even map projections? (Or does it avoid the complexity altogether by not doing any work that cares about distances?)