[Patch] Improve boundary splitting

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

[Patch] Improve boundary splitting

Gerd Petermann
Hi WanMil,

attached is a patch that uses an optimized implementation of the Sutherland-Hodgman algorithm

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.

BoundarySplitter.patch

Gerd
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Improve boundary splitting

WanMil
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.

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?

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.

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-tp5670294p5670294.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Improve boundary splitting

Gerd Petermann
Hi WanMil,

> Date: Wed, 2 May 2012 22:46:11 +0200

> From: [hidden email]
> To: [hidden email]
> 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-tp5670294p5670294.html
> > Sent from the Mkgmap Development mailing list archive at Nabble.com.
> > _______________________________________________
> > mkgmap-dev mailing list
> > [hidden email]
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Improve boundary splitting

WanMil
In reply to this post by Gerd Petermann
Hi Gerd,

I decided not to include your patch.
The improvement is done only for the precompilation step. So it affects
only a very few people that precompile the boundaries.
The patch itself adds another conversion step from Area to Shape format.
In my point of view this is the breaking point where the source code
will be no longer maintainable.

Before adding some special algorithms to improve performance it is
necessary to overwork the boundary related classes and give them a clean
structure. The current structure is the result of implementing a totally
new function of mkgmap and improving and changing it completely for
performance reasons (with a great result!). Now once it's working there
is the time for some restructuring.

Sorry for that! I hope you understand my reasons.

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-tp5670294p5670294.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Improve boundary splitting

Gerd Petermann
Hi WanMil,


> Date: Sun, 6 May 2012 20:56:48 +0200

> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] [Patch] Improve boundary splitting
>
> Hi Gerd,
>
> I decided not to include your patch.
> The improvement is done only for the precompilation step. So it affects
> only a very few people that precompile the boundaries.
> The patch itself adds another conversion step from Area to Shape format.
> In my point of view this is the breaking point where the source code
> will be no longer maintainable.

I used  the Shape superclass because it allows to pass Area and Path2D parameters
without conversion. In my eyes, Area should only be used when we need its methods
like contains or intersect. It is very inefficient when you just want to store
a closed way with double precision that is already known to be not self-intersecting.

>
> Before adding some special algorithms to improve performance it is
> necessary to overwork the boundary related classes and give them a clean
> structure. The current structure is the result of implementing a totally
> new function of mkgmap and improving and changing it completely for
> performance reasons (with a great result!). Now once it's working there
> is the time for some restructuring.

Yes, that's true. The methods are spread over multiple files, and I had
problems to decide where to put new methods.
I guess you working on the restructuring  to finish the precompiled-sea code?

>
> Sorry for that! I hope you understand my reasons.

Yes, sure.  I'll continue working on splitter now.

Gerd

>
> 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-tp5670294p5670294.html
> > Sent from the Mkgmap Development mailing list archive at Nabble.com.
> > _______________________________________________
> > mkgmap-dev mailing list
> > [hidden email]
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Improve boundary splitting

WanMil
> Hi WanMil,
>
>
>  > Date: Sun, 6 May 2012 20:56:48 +0200
>  > From: [hidden email]
>  > To: [hidden email]
>  > Subject: Re: [mkgmap-dev] [Patch] Improve boundary splitting
>  >
>  > Hi Gerd,
>  >
>  > I decided not to include your patch.
>  > The improvement is done only for the precompilation step. So it affects
>  > only a very few people that precompile the boundaries.
>  > The patch itself adds another conversion step from Area to Shape format.
>  > In my point of view this is the breaking point where the source code
>  > will be no longer maintainable.
>
> I used the Shape superclass because it allows to pass Area and Path2D
> parameters
> without conversion. In my eyes, Area should only be used when we need
> its methods
> like contains or intersect. It is very inefficient when you just want to
> store
> a closed way with double precision that is already known to be not
> self-intersecting.
>
>  >
>  > Before adding some special algorithms to improve performance it is
>  > necessary to overwork the boundary related classes and give them a clean
>  > structure. The current structure is the result of implementing a totally
>  > new function of mkgmap and improving and changing it completely for
>  > performance reasons (with a great result!). Now once it's working there
>  > is the time for some restructuring.
>
> Yes, that's true. The methods are spread over multiple files, and I had
> problems to decide where to put new methods.
> I guess you working on the restructuring to finish the precompiled-sea code?

I started with that. But I don't have very much time at the moment. So
it will take some time until I have the first good results.

>
>  >
>  > Sorry for that! I hope you understand my reasons.
>
> Yes, sure. I'll continue working on splitter now.

Great! We keep the patch in mind and try to integrate it at a later step.

WanMil

>
> Gerd
>
>  >
>  > 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-tp5670294p5670294.html
>  > > Sent from the Mkgmap Development mailing list archive at Nabble.com.
>  > > _______________________________________________
>  > > mkgmap-dev mailing list
>  > > [hidden email]
>  > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>  >
>  > _______________________________________________
>  > mkgmap-dev mailing list
>  > [hidden email]
>  > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev