[mkgmap-dev] pois and wrong citynames
From Chris Miller chris_overseas at hotmail.com on 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.
- Previous message: [mkgmap-dev] pois and wrong citynames
- Next message: [mkgmap-dev] New mkgmap styles
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the mkgmap-dev mailing list