Ramer-Douglas-Peucker line simplification: Difference between revisions

← Older edit

Ramer-Douglas-Peucker line simplification (view source)

Revision as of 15:28, 29 January 2024

8,633 bytes added , 3 months ago

m

→‎{{header|Wren}}: Minor tidy

PureFox

9,479

edits

Revision as of 17:47, 19 November 2023 (view source) Tigerofdarkness (talk \| contribs) (→‎{{header\|ALGOL 68}}: Fix typos) ← Older edit		Latest revision as of 15:28, 29 January 2024 (view source) PureFox (talk \| contribs) m (→‎{{header\|Wren}}: Minor tidy)
(7 intermediate revisions by 3 users not shown)
Line 525: 9,9</pre> =={{header\|EasyLang}}== {{trans\|C}} <syntaxhighlight> func perpdist px py p1x p1y p2x p2y . dx = p2x - p1x dy = p2y - p1y d = sqrt (dx * dx + dy * dy) return abs (px * dy - py * dx + p2x * p1y - p2y * p1x) / d . proc peucker eps . ptx[] pty[] outx[] outy[] . n = len ptx[] idx = 1 for i = 2 to n - 1 dist = perpdist ptx[i] pty[i] ptx[1] pty[1] ptx[n] pty[n] if dist > dmax dmax = dist idx = i . . if dmax > eps for i to idx px[] &= ptx[i] py[] &= pty[i] . peucker eps px[] py[] outx[] outy[] # for i = idx to n p2x[] &= ptx[i] p2y[] &= pty[i] . peucker eps p2x[] p2y[] ox[] oy[] for i = 2 to len ox[] outx[] &= ox[i] outy[] &= oy[i] . else outx[] = [ ptx[1] ptx[n] ] outy[] = [ pty[1] pty[n] ] . . proc prpts px[] py[] . . for i to len px[] write "(" & px[i] & " " & py[i] & ") " . print "" . px[] = [ 0 1 2 3 4 5 6 7 8 9 ] py[] = [ 0 0.1 -0.1 5 6 7 8.1 9 9 9 ] peucker 1 px[] py[] ox[] oy[] prpts ox[] oy[] </syntaxhighlight> =={{header\|FreeBASIC}}== Line 596 ⟶ 648: ( 0, 0) ( 2, -0.1) ( 3, 5) ( 7, 9) ( 9, 9) </pre> =={{header\|Go}}== Line 1,014 ⟶ 1,065: {{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\|ooRexx}}== <syntaxhighlight lang="oorexx"> /REXX program uses the Ramer-Douglas-Peucker (RDP) line simplification algorithm for/ /--------------------------- reducing the number of points used to define its shape. / Parse Arg epsilon pl /obtain optional arguments from the CL/ If epsilon='' \| epsilon=',' then epsilon= 1 /Not specified? Then use the default./ If pl='' Then pl= '(0,0) (1,0.1) (2,-0.1) (3,5) (4,6) (5,7) (6,8.1) (7,9) (8,9) (9,9)' Say ' error threshold:' epsilon Say ' points specified:' pl Say 'points simplified:' dlp(pl) Exit dlp: Procedure Expose epsilon Parse Arg pl plc=pl Do i=1 By 1 While plc<>'' Parse Var plc '(' X ',' y ')' plc p.i=.point~new(x,y) End end=i-1 dmax=0 index=0 Do i=2 To end-1 d=distpg(p.i,.line~new(p.1,p.end)) If d>dmax Then Do index=i dmax=d End End If dmax>epsilon Then Do rla=dlp(subword(pl,1,index)) rlb=dlp(subword(pl,index,end)) rl=subword(rla,1,words(rla)-1) rlb End Else rl=word(pl,1) word(pl,end) Return rl ::CLASS point public ::ATTRIBUTE X ::ATTRIBUTE Y ::METHOD init PUBLIC Expose X Y Use Arg X,Y ::CLASS line public ::ATTRIBUTE A ::ATTRIBUTE B ::METHOD init PUBLIC Expose A B Use Arg A,B If A~x=B~x & A~y=B~y Then Do Say 'not a line' Return .nil End ::METHOD k PUBLIC Expose A B ax=A~x; ay=A~y; bx=B~x; by=B~y If ax=bx Then res='infinite' Else res=(by-ay)/(bx-ax) Return res ::METHOD d PUBLIC Expose A B ax=A~x; ay=A~y If self~k='infinite' Then res='indeterminate' Else res=round(ay-axself~k) Return res ::ROUTINE distpg PUBLIC --Compute the distance from a point to a line /********************************************************************** * Compute the distance from a point to a line **********************************************************************/ Use Arg A,g ax=A~x; ay=A~y k=g~k If k='infinite' Then Do Parse Value g~kxd With 'x='gx res=gx-ax End Else res=(ay-kax-g~d)/rxCalcsqrt(1+k2) Return abs(res) ::ROUTINE round PUBLIC --Round a number to 3 decimal digits /********************************************************************* * Round a nmber to 3 decimal digits **********************************************************************/ Use Arg z,d Numeric Digits 30 res=z+0 If d>'' Then res=format(res,9,6) Return strip(res) ::requires rxMath library </syntaxhighlight> {{out}} <pre> error threshold: 1 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\|Openscad}}== Line 1,371 ⟶ 1,529: =={{header\|REXX}}== ===Version 1=== The computation for the   ''perpendicular distance''   was taken from the   '''GO'''   example. Line 1,404 ⟶ 1,563: end return @.1 @.#</syntaxhighlight> {{out\|output\|text=  when using the default inputs:}} <pre> error threshold: 1 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> ===Version 2=== {{trans\|ooRexx}} <syntaxhighlight lang="rexx"> /REXX program uses the Ramer-Douglas-Peucker (RDP) line simplification algorithm for/ /--------------------------- reducing the number of points used to define its shape. / Parse Arg epsilon pl /obtain optional arguments from the CL/ If epsilon='' \| epsilon=',' then epsilon= 1 /Not specified? Then use the default./ If pl='' Then pl= '(0,0) (1,0.1) (2,-0.1) (3,5) (4,6) (5,7) (6,8.1) (7,9) (8,9) (9,9)' Say ' error threshold:' epsilon Say ' points specified:' pl Say 'points simplified:' dlp(pl) Exit dlp: Procedure Expose epsilon Parse Arg pl plc=pl Do i=1 By 1 While plc<>'' Parse Var plc '(' x ',' y ')' plc p.i=x y End end=i-1 dmax=0 index=0 Do i=2 To end-1 d=distpg(p.i,p.1,p.end) If d>dmax Then Do index=i dmax=d End End If dmax>epsilon Then Do rla=dlp(subword(pl,1,index)) rlb=dlp(subword(pl,index,end)) rl=subword(rla,1,words(rla)-1) rlb End Else rl=word(pl,1) word(pl,end) Return rl distpg: Procedure /********************************************************************* * compute the distance of point P from the line giveb by A and B *********************************************************************/ Parse Arg P,A,B Parse Var P px py Parse Var A ax ay Parse Var B bx by If ax=bx Then res=px-ax Else Do k=(by-ay)/(bx-ax) d=(ay-axk) res=(py-kpx-d)/sqrt(1+k2) End Return abs(res) sqrt: Procedure / REXX *************************************************************** * EXEC to calculate the square root of a = 2 with high precision *********************************************************************/ Parse Arg x,prec If prec<9 Then prec=9 prec1=2prec eps=10*(-prec1) k = 1 Numeric Digits 3 r0= x r = 1 Do i=1 By 1 Until r=r0 \| (abs(rr-x)<eps) r0 = r r = (r + x/r) / 2 k = min(prec1,2k) Numeric Digits (k + 5) End Numeric Digits prec r=r+0 Return r </syntaxhighlight> {{out\|output\|text=  when using the default inputs:}} <pre> Line 1,557 ⟶ 1,798: (9, 9) </pre> =={{header\|Scala}}== {{trans\|Kotlin}} <syntaxhighlight lang="scala">// version 1.1.0 object SimplifyPolyline extends App { type Point = (Double, Double) def perpendicularDistance( pt: Point, lineStart: Point, lineEnd: Point ): Double = { var dx = lineEnd._1 - lineStart._1 var dy = lineEnd._2 - lineStart._2 // Normalize val mag = math.hypot(dx, dy) if (mag > 0.0) { dx /= mag; dy /= mag } val pvx = pt._1 - lineStart._1 val pvy = pt._2 - lineStart._2 // Get dot product (project pv onto normalized direction) val pvdot = dx pvx + dy * pvy // Scale line direction vector and subtract it from pv val ax = pvx - pvdot * dx val ay = pvy - pvdot * dy math.hypot(ax, ay) } def RamerDouglasPeucker( pointList: List[Point], epsilon: Double ): List[Point] = { if (pointList.length < 2) throw new IllegalArgumentException("Not enough points to simplify") // Check if there are points to process if (pointList.length > 2) { // Find the point with the maximum distance from the line between the first and last val (dmax, index) = pointList.zipWithIndex .slice(1, pointList.length - 1) .map { case (point, i) => (perpendicularDistance(point, pointList.head, pointList.last), i) } .maxBy(_._1) // If max distance is greater than epsilon, recursively simplify if (dmax > epsilon) { val firstLine = pointList.take(index + 1) val lastLine = pointList.drop(index) val recResults1 = RamerDouglasPeucker(firstLine, epsilon) val recResults2 = RamerDouglasPeucker(lastLine, epsilon) // Combine the results (recResults1.init ++ recResults2).distinct } else { // If no point is further than epsilon, return the endpoints List(pointList.head, pointList.last) } } else { // If there are only two points, just return them pointList } } val pointList = List( (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) ) val simplifiedPointList = RamerDouglasPeucker(pointList, 1.0) println("Points remaining after simplification:") simplifiedPointList.foreach(println) } </syntaxhighlight> {{out}} <pre> Points remaining after simplification: (0.0,0.0) (2.0,-0.1) (3.0,5.0) (7.0,9.0) (9.0,9.0) </pre> =={{header\|Sidef}}== Line 1,662 ⟶ 2,004: {{trans\|Go}} {{libheader\|Wren-dynamic}} <syntaxhighlight lang="~~ecmascript~~wren">import "./dynamic" for Tuple var Point = Tuple.create("Point", ["x", "y"])