Ramer-Douglas-Peucker line simplification: Difference between revisions

:*   the Wikipedia article:   [https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm Ramer-Douglas-Peucker algorithm].

<br><br>

 

=={{header|C}}==

#include <math.h>

#include <stdio.h>

print_points(out, n);

return 0;

 

{{out}}

=={{header|C sharp|C#}}==

{{trans|Java}}

using System.Collections.Generic;

using System.Linq;

}

}

{{out}}

<pre>Points remaining after simplification:

=={{header|C++}}==

 

#include <cmath>

#include <utility>

 

return 0;

 

{{out}}

=={{header|D}}==

{{trans|C++}}

import std.exception : enforce;

import std.math;

output ~= pointList[end];

}

 

{{out}}

7,9

9,9</pre>

 

=={{header|Go}}==

 

import (

fmt.Println(RDP([]point{{0, 0}, {1, 0.1}, {2, -0.1},

{3, 5}, {4, 6}, {5, 7}, {6, 8.1}, {7, 9}, {8, 9}, {9, 9}}, 1))

{{out}}

<pre>

=={{header|J}}==

'''Solution:'''

norm=: +/&.:*: NB. vector norm

normalize=: (% norm)^:(0 < norm)

({. ,: {:) points

end.

'''Example Usage:'''

1.0 rdp Points

0 0

3 5

7 9

 

=={{header|Java}}==

{{trans|Kotlin}}

{{works with|Java|9}}

 

import java.util.ArrayList;

pointListOut.forEach(System.out::println);

}

{{out}}

<pre>Points remaining after simplification:

=={{header|JavaScript}}==

{{trans|Go}}

* @typedef {{

* x: (!number),

{x: 9, y: 9}];

 

{{out}}

<pre>[{x: 0, y: 0},

{{trans|C++}}

 

 

function perpdist(pt::Point, lnstart::Point, lnend::Point)

plist = Point[[0.0, 0.0], [1.0, 0.1], [2.0, -0.1], [3.0, 5.0], [4.0, 6.0], [5.0, 7.0], [6.0, 8.1], [7.0, 9.0], [8.0, 9.0], [9.0, 9.0]]

@show plist

 

{{out}}

=={{header|Kotlin}}==

{{trans|C++}}

 

typealias Point = Pair<Double, Double>

println("Points remaining after simplification:")

for (p in pointListOut) println(p)

 

{{out}}

 

=={{header|Nim}}==

 

type

var line: seq[Point] = @[(0.0, 0.0), (1.0, 0.1), (2.0, -0.1), (3.0, 5.0), (4.0, 6.0),

(5.0, 7.0), (6.0, 8.1), (7.0, 9.0), (8.0, 9.0), (9.0, 9.0)]

 

{{out}}

<pre>@[(x: 0.0, y: 0.0), (x: 2.0, y: -0.1), (x: 3.0, y: 5.0), (x: 7.0, y: 9.0), (x: 9.0, y: 9.0)]</pre>

 

=={{header|Openscad}}==

{{works with|Openscad|2019.05}}

 

 

// Find the distance from the point to the line

$fn=16;

points = [[0,0], [1,0.1], [2,-0.1], [3,5], [4,6], [5,7], [6,8.1], [7,9], [8,9], [9,9]];

 

{{out}}

=={{header|Perl}}==

{{trans|Raku}}

use warnings;

use feature 'say';

 

say '(' . join(' ', @$_) . ') '

{{out}}

<pre>(0 0)

=={{header|Phix}}==

{{trans|Go}}

{{out}}

<pre>

=={{header|PHP}}==

{{trans|C++}}

// Calculate the normalized delta x and y of the line.

$dx = $line[1][0] - $line[0][0];

foreach ($result as $point) {

print $point[0] . ',' . $point[1] . "\n";

 

{{out}}

{{libheader|Shapely}}

An approach using the shapely library:

from shapely.geometry import LineString

if __name__=="__main__":

line = LineString([(0,0),(1,0.1),(2,-0.1),(3,5),(4,6),(5,7),(6,8.1),(7,9),(8,9),(9,9)])

{{out}}

<pre>LINESTRING (0 0, 2 -0.1, 3 5, 7 9, 9 9)</pre>

=={{header|Racket}}==

 

(require math/flonum)

;; points are lists of x y (maybe extensible to z)

(module+ test

(require rackunit)

 

{{out}}

{{trans|C++}}

 

 

sub perpendicular-distance (@start, @end where @end !eqv @start, @point) {

say Ramer-Douglas-Peucker(

[(0,0),(1,0.1),(2,-0.1),(3,5),(4,6),(5,7),(6,8.1),(7,9),(8,9),(9,9)]

{{out}}

<pre>((0 0) (2 -0.1) (3 5) (7 9) (9 9))</pre>

 

=={{header|REXX}}==

/*───────────────────────────── reducing the number of points used to define its shape. */

parse arg epsilon pts /*obtain optional arguments from the CL*/

if pts='' then pts= '(0,0) (1,0.1) (2,-0.1) (3,5) (4,6) (5,7) (6,8.1) (7,9) (8,9) (9,9)'

pts= space(pts) /*elide all superfluous blanks. */

$= RDP(pts) /*invoke Ramer─Douglas─Peucker function*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

bld: parse arg _; #= words(_); dMax=-#; idx=1; do j=1 for #; @.j= word(_, j); end; return

px: parse arg _; return word( translate(_, , ','), 1) /*obtain the X coörd.*/

py: parse arg _; return word( translate(_, , ','), 2) /* " " Y " */

rez: parse arg z,_; do k=1 for words(z); _= _ '('word(z, k)") "; end; return strip(_)

/*──────────────────────────────────────────────────────────────────────────────────────*/

 

if dMax>epsilon then do; r= RDP( reb(1, idx) )

return subword(r, 1, words(r) - 1) RDP( reb(idx, #) )

end

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

points specified: (0,0) (1,0.1) (2,-0.1) (3,5) (4,6) (5,7) (6,8.1) (7,9) (8,9) (9,9)

points simplified: (0,0) (2,-0.1) (3,5) (7,9) (9,9)

</pre>

 

=={{header|Rust}}==

===An implementation of the algorithm===

struct Point {

x: f64,

println!("{}", p);

}

 

{{out}}

The geo crate contains an implementation of the Ramer-Douglas-Peucker line

simplification algorithm.

// geo = "0.14"

 

println!("({}, {})", p.x, p.y);

}

 

{{out}}

(9, 9)

</pre>

 

=={{header|Sidef}}==

{{trans|Raku}}

((point == start) || (point == end)) && return 0

var h = hypot(Δx, Δy)

[\Δx, \Δy].map { *_ /= h }

}

 

if (d.max > ε) {

var i = d.index(d.max)

}

 

say Ramer_Douglas_Peucker(

[[0,0],[1,0.1],[2,-0.1],[3,5],[4,6],[5,7],[6,8.1],[7,9],[8,9],[9,9]]

{{out}}

<pre>

[[0, 0], [2, -1/10], [3, 5], [7, 9], [9, 9]]

</pre>

 

=={{header|Yabasic}}==

local dx, cy, mag, pvx, pvy, pvdot, dsx, dsy, ax, ay

 

for i = 1 to 10

if matriz(i, 3) print matriz(i, 1), matriz(i, 2)

 

=={{header|zkl}}==

{{trans|Raku}}

dx,dy := end .zipWith('-,start); // deltas

dpx,dpy := point.zipWith('-,start);

RamerDouglasPeucker(points[index,*],epsilon)))

} else return(points[0],points[-1]);

T( T(0.0, 0.0), T(1.0, 0.1), T(2.0, -0.1), T(3.0, 5.0), T(4.0, 6.0),

T(5.0, 7.0), T(6.0, 8.1), T(7.0, 9.0), T(8.0, 9.0), T(9.0, 9.0) ))

{{out}}

<pre>