Efficient Polygon intersection test

Questions
1

I have several thousand polygons from a geographical map.
What is the most recommended way to do intersection test or hover test on such large polygons without hitting much of the performance.

2

Are these polygons static or moving on the map?

3

Thanks for replying. The polygons are static in nature.

4

Hi @giraphics,

I think you can get it done with a physics engine like ammo.js. You can make each side of polygon a rotated thin box (OBB) and set it as obstacle. And delegate the heavy calculation to ammo.js.

If you want to implement it yourself, you first want to avoid checking all the OBB obstacles. You can divide your map to n * m grid cells. And you partition the OBBs into these grid cells. Given the current position of your moving entity, you can find the grid cells that are within certain radius of your moving entity, and then you only need to do collision detection on the OBBs within these close grid cells. I remember there was a post about this a few weeks ago. I will add the link if I can find it.

5

Thanks, Slin for your advice.