2 ms·
Let's assume a naive approach. Also, assume each point falls within a polygon. For every point to test, you need, on average, to test half the polygons. Testin
by Someone 14y ago
Let's assume a naive approach. Also, assume each point falls within a polygon.
For every point to test, you need, on average, to test half the polygons. Testing a point against a polygon means testing the point against, on average, about half the polygon's edges. Each of those tests takes a multiplication, an addition, and a comparison.
That's 4E7 points times 2500 polygons times, at least, 1.5 edges. Total: 1.5E11 multiplications, additions, and comparisons.
With 100-sided polygons, it would be 1E13 or so multiplications/addition/comparison steps.
Memory pressure is dominated by polygon storage. 5000 poly's, 100 points each, is 500,000 edges at two doubles each, or 4MB. That fits comfortably in cache.
So, 1E9 multiplications/addition/comparison steps a second should be possible. That's 10,000 seconds or 3 hours.
=> Should be doable on one CPU in hours (famous last words)
- corresation 14y agoIt really is a fascinating sounding problem and I'd really like to see the source data (regions and points), if I'm understanding the problem right, to discern alternative approaches.