On Fri, May 7, 2010 at 11:55 AM, Minko <ligfietser@online.nl> wrote:
I can't add too much here, but I think it is worth mentioning that, as I understand it, the algorithm for determining if a point lies within a polygon can be quite performance intensive:
http://en.wikipedia.org/wiki/Point_in_polygon
There are of course libraries for dealing with this problem, but I still think the performance question is still significant.
Performance shouldn't be a problem, since there's no need to perform a full polygon intersection test for each point and each city boundary. If a pre-processing stage builds up a data structure (eg a quadtree, where each node has at most a single polygon edge segment running through it), the lookups become pretty cheap (O(log n)). Other options include narrowing down the tests using bounding rectangles around each polygons with perhaps an r-tree (assuming some bounding rectangles overlap?) to rapidly determine which bounding rectangle to test further. Of course implementing the above is a fair amount of work, however it'll be much much faster than the brute force approach. If anyone is interested in actually implementing this, feel free to ping me for further ideas or details.