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?)
I've tried martinez-polygon-clipping, polygon-clipping, and polyclip-ts, all of which are based on the same algorithm, and all of which seem to throw exceptions frequently on geometry with overlapping edges.
I'm thinking I'll need to dig into JSTS in the hope it'll prove more stable... or learn how to write these kinds of algorithms myself.
[0]: https://docs.rs/geo/latest/geo/#algorithms
[1]: https://observablehq.com/@kylebarron/prototyping-georust-geo...
[2]: https://github.com/chrispahm/geos-wasm
[3]: https://observablehq.com/@kylebarron/zero-copy-apache-arrow-...
A) if you're handling projections or doing geodesic geometry then there's a bunch of other stuff to do and you'd probably have to mention it.
B) it would be obvious in the codebase if that was a part of it there'd be mentions of projections or some sort of constants for spherical maths.
C) Projections etc are often very application specific afaik it's not really possible to generalise it safely.
I blogged about it here: https://simonwillison.net/2023/Sep/23/tg-polygon-indexing/
> return !((x < y) | (x > y));
Is it supposed to avoid x == y. If yes, why?
It will be helpful, if you add comments discussing why certain functions are implemented in that way, and what algorithms (references) is used. For example, there are some magic numbers without explanation: if (cap < 1000) {
Have you looked at: https://github.com/davideberly/GeometricTools Each algorithm is well documented and explained. There is even a short pdf papers for some of the algorithms explainimg why some decisions are taken and what numerical issues may be expected.
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...
As I said in the README. My goals are fast point-in-polygon, geometry intersections, and low memory footprint. Those are my bread-and-butter.
From what I know about S2, it has different goals. Such as being spherical and using discrete cells for distributed spatial indexes. Those are great things of course, but not really what I need.
This is the second comment that recommends using Shewchuk’s methods. And while yes I agree that that may be a superior way to go, and always on the table for the future, I'm still able to achieve my goals without those methods. At least for now.
[1] https://datatracker.ietf.org/doc/html/rfc7946#section-3.1.9
Then instead of
struct tg_geom *geom = tg_geom_new_point(-112, 33);
if (!geom) {
// System is out of memory.
}
struct tg_geom geom;
tg_geom_init_point(&geom, -112, 33);
Yet I do see the need for avoiding allocations when working with lots of simple geometries like points and rects, and for my use I made functions like tg_geom_intersects_xy and tg_geom_intersects_rect to perform relation operations directly on point and rectangle values.
I'm sure it's not all perfect but I feel pretty good about it overall. It certainly helps that much of the logic derived from the Tile38 [2] project, which has 8 years of use in production. I ported many of the tests too, which make me warm and fuzzy every time they pass.
There are more modern implementations available on GitHub, but I’ve found it to be fairly easy to integrate into C-family projects without much modification.
This could make for a really neat SQLite extension, as a much lighter alternative to SpatiaLite.
[1] https://github.com/tidwall/tg/blob/main/docs/POLYGON_INDEXIN...
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!