[Patch] Douglas-Peucker implementation is wrong

[GerdP]

What steps will reproduce the problem?

1. Load attached file
2. Simplify with 10m error

What is the expected result?

No change

What happens instead?

Very long line is shortened to a very short line

Please provide any additional information below. Attach a screenshot if possible.

The Douglas-Peucker implementation should calculate the distance to the segment between the end nodes, not the the distance to the line through those nodes.

URL:https://josm.openstreetmap.de/svn/trunk
Repository:UUID: 0c6e7542-c601-0410-84e7-c038aed88b3b
Last:Changed Date: 2021-06-02 22:03:39 +0200 (Wed, 02 Jun 2021)
Build-Date:2021-06-02 20:11:30
Revision:17919
Relative:URL: ^/trunk

Identification: JOSM/1.5 (17919 en) Windows 10 64-Bit
OS Build number: Windows 10 Home 2009 (19043)
Memory Usage: 422 MB / 3641 MB (282 MB allocated, but free)
Java version: 1.8.0_221-b11, Oracle Corporation, Java HotSpot(TM) 64-Bit Server VM
Look and Feel: com.sun.java.swing.plaf.windows.WindowsLookAndFeel
Screen: \Display0 1920×1080 (scaling 1.00×1.00)
Maximum Screen Size: 1920×1080
Best cursor sizes: 16×16→32×32, 32×32→32×32
System property file.encoding: Cp1252
System property sun.jnu.encoding: Cp1252
Locale info: en_DE
Numbers with default locale: 1234567890 -> 1234567890
Dataset consistency test: No problems found

Plugins:
+ apache-commons (35524)
+ buildings_tools (35756)
+ contourmerge (v0.1.8)
+ ejml (35458)
+ geotools (35458)
+ imagery-xml-bounds (35723)
+ jaxb (35543)
+ jts (35458)
+ o5m (35640)
+ opendata (35640)
+ pbf (35720)
+ poly (35640)
+ reltoolbox (35640)
+ reverter (35732)
+ undelete (35640)
+ utilsplugin2 (35691)

Validator rules:
+ c:\josm\core\resources\data\validator\geometry.mapcss
+ d:\java_tools\JOSM\mygeometry.mapcss

[GerdP]

See also ​http://gis.19327.n8.nabble.com/Wrong-Douglas-Peucker-implementation-tt5992886.html

[GerdP]

The patch adds code to determine the closest point on the segment, taken from Geometry.
An alternative might be to use Geometry.getSegmentNodeDistSq(EastNorth s1, EastNorth s2, EastNorth p) and drop the code that is impplemented in SimplifyWayAction, but those use rather simple distance calculations, so results are different for large objects. Not sure if this matters.

[GerdP]

Hmm, the distance results from Geometry depend on the projection settings. I always expected that they return values in metres, maybe with small rounding differences, but the values are completely different.
How can that ever work?

[taylor.smock]

Replying to GerdP:

Hmm, the distance results from Geometry depend on the projection settings. I always expected that they return values in metres, maybe with small rounding differences, but the values are completely different.
How can that ever work?

Good question. Last time I was messing around with Geometry, I think I noted that the return units were in meters or that of the current projection. I think I went that route since I assumed that is what the current measurements did.

Looking at it again (Geometry#getDistance),

• LatLon#greatCircleDistance always returns meters (hardcoded to use WGS84)
• The rest of the methods are reliant upon the distance calculations for EastNorth (or Coordinate), which are dependent upon the projection (but always Euclidean).

Solutions:

• Convert all the EastNorth objects into LatLon objects and reuse the LatLon#greatCircleDistance method.
• Add a greatCircleDistance method to EastNorth and modify the greatCircleDistance method in LatLon to use the current projection.

[Don-vip]

Milestone renamed

[GerdP]

In 18316/josm:

fix #20982: Douglas-Peucker implementation is wrong
The Douglas-Peucker implementation should calculate the distance to the segment between the end nodes, not the distance to the line through those nodes.

[GerdP]

In 18317/josm:

see #20982: Douglas-Peucker implementation is wrong
adapt unit test

[Don-vip]

Milestone renamed

[gaben]

Erm, I know this is an old ticket, but could you please add a comment in the code explicitly mentioning it's the Douglas-Peucker algorithm?

I'm trying to find general algorithms in the source and without comments, it's really hard to recognize what is it. The backstory is that I'd like to put all of them in a separate place to make them reusable (and possibly find duplicate implementations across JOSM).

[GerdP]

Done with r18883

[gaben]

Thank you!