Ramer-Douglas-Peucker line simplification: Difference between revisions
Ramer-Douglas-Peucker line simplification (view source)
Revision as of 15:28, 29 January 2024
, 4 months ago→{{header|Wren}}: Minor tidy
Walterpachl (talk | contribs) (add ooRexx) |
m (→{{header|Wren}}: Minor tidy) |
||
| (5 intermediate revisions by 2 users not shown) | |||
Line 1,066:
<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*/
Line 1,529:
=={{header|REXX}}==
===Version 1===
The computation for the ''perpendicular distance'' was taken from
the '''GO''' example.
Line 1,562 ⟶ 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-ax*k)
res=(py-k*px-d)/sqrt(1+k**2)
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=2*prec
eps=10**(-prec1)
k = 1
Numeric Digits 3
r0= x
r = 1
Do i=1 By 1 Until r=r0 | (abs(r*r-x)<eps)
r0 = r
r = (r + x/r) / 2
k = min(prec1,2*k)
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,715 ⟶ 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,820 ⟶ 2,004:
{{trans|Go}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="
var Point = Tuple.create("Point", ["x", "y"])
| |||