[mkgmap-dev] [locator] Simplifying the check line in polygon

Sun May 15 13:31:40 BST 2011

Hi all,

I am thinking about how to reduce the processing time of the locator 
branch. One time consuming task is the check if a point, a line or a 
polygon lies inbetween, cuts or lies outside another polygon.

Processing time for this check is directly related to the number of 
nodes that define the polygon. So I have the idea to simplify the 
boundary polygons. By cutting some complex parts of the polygon the 
number of points should be lowered although most of the elements lying 
completely inside the polygons should still lying completely inside.
The elements that cut the simplified edges must be rechecked with the 
original polygon.

Does anyone know a suitable algorithm for that?
Any other ideas concerning this problem?

WanMil
-------------- next part --------------
A non-text attachment was scrubbed...
Name: simplifypolygon_1.svg
Type: image/svg+xml
Size: 3682 bytes
Desc: not available
Url : http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20110515/e204ef8f/attachment.bin 