package PEU.P.image;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.List;
import java.util.Vector;
//作者,著作权人： 罗瑶光，浏阳
//convexHull的向量进行角度计算边缘，作者在2012年 美国洛杉矶进行，谷歌搜索到一个繁体字的文章关于compareSlope,
//于是进行修改，纠正。15-115行作者这几年一直找不到原文出处，就文字描述下。
//因此，此函数未出现在 DNA元基编码第四卷00919的函数列表中。此函数已被第6章数据预测的雷达机算法替代。
public class ConvexHull {
  double seconds;
  public List<Vertex> convexHull(List<Vertex> vertices){
    List<Vertex> polygon = new Vector<Vertex>();     
    int sx,lx; 
    Vertex vcurr = null; 
    Vertex vnext = null; 
    int i,x;
    lx = vertices.get(0).x;
    sx = vertices.get(0).x;
    for(i=1;i<vertices.size();i++) {
      x = vertices.get(i).x;
      if(x>lx) lx = x;
      if(x<sx) sx = x;
    }
    for(Vertex v : vertices) {
      if(v.x==sx && (vcurr==null || v.y>vcurr.y)) {
        vcurr = v;
      }
    }  
    int dxs,dys; 
    int dxc,dyc; 
    int dxt,dyt; 
    int lqc,lqt; 
    int scmp;  
    polygon.add(vcurr);
    dys = 1; dxs = 0;
    while(vcurr.x<=lx) {
      dyc = -1; dxc = 0; lqc = 0;
      for(Vertex v : vertices) {
        if(v.x>=vcurr.x) {
          dyt = v.y - vcurr.y;
          dxt = v.x - vcurr.x;
          if(compareSlope(dyt,dxt,dys,dxs)==-1) {
            scmp = compareSlope(dyt,dxt,dyc,dxc);
            lqt  = dyt*dyt+dxt*dxt;
            if(scmp>=0) {
              if(scmp>0 || lqt>lqc) {
                vnext = v;
                dyc = dyt;
                dxc = dxt;
                lqc = lqt;
              }
            }
          }
        }
      }
      if(vnext==null) {break;}
      dys = dyc; dxs = dxc;
      polygon.add(vnext);
      vertices.remove(vnext);
      vcurr = vnext; vnext = null;
    }
    dys = 1; dxs = 0;
    while(vcurr.x>sx) {
      dyc=-1; dxc = 0; lqc = 0;
      for(Vertex v : vertices) {
        if(v.x<vcurr.x) {
          dyt = v.y - vcurr.y;
          dxt = v.x - vcurr.x;
          if(compareSlope(dyt,dxt,dys,dxs)==-1) {
            scmp = compareSlope(dyt,dxt,dyc,dxc);
            lqt  = dyt*dyt+dxt*dxt;
            if(scmp>=0) {
              if(scmp>0 || lqt>lqc) {
                vnext = v;
                dyc = dyt;
                dxc = dxt;
                lqc = lqt;
              }
            }
          }
        }
      }

      if(vnext==null) break;
      dys = dyc; dxs = dxc;
      polygon.add(vnext);
      vertices.remove(vnext);
      vcurr = vnext; vnext = null;
    }    
    return polygon;
  }
  public int compareSlope(int dy2, int dx2, int dy1, int dx1) {
    if(dx2!=0 && dx1!=0) {
      double test = dy2*dx1-dy1*dx2;
      return (int)Math.signum(test);
    } else {
      if(dx2!=0 || dx1!=0) {
        if(dx2==0) {
          return dy2>=0 ? 1 : -1;
        } else {
          return dy1>=0 ? -1 : 1;
        }
      } else {
        if(dy2>=0) {
          return dy1>=0 ? 0 : 1;
        } else {
          return dy1>=0 ? -1 : 0;
        }
      }
    }
  }
  public class Vertex {
    public int x;
    public int y;
    public Vertex(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
  public void PNGWrite(int[][] g, int pix, String output) throws IOException {
    int [][]g1=new int[g.length][g[0].length]; 
    int n=0;
    for(int p=0;p<g.length;p++){
      for(int q=0;q<g[0].length;q++){
        if(g[p][q]==pix){
          g1[p][q]=g[p][q];
          n+=2;
        }else{
          g1[p][q]=0;
        }
      }  
    }      
    int[] points = new int[n];
    int n1=0;
    //converxto vetx
    for(int p=0;p<g1.length;p++){
      for(int q=0;q<g1[0].length;q++){
        if(g1[p][q]!=0){
          points[n1++]=p;
          points[n1++]=q;
        }
      }
    }
    List<Vertex> vertices = new Vector<Vertex>();
    for(int i1=0;i1<points.length;i1+=2) {
      Vertex v = new Vertex(points[i1],points[i1+1]);
      vertices.add(v);
    }
    //find  
    long begin = System.currentTimeMillis();
    List<Vertex> polygon = convexHull(vertices);
    long elapsed = System.currentTimeMillis()-begin;
    seconds = elapsed/1000.0;
    //converx to g[][]
    for(int p=0;p<g1.length;p++){
      for(int q=0;q<g1[0].length;q++){
        g1[p][q]=0;
      }
    }
    for(int i1=0;i1<polygon.size();i1++) {
      g1[polygon.get(i1).x][polygon.get(i1).y]=255;
    }    
    new ReadWritePng().writePNG(output, g1); 
  }
  public void CSVWrite(int[][] g, int pix, String outputcsv) throws IOException {
    int [][]g1=new int[g.length][g[0].length]; 
    int n=0;
    for(int p=0;p<g.length;p++){
      for(int q=0;q<g[0].length;q++){
        if(g[p][q]==pix){
          g1[p][q]=g[p][q];
          n+=2;
        }
        else{
          g1[p][q]=0;
        }
      }  
    }      
    int[] points = new int[n];
    int n1 = 0;
    //converxto vetx
    for(int p=0;p<g1.length;p++){
      for(int q=0;q<g1[0].length;q++){
        if(g1[p][q]!=0){
          points[n1++]=p;
          points[n1++]=q;
        }
      }
    }
    List<Vertex> vertices = new Vector<Vertex>();
    for(int i1=0;i1<points.length;i1+=2) {
      Vertex v = new Vertex(points[i1],points[i1+1]);
      vertices.add(v);
    }
    //find  
    long begin = System.currentTimeMillis();
    List<Vertex> polygon = convexHull(vertices);
    long elapsed = System.currentTimeMillis()-begin;
    seconds = elapsed/1000.0;
    //converx to g[][]
    for(int p=0;p<g1.length;p++){
      for(int q=0;q<g1[0].length;q++){
        g1[p][q]=0;
      }
    }
    for(int i1=0;i1<polygon.size();i1++) {
      g1[polygon.get(i1).x][polygon.get(i1).y]=255;
    }    
    File file = new File(outputcsv); 
    FileOutputStream out = new FileOutputStream(file);
    OutputStreamWriter osw = new OutputStreamWriter(out, "GB2312");
    BufferedWriter bw = new BufferedWriter(osw);
    bw.write("cod_x" + "," + "cod_y" + "\r\n");
    for(int i1=0;i1<polygon.size();i1++) {
      bw.write(polygon.get(i1).x+","+polygon.get(i1).y+ "\r\n");
    }    
    bw.close();
    osw.close();
    out.close();
  }
}