Hi WanMil,
Date: Wed, 2 May 2012 22:46:11 +0200 From: wmgcnfg@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] [Patch] Improve boundary splitting
Hi Gerd, I have some question :-)
1. If the intersect algorithm is noticeably faster it should not be buried into the boundary section! Please have a look a the common Clipper classes (PolygonClipper, AreaClipper etc.). Maybe it improves the overall mkgmap performance if you include the new algorithm in these classes.
Well, it is much faster, but it cannot be used everywhere. See 2.
2. Wikipedia points out "Note that if the subject polygon was concave at vertices outside the clipping polygon, the new polygon may have coincident (i.e. overlapping) edges – this is acceptable for rendering, but not for other applications such as computing shadows." Did you test if this is a problem?
Yes. The test cases in BoundarySplitter.main() show that you can get dangling edges, e.g. something like this: ---------- | | | | \__| For the boundaries, this doesn't matter because we convert to java.awt.geom.Area before we use the result, and this conversion removes the dangling edges. It is also required that the original shape is an java.awt.geom.Area because it must not be self intersecting or contain holes. I did not want to change the rest of the code because I did not see many calls, so the possible improvement is rather small and the risk to break something was too large. The Sutherland-Hodgman algorithm is only useful when you split multiple times without using the conversion to java.awt.geom.Area.
3. I have posted a first patch to use precompiled sea files. I want to (or better I do) use the boundary classes to read and write the precompiled files. This will require some changes to them: - The RASTER size should not be defined by a constant. For sea files I want to use a RASTER size 2^n because that reduces some visual artefacts. - Most of BoundaryUtil must be transferred to a class BoundaryLoader which is then no longer static. - Maybe the BoundarySaver and BoundaryLoader can be splitted to more classes to implement the different formats (quadtree and raw). So if you implement any changes to the existing classes please do not introduce more uses of the static methods and constants.
OK. Gerd
Have fun! WanMil
Hi WanMil,
attached is a patch that uses an optimized implementation of the Sutherland-Hodgman algorithm
http://en.wikipedia.org/wiki/Sutherland-Hodgeman wikipedia
which is much faster than the area.intersect. It is only used to create the precompiled boundaries.
The improvements depend on the continent, for africa I see 130 secs with r2272 and 84 secs with the patched version. For asia, I see only a small improvement of ~ 10%
On my machine, the precompilation of the boundaries is now quite often waiting for the disk.
http://gis.19327.n5.nabble.com/file/n5670294/BoundarySplitter.patch BoundarySplitter.patch
Gerd
-- View this message in context: http://gis.19327.n5.nabble.com/Patch-Improve-boundary-splitting-tp5670294p56... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev