/* Class PolylineSimplification
*
* Simplifies a polyline (a polygonal chain) using the algorithm of Douglas and Peucker
* This is a Java implementation modelled on softSurfer's C++ implementation
* See http://softsurfer.com/Archive/algorithm_0205/algorithm_0205.htm#Implementation
*
* WRITTEN BY: Dr Michael Thomas Flanagan
*
* DATE: November - December 2011
* UPDATES: 5 December 2011
*
* DOCUMENTATION:
* See Michael Thomas Flanagan's Java library on-line web page:
* http://www.ee.ucl.ac.uk/~mflanaga/java/PolyLineSimplification.html
* http://www.ee.ucl.ac.uk/~mflanaga/java/
*
* Copyright (c) 2011 Michael Thomas Flanagan
* PERMISSION TO COPY:
*
* Permission to use, copy and modify this software and its documentation for NON-COMMERCIAL purposes is granted, without fee,
* provided that an acknowledgement to the author, Dr Michael Thomas Flanagan at www.ee.ucl.ac.uk/~mflanaga, appears in all copies
* and associated documentation or publications.
*
* Redistributions of the source code of this source code, or parts of the source codes, must retain the above copyright notice, this list of conditions
* and the following disclaimer and requires written permission from the Michael Thomas Flanagan:
*
* Redistribution in binary form of all or parts of this class must reproduce the above copyright notice, this list of conditions and
* the following disclaimer in the documentation and/or other materials provided with the distribution and requires written permission from the Michael Thomas Flanagan:
*
* Dr Michael Thomas Flanagan makes no representations about the suitability or fitness of the software for any or for a particular purpose.
* Dr Michael Thomas Flanagan shall not be liable for any damages suffered as a result of using, modifying or distributing this software
* or its derivatives.
*
***************************************************************************************/
package flanagan.interpolation;
import java.util.ArrayList;
import java.lang.reflect.Array;
import flanagan.math.*;
import flanagan.plot.*;
public class PolylineSimplification{
private Point[] originalPoints = null; // array of original points
private int nPoints = 0; // number of original points
private Point[] simplifiedPoints = null; // array of final points
private int[] simplifiedIndices = null; // original indices of simplified curve points
private int nSimplifiedPoints = 0; // number of final points
private int pointDimension = 0; // Point dimension
private double tolerance = 0.0; // tolerance required by Douglas Peucker algorithm
private double toleranceSquared = 0.0; // above tolerance squared
private boolean tolerenceEntered = false; // = true when tolerance entered
private boolean simplifyDone = false; // = true when simplification performed
// CONSTRUCTORS
// Constructor - Polyline coordinates supplied as an array of Point
public PolylineSimplification(Point[] points){
this.originalPoints = points;
int n[] = Point.getArrayDimensions(points);
this.nPoints = n[0];
this.pointDimension = n[1];
if(this.pointDimension>3 || this.pointDimension<2)throw new IllegalArgumentException("This method will not operate on dimensions greater than 3");
this.simplifyDone = false;
}
// Constructor - Polyline coordinates supplied as two 1-dimensional arrays of doubles
public PolylineSimplification(double[] xpoints, double[] ypoints){
this.pointDimension = 2;
this.nPoints = xpoints.length;
if(this.nPoints!=ypoints.length)throw new IllegalArgumentException("The number of x-coordinate points, " + this.nPoints + ", must equal the number of y-coordinate points, " + ypoints.length);
this.originalPoints = Point.oneDarray(xpoints, ypoints);
this.simplifyDone = false;
}
// Constructor - Polyline coordinates supplied as three 1-dimensional arrays of doubles
public PolylineSimplification(double[] xpoints, double[] ypoints, double[] zpoints){
this.pointDimension = 3;
this.nPoints = xpoints.length;
if(this.nPoints!=ypoints.length)throw new IllegalArgumentException("The number of x-coordinate points, " + this.nPoints + ", must equal the number of y-coordinate points, " + ypoints.length);
if(this.nPoints!=zpoints.length)throw new IllegalArgumentException("The number of x-coordinate points, " + this.nPoints + ", must equal the number of z-coordinate points, " + zpoints.length);
this.originalPoints = Point.oneDarray(xpoints, ypoints, zpoints);
this.simplifyDone = false;
}
// Constructor - Polyline coordinates supplied as a multidimensional array of doubles
public PolylineSimplification(double[][] points){
this.pointDimension = points.length;
this.nPoints = points[0].length;
this.originalPoints = Point.oneDarray(points);
if(this.pointDimension>3 || this.pointDimension<2)throw new IllegalArgumentException("This method will not operate on dimensions greater than 3");
this.simplifyDone = false;
}
// Constructor - Polyline coordinates supplied as a multidimensional array of doubles dclared as an Object
public PolylineSimplification(Object points){
Object internalArrays = Fmath.copyObject(points);
this.nPoints = 1;
while(!((internalArrays = Array.get(internalArrays, 0)) instanceof Double))this.nPoints++;
double[][] hold = (double[][])points;
this.pointDimension = hold.length;
this.originalPoints = Point.oneDarray(hold);
if(this.pointDimension>3 || this.pointDimension<2)throw new IllegalArgumentException("This method will not operate on dimensions greater than 3 or less than 2");
this.simplifyDone = false;
}
// DOUGLAS PEUKER POLYLINE SIMPLIFICATION
// Douglas Peucker polyline simplification with supplied tolerance - replaces any preset tolerance
public Point[] douglasPeucker(double tolerance){
this.tolerance = tolerance;
this.toleranceSquared = tolerance*tolerance;
this.tolerenceEntered = true;
return douglasPeucker();
}
// Douglas Peucker polyline simplification with a preset tolerance
public Point[] douglasPeucker() {
int i = 0;
int k = 0; // counters
int toleratedCounter = 0;; // tolerated points counter
Point[] buffer = Point.oneDarray(this.nPoints); // vertex buffer
int[] indicesBuffer = new int[this.nPoints]; // vertex index buffer
boolean[] pointMarker = new boolean[this.nPoints]; // point marker buffer
if(this.pointDimension==2)this.toThreeDimO(); // 2D to 3D to facilitate the use of VectorMaths
// STAGE 1. Vertex Reduction within the supplied tolerance
buffer[0] = this.originalPoints[0].copy();
indicesBuffer[0] = 0;
for (i = k = 1; i < this.nPoints; i++) {
if(Point.distanceSquared(this.originalPoints[i], this.originalPoints[toleratedCounter]) < this.toleranceSquared)continue;
buffer[k] = this.originalPoints[i].copy();
indicesBuffer[k] = i;
toleratedCounter = i;
k++;
}
if (toleratedCounter < this.nPoints - 1){
buffer[k] = this.originalPoints[this.nPoints - 1].copy();
indicesBuffer[k] = this.nPoints - 1;
k++;
}
// STAGE 2. Douglas-Peucker polyline simplification
pointMarker[0] = true;
pointMarker[k - 1] = true; // mark the first and last vertices
douglasPeuckerSimplificationRoutine(buffer, 0, k - 1, pointMarker);
// collect marked verics to a Point array
ArrayList results = new ArrayList();
ArrayList indices = new ArrayList();
for (i = 0; i < k; i++) {
if (pointMarker[i]){
results.add(buffer[i]);
indices.add(new Integer(indicesBuffer[i]));
}
}
this.nSimplifiedPoints = results.size();
this.simplifiedPoints = Point.oneDarray(this.nSimplifiedPoints);
this.simplifiedIndices = new int[this.nSimplifiedPoints];
for(i=0; i this.toleranceSquared){ // error is worse than the tolerance
// split the polyline at the farthest vertex from S
pointMarker[farthesti] = true;
// recursively simplify the two subpolylines
douglasPeuckerSimplificationRoutine(bpoints, j, farthesti, pointMarker);
douglasPeuckerSimplificationRoutine(bpoints, farthesti, k, pointMarker);
}
}
// Fill out original points to 3D to facilitate use of VectorMaths
private void toThreeDimO(){
for(int i=0; i
Ads help maintain this website.