3 ms·
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
by buckhx 11y ago
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.
- brianwawok 11y agoWell 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.
- sesquipedalian 11y agoI'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.