0

Task

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.

Solution

Simple point-in-polygon test for every hit-test.

Problem

Far too slow.

Improvement

Rasterize the polygons and check which polygon the pixel of the hit-tests belongs to.

New problem

Rasterization of the polygons is slow. I'm using this algorithm: http://alienryderflex.com/polygon_fill/

Idea

Rasterize the polygons on the GPU since it's optimized for this task and can perform it in hardware.

Question

What do you think about my idea and can you give me advice where to start? Will it lead to high performance?

Sidenote

The area is sparsly covered with polygons. I want to maintain a list of pixels instead of a bitmap.

user2033412
  • 1,950
  • 2
  • 27
  • 47
  • Have you tried rasterization with standard graphic libraries (GDI, Direct** for Windows, OpenGL etc)? – MBo Oct 25 '14 at 13:31
  • These libraries always paint directly on the screen. I don't want to paint. I want to perform hit-tests. – user2033412 Oct 25 '14 at 13:42
  • No, they can paint to in-memory context (select bitmap in MemDC). This is effective way to solve problems like yours, if polygon coordinates are in reasonable limits – MBo Oct 25 '14 at 13:46
  • How would I get the pixels hit by the polygon? Will I have to go through the whole bitmap? Wouldn't that be inefficient (imagine a thin horseshoe as polygon)? – user2033412 Oct 25 '14 at 14:10
  • Why would you want the pixels hit by the polygon? You could just index into the bitmap at whatever place you were doing a hit test, and get just 1 pixel that shows you whether it hit or not. – harold Oct 25 '14 at 14:23
  • Are the polygons in 2D? Are they connected? Can you post an example image? – Stefan Haustein Oct 25 '14 at 14:26
  • I need to know which polygon is hit. – user2033412 Oct 25 '14 at 14:27
  • p.s. Are they convex? I suppose you are already doing a quick check if a point is in the square/cube spanned by the coordinate min/max before doing a detailed check? – Stefan Haustein Oct 25 '14 at 14:33
  • The polygons are not convex. :-( – user2033412 Oct 25 '14 at 14:34
  • Fill bitmap with 0 (black color). Draw (fill) the first polygon with color 0x000001, the second one with color 0x000002 etc. Pick a pixel at hit-test coordinates. Its color is for polygon number (if they don't intersect) – MBo Oct 25 '14 at 14:39
  • Another approach is to use a spatial database like PostGIS. They can do efficient point-in-polygon queries using R-trees among other things. – nwellnhof Oct 25 '14 at 15:33

1 Answers1

1

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).

Community
  • 1
  • 1
Stefan Haustein
  • 18,427
  • 3
  • 36
  • 51