Wrong Douglas-Peucker implementation?
Hi all, I've noticed that the line simplification in JOSM works different to the one in mkgmap. Both implement a Douglas-Peucker algo, so I wondered why. It turned out that JOSM calculates the distance of point `px` to the line through(!) end-points `p1` and `p2`, while mkgmap calculates the distance to the segment between(1) those points. So, they get the same distance when the perpendicular is on the segment, but very different values when not. This page helps to see the difference: https://karthaus.nl/rdp/ It would be a bit faster to use distToLineSegment() (like JOSM) instead of shortestDistToLineSegment() but I am not sure which result is better. Any thouhts? Gerd
Hi Gerd, Josm's algorithm removes some spikes, which probably aren't common for real data and layer 0 of img. So differences aren't big. But maybe for lower resolution it could be better, especially for polygons. Wouldn't it be faster? -- Best regards, Andrzej
Hi Andrzej, I don't see any specific difference in the behaviour, but overall the JOSM algo removes a few more points compared to the mkgmap version. With r4763 you can simply replace the call to shortestDistToLineSegment() by distToLineSegment() in DouglasPeuckerFilter.java Reg. speed it probably doesn't matter that much. I looked at this because VisualVM claimed that Douglas-Peucker is responsible for a lot of run time but now I think that VisualVM was wrong. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Andrzej Popowski <popej@poczta.onet.pl> Gesendet: Dienstag, 8. Juni 2021 21:43 An: mkgmap-dev@lists.mkgmap.org.uk Betreff: Re: [mkgmap-dev] Wrong Douglas-Peucker implementation? Hi Gerd, Josm's algorithm removes some spikes, which probably aren't common for real data and layer 0 of img. So differences aren't big. But maybe for lower resolution it could be better, especially for polygons. Wouldn't it be faster? -- Best regards, Andrzej _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Firstly, the algo for DP when the start & end points are close but other points are more distant should be considered - maybe preserving the most distant points from the start & end or the points on the bounding box. DP using distance to line-through-points could reduce a very long line to a very short line if all the points are aligned. So, should stick with distance to line-segment Ticker
Hi Ticker, cannot follow. When start and end are close the first iteration will find the most distant point and continue with the two intervals. Do you have an example *.osm file that shows how JOSM will "reduce a very long line to a very short line"? Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 10. Juni 2021 10:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Wrong Douglas-Peucker implementation? Hi Firstly, the algo for DP when the start & end points are close but other points are more distant should be considered - maybe preserving the most distant points from the start & end or the points on the bounding box. DP using distance to line-through-points could reduce a very long line to a very short line if all the points are aligned. So, should stick with distance to line-segment Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Hi Ticker, you are right, JOSM is wrong. Simplify attached example with 10m tolerance. Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Gerd Petermann <gpetermann_muenchen@hotmail.com> Gesendet: Donnerstag, 10. Juni 2021 10:14 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Wrong Douglas-Peucker implementation? Hi Ticker, cannot follow. When start and end are close the first iteration will find the most distant point and continue with the two intervals. Do you have an example *.osm file that shows how JOSM will "reduce a very long line to a very short line"? Gerd ________________________________________ Von: mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von Ticker Berkin <rwb-mkgmap@jagit.co.uk> Gesendet: Donnerstag, 10. Juni 2021 10:07 An: Development list for mkgmap Betreff: Re: [mkgmap-dev] Wrong Douglas-Peucker implementation? Hi Firstly, the algo for DP when the start & end points are close but other points are more distant should be considered - maybe preserving the most distant points from the start & end or the points on the bounding box. DP using distance to line-through-points could reduce a very long line to a very short line if all the points are aligned. So, should stick with distance to line-segment Ticker _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk https://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
participants (4)
-
Andrzej Popowski -
Gerd Petermann -
Gerd Petermann
-
Ticker Berkin