from Hacker News

Show HN: TG – Fast geometry library for C

by tidwall on 9/22/23, 11:27 PM with 32 comments

• by s2mcallis on 9/23/23, 4:04 PM

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

• by hgs3 on 9/23/23, 1:39 AM

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

• by ginko on 9/23/23, 10:37 AM

  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.

• by pasabagi on 9/23/23, 9:16 AM

  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?

• by simonw on 9/23/23, 4:12 AM

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

• by simonw on 9/23/23, 4:25 AM

  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.

• by unnah on 9/23/23, 4:38 AM

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

• by MoSarwatSpatial on 9/23/23, 1:10 PM

  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!

• by Waterluvian on 9/23/23, 2:34 AM

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

• by aquarin on 9/23/23, 6:28 AM

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

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

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

• by sylware on 9/23/23, 9:26 AM

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