[Octave-cvsupdate] SF.net SVN: octave:[10228] trunk/octave-forge/main/geometry

[<jpi...@us...>]

Revision: 10228
          http://octave.svn.sourceforge.net/octave/?rev=10228&view=rev
Author:   jpicarbajal
Date:     2012-04-15 14:29:54 +0000 (Sun, 15 Apr 2012)
Log Message:
-----------
geometry: Ramer-Douglas-Peucker algorithm to simplify polylines and polygons.

Modified Paths:
--------------
    trunk/octave-forge/main/geometry/NEWS
    trunk/octave-forge/main/geometry/inst/polygons2d/simplifypolyline.m

Modified: trunk/octave-forge/main/geometry/NEWS
===================================================================
--- trunk/octave-forge/main/geometry/NEWS	2012-04-15 11:23:54 UTC (rev 10227)
+++ trunk/octave-forge/main/geometry/NEWS	2012-04-15 14:29:54 UTC (rev 10228)
@@ -4,12 +4,13 @@
 geometry-1.4.2   Release Date: 2012-XX-XX  Release Manager: Juan Pablo Carbajal
 ===============================================================================
 
-* Added function
+* Added functions:
  - curveval.m: Evaluates a polynomial curve defined as a 2-by-N matrix.
  - curve2polyline.m: Converts a polynomial curve into a polyline by the adaptive
                      sampling method.
+ - simplifypolyline.m:  Ramer-Douglas-Peucker algorithm to simplify polylines.
 
-* Changed functions
+* Changed functions:
  - distancePointEdge.m: Now the function computes the distance between all points
                         and all edges. A third optional argument provides
                         backward compatibility.

Modified: trunk/octave-forge/main/geometry/inst/polygons2d/simplifypolyline.m
===================================================================
--- trunk/octave-forge/main/geometry/inst/polygons2d/simplifypolyline.m	2012-04-15 11:23:54 UTC (rev 10227)
+++ trunk/octave-forge/main/geometry/inst/polygons2d/simplifypolyline.m	2012-04-15 14:29:54 UTC (rev 10228)
@@ -42,6 +42,7 @@
 %% @end deftypefn
 
 function [pline idx] = simplifypolyline (pline_o, varargin)
+%% TODO do not print warnings if user provided Nmax or MaxIter.
 
   # --- Parse arguments --- #
   parser = inputParser ();
@@ -67,11 +68,13 @@
     % Find the point with the maximum distance.
     [dist ii] = maxdistance (pline_o, idx);
 
-    if dist < tol;
+    tf = dist > tol;
+    n = sum(tf);
+    if all(!tf);
       break;
     end
 
-    idx(end+1) = ii;
+    idx(end+1:end+n) = ii(tf);
     idx = sort(idx);
 
     if length(idx) >= Nmax
@@ -87,22 +90,29 @@
   pline = pline_o(idx,:);
 endfunction
 
-function [dist ii] = maxdistance (p,idx)
+function [dist ii] = maxdistance (p, idx)
 
+  %% Separate the groups of points according to the edge they can divide.
+  func = @(x,y) x:y;
+  idxc   = arrayfun (func, idx(1:end-1), idx(2:end), "UniformOutput",false);
+  points = cellfun (@(x)p(x,:), idxc, "UniformOutput",false);
+
+  %% Build the edges
   edges = [p(idx(1:end-1),:) p(idx(2:end),:)];
-  %% Calculate distance between all points and edges
-  %% What is better? this or a only comparing the points that are between the extrema
-  %% of each edge.
-  [d pos] = distancePointEdge (p, edges);
+  edges = mat2cell (edges, ones(1,size(edges,1)), 4)';
 
-  %% Filter out all points outside the edges
-  tf = pos == 0 | pos == 1;
-  d(tf) = -1;
+  %% Calculate distance between the points and the corresponding edge
+  [dist ii] = cellfun(@dd, points,edges,idxc);
 
-  [dist j] = max(d(:));
-  ii = ind2sub (size(d),j);
+endfunction
 
-end
+function [dist ii] = dd (p,e,idx)
+  [d pos] = distancePointEdge(p,e);
+  tf = abs(pos) <= abs(pos*eps) | abs(pos-1) <= abs((pos-1)*eps);
+  d(tf) = -1;
+  [dist ii] = max(d);
+  ii = idx(ii);
+endfunction
 
 %!demo
 %! t     = linspace(0,1,100).';

This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.