Efficient method to check which polygon a certain located inside

Question

In my JavaScript application I have more than 30+ polygons. They are defined like this:

polygons:[
{name:'xx',bounds:[20,20,60,20,50,40,30,10...],minzoom:0,maxzoom:5},
{name:'yy',bounds:[.....],minzoom:6,maxzoom:8},
........
]

Now given a certain point like [10,10] with zoom 4.

Which is the fast way to check which polygon this point is located inside?

My first thought is iterator the polygons, and to check if the point is inside the polygon.

Then this question came to be a point-in-polygon question which have a lot of answers at stackoverflow.

I just wonder if there is any alternative methods?

Answer 1

Assuming the polygons do not overlap (or that if they do, you're only interested in the top-most polygon), you can employ the "point-in-polygon" solution that involves a canvas:

• Create a canvas big enough to hold all your polygons.
• Draw each polygon in a different colour, one after the other
• Look up what colour the pixel is where the point is located
• This will tell you the polygon that's there.

Note that you don't even need them to be human-distinguishable colours, you could literally use #000000, #000001, #000002 and so on, and use the colour's hex code as the index of the polygon.