Perform many hit-tests on polygons. I have about 10,000 polygons with 1,000 points each. About 100,000,000 hit-tests will be performed against these polygons. The polygons may touch each other but never overlap.
Simple point-in-polygon test for every hit-test.
Far too slow.
Rasterize the polygons and check which polygon the pixel of the hit-tests belongs to.
Rasterization of the polygons is slow. I'm using this algorithm: http://alienryderflex.com/polygon_fill/
Rasterize the polygons on the GPU since it's optimized for this task and can perform it in hardware.
What do you think about my idea and can you give me advice where to start? Will it lead to high performance?
The area is sparsly covered with polygons. I want to maintain a list of pixels instead of a bitmap.
This answer suggests to use the GPU if you can: How can I determine whether a 2D Point is within a Polygon?
Your case seems to be dominated by the hit tests, which are O(1) with rasterization. GPUs are able to rasterize to memory, but I am not aware of any GPU / rendering API that is able to work with a list of points. Also, with a list of points, you may lose the O(1) runtime for the hit check. You may be able to save some memory by using a 16 bit raster buffer (not sure if that's feasible with your GPU setup -- but you only seem to need 10000 colors).