基本思路是：对每一条曲线的首末点虚连一条直线，求所有点与直线的距离，并找出最大距离值dmax，用dmax与限差D相比： 若dmax＜D，这条曲线上的中间点全部舍去；
若dmax≥D，保留dmax对应的坐标点，并以该点为界，把曲线分为两部分，对这两部分重复使用该方法。
定义曲线上的点：
代码语言：javascript复制public class Point {
private double x;
private double y;
public Point(double x,double y){
this.x = x;
this.y = y;
}
public Point(String x,String y){
this.x = Double.parseDouble(x);
this.y = Double.parseDouble(y);
}
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}
public void printPoint(){
System.out.print(MessageFormat.format("({0},{1})", this.x,this.y));
}
}定义线
代码语言：javascript复制public class Line {
private Point start;
private Point end;
private ArrayList<Point> linePoints = new ArrayList<Point>();
private double A;
private double B;
private double C;
private int index;//最大距离所对应曲线上的点的索引号
private double distance;//最大距离，与阈值比较
public ArrayList<Point> getLinePoints() {
return linePoints;
}
public void setLinePoints(ArrayList<Point> linePoints) {
this.linePoints = linePoints;
}
//已知了线的两个端点，求两个端点所连线段到线的最大距离
public Line(Point start,Point end ){
this.start = start;
this.end = end;
linePoints.add(start);
linePoints.add(end);
}
public Line(ArrayList<Point> linePoints){
this.linePoints = linePoints;
this.start = linePoints.get(0);
this.end = linePoints.get(linePoints.size()-1);
initABC();
computeLineToLine();
}
public Line(Point start,Point end,ArrayList<Point> linePoints){
this.start = start;
this.end = end;
this.linePoints = linePoints;
}
public Point getStart() {
return start;
}
public void setStart(Point start) {
this.start = start;
}
public Point getEnd() {
return end;
}
public void setEnd(Point end) {
this.end = end;
}
public double getDistance() {
return distance;
}
public void setDistance(double distance) {
this.distance = distance;
}
public void computeLineToLine(){
double maxDist=Double.MIN_VALUE;
double dist = 0;
index=0;
for(int i=0;i<linePoints.size();i ){
dist = computePointToLineDist(linePoints.get(i));
if(dist>maxDist)
{
maxDist = dist;
index = i;
}
}
this.distance = maxDist;
}
public double getA() {
return A;
}
public void setA(double a) {
A = a;
}
public double getB() {
return B;
}
public void setB(double b) {
B = b;
}
public double getC() {
return C;
}
public void setC(double c) {
C = c;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public double computePointToLineDist(Point point){
return (A*point.getX() B*point.getY() C)/Math.sqrt(A*A B*B);
}
public void initABC(){
this.A = start.getY()-end.getY();
this.B = end.getX()-start.getX();
this.C = start.getY()*(-B)-start.getX()*A;
}
public void printLine(){
System.out.print("-------");
for(Point point:linePoints){
point.printPoint();
}
System.out.print("-------");
}
public void addPoint(Point p){
this.linePoints.add(p);
}
}压缩：
代码语言：javascript复制import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
public class DP_Tool {
private String filePath;
private double threshold;
private ArrayList<Point> pointList;
private ArrayList<String[]> listTemp;//存放从文件中读入的数据
private ArrayList<Line> lineList = new ArrayList<Line>();
private ArrayList<Line> resultLine = new ArrayList<Line>();//存储一条曲线压缩完成后的结果
private ArrayList<ArrayList<Line>> compressionCollection = new ArrayList<ArrayList<Line>>();//存储所有被压缩完成的线段;
public DP_Tool(String filePath,double threshold){
this.filePath = filePath;
this.threshold = threshold;
readDataFile();
initPointAndLine();
}
private void readDataFile() {
File file = new File(filePath);
listTemp = new ArrayList<String[]>();
try{
BufferedReader in = new BufferedReader(new FileReader(file));
String str;
String[] strTemp;
while((str=in.readLine())!=null){
strTemp = str.split(" ");
listTemp.add(strTemp);
}
in.close();
}catch(IOException e){
e.printStackTrace();
}
}
private void initPointAndLine(){
Line line;
for(int i=0;i<listTemp.size();i ){
pointList = new ArrayList<Point>();
Point point;
String st;
int start;
int end1;
int end2;
String[] str = listTemp.get(i);
for(int j=0;j<str.length;j ){
st = str[j];
start = st.indexOf("(");
end1 =st.indexOf(",");
end2 = st.indexOf(")");
point = new Point(st.substring(start 1,end1),st.substring(end1 1,end2));
pointList.add(point);
}
line = new Line(pointList);
lineList.add(line);
}
}
public void compressLine(Line line){
Line lineTemp;
if(line.getDistance()<threshold){
//说明可以利用这条线段来代替曲线
lineTemp = new Line(line.getStart(),line.getEnd());
resultLine.add(lineTemp);
}
else{
ArrayList<Point> pointsTemp1 = new ArrayList<Point>();
ArrayList<Point> pointsTemp2 = new ArrayList<Point>();
for(int i=0;i<=line.getIndex();i ){
pointsTemp1.add(line.getLinePoints().get(i));
}
for(int j=line.getIndex();j<line.getLinePoints().size();j ){
pointsTemp2.add(line.getLinePoints().get(j));
}
compressLine(new Line(pointsTemp1));//分两段进行压缩，分段的位置极为距离最大的点
compressLine(new Line(pointsTemp2));
}
compressionCollection.add(resultLine);
}
public void startCompression(){
for(int i=0;i<lineList.size();i ){
lineList.get(i).printLine();
resultLine.clear();//这里负责的是清除前一条曲线压缩的线段
compressLine(lineList.get(i));
System.out.print("在结果集合中曲线被压缩成" resultLine.size() "段");
//每压缩一条曲线则会初始化一次resultLine，则把它打印出来
for(Line line:resultLine){
line.printLine();
}
System.out.println();
}
//打印出压缩结果
}
}输入：
代码语言：javascript复制(1,2) (30,4) (5,60) (70,8) (9,100) (110,12)
(12,58) (30,2) (6,60) (10,88) (45,100) (77,12)
(2,14) (15,6) (7,24) (35,6) (45,44) (51,37)输出：
代码语言：javascript复制-------(1,2)(30,4)(5,60)(70,8)(9,100)(110,12)-------在结果集合中曲线被压缩成2段-------(1,2)(9,100)--------------(9,100)(110,12)-------
-------(12,58)(30,2)(6,60)(10,88)(45,100)(77,12)-------在结果集合中曲线被压缩成5段-------(12,58)(30,2)--------------(30,2)(6,60)--------------(6,60)(10,88)--------------(10,88)(45,100)--------------(45,100)(77,12)-------
-------(2,14)(15,6)(7,24)(35,6)(45,44)(51,37)-------在结果集合中曲线被压缩成3段-------(2,14)(7,24)--------------(7,24)(45,44)--------------(45,44)(51,37)-------
