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

Sun May 15 15:30:11 BST 2011

On Sun, 2011-05-15 at 15:42 +0200, WanMil wrote:
> Am 15.05.2011 15:10, schrieb Jon Burgess:
> > 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
> >
> 
> Jon,
> 
> sounds great! I already tested the performance of different RTree 
> implementations and the JTS was one of the best so that's one reason 
> more to use the JTS lib.
> 
> Maybe you can give some hints and links (to classes or methods?) how JTS 
> can help to solve the following things:
> 
> 1. A street (a line) may cross multiple boundaries (polygons). Is there 
> a JTS class that does the splitting?

I think the intersection() between the polygon and linestring geometries
is what you are looking for. 
http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/geom/Geometry.html#intersection%28com.vividsolutions.jts.geom.Geometry%29

In postgis the equivalent geos intersection function is used for
ST_Intersection(). An example given on the page below has trail
geometries being clipped to country polygons.

http://postgis.refractions.net/documentation/manual-1.5/ST_Intersection.html

> 2. How does this class handle parts that lie exactly on the border of 
> the polygon?

I don't know.

   Jon