1

The quad tree suggestion by D.W. is interesting. I want to expand on it here. The principle of it is to break the area into big (and then progressively smaller) squares and check whether these squares are fully in or fully out of any polygon. Let's call these cases "black" and "white" respectively. If a big square is either black or white you do not have to ...


1

An alternative approach is to use a quad-tree. One approach is to store each polygon in the deepest node that corresponds to a region that wholly contains the polygon. Given a test point, you traverse the quad-tree, and when you visit a node, you do a point-in-polygon test for each polygon associated with that node. This then lets you do a smaller number ...


Only top voted, non community-wiki answers of a minimum length are eligible