Show HN: TG – Fast geometry library for C

s2mcallis

Howdy, I work on S2 [1] so I have questions! How do you deal with polygons that cross the antimeridian?

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?

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.

[1] https://s2geometry.io/ [2] https://github.com/mourner/robust-predicates [3] https://github.com/google/s2geometry/blob/master/src/s2/s2pr...

hgs3

Nice library. +1 for the excellent visualizations [1]. Will you keep it focused on intersections or might you dabble with triangulation?

[1] https://github.com/tidwall/tg/blob/main/docs/POLYGON_INDEXIN...

ginko

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?

Then instead of

  struct tg_geom *geom = tg_geom_new_point(-112, 33);
  if (!geom) {
      // System is out of memory.
  }

you could do

  struct tg_geom geom;
  tg_geom_init_point(&geom, -112, 33);

without need for error checking or cleanup. You can still allocate on the heap if you want but you wouldn't have to.

pasabagi

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?

simonw

This is a really great README - clearly explained the benefits of the library and anticipated all of my questions about it.

simonw

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).

This could make for a really neat SQLite extension, as a much lighter alternative to SpatiaLite.

unnah

It looks like the coordinates are 64-bit doubles. How accurate and repeatable are the implementations of geometry operations here?

MoSarwatSpatial

This is awesome! I wonder how feasible is it to include TG in Apache Sedona (https://github.com/apache/sedona)

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!

Waterluvian

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.

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?)

aquarin

I am curious, what exactly "feq" is calculating?

> return !((x < y) | (x > y));

Is it supposed to avoid x == y. If yes, why?

sylware

The author should consider some assembly versions of parts of it (ofc, without abusing the assembler pre-processor).