道格拉斯·普克演算法 JAVA實作

道格拉斯·普克演算法 JAVA實作

作用：

假如現在有個需求，后端計算出來一條路線規劃，路線是由無數個坐標點組成，但是其中大部分連起來都是直線，那直線中有用的點也就起始點和終點，中間的全部點都是可以省略的，

原理：

對一條路徑的起點和終點做一條直線，計算其余全部點到直線的距離，并找出最大距離，若最大距離比閾值小，則去掉全部中間點，若距離比閾值大，則保留當前點，以當前點為界，分成左右兩條路徑，重復前面的程序，直到所有的距離都小于閾值，就完事了，所以閾值越大，點越稀少，閾值越小，路徑越接近真實的，

1、坐標點物體

package com.pet.utils;

import lombok.AllArgsConstructor;
import lombok.Data;

@Data
@AllArgsConstructor
class Coordinate {
    private double x;
    private double y;
}

2、抽稀

閾值應大于等于1，閾值越大，路徑越簡單，閾值越小，路徑越全，

package com.pet.utils;

import java.util.ArrayList;
import java.util.List;

public class DouglasUtil {
    public static void main(String[] args) {
        List<Coordinate> points = new ArrayList<>();
        points.add(new Coordinate(1, 2));
        points.add(new Coordinate(2, 2));
        points.add(new Coordinate(3, 4));
        points.add(new Coordinate(4, -5));
        points.add(new Coordinate(5, 3));
        points.add(new Coordinate(6, 3));
        points.add(new Coordinate(7, 5));
        points.add(new Coordinate(8, 2));
        points.add(new Coordinate(9, 0));
        points.add(new Coordinate(10, 9));
        points.add(new Coordinate(11, 5));

        for (Coordinate p : douglas(points, 1)) {
            System.out.print("(" + p.getX() + "," + p.getY() + ") ");
        }
    }

    private static List<Coordinate> douglas(List<Coordinate> points, int threshold) {
        List<Coordinate> result = new ArrayList<>();

        // 找到最大閾值點
        double maxH = 0;
        int index = 0;
        int end = points.size();
        for (int i = 1; i < end - 1; i++) {
            // 計算點到起點和終點組成線段的高
            double h = getDistance(points.get(i), points.get(0), points.get(end - 1));
            if (h > maxH) {
                maxH = h;
                index = i;
            }
        }

        // 如果存在最大閾值點，就進行遞回遍歷出所有最大閾值點
        return getCoordinates(points, threshold, maxH, index, end, result);
    }

    private static List<Coordinate> getCoordinates(List<Coordinate> points, int epsilon, double maxH, int index, int end, List<Coordinate> result) {
        if (maxH > epsilon) {
            List<Coordinate> leftPoints = new ArrayList<>();
            List<Coordinate> rightPoints = new ArrayList<>();
            // 分成兩半 繼續找比閾值大的
            for (int i = 0; i < end; i++) {
                if (i < index) {
                    leftPoints.add(points.get(i));
                } else {
                    rightPoints.add(points.get(i));
                }
            }
            List<Coordinate> leftResult = douglas(leftPoints, epsilon);
            List<Coordinate> rightResult = douglas(rightPoints, epsilon);

            rightResult.remove(0);
            leftResult.addAll(rightResult);
            result = leftResult;
        } else {
            result.add(points.get(0));
            result.add(points.get(end - 1));
        }
        return result;
    }

    /**
     * 計算點到直線的距離
     */
    private static double getDistance(Coordinate p, Coordinate s, Coordinate e) {
        double AB = distance(s, e);
        double CB = distance(p, s);
        double CA = distance(p, e);
        // 三角形面積
        double S = helen(CB, CA, AB);
        // 三角形面積 = AB（底） * 高 / 2
        // 所以 高 = 2 * 三角形面積 / AB（底）
        return 2 * S / AB;
    }

    /**
     * 計算兩點之間的距離
     */
    private static double distance(Coordinate p1, Coordinate p2) {
        double x1 = p1.getX();
        double y1 = p1.getY();
        double x2 = p2.getX();
        double y2 = p2.getY();
        return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    }

    /**
     * 三角形面積
     */
    private static double helen(double CB, double CA, double AB) {
        double p = (CB + CA + AB) / 2;
        return Math.sqrt(p * (p - CB) * (p - CA) * (p - AB));
    }
}

3、路徑從哪兒來？那下一篇再整個迪杰特斯拉（最短路徑）演算法