[mkgmap-dev] pois and wrong citynames

Sat May 8 17:16:34 BST 2010

> On Fri, May 7, 2010 at 11:55 AM, Minko <ligfietser at 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.