Our great sponsors
-
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
-
GeometricTools
A collection of source code for computing in the fields of mathematics, geometry, graphics, image analysis and physics.
-
-
InfluxDB
Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.
I can't stop precision loss in all cases, but I do my darnedest to avoid loss when it causes false positives, especially for stuff like intersect detection code. For example the collinear [1] function looks really big for a seemingly simple operation, but there are extra checks built in to check for precision loss and in the cases of compiler associate math issues (like a user borking a build with -ffast-math).
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 tests too, which makes me warm and fuzzy every time they pass.
[1] https://github.com/tidwall/tg/blob/v0.1.0/tg.c#L389
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/
if (cap < 1000) {
Have you looked at: https://github.com/davideberly/GeometricTools
[2] https://github.com/tidwall/tile38
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!
... and here's Alex Garcia's first version of that SQLite extension: https://github.com/asg017/sqlite-tg