Go语言视频零基础入门到精通

javalearner

求凸包java演示程序:

1. import java.awt.*;
   
2. import java.awt.event.*;
   
3. import javax.swing.*;
   
4. import javax.swing.event.*;
   
5. import javax.swing.border.*;
   
6. import java.util.*;
   
7. /*
   
8. *        直线类
   
9. */
   
10. class Line {
    
11. Point p1, p2;
    
12. Line(Point p1, Point p2) {
    
13.   this.p1 = p1;
    
14.   this.p2 = p2;
    
15. }
    
16. void draw(Graphics g) {
    
17.         g.drawLine(p1.x, p1.y, p2.x, p2.y);
    
18. }
    
19. public String toString() {
    
20.    return "(" + p1.x + ", " + p1.y + ") -> (" + p2.x + ", " + p2.y + ")";
    
21. }
    
22. }
    
23. /*
    
24. *        凸包接口
    
25. */
    
26. interface TuBao {
    
27.         void setPointList(java.util.List< Point> pts);
    
28.         java.util.List< Line> eval();
    
29. }
    
30. /*
    
31. *        暴力法求凸包
    
32. */
    
33. class BaoLiTuBao implements TuBao {
    
34.   java.util.List< Point> pts = null;
    
35.   java.util.List< Line> lines = new ArrayList< Line>();
    
36.    public void setPointList(java.util.List< Point> pts) {
    
37.      this.pts = pts;
    
38.    }
    
39.        
    
40.    public java.util.List< Line> eval() {
    
41.     lines.clear();
    
42.     if (pts == null) { return lines; }
    
43.     int n = pts.size();
    
44.     int a, b, c, cc, l, r;
    
45.     for (int i = 0; i < n; i++) {
    
46.      for (int j = i+1; j < n; j++) {
    
47.        a = pts.get(j).y - pts.get(i).y;
    
48.        b = pts.get(i).x - pts.get(j).x;
    
49.        c = pts.get(i).x * pts.get(j).y -pts.get(i).y * pts.get(j).x;
    
50.        l = r = 0;
    
51.        int k;
    
52.        for (k = 0; k < n; k++) {
    
53.          cc = a * pts.get(k).x + b * pts.get(k).y;
    
54.          if (cc > c) l++;
    
55.          else if (cc < c) r++;
    
56.          if (l * r != 0) break;
    
57.        }
    
58.       if (k == n) {
    
59.         lines.add(new Line(pts.get(i), pts.get(j)));
    
60.       }
    
61.      }
    
62.    }
    
63.    return lines;
    
64.   }
    
65. }
    
66. /*
    
67. *        分治法求凸包
    
68. */
    
69. class QuickTuBao implements TuBao {
    
70. java.util.List< Point> pts = null;
    
71. java.util.List< Line> lines = new ArrayList< Line>();
    
72.        
    
73. public void setPointList(java.util.List< Point> pts) {
    
74.         this.pts = pts;
    
75. }
    
76. 
    
77.   //求凸包，结果存入lines中
    
78.   public java.util.List< Line> eval() {
    
79.     lines.clear();
    
80.     if (pts == null || pts.isEmpty()) { return lines; }
    
81.                
    
82.     java.util.List< Point> ptsLeft = new ArrayList< Point>();
    
83.     java.util.List< Point> ptsRight = new ArrayList< Point>();
    
84.                
    
85.     //按x坐标对pts排序
    
86.      Collections.sort(pts, new Comparator< Point>() {
    
87.        public int compare(Point p1, Point p2) {
    
88.           return p1.x-p2.x;
    
89.        }
    
90.     });
    
91.     Point p1 = pts.get(0);        //最左边的点
    
92.     Point p2 = pts.get(pts.size()-1);        //最右边的点
    
93.     Point p3 = null;
    
94.     int area = 0;
    
95.     for (int i = 1; i < pts.size(); i++) {
    
96.        p3 = pts.get(i);
    
97.        area = getArea(p1, p2, p3);
    
98.        if (area > 0) {               
    
99.          ptsLeft.add(p3);
    
100.        } else if (area < 0) {
     
101.          ptsRight.add(p3);
     
102.        }
     
103.      }
     
104.      d(p1, p2, ptsLeft);
     
105.      d(p2, p1, ptsRight);
     
106.       return lines;
     
107.    }
     
108.    private void d(Point p1, Point p2, java.util.List< Point> s) {
     
109.       //s集合为空
     
110.       if (s.isEmpty()) {
     
111.         lines.add(new Line(p1, p2));
     
112.         return;
     
113.        }
     
114.        //s集合不为空，寻找Pmax
     
115.        int area = 0;
     
116.        int maxArea = 0;
     
117.        Point pMax = null;
     
118.        for (int i = 0; i < s.size(); i++) {
     
119.          area = getArea(p1, p2, s.get(i));
     
120.          if (area > maxArea) {
     
121.             pMax = s.get(i);
     
122.             maxArea = area;
     
123.           }
     
124.         }
     
125.           //找出位于(p1, pMax)直线左边的点集s1
     
126.           //找出位于(pMax, p2)直线左边的点集s2
     
127.         java.util.List< Point> s1 = new ArrayList< Point>();
     
128.         java.util.List< Point> s2 = new ArrayList< Point>();
     
129.         Point p3 = null;
     
130.         for (int i = 0; i < s.size(); i++) {
     
131.             p3 = s.get(i);
     
132.             if (getArea(p1, pMax, p3) > 0) {
     
133.                s1.add(p3);
     
134.             } else if (getArea(pMax, p2, p3) > 0) {
     
135.                s2.add(p3);
     
136.             }
     
137.          }
     
138.          //递归
     
139.          d(p1, pMax, s1);
     
140.          d(pMax, p2, s2);       
     
141.     }
     
142.        
     
143.        // 三角形的面积等于返回值绝对值的二分之一
     
144.        // 当且仅当点p3位于直线(p1, p2)左侧时，表达式的符号为正
     
145.         private int getArea(Point p1, Point p2, Point p3) {
     
146.            return p1.x * p2.y + p3.x * p1.y + p2.x * p3.y -
     
147.             p3.x * p2.y - p2.x * p1.y - p1.x * p3.y;
     
148.         }
     
149. }
     
150. /*
     
151. *        绘制点及凸包的面板
     
152. */
     
153. class DrawPanel extends JPanel {
     
154.         public static final int WIDTH = 640;
     
155.         public static final int HEIGHT = 480;
     
156.         public static final int BORDER = 100;
     
157.         java.util.List< Point> pts = new ArrayList< Point>();
     
158.         TuBao tuBao = null;
     
159.         int n;
     
160.         public DrawPanel() {
     
161.             setPreferredSize(new Dimension(WIDTH, HEIGHT));
     
162.             setBorder(new LineBorder(Color.RED));
     
163.             n = 100;
     
164.         }
     
165.         public void setN(int n) { this.n = n; }
     
166.         public void setTuBao(TuBao tuBao) {
     
167.                 this.tuBao = tuBao;
     
168.                 tuBao.setPointList(pts);
     
169.         }
     
170.         public void randPoints() {
     
171.           pts.clear();
     
172.           Random rd = new Random(new Date().getTime());
     
173.           for (int i = 0; i < n; i++) {
     
174.           pts.add(new Point(rd.nextInt(WIDTH-BORDER*2)+BORDER,
     
175.              rd.nextInt(HEIGHT-BORDER*2)+BORDER));
     
176.         }
     
177.      }
     
178.      public void paintComponent(Graphics g) {
     
179.         super.paintComponent(g);       
     
180.         Color c = g.getColor();
     
181.         g.setColor(Color.red);
     
182.         for (Point pt : pts) {
     
183.            g.fillOval(pt.x, pt.y, 5, 5);
     
184.         }
     
185.         g.setColor(c);
     
186.         if (tuBao == null) return;
     
187.         for (Line line : tuBao.eval()) {
     
188.                 line.draw(g);
     
189.         }
     
190.         tuBao = null;
     
191.      }
     
192.   }
     
193. /*
     
194. *        主窗体
     
195. */
     
196. public class GetTuBao extends JFrame {
     
197.         DrawPanel drawPanel;
     
198.         JSlider sd;
     
199.         JLabel lb;
     
200.         TuBao baoLiTuBao = new BaoLiTuBao();
     
201.         TuBao quickTuBao = new QuickTuBao();
     
202.         public GetTuBao() {
     
203.           setTitle("凸包问题演示");
     
204.                
     
205.           JPanel menu = new JPanel();
     
206.           menu.setLayout(new FlowLayout(FlowLayout.LEFT));
     
207.           sd = new JSlider(JSlider.HORIZONTAL, 0, 100, 100);
     
208.           sd.setMajorTickSpacing(20);
     
209.           sd.setMinorTickSpacing(10);
     
210.           sd.setPaintTicks(true);
     
211.           lb = new JLabel("100");
     
212.           JButton btnRand = new JButton("随机点");
     
213.           JButton btnBaoLi = new JButton("暴力法");
     
214.           JButton btnQuick = new JButton("快包法");
     
215.           menu.add(sd);
     
216.           menu.add(lb);
     
217.           menu.add(btnRand);
     
218.           menu.add(btnBaoLi);
     
219.           menu.add(btnQuick);
     
220.                
     
221.           drawPanel = new DrawPanel();
     
222.           add(BorderLayout.NORTH, menu);
     
223.           add(BorderLayout.CENTER, drawPanel);
     
224.                
     
225.           pack();
     
226.           setResizable(false);
     
227.                
     
228.           sd.addChangeListener(new ChangeListener() {
     
229.             public void stateChanged(ChangeEvent e) {
     
230.                 lb.setText(String.valueOf(sd.getValue()));
     
231.                 drawPanel.setN(sd.getValue());
     
232.             }
     
233.           });
     
234.                
     
235.         btnRand.addActionListener(new ActionListener() {
     
236.            public void actionPerformed(ActionEvent e) {
     
237.                 drawPanel.randPoints();
     
238.                 repaint();
     
239.            }
     
240.         });
     
241.                
     
242.         btnBaoLi.addActionListener(new ActionListener() {
     
243.            public void actionPerformed(ActionEvent e) {
     
244.                 drawPanel.setTuBao(baoLiTuBao);
     
245.                 repaint();
     
246.            }
     
247.         });
     
248.                
     
249.         btnQuick.addActionListener(new ActionListener() {
     
250.            public void actionPerformed(ActionEvent e) {
     
251.                 drawPanel.setTuBao(quickTuBao);
     
252.                 repaint();
     
253.                
     
254.            }
     
255.         });
     
256.                
     
257.         setVisible(true);
     
258.      }
     
259.     public static void main(String[] args) {
     
260.       try {
     
261.         UIManager.setLookAndFeel("com.sun.java.swing.plaf.windows.WindowsLookAndFeel");
     
262.       } catch(Exception e) {
     
263.         e.printStackTrace();
     
264.       }
     
265.                
     
266.       EventQueue.invokeLater(new Runnable() {
     
267.             public void run() {
     
268.                 GetTuBao getTuBao = new GetTuBao();
     
269.            }
     
270.        });
     
271.     }
     
272. }
     

复制代码

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/13/235943406.zip