package com.huashe.park.common.geo.convex;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class ConcaveHull {
    // 点点之间距离列表
    private Double[][] _distances;

    // 邻居列表
    private List<List<Integer>> _neigbours;

    private Boolean[] _signs;

    private List<Point> _points;

    public ConcaveHull(List<Point> list) {
        // list stream 先按x升序，再按y升序排序
        _points = list.stream().sorted(Comparator.comparing(Point::getY) // 先按y排序
            .thenComparing(Point::getX)) // y相同则按x排序
            .collect(Collectors.toList());
        _signs = new Boolean[_points.size()];
        Arrays.fill(_signs, false);
        InitDistance();
        InitNeighbours();
    }

    /// <summary>
    /// 计算默认的半径
    /// </summary>
    /// <returns></returns>
    public double CalDefaultRadius() {
        double r = Double.MIN_VALUE;
        for (int i = 0; i < _points.size(); i++) {
            if (_distances[i][_neigbours.get(i).get(1)] > r) {
                r = _distances[i][_neigbours.get(i).get(1)];
            }
        }
        return r;
    }

    /// <summary>
    /// 使用滚球法获取凹包
    /// 不输入半径时，用默认计算半径代替
    /// </summary>
    /// <param name="radius"></param>
    /// <returns></returns>
    public List<Point> Compute(Double radius) {
        // 计算默认半径
        if (Double.compare(radius, -1) == 0) {
            radius = CalDefaultRadius();
        }
        List<Point> results = new ArrayList<>();
        List<Integer>[] neighs = GetNeighbourList(2 * radius);
        results.add(_points.get(0));
        int i = 0, j = -1, pre = -1;
        while (true) {
            j = GetNextPoint(pre, i, neighs[i], radius);
            if (j == -1) {
                break;
            }
            Point p = CalCenterByPtsAndRadius(_points.get(i), _points.get(j), radius);
            results.add(_points.get(j));
            _signs[j] = true;
            pre = i;
            i = j;
        }
        return results;
    }

    /// <summary>
    /// 初始化每个点的按距离排序的邻居列表
    /// </summary>
    private void InitNeighbours() {
        _neigbours = new ArrayList<>(_points.size());
        for (int i = 0; i < _points.size(); i++) {
            _neigbours.add(i, SortNeighboursByDis(i));
        }
    }

    /// <summary>
    /// 初始化点之间的距离
    /// </summary>
    private void InitDistance() {
        _distances = new Double[_points.size()][_points.size()];
        for (int i = 0; i < _points.size(); i++) {
            for (int j = 0; j < _points.size(); j++) {
                _distances[i][j] = CalDistanceToPts(_points.get(i), _points.get(j));
            }
        }
    }

    /// <summary>
    /// 获取下一个凹包点
    /// </summary>
    /// <param name="pre"></param>
    /// <param name="cur"></param>
    /// <param name="list"></param>
    /// <param name="radius"></param>
    /// <returns></returns>
    private int GetNextPoint(Integer pre, Integer cur, List<Integer> list, Double radius) {
        SortNeighbours(list, pre, cur);
        for (int j = 0; j < list.size(); j++) {
            if (_signs[list.get(j)]) {
                continue;

            }
            Integer adjIndex = list.get(j);
            Point xianp = _points.get(adjIndex);
            Point rightCirleCenter = CalCenterByPtsAndRadius(_points.get(cur), xianp, radius);
            if (!IsPointsInCircle(list, rightCirleCenter, radius, adjIndex)) {
                return list.get(j);
            }
        }
        return -1;
    }

    /// <summary>
    /// 根据角度对邻居列表进行排序
    /// </summary>
    /// <param name="list"></param>
    /// <param name="pre"></param>
    /// <param name="cur"></param>
    private void SortNeighbours(List<Integer> list, Integer pre, Integer cur) {
        Point origin = _points.get(cur);
        Point df;
        if (pre != -1) {
            df = new Point(_points.get(pre).getX() - origin.getX(), _points.get(pre).getY() - origin.getY());
        }
        else {
            df = new Point(1, 0);
        }
        int temp = 0;
        for (int i = list.size(); i > 0; i--) {
            for (int j = 0; j < i - 1; j++) {
                if (CompareAngle(_points.get(list.get(j)), _points.get(list.get(j + 1)), origin, df)) {
                    temp = list.get(j);
                    list.set(j, list.get(j + 1));
                    list.set(j + 1, temp);
                }
            }
        }
    }

    /// <summary>
    /// 检查圆内是否存在其他点
    /// </summary>
    /// <param name="roundPts"></param>
    /// <param name="center"></param>
    /// <param name="radius"></param>
    /// <param name="roundId"></param>
    /// <returns></returns>
    private Boolean IsPointsInCircle(List<Integer> roundPts, Point center, Double radius, Integer roundId) {
        for (int k = 0; k < roundPts.size(); k++) {
            if (!roundPts.get(k).equals(roundId)) {
                Integer index2 = roundPts.get(k);
                if (IsPtInCircle(_points.get(index2), center, radius)) {
                    return true;
                }
            }
        }
        return false;
    }

    /// <summary>
    /// 根据两点及半径计算圆心
    /// </summary>
    /// <param name="a"></param>
    /// <param name="b"></param>
    /// <param name="r"></param>
    /// <returns></returns>
    private static Point CalCenterByPtsAndRadius(Point a, Point b, Double r) {
        Double dx = b.getX() - a.getX();
        Double dy = b.getY() - a.getY();
        Double cx = 0.5 * (b.getX() + a.getX());
        Double cy = 0.5 * (b.getY() + a.getY());
        Double v = r * r / (dx * dx + dy * dy) - 0.25;
        if (v < 0) {
            return new Point(-1, -1);
        }
        Double sqrt = Math.sqrt(v);
        return new Point(cx - dy * sqrt, cy + dx * sqrt);
    }

    /// <summary>
    /// 检查点是否在圆内
    /// </summary>
    /// <param name="p"></param>
    /// <param name="center"></param>
    /// <param name="r"></param>
    /// <returns></returns>
    private static Boolean IsPtInCircle(Point p, Point center, Double r) {
        double dis2 = (p.getX() - center.getX()) * (p.getX() - center.getX())
            + (p.getY() - center.getY()) * (p.getY() - center.getY());
        return dis2 < r * r;
    }

    /// <summary>
    /// 获取半径范围内的邻居列表
    /// </summary>
    /// <param name="radius"></param>
    /// <returns></returns>
    private List<Integer>[] GetNeighbourList(double radius) {
        List<Integer>[] adjs = new ArrayList[_points.size()];
        for (int i = 0; i < _points.size(); i++) {
            adjs[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < _points.size(); i++) {

            for (int j = 0; j < _points.size(); j++) {
                if (i < j && _distances[i][j] < radius) {
                    adjs[i].add(j);
                    adjs[j].add(i);
                }
            }
        }
        return adjs;
    }

    /// <summary>
    /// 按距离排序的邻居列表
    /// </summary>
    /// <param name="index"></param>
    /// <returns></returns>
    private List<Integer> SortNeighboursByDis(int index) {
        List<Point> pts = new ArrayList<>();

        for (int i = 0; i < _points.size(); i++) {
            Point pt = _points.get(i);
            pt.setId(i);
            pt.setDistance(_distances[index][i]);
            pts.add(pt);
        }
        pts = pts.stream().sorted(Comparator.comparing(Point::getDistance)).collect(Collectors.toList());

        List<Integer> adj = new ArrayList<>();
        for (int i = 1; i < pts.size(); i++) {
            adj.add(pts.get(i).getId());
        }
        return adj;
    }

    /// <summary>
    /// 比较两个点相对于参考点的角度
    /// </summary>
    /// <param name="a"></param>
    /// <param name="b"></param>
    /// <param name="origin"></param>
    /// <param name="reference"></param>
    /// <returns></returns>
    private Boolean CompareAngle(Point a, Point b, Point origin, Point reference) {

        Point da = new Point(a.getX() - origin.getX(), a.getY() - origin.getY());
        Point db = new Point(b.getX() - origin.getX(), b.getY() - origin.getY());
        // b相对于参考向量的叉积
        Double detb = CalCrossProduct(reference, db);
        // 如果 b 的叉积为零且 b 与参考向量的夹角大于等于零度，则返回 false
        if (detb == 0 && db.getX() * reference.getX() + db.getY() * reference.getY() >= 0) {
            return false;
        }
        // a 相对于参考向量的叉积
        Double deta = CalCrossProduct(reference, da);
        // 如果 a 的叉积为零且 a 与参考向量的夹角大于等于零度，则返回 true
        if (deta == 0 && da.getX() * reference.getX() + da.getY() * reference.getY() >= 0) {
            return true;
        }
        // 如果 a 和 b 在参考向量的同一侧，则比较它们之间的叉积大小
        if (deta * detb >= 0) {
            // 如果叉积大于零，返回 true；否则返回 false
            return CalCrossProduct(da, db) > 0;
        }

        // 向量小于零度实际上是很大的，接近 2pi
        return deta > 0;
    }

    /// <summary>
    /// 计算两点之间的距离
    /// </summary>
    /// <param name="p1"></param>
    /// <param name="p2"></param>
    /// <returns></returns>
    private static Double CalDistanceToPts(Point p1, Point p2) {
        return Math.sqrt(
            (p1.getX() - p2.getX()) * (p1.getX() - p2.getX()) + (p1.getY() - p2.getY()) * (p1.getY() - p2.getY()));
    }

    /// <summary>
    /// 计算两个向量的叉积
    /// </summary>
    /// <param name="a"></param>
    /// <param name="b"></param>
    /// <returns></returns>
    private static Double CalCrossProduct(Point a, Point b) {
        return a.getX() * b.getY() - a.getY() * b.getX();
    }
}
