Re:Ask HN: What are some cool but obscure data structures yo...
by hubadu on Friday July 22, 2022 @06:28AM
(#32190464)
Seems exactly like broad phase and narrow phase in games physics engine.
Re:Ask HN: What are some cool but obscure data structures yo...
by djmips on Friday July 22, 2022 @06:56AM
(#32190624)
The same things get invented over and over again and named different things depending on the field. Sometimes it's not immediately clear that they are the same things mathematically.
In my recent experience working with collections containing million of documents, each containing a geoJSON-style polygon/multipolygon representing a property (i.e. a block of land), I found invalid geometries to occur for about 1 document in 1 million. For a while, I suspected the data-vendor was the cause, however it became more puzzling when other geospatial software confirmed they were valid. Eventually we traced the issue to the 2d-sphere index.
A very clever workaround was suggested by a colleague of mine, inspired by [1]. It preserved the original geometries. In each document, we added a new field containing the geometry's extent. A 2d-sphere index was then built on the extent field instead of the original geometry field. Invalid geometries were no longer an issue since we were dealing with much simpler geometries that were substantially larger than the max precision of the index.
When running geoIntersects queries on our collection of millions of documents, we did so in 2 steps (aggregation queries):
1. GeoIntersects on the extent field (uses the index).
2. On the result set from the last step, perform geoIntersects on the original geometry field (operates on a much smaller set of records compared to querying the collection directly)
[1] https://www.mongodb.com/docs/manual/tutorial/create-queries-...