tiger870922

Untitled

May 28th, 2020
225
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.awt.*;
  2.         import java.awt.Color;
  3.         import java.awt.Graphics;
  4.         import java.awt.event.*;
  5.         import java.awt.event.WindowAdapter;
  6.         import java.awt.event.WindowEvent;
  7.         import java.util.List;
  8.         import java.util.Vector;
  9.  
  10.         class Convex extends Frame implements ActionListener, TextListener, MouseMotionListener{
  11.            
  12.             static Convex frm = new Convex();
  13.             static Button btn = new Button("Send");
  14.             static TextArea txa = new TextArea("請輸入要幾個點");
  15.             //static TextArea txa1 = new TextArea("Convex Hull");
  16.             static Label lab = new Label();
  17.             static Label lab1 = new Label("Convex Hull");
  18.             int amount;  
  19.            
  20.             private static class Vertex {
  21.                 public int x;
  22.                 public int y;
  23.  
  24.                
  25.                 public Vertex(int x, int y) {
  26.                     this.x = x;
  27.                     this.y = y;
  28.                 }
  29.             }
  30.             /*----------------------------------------------*/
  31.  
  32.  
  33.  
  34.            
  35.             public static void main(String args[]){
  36.                 btn.addActionListener(frm);  
  37.                 txa.addTextListener(frm);  
  38.                 frm.addMouseMotionListener(frm);
  39.  
  40.                 frm.setLayout(null);
  41.                 frm.setTitle("Convex Hull");
  42.                 btn.setBounds(425,500,75,50);
  43.                 txa.setBounds(200,500,225,50);
  44.                 lab1.setBounds(100,30,300,40);
  45.                 lab1.setBackground(Color.yellow);
  46.                 lab.setBounds(30,500,190,50);
  47.                
  48.                 frm.setSize(500,550);
  49.                 frm.add(btn);
  50.                 frm.add(txa);
  51.                 frm.add(lab1);
  52.                 frm.add(lab);
  53.                 frm.setVisible(true);
  54.  
  55.        
  56.                 frm.addWindowListener(new WindowAdapter(){
  57.                     public void windowClosing(WindowEvent e){
  58.                         frm.dispose();
  59.                     }
  60.                 });
  61.             }
  62.        
  63.  
  64.  
  65.    
  66.             public void actionPerformed(ActionEvent e){
  67.                 Graphics g = getGraphics();
  68.                 update(g);
  69.             }
  70.  
  71.        
  72.             public void textValueChanged(TextEvent e){
  73.                
  74.                 amount = Integer.valueOf(txa.getText());
  75.             }
  76.  
  77.            
  78.             public void mouseMoved(MouseEvent e){
  79.                 lab.setText("座標:("+e.getX()+","+e.getY()+")");
  80.             }
  81.  
  82.            
  83.             public void mouseDragged(MouseEvent e){
  84.                 lab.setText("座標:("+e.getX()+","+e.getY()+")");
  85.             }
  86.             /*-----------------------------------------------*/
  87.  
  88.  
  89.  
  90.            
  91.             public void paint(Graphics g){
  92.                
  93.                 int x[] = new int[amount];
  94.                 int y[] = new int[amount];
  95.                 List<Vertex> vertices = new Vector<Vertex>();
  96.  
  97.                
  98.                 for(int i=0; i<x.length; i++){
  99.                    
  100.                     x[i] = (int)(Math.random()*441)+30;
  101.                     y[i] = (int)(Math.random()*405)+75;
  102.  
  103.                     Vertex v = new Vertex(x[i], y[i]);
  104.                     vertices.add(v);  
  105.                     g.setColor(Color.red);
  106.                     g.fillOval(x[i], y[i], 5, 5);
  107.                 }
  108.  
  109.                
  110.                 long begin = System.currentTimeMillis();
  111.                 List<Vertex> polygon = convexhull(vertices);
  112.                 long elapsed = System.currentTimeMillis()-begin;
  113.                 double seconds = elapsed/1000.0;
  114.  
  115.                
  116.                 for(int i=1; i<polygon.size(); i++) {
  117.                     g.setColor(Color.black);
  118.                     g.drawLine(polygon.get(i-1).x, polygon.get(i-1).y, polygon.get(i).x, polygon.get(i).y);
  119.                 }
  120.                
  121.                 g.setColor(Color.black);
  122.                 g.drawLine(polygon.get(0).x, polygon.get(0).y, polygon.get(polygon.size()-1).x, polygon.get(polygon.size()-1).y);
  123.  
  124.                 System.out.printf("耗費了 %f 秒\n", seconds);
  125.             }
  126.             /*-----------------------------------------------*/
  127.  
  128.  
  129.  
  130.            
  131.             public static List<Vertex> convexhull(List<Vertex> vertices){
  132.                 List<Vertex> polygon = new Vector<Vertex>();
  133.                 int left, right;
  134.                 int dxs,dys;
  135.                 int dxc,dyc;  
  136.                 int dxt,dyt;
  137.                 int lqc,lqt;
  138.                 int compareResult;
  139.                 int x;
  140.                 Vertex current = null;
  141.                 Vertex next = null;
  142.  
  143.                
  144.                 left = vertices.get(0).x;
  145.                 right = vertices.get(0).x;
  146.                 for(int i=1; i<vertices.size(); i++){
  147.                    
  148.                     x = vertices.get(i).x;
  149.                     if(x<left) left = x;
  150.                     if(x>right) right = x;
  151.                 }
  152.  
  153.                
  154.                 for(Vertex v : vertices){
  155.                
  156.                     if(v.x==left && (current==null || v.y>current.y))
  157.                         current = v;
  158.                        
  159.                 }
  160.  
  161.                
  162.                 polygon.add(current);
  163.  
  164.  
  165.  
  166.                
  167.                 dys = 1;  dxs = 0;
  168.                 while(current.x<=right){
  169.                     dyc = -1;  dxc = 0;  lqc = 0;
  170.                     for(Vertex v : vertices){
  171.                     //依序把 vertices 加入 v
  172.                         if(v.x>=current.x){
  173.                             dyt = v.y - current.y;
  174.                             dxt = v.x - current.x;
  175.  
  176.                            
  177.                             if(compareSlope(dyt, dxt, dys, dxs) == -1){
  178.                                 compareResult = compareSlope(dyt,dxt,dyc,dxc);
  179.                                 lqt = dyt*dyt+dxt*dxt;  
  180.  
  181.                                 if(compareResult>=0)
  182.                                     if(compareResult>0 || lqt>lqc){
  183.                                         next = v;
  184.                                         dyc = dyt;
  185.                                         dxc = dxt;
  186.                                         lqc = lqt;
  187.                                     }
  188.                             }
  189.                         }
  190.                     }
  191.  
  192.                     if(next == null) break;
  193.                    
  194.                     dys = dyc;
  195.                     dxs = dxc;
  196.                     polygon.add(next);  
  197.                     vertices.remove(next);
  198.                     current = next;
  199.                     next = null;
  200.                 }
  201.  
  202.  
  203.            
  204.                 dys = 1;  dxs = 0;
  205.                 while(current.x>left){
  206.                     dyc = -1;  dxc = 0;  lqc = 0;
  207.                     for(Vertex v : vertices){
  208.                         if(v.x<current.x){
  209.                             dyt = v.y - current.y;
  210.                             dxt = v.x - current.x;
  211.  
  212.                             if(compareSlope(dyt, dxt, dys, dxs) == -1){
  213.                                 compareResult = compareSlope(dyt, dxt, dyc, dxc);
  214.                                 lqt = dyt*dyt+dxt*dxt;  //計算長度平方
  215.  
  216.                                 if(compareResult>=0)
  217.                                     if(compareResult>0 || lqt>lqc){
  218.                                         next = v;
  219.                                         dyc = dyt;
  220.                                         dxc = dxt;
  221.                                         lqc = lqt;
  222.                                     }
  223.                             }
  224.                         }
  225.                     }
  226.  
  227.                     if(next == null) break;
  228.                     dys = dyc;
  229.                     dxs = dxc;
  230.                     polygon.add(next);
  231.                     current = next;
  232.                     next = null;
  233.                 }
  234.  
  235.                 return polygon;
  236.                 //回傳我們找到的最外圍的點
  237.             }
  238.            
  239.  
  240.  
  241.  
  242.    
  243.             public static int compareSlope(int dy2, int dx2, int dy1, int dx1){
  244.                 if(dx2!=0 && dx1!=0){
  245.                
  246.                      double test = dy2*dx1-dy1*dx2;
  247.                      return (int)Math.signum(test);
  248.                    
  249.                 }
  250.  
  251.                 else{
  252.                    
  253.                     if(dx2!=0 || dx1!=0){
  254.                         if(dx2 == 0){
  255.                            
  256.                             return dy2>=0 ? 1 : -1;
  257.                         }
  258.                         else{
  259.                            
  260.                             return dy1>=0 ? -1 : 1;
  261.                         }
  262.                     }
  263.  
  264.                     else{
  265.                    
  266.                         if(dy2>=0){
  267.                            
  268.                             return dy1>=0 ? 0 : 1;
  269.                         }
  270.                         else{
  271.                            
  272.                             return dy1>=0 ? -1 : 0;
  273.                         }
  274.                     }
  275.                 }
  276.             }
  277.             /*-----------------------------------------------*/
  278.         }
RAW Paste Data