3 ms·
how fast is within? does it use ray tracing?
by 3adawi 10y ago
how fast is within? does it use ray tracing?
- tidwall 10y ago> how fast is within? I replied to another question shortly ago regarding performance. https://news.ycombinator.com/item?id=13285538 https://news.ycombinator.com/item?id=13285538 > does it use ray tracing? No.
- bpicolo 10y agoDepends on which method you use I assume. For geohashing, WITHIN should be best case O(1) and worst case O(n) depending on specificity you care about, where n is the number of geohash cells you need to generate to match the bounding box you care about (which is typically pretty small unless you want, like, a 1km box with 1cm granularity) Frontloading computation into generating smart data structures give you better choices here.
- tidwall 10y agoSorry, my previous answer was not very descriptive. The WITHIN call will be on average O(log(N)) because all objects are stored in an rtree. But it's usually very very fast to locate objects based on their outermost bounding area. The complexity of the object will add to the duration. Simple points are super fast, like sub microsecond fast in many cases. A MultiPolygon can be much slower. Tile38 uses a modified raycasting algorithm, not raytracing for it's polygon detections.