4 ms·
My background is very different so this post made me sad. Doing tons of point-in-polygon tests is a common problem and should use spatial index. If we're testin
by phkahler 2y ago
My background is very different so this post made me sad. Doing tons of point-in-polygon tests is a common problem and should use spatial index. If we're testing N points against P polygons, the problem should scale O(N * log(P)) not O(N * P). The author was on the right track with bounding box tests, but that's more of a micro optimization. You want something like nested bounding boxes where each level contains 2 or more smaller ones, this is how you go from P to log(P) time - by never testing most of the polygons at all. I have my own preferred spatial index, but all of them tend toward this complexity improvement.
- cl3misch 2y agoWould "quadtree" be the keyword here? That's always the first thing I think of when handling distributed points and doing some (local) measure on them.
- nielsenmandela 2y agoYou want a spatial indexing scheme. Quadtree is one approach, but depending on the distribution of your data (both size + location), an RTree would be better. Related: - Quatree - RTree - BVH - Grid
- phkahler 2y ago>> Would "quadtree" be the keyword here? Quadtree is one option, and would be my choice for 2D. Most people seem to prefer other structures for various reasons. You may also look at BSP trees, BVH or nested Bounding Boxes. There are others as well.