4 ms·
I'm not terribly familiar with geo algorithms but I'm curious why it's worthwhile taking the two layer approach. Can't you precompute the X and Y minima and ma
by mbell 11y ago
I'm not terribly familiar with geo algorithms but I'm curious why it's worthwhile taking the two layer approach.
Can't you precompute the X and Y minima and maxima for each geo fence and throw out 99% of candidates extremely quickly? In other words store the bounding rectangle for each geofence. Even with 100,000s of entries we're talking 4 primitive type comparisons per entry to exclude all non-possible candidates. I would have a hard time believing this is slower than ray casting to city geofences.
- silenz 11y agoIt would still be faster with a two layer approach. Check 100 000 entries (4 comparisons each) - > filter out 1% to do expensive calculations on. Vs Check 25 cities (4 comparisons each) - > filter out 1/25 Do another easy run on the filtered 4000 and get the same areas to do expensive calculations on as above. That's 25+4000 easy calculations against 100 000. But yeah, I'm not sure why they seem to go the hard route from the beginning.
- mbell 11y agoThat assumes the cities have rectangular boundaries, at least the inference I got from the article is that they are also polygonal geofences. If you have a nested series of rectangular bounding boxes you're well on your way to building an R-tree.