up previous next

Reduce redundancy in a set of approximate points

PreprocessPts(Pts: MAT, Toler: MAT): RECORD
PreprocessPtsGrid(Pts: MAT, Toler: MAT): RECORD
PreprocessPtsAggr(Pts: MAT, Toler: MAT): RECORD
PreprocessPtsSubDiv(Pts: MAT, Toler: MAT): RECORD

Thanks to Maria-Laura Torrente.

These functions detect groupings of close points, and choose a single representative for them (which lies within the given tolerance of each original point); the result is the list of these representatives, and the number of original points associated to each representative.

The first argument is a matrix whose rows represent a set of points in k-dimensional space, and the second argument is row-matrix of k tolerances (one for each dimension).

The return value is a record containing two fields: NewPoints contains a matrix whose rows represent a list of well-separated points, and weights which contains the number of input points associated to each output point.

There are three underlying algorithms: Grid is fast but crude; Subdiv works best when the original points are densely packed (so the result will be a small list); finally Aggr is best suited to situations where the original points are less densely packed.

The function PreprocessPts automatically chooses between Subdiv and Aggr with the aim of minimising computation time. Note that the Aggr and Subdiv methods regard the tolerances as being slightly flexible.

For a full description of the algorithms we refer to the paper J.Abbott, C.Fassino, L.Torrente Thinning Out Redundant Empirical Data (Mathematics in Computer Science, 2007).

/**/  Pts := matrix([[-1,0],[0,0],[1,0],[99,1],[99,0],[99,-1]]);
/**/  Toler := RowMat([3,3]);
/**/  PreprocessPts(Pts, Toler);
record[NewPoints := matrix(QQ,
 [[99, 0],
  [0, 0]]), weights := [3, 3]]

/**/  PreprocessPts(Pts, RowMat([0.8,0.8]));
record[NewPoints := matrix(QQ,
 [[-1/2, 0],
  [1, 0],
  [99, 1/2],
  [99, -1]]), weights := [2, 1, 2, 1]]

/**/  PreprocessPtsAggr(Pts, RowMat([0.9,0.9])); -- exhibits tolerance flex
record[NewPoints := matrix(QQ,
 [[0, 0],
  [99, 0]], weights := [3, 3]]