Ramer-Douglas-Peucker line simplification: Difference between revisions
Content added Content deleted
(Solve in Openscad) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 18: | Line 18: | ||
:* the Wikipedia article: [https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm Ramer-Douglas-Peucker algorithm]. |
:* the Wikipedia article: [https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm Ramer-Douglas-Peucker algorithm]. |
||
<br><br> |
<br><br> |
||
=={{header|C sharp|C#}}== |
|||
{{trans|Java}} |
|||
<lang csharp>using System; |
|||
using System.Collections.Generic; |
|||
using System.Linq; |
|||
namespace LineSimplification { |
|||
using Point = Tuple<double, double>; |
|||
class Program { |
|||
static double PerpendicularDistance(Point pt, Point lineStart, Point lineEnd) { |
|||
double dx = lineEnd.Item1 - lineStart.Item1; |
|||
double dy = lineEnd.Item2 - lineStart.Item2; |
|||
// Normalize |
|||
double mag = Math.Sqrt(dx * dx + dy * dy); |
|||
if (mag > 0.0) { |
|||
dx /= mag; |
|||
dy /= mag; |
|||
} |
|||
double pvx = pt.Item1 - lineStart.Item1; |
|||
double pvy = pt.Item2 - lineStart.Item2; |
|||
// Get dot product (project pv onto normalized direction) |
|||
double pvdot = dx * pvx + dy * pvy; |
|||
// Scale line direction vector and subtract it from pv |
|||
double ax = pvx - pvdot * dx; |
|||
double ay = pvy - pvdot * dy; |
|||
return Math.Sqrt(ax * ax + ay * ay); |
|||
} |
|||
static void RamerDouglasPeucker(List<Point> pointList, double epsilon, List<Point> output) { |
|||
if (pointList.Count < 2) { |
|||
throw new ArgumentOutOfRangeException("Not enough points to simplify"); |
|||
} |
|||
// Find the point with the maximum distance from line between the start and end |
|||
double dmax = 0.0; |
|||
int index = 0; |
|||
int end = pointList.Count - 1; |
|||
for (int i = 1; i < end; ++i) { |
|||
double d = PerpendicularDistance(pointList[i], pointList[0], pointList[end]); |
|||
if (d > dmax) { |
|||
index = i; |
|||
dmax = d; |
|||
} |
|||
} |
|||
// If max distance is greater than epsilon, recursively simplify |
|||
if (dmax > epsilon) { |
|||
List<Point> recResults1 = new List<Point>(); |
|||
List<Point> recResults2 = new List<Point>(); |
|||
List<Point> firstLine = pointList.Take(index + 1).ToList(); |
|||
List<Point> lastLine = pointList.Skip(index).ToList(); |
|||
RamerDouglasPeucker(firstLine, epsilon, recResults1); |
|||
RamerDouglasPeucker(lastLine, epsilon, recResults2); |
|||
// build the result list |
|||
output.AddRange(recResults1.Take(recResults1.Count - 1)); |
|||
output.AddRange(recResults2); |
|||
if (output.Count < 2) throw new Exception("Problem assembling output"); |
|||
} |
|||
else { |
|||
// Just return start and end points |
|||
output.Clear(); |
|||
output.Add(pointList[0]); |
|||
output.Add(pointList[pointList.Count - 1]); |
|||
} |
|||
} |
|||
static void Main(string[] args) { |
|||
List<Point> pointList = new List<Point>() { |
|||
new Point(0.0,0.0), |
|||
new Point(1.0,0.1), |
|||
new Point(2.0,-0.1), |
|||
new Point(3.0,5.0), |
|||
new Point(4.0,6.0), |
|||
new Point(5.0,7.0), |
|||
new Point(6.0,8.1), |
|||
new Point(7.0,9.0), |
|||
new Point(8.0,9.0), |
|||
new Point(9.0,9.0), |
|||
}; |
|||
List<Point> pointListOut = new List<Point>(); |
|||
RamerDouglasPeucker(pointList, 1.0, pointListOut); |
|||
Console.WriteLine("Points remaining after simplification:"); |
|||
pointListOut.ForEach(p => Console.WriteLine(p)); |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>Points remaining after simplification: |
|||
(0, 0) |
|||
(2, -0.1) |
|||
(3, 5) |
|||
(7, 9) |
|||
(9, 9)</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
Line 138: | Line 238: | ||
7,9 |
7,9 |
||
9,9</pre> |
9,9</pre> |
||
=={{header|C#|C sharp}}== |
|||
{{trans|Java}} |
|||
<lang csharp>using System; |
|||
using System.Collections.Generic; |
|||
using System.Linq; |
|||
namespace LineSimplification { |
|||
using Point = Tuple<double, double>; |
|||
class Program { |
|||
static double PerpendicularDistance(Point pt, Point lineStart, Point lineEnd) { |
|||
double dx = lineEnd.Item1 - lineStart.Item1; |
|||
double dy = lineEnd.Item2 - lineStart.Item2; |
|||
// Normalize |
|||
double mag = Math.Sqrt(dx * dx + dy * dy); |
|||
if (mag > 0.0) { |
|||
dx /= mag; |
|||
dy /= mag; |
|||
} |
|||
double pvx = pt.Item1 - lineStart.Item1; |
|||
double pvy = pt.Item2 - lineStart.Item2; |
|||
// Get dot product (project pv onto normalized direction) |
|||
double pvdot = dx * pvx + dy * pvy; |
|||
// Scale line direction vector and subtract it from pv |
|||
double ax = pvx - pvdot * dx; |
|||
double ay = pvy - pvdot * dy; |
|||
return Math.Sqrt(ax * ax + ay * ay); |
|||
} |
|||
static void RamerDouglasPeucker(List<Point> pointList, double epsilon, List<Point> output) { |
|||
if (pointList.Count < 2) { |
|||
throw new ArgumentOutOfRangeException("Not enough points to simplify"); |
|||
} |
|||
// Find the point with the maximum distance from line between the start and end |
|||
double dmax = 0.0; |
|||
int index = 0; |
|||
int end = pointList.Count - 1; |
|||
for (int i = 1; i < end; ++i) { |
|||
double d = PerpendicularDistance(pointList[i], pointList[0], pointList[end]); |
|||
if (d > dmax) { |
|||
index = i; |
|||
dmax = d; |
|||
} |
|||
} |
|||
// If max distance is greater than epsilon, recursively simplify |
|||
if (dmax > epsilon) { |
|||
List<Point> recResults1 = new List<Point>(); |
|||
List<Point> recResults2 = new List<Point>(); |
|||
List<Point> firstLine = pointList.Take(index + 1).ToList(); |
|||
List<Point> lastLine = pointList.Skip(index).ToList(); |
|||
RamerDouglasPeucker(firstLine, epsilon, recResults1); |
|||
RamerDouglasPeucker(lastLine, epsilon, recResults2); |
|||
// build the result list |
|||
output.AddRange(recResults1.Take(recResults1.Count - 1)); |
|||
output.AddRange(recResults2); |
|||
if (output.Count < 2) throw new Exception("Problem assembling output"); |
|||
} |
|||
else { |
|||
// Just return start and end points |
|||
output.Clear(); |
|||
output.Add(pointList[0]); |
|||
output.Add(pointList[pointList.Count - 1]); |
|||
} |
|||
} |
|||
static void Main(string[] args) { |
|||
List<Point> pointList = new List<Point>() { |
|||
new Point(0.0,0.0), |
|||
new Point(1.0,0.1), |
|||
new Point(2.0,-0.1), |
|||
new Point(3.0,5.0), |
|||
new Point(4.0,6.0), |
|||
new Point(5.0,7.0), |
|||
new Point(6.0,8.1), |
|||
new Point(7.0,9.0), |
|||
new Point(8.0,9.0), |
|||
new Point(9.0,9.0), |
|||
}; |
|||
List<Point> pointListOut = new List<Point>(); |
|||
RamerDouglasPeucker(pointList, 1.0, pointListOut); |
|||
Console.WriteLine("Points remaining after simplification:"); |
|||
pointListOut.ForEach(p => Console.WriteLine(p)); |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre>Points remaining after simplification: |
|||
(0, 0) |
|||
(2, -0.1) |
|||
(3, 5) |
|||
(7, 9) |
|||
(9, 9)</pre> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
Line 893: | Line 893: | ||
(7 9) |
(7 9) |
||
(9 9)</pre> |
(9 9)</pre> |
||
=={{header|Perl 6}}== |
|||
{{works with|Rakudo|2017.05}} |
|||
{{trans|C++}} |
|||
<lang perl6>sub norm (*@list) { @list»².sum.sqrt } |
|||
sub perpendicular-distance (@start, @end where @end !eqv @start, @point) { |
|||
return 0 if @point eqv any(@start, @end); |
|||
my ( $Δx, $Δy ) = @end «-» @start; |
|||
my ($Δpx, $Δpy) = @point «-» @start; |
|||
($Δx, $Δy) «/=» norm $Δx, $Δy; |
|||
norm ($Δpx, $Δpy) «-» ($Δx, $Δy) «*» ($Δx*$Δpx + $Δy*$Δpy); |
|||
} |
|||
sub Ramer-Douglas-Peucker(@points where * > 1, \ε = 1) { |
|||
return @points if @points == 2; |
|||
my @d = (^@points).map: { perpendicular-distance |@points[0, *-1, $_] }; |
|||
my ($index, $dmax) = @d.first: @d.max, :kv; |
|||
return flat |
|||
Ramer-Douglas-Peucker( @points[0..$index], ε )[^(*-1)], |
|||
Ramer-Douglas-Peucker( @points[$index..*], ε ) |
|||
if $dmax > ε; |
|||
@points[0, *-1]; |
|||
} |
|||
# TESTING |
|||
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)] |
|||
);</lang> |
|||
{{out}} |
|||
<pre>((0 0) (2 -0.1) (3 5) (7 9) (9 9))</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 957: | Line 925: | ||
{{0,0},{2,-0.1},{3,5},{7,9},{9,9}} |
{{0,0},{2,-0.1},{3,5},{7,9},{9,9}} |
||
</pre> |
</pre> |
||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
Line 1,107: | Line 1,074: | ||
{{out}} |
{{out}} |
||
<pre>'((0 0) (2 -0.1) (3 5) (7 9) (9 9))</pre> |
<pre>'((0 0) (2 -0.1) (3 5) (7 9) (9 9))</pre> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
{{works with|Rakudo|2017.05}} |
|||
{{trans|C++}} |
|||
<lang perl6>sub norm (*@list) { @list»².sum.sqrt } |
|||
sub perpendicular-distance (@start, @end where @end !eqv @start, @point) { |
|||
return 0 if @point eqv any(@start, @end); |
|||
my ( $Δx, $Δy ) = @end «-» @start; |
|||
my ($Δpx, $Δpy) = @point «-» @start; |
|||
($Δx, $Δy) «/=» norm $Δx, $Δy; |
|||
norm ($Δpx, $Δpy) «-» ($Δx, $Δy) «*» ($Δx*$Δpx + $Δy*$Δpy); |
|||
} |
|||
sub Ramer-Douglas-Peucker(@points where * > 1, \ε = 1) { |
|||
return @points if @points == 2; |
|||
my @d = (^@points).map: { perpendicular-distance |@points[0, *-1, $_] }; |
|||
my ($index, $dmax) = @d.first: @d.max, :kv; |
|||
return flat |
|||
Ramer-Douglas-Peucker( @points[0..$index], ε )[^(*-1)], |
|||
Ramer-Douglas-Peucker( @points[$index..*], ε ) |
|||
if $dmax > ε; |
|||
@points[0, *-1]; |
|||
} |
|||
# TESTING |
|||
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)] |
|||
);</lang> |
|||
{{out}} |
|||
<pre>((0 0) (2 -0.1) (3 5) (7 9) (9 9))</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |