分治法——凸包问题

package com.算法.分治法;

import java.util.*;


public class 凸包问题 {
    public static void main(String[] args) {
        int[][] matrix = {{12,5},{23,1},{3,27},{65,4},{2,5},{5,3},{3,7},{5,7}};
        List P = new ArrayList<>();
        for (int[] ints : matrix) P.add(new Node(ints[0], ints[1],0));
        Set result = ConvexHull(P);
        System.out.println(result);
    }

    public static Set ConvexHull(List P){
        if (P.size()<=2) new HashSet<>(P);
        Set result = new HashSet<>();
        P.sort(Comparator.comparingInt(o -> o.x));
        Node n1 = P.get(0);
        Node n2 = P.get(P.size()-1);
        result.add(n1);
        result.add(n2);
        List u = new ArrayList<>();
        List d = new ArrayList<>();
        for (int i=1;i0) u.add(p);
            else if (prod<0) d.add(p);
            p.prod = prod;
        }
        result.addAll(upConvexHull(u,n1,n2));
        result.addAll(downConvexHull(d,n1,n2));
        return result;
    }

    private static Set downConvexHull(List list, Node n1, Node n2) {
        if (list.size()<=1) return new HashSet<>(list);
        else {
            Set result = new HashSet<>();
            //大家的底都是n1n2，所以直接比较面积大小即可
            Node max = list.get(0);
            for (Node node:list){
                if (Math.abs(max.prod) d1 = new ArrayList<>();
            List d2 = new ArrayList<>();
            result.add(max);
            for (Node node:list){
                int prod = sign(n1,max,node);
                if (prod<0) {
                    d1.add(node);
                }else {
                    prod = sign(max,n2,node);
                    if (prod<0) d2.add(node);
                }
                node.prod = prod;
            }
            result.addAll(upConvexHull(d1,n1,max));
            result.addAll(upConvexHull(d2,max,n2));
            return result;
        }
    }

    private static Set upConvexHull(List list, Node n1, Node n2) {
        if (list.size()<=1) return new HashSet<>(list);
        else {
            Set result = new HashSet<>();
            //大家的底都是n1n2，所以直接比较面积大小即可
            Node max = list.get(0);
            for (Node node:list){
                if (max.prod u1 = new ArrayList<>();
            List u2 = new ArrayList<>();
            result.add(max);
            for (Node node:list){
                int prod = sign(n1,max,node);
                if (prod>0) {
                    u1.add(node);
                }else {
                    prod = sign(max,n2,node);
                    if (prod>0) u2.add(node);
                }
                node.prod = prod;
            }
            result.addAll(upConvexHull(u1,n1,max));
            result.addAll(upConvexHull(u2,max,n2));
            return result;
        }
    }

    public static int sign(Node n1,Node n2,Node n3){
        return n1.x* n2.y+ n3.x*n1.y+ n2.x* n3.y- n3.x* n2.y- n2.x* n1.y- n1.x* n3.y;
    }

    static class Node{
        int x;int y;int prod;
        Node(int x,int y,int prod){
            this.x = x;
            this.y = y;
            this.prod = prod;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}