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/Prep...
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.... 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