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

Sun May 15 14:10:40 BST 2011

On Sun, 2011-05-15 at 14:31 +0200, WanMil wrote:
> 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?

This sounds like the prepared geometries supported in geos and jts. 
http://trac.osgeo.org/geos/wiki/PreparedGeometry 
http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/geom/prep/PreparedPolygon.html

A few months back osm2pgsql moved to using prepared polygons for part of
its multipolygon processing and this accelerated the processing of one
very complex multipolygon with 100k+ nodes from a couple of hours to a
couple of minutes. 

  Jon