凸包问题

相关解读

Java代码

package com.算法.分治法;import java.util.*;/ * @Author Lanh /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<Node> P = new ArrayList<>(); for (int[] ints : matrix) P.add(new Node(ints[0], ints[1],0)); Set<Node> result = ConvexHull(P); System.out.println(result);    }    public static Set<Node> ConvexHull(List<Node> P){ if (P.size()<=2) new HashSet<>(P); Set<Node> 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<Node> u = new ArrayList<>(); List<Node> d = new ArrayList<>(); for (int i=1;i<P.size()-1;i++){     Node p = P.get(i);     int prod = sign(n1,n2,p);     if (prod>0) 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<Node> downConvexHull(List<Node> list, Node n1, Node n2) { if (list.size()<=1) return new HashSet<>(list); else {     Set<Node> result = new HashSet<>();     //大家的底都是n1n2，所以直接比较面积大小即可     Node max = list.get(0);     for (Node node:list){  if (Math.abs(max.prod)<Math.abs(node.prod)) max = node;     }     List<Node> d1 = new ArrayList<>();     List<Node> 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<Node> upConvexHull(List<Node> list, Node n1, Node n2) { if (list.size()<=1) return new HashSet<>(list); else {     Set<Node> result = new HashSet<>();     //大家的底都是n1n2，所以直接比较面积大小即可     Node max = list.get(0);     for (Node node:list){  if (max.prod<node.prod) max = node;     }     List<Node> u1 = new ArrayList<>();     List<Node> 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 +      '}'; }    }}