Ну из того, что я понял по описанию, я бы использовал Quad-tree для того, чтобы сгруппировать и точки и полигоны по областям. Минимальный уровень Qaud я бы делал таким, чтобы его размер был много меньше размера полигона, чтобы в случае пересечения полигоном Qaud-a он бы разбивался на 2 или несколько треугольников. Ну и далее сам алгоритм проверки: находим Qaud для точки (константная по времени операция, т.к. по позиции можно формулой определить), смотрим, есть ли в этом Qaud часть заданного полигона, проверяем, полностью ли эта часть содержится в Quad или нет., если полностью - все ок, если не полностью - делим на треугольники, образованные точками пересечения полигона и Quad-а и проверяем попадание точки в треугольник, принадлежащий полигону.
