Re:How We Built Uber’s Highest Query per Second Service Usin...
by buckhx on Tuesday March 01, 2016 @05:03PM
(#11206476)
Raycasting is a pretty expensive operation since you have to check every edge of the polygon. Honestly I'm guessing they implemented the brute force method and called it good enough. Otherwise they would have posted comparisons as to why they stuck with brute force.
[ Parent
| on HN ]
Re:How We Built Uber’s Highest Query per Second Service Usin...
by brianwawok on Tuesday March 01, 2016 @05:05PM
(#11206483)
Well they had a clearly defined goal (which is rare!). 99% of requests in <= 100ms. So if brute force was a very simple algo and met the goal - hey why not?
If you can come up with a goal of what you need the response times to be, I think the easiest (in terms of readability, testability, length, etc) solution to meet the goal should win.
Re:How We Built Uber’s Highest Query per Second Service Usin...
by sesquipedalian on Tuesday March 01, 2016 @07:16PM
(#11207263)
I've found that BSP trees are a quite elegant, albeit, more complicated alternative for handling point-in-polygon queries compared to raycasting. Essentially, it decomposes an arbitrary non-convex polygon into a binary tree of half-spaces. A point-in-poly test then just becomes a binary search.
That being said sometimes brute force is good enough.