道格拉斯抽稀算法实现

package com.ctfo.dataserver.util.vacuate;

import java.util.List;

/**
 * 道格拉斯抽稀
 * @author OracleGao
 * @date 2015-03-27
 */
public class DouglasVacuater2D extends Vacuater2D {
 
 public DouglasVacuater2D() {
  super();
 }

 /**
  * 不做抽稀限制
  * @param precision
  */
 public DouglasVacuater2D(double precision) {
  super(precision, 0);
 }

 /**
  * @param vacuateLimit 抽稀界限小于该值的数据集合不被抽稀
  * @param precision 抽稀精度越大抽稀的数量越多
  */
 public DouglasVacuater2D(double precision, int vacuateLimit) {
  super(precision, vacuateLimit);
 }
 
 @Override
 protected void vacuate(List<Point> pointList) {
  vacuate(0, pointList.size() - 1, pointList);
 }

 /**
  * 道格拉斯抽稀
  * @param headIndex
  * @param tailIndex
  * @param pointList
  */
 private void vacuate(int headIndex, int tailIndex, List<Point> pointList) {
  Point head = pointList.get(headIndex);
  Point tail = pointList.get(tailIndex);
  int maxLengthIndex = -1;
  double maxLength = -1;
  double length = 0;
  for (int i = headIndex 1; i < tailIndex; i ) {
   length = minimumLengthOfPoint2SegmentP2(head, tail, pointList.get(i));
   if (maxLength < length) {
    maxLength = length;
    maxLengthIndex = i;
   }
  }
  if (maxLength <= precision) {
   for (int i = headIndex 1; i < tailIndex; i ) {
    pointList.get(i).vacuate = true;
   }
  } else {
   vacuate(headIndex, maxLengthIndex, pointList);
   vacuate(maxLengthIndex, tailIndex, pointList);
  }
 }
 
 /**
  * 点到线段的最短距离的平方
  * 为了提高计算性能，尽量不使用面向对象封装，且结果使用平方值
  * @param segmentHead
  * @param segmentTail
  * @param point
  * @return 最短距离的平方
  */
 private double minimumLengthOfPoint2SegmentP2(Point head, Point tail, Point point) {
  double product = (point.getX() - head.getX()) * (tail.getX() - head.getX()) (point.getY() - head.getY()) * (tail.getY() - head.getY());
  if (product <= 0) {
   return distanceP2(head, point);
  }
  double htdP2 = distanceP2(head, tail);
  double r = product / htdP2;
  if (r >= 1) {
   return distanceP2(tail, point);
  }
  double ppx = r * (tail.x - head.x) head.x;
  double ppy = r * (tail.y - head.y) head.y;
  return (ppx - point.x) * (ppx - point.x) (ppy - point.y) * (ppy - point.y);
 }
 
 /**
  * 两点距离的平方
  * @param point1
  * @param point2
  * @return
  */
 private double distanceP2(Point point1, Point point2) {
  return (point1.x - point2.x) * (point1.x - point2.x) (point1.y - point2.y) * (point1.y - point2.y);
 }

 
}