[PATCH v1] Optimize filters for shapes
Hi, while working on the mp_cut branch I observed that some of the filter have some potential for improvements when dealing with shapes. 1st change: The RemoveEmpty filter let all shapes pass with at least 3 points. But there must be at least 4 points (1st==last point) to define a shape with a non zero area. 2nd change: The RoundCoordsFilter does not care if an area is rounded to a line which happens quite often. The patch tries to remove the line parts. The img file size is reduced slightly (~1%) using this patch. Anyhow I think there is more improvement possible. I have attached two gpx files. Bye the way the patch contains some commented lines that creates the GPX files for each polygon treated by the patch. 11315_16_org.gpx is the input polygon to the RoundCoordsFilter and 11315_16.gpx is the result (using the patch). Some possible improvements: * Straight lines sometimes contain more that one point and it should be easily possible to remove these additional points. * The filtered polygon sometimes still contains lines which are not removed by patch because the overlapping lines do not contain the same points. You can see this in the attached gpx in the upper middle of the right polygon block. * The filtered polygon could be simplified and sometimes split into more separate polygons which are now connected by a line. * Better resolution dependend filtering? I don't have time to do these improvements but maybe I could give some ideas what can be done. So if you anyone of you has time and fun to play with the filters just do it! Thanks WanMil
WanMil wrote
2nd change: The RoundCoordsFilter does not care if an area is rounded to a line which happens quite often. The patch tries to remove the line parts.
please check: the patch ignores preserved points, so I think it could break routing. WanMil wrote
Anyhow I think there is more improvement possible. I have attached two gpx files. Bye the way the patch contains some commented lines that creates the GPX files for each polygon treated by the patch. 11315_16_org.gpx is the input polygon to the RoundCoordsFilter and 11315_16.gpx is the result (using the patch).
Some possible improvements: * Straight lines sometimes contain more that one point and it should be easily possible to remove these additional points. * The filtered polygon sometimes still contains lines which are not removed by patch because the overlapping lines do not contain the same points. You can see this in the attached gpx in the upper middle of the right polygon block. * The filtered polygon could be simplified and sometimes split into more separate polygons which are now connected by a line. * Better resolution dependend filtering?
I would assume that straight lines are filtered by DouglasPeuckerFilter ? (at least now that I've committed the removeShortArcs patch) I did already look for other algos, eg. the VW algo http://www2.dcs.hull.ac.uk/CISRG/publications/DPs/DP10/DP10.html sounds like a possible alternative to DouglasPeucker. On the other hand, I assume that the input for the filters will change with the intended mp_cut changes, so we may end up solving the same problem at two different places. Gerd -- View this message in context: http://gis.19327.n5.nabble.com/PATCH-v1-Optimize-filters-for-shapes-tp574414... Sent from the Mkgmap Development mailing list archive at Nabble.com.
WanMil wrote
2nd change: The RoundCoordsFilter does not care if an area is rounded to a line which happens quite often. The patch tries to remove the line parts.
please check: the patch ignores preserved points, so I think it could break routing.
You cannot route over polygons. So I don't expect that removing a point from a polygon can break routing?
WanMil wrote
Anyhow I think there is more improvement possible. I have attached two gpx files. Bye the way the patch contains some commented lines that creates the GPX files for each polygon treated by the patch. 11315_16_org.gpx is the input polygon to the RoundCoordsFilter and 11315_16.gpx is the result (using the patch).
Some possible improvements: * Straight lines sometimes contain more that one point and it should be easily possible to remove these additional points. * The filtered polygon sometimes still contains lines which are not removed by patch because the overlapping lines do not contain the same points. You can see this in the attached gpx in the upper middle of the right polygon block. * The filtered polygon could be simplified and sometimes split into more separate polygons which are now connected by a line. * Better resolution dependend filtering?
I would assume that straight lines are filtered by DouglasPeuckerFilter ?
Probably not. Otherwise the file size of the img files should have been the same.
(at least now that I've committed the removeShortArcs patch) I did already look for other algos, eg. the VW algo http://www2.dcs.hull.ac.uk/CISRG/publications/DPs/DP10/DP10.html sounds like a possible alternative to DouglasPeucker. On the other hand, I assume that the input for the filters will change with the intended mp_cut changes, so we may end up solving the same problem at two different places.
Yes and no. The mp_cut changes will only affect how polygons are cut when they are part of a multipolygon. But there are many polygons that are not. On the other hand I also use the algorithm of the RoundCoordsFilter in the mp_cut branch (not yet committed) and therefore observe exactly the same problems. So improving the RoundCoordsFilter algo will also solve problems in the mp_cut branch. WanMil
Gerd
please check: the patch ignores preserved points, so I think it could break routing.
You cannot route over polygons. So I don't expect that removing a point from a polygon can break routing?
The filter is also used in MapBuilder.processLines()
I would assume that straight lines are filtered by DouglasPeuckerFilter ?
Probably not. Otherwise the file size of the img files should have been the same.
I don't understand. Your patch doesn't change the number of points on straigth lines, does it?
(at least now that I've committed the removeShortArcs patch) I did already look for other algos, eg. the VW algo http://www2.dcs.hull.ac.uk/CISRG/publications/DPs/DP10/DP10.html sounds like a possible alternative to DouglasPeucker. On the other hand, I assume that the input for the filters will change with the intended mp_cut changes, so we may end up solving the same problem at two different places.
Yes and no. The mp_cut changes will only affect how polygons are cut when they are part of a multipolygon. But there are many polygons that are not. On the other hand I also use the algorithm of the RoundCoordsFilter in the mp_cut branch (not yet committed) and therefore observe exactly the same problems. So improving the RoundCoordsFilter algo will also solve problems in the mp_cut branch.
OK. The RoundCoordsFilter really looks a bit brutal ;-) Gerd
please check: the patch ignores preserved points, so I think it
could break
routing.
You cannot route over polygons. So I don't expect that removing a point from a polygon can break routing?
The filter is also used in MapBuilder.processLines()
You are right. I thought my patch checks if the element is a MapShape like it is done in the RemoveEmpty. But it doesn't. So this has to be added and/or be extended to check for preserved points.
I would assume that straight lines are filtered by
DouglasPeuckerFilter ?
Probably not. Otherwise the file size of the img files should have been the same.
I don't understand. Your patch doesn't change the number of points on straigth lines, does it?
No, but it removes spikes from polygons. So the following polygon: a-b-c-d-c-e-a will become a-b-c-e-a I don't know if the DouglasPeuckerFilter does the same?
(at least now that I've committed the removeShortArcs patch) I did already look for other algos, eg. the VW algo http://www2.dcs.hull.ac.uk/CISRG/publications/DPs/DP10/DP10.html sounds like a possible alternative to DouglasPeucker. On the other hand, I assume that the input for the filters will change with the intended mp_cut changes, so we may end up solving the same
problem
at two different places.
Yes and no. The mp_cut changes will only affect how polygons are cut when they are part of a multipolygon. But there are many polygons that are not. On the other hand I also use the algorithm of the RoundCoordsFilter in the mp_cut branch (not yet committed) and therefore observe exactly the same problems. So improving the RoundCoordsFilter algo will also solve problems in the mp_cut branch.
OK. The RoundCoordsFilter really looks a bit brutal ;-)
Gerd
Hi WanMil, I've committed the change to the RemoveEmptyFilter, but not the change to RoundCoordsFilter. After I added switch so that your change did not handle roads the effect was near zero. Ciao, Gerd
Date: Sun, 13 Jan 2013 18:22:25 +0100 From: wmgcnfg@web.de To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] [PATCH v1] Optimize filters for shapes
please check: the patch ignores preserved points, so I think it
could break
routing.
You cannot route over polygons. So I don't expect that removing a point from a polygon can break routing?
The filter is also used in MapBuilder.processLines()
You are right. I thought my patch checks if the element is a MapShape like it is done in the RemoveEmpty. But it doesn't. So this has to be added and/or be extended to check for preserved points.
I would assume that straight lines are filtered by
DouglasPeuckerFilter ?
Probably not. Otherwise the file size of the img files should have been the same.
I don't understand. Your patch doesn't change the number of points on straigth lines, does it?
No, but it removes spikes from polygons. So the following polygon: a-b-c-d-c-e-a will become a-b-c-e-a
I don't know if the DouglasPeuckerFilter does the same?
(at least now that I've committed the removeShortArcs patch) I did already look for other algos, eg. the VW algo http://www2.dcs.hull.ac.uk/CISRG/publications/DPs/DP10/DP10.html sounds like a possible alternative to DouglasPeucker. On the other hand, I assume that the input for the filters will change with the intended mp_cut changes, so we may end up solving the same
problem
at two different places.
Yes and no. The mp_cut changes will only affect how polygons are cut when they are part of a multipolygon. But there are many polygons that are not. On the other hand I also use the algorithm of the RoundCoordsFilter in the mp_cut branch (not yet committed) and therefore observe exactly the same problems. So improving the RoundCoordsFilter algo will also solve problems in the mp_cut branch.
OK. The RoundCoordsFilter really looks a bit brutal ;-)
Gerd
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://lists.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Gerd,
Hi WanMil,
I've committed the change to the RemoveEmptyFilter, but not the change to RoundCoordsFilter.
Good.
After I added switch so that your change did not handle roads the effect was near zero.
What do you mean with effect? I think that you cannot measure the effect just by checking the img file sizes. I observed that the RoundCoordsFilter is far away from being a good filter for polygons. The patch did not fix all these problems but it was a first try to improve things. So it's ok not to commit it but the problem still exists that the filter is suboptimal. I think it does not make sense to focus on the result of a single filter without analysing what the other filters are doing the with its result. On the other hand it doesn't hurt trying to optimize each filter.
Ciao, Gerd
WanMil
Hi WanMil,
After I added switch so that your change did not handle roads the effect was near zero.
What do you mean with effect? I think that you cannot measure the effect just by checking the img file sizes.
I know that the img file size changes do not increase in steps of one byte. Well, your special case did not occur in my test data. Maybe that was bad luck, I try with some more tiles. I thought the change is meant to reduce the *.img size? Or do you think that it is an error to have such spikes in the *.img? Ciao, Gerd
Hi WanMil,
After I added switch so that your change did not handle roads the effect was near zero.
What do you mean with effect? I think that you cannot measure the effect just by checking the img file sizes.
I know that the img file size changes do not increase in steps of one byte. Well, your special case did not occur in my test data. Maybe that was bad luck, I try with some more tiles. I thought the change is meant to reduce the *.img size? Or do you think that it is an error to have such spikes in the *.img?
Ciao, Gerd
Reducing the img file size is a nice subeffect. As long as I don't know for sure that spikes are not an error I would avoid to leave them in the img. Sometimes the result of the RoundCoordsFilter is an invalid polygons, which means the polygon might be self intersecting and/or contains spikes and holes as it could be seen in my example. These invalid polygons are forwarded to other filters. To be honest: I haven't checked if my example polygon looks bad in the map. But checking the code I see the following might happen: 1. RoundCoordsFilter creates an invalid polygon with hole 2. PolygonSplitterFilter might split the polygon because it is too large. It converts the polygon to a java.awt.geom.Area object, splits it into two halves and converts it back in the method PolygonSplitterBase.areaToShapes(..) method. This method does not check the orientation of the returned polygons and therefore converts the hole to same type the polygon has - in other words the hole is removed. Of course we could say this is an error of the PolygonSplitterBase.areaToShapes(..) method (and we can fix it) but I think it would be worthy to check and optimize the whole chain a polygon goes through. Maybe we find needless steps we can remove, maybe we find other errors we can fix and maybe we can improve some steps which will improve the overall results. At the moment I guess nobody can say for sure what really happens in the long chain. WanMil
Hi WanMil,
Reducing the img file size is a nice subeffect. As long as I don't know for sure that spikes are not an error I would avoid to leave them in the img.
I agree.
Sometimes the result of the RoundCoordsFilter is an invalid polygons, which means the polygon might be self intersecting and/or contains spikes and holes as it could be seen in my example. These invalid polygons are forwarded to other filters.
To be honest: I haven't checked if my example polygon looks bad in the map. But checking the code I see the following might happen: 1. RoundCoordsFilter creates an invalid polygon with hole 2. PolygonSplitterFilter might split the polygon because it is too large. It converts the polygon to a java.awt.geom.Area object, splits it into two halves and converts it back in the method PolygonSplitterBase.areaToShapes(..) method. This method does not check the orientation of the returned polygons and therefore converts the hole to same type the polygon has - in other words the hole is removed.
Of course we could say this is an error of the PolygonSplitterBase.areaToShapes(..) method (and we can fix it) but I think it would be worthy to check and optimize the whole chain a polygon goes through. Maybe we find needless steps we can remove, maybe we find other errors we can fix and maybe we can improve some steps which will improve the overall results. At the moment I guess nobody can say for sure what really happens in the long chain.
Yes, I got the same impression. I started to add some createGPX calls to be able to compare the input coming from StyledConverter and the output that is written to the img (if at all). I think the most obvious problem is the cutOutInnerPolygons() method that creates the thin areas which are later deformed by the filters. I will focus on that. Ciao, Gerd
Hi WanMil, WanMil wrote
Reducing the img file size is a nice subeffect. As long as I don't know for sure that spikes are not an error I would avoid to leave them in the img.
I've analysed the filters a bit more. It seems that it is better to let DouglasPeuckerFilter "see" the data that RoundCoordsFilter produces (including spikes) Ive coded a new filter that can be used to filter spikes and and points on straight lines, see attached patch. It reduces img size a little bit, but also increases run time a little bit. It is able to find obsolete points on diagonal lines, maybe that is not really needed because I only see them on vertical and horizontal lines. Gerd filter_shapes_v1.patch <http://gis.19327.n5.nabble.com/file/n5745401/filter_shapes_v1.patch> -- View this message in context: http://gis.19327.n5.nabble.com/PATCH-v1-Optimize-filters-for-shapes-tp574414... Sent from the Mkgmap Development mailing list archive at Nabble.com.
participants (3)
-
Gerd Petermann -
GerdP
-
WanMil