JWorld@TW the best professional Java site in Taiwan
      註冊 | 登入 | 全文檢索 | 排行榜  

» JWorld@TW » Java 技巧文件 » Java與演算法  

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友    訂閱主題
reply to postflat modego to previous topicgo to next topic
本主題所含的標籤
作者 Convex Hull (凸包) 演算法 Swing 解說版
秒殺



版主

發文: 131
積分: 2
於 2010-04-15 11:04 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
這是一個平面幾何上實用的演算法
這個演算法的輸入是許多點座標
然後分析出怎麼畫多邊形能夠包住所有的點
因為這是幾何問題
所以在下寫成 Swing 版本很容易就能看懂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
import java.awt.Color;
import java.awt.Graphics;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.awt.image.BufferedImage;
import java.util.List;
import java.util.Vector;
 
import javax.swing.JFrame;
import javax.swing.JPanel;
 
public class ConvexHullSwing extends JPanel {
 
  private static final long serialVersionUID = 0;
  private static final int  EDGE_LENGTH = 500;
  
  int space;
  int xcount;
  int ycount;
  double seconds;
  BufferedImage bimg = new BufferedImage(EDGE_LENGTH,EDGE_LENGTH,BufferedImage.TYPE_INT_ARGB);
  
  // ConvexHull 視窗
  public ConvexHullSwing() {
    int i;
    space = 10;
    xcount = bimg.getWidth()/space;
    ycount = bimg.getHeight()/space;
    for(i=0;i<ycount;i++) drawHL(i);
    for(i=0;i<xcount;i++) drawVL(i);
 
    // 畫點
    int[] points = {
      1,  1,
      2,  5,
      20, 4,
      33, 2,
      40, 20,
      11, 7,
      37, 31,
      17, 21,
      20, 15
    };
    List<Vertex> vertices = new Vector<Vertex>();
    for(i=0;i<points.length;i+=2) {
      Vertex v = new Vertex(points[i],points[i+1]);
      vertices.add(v);
      drawPoint(v);
    }
    
    // 執行 Convex Hull 演算法, 畫出多邊形
    long begin   = System.currentTimeMillis();
    List<Vertex> polygon = convexHull(vertices);
    long elapsed = System.currentTimeMillis()-begin;
    seconds = elapsed/1000.0;
    for(i=1;i<polygon.size();i++) {
      drawLine(polygon.get(i-1),polygon.get(i));
    }
    drawLine(polygon.get(i-1),polygon.get(0));
    System.out.printf("處理 %d 個點消耗 %f 秒\n",vertices.size(),seconds);
  }
 
  // 畫面更新 (把 buffer 畫到 swing 視窗上)
  public void paintComponent(Graphics g) {
    int fetch_w = Math.min(getWidth()-40,EDGE_LENGTH);
    int fetch_h = Math.min(getHeight()-40,EDGE_LENGTH);    
    int sx1 = 20;
    int sy1 = 20;
    int sx2 = sx1+fetch_w-1;
    int sy2 = sy1+fetch_h-1;
    int dx1 = 0;
    int dy1 = EDGE_LENGTH-fetch_h+1;
    int dx2 = fetch_w-1;
    int dy2 = EDGE_LENGTH;
    g.drawImage(bimg,sx1,sy1,sx2,sy2,dx1,dy1,dx2,dy2,null);
  }
 
  // 格子座標系畫水平線
  public void drawHL(int y) {
    int ty = transY(y);
    int lx = transX(0)+1;
    int rx = transX(xcount);
    
    Color c = y==0 ? Color.BLACK : new Color(200,200,200);
    Graphics g = bimg.getGraphics();
    g.setColor(c);
    g.drawLine(lx,ty,rx,ty);
  }
 
  // 格子座標系畫垂直線
  public void drawVL(int x) {
    int tx = transX(x);
    int by = transY(0)-1;
    int ty = transY(ycount);
    
    Color c = x==0 ? Color.BLACK : new Color(200,200,200);
    Graphics g = bimg.getGraphics();
    g.setColor(c);
    g.drawLine(tx,ty,tx,by);
  }
 
  // 格子座標系畫叉叉的點
  public void drawPoint(Vertex v) {
    int tx = transX(v.x);
    int ty = transY(v.y);
    
    Graphics g = bimg.getGraphics();
    g.setColor(Color.RED);
    g.drawLine(tx-2,ty-2,tx+2,ty+2);
    g.drawLine(tx-2,ty+2,tx+2,ty-2);
  }
  
  // 格子座標系畫線
  public void drawLine(Vertex v1, Vertex v2) {
    int tx1 = transX(v1.x);
    int ty1 = transY(v1.y);
    int tx2 = transX(v2.x);
    int ty2 = transY(v2.y);
    
    Graphics g = bimg.getGraphics();
    g.setColor(Color.BLUE);
    g.drawLine(tx1,ty1,tx2,ty2);
  }
  
  // x 座標轉換
  private int transX(int x) {
    return x*space;
  }
  
  // y 座標轉換
  private int transY(int y) {
    return EDGE_LENGTH-y*space-1;
  }
  
  // 點 
  private static class Vertex {
    public int x;
    public int y;
    
    public Vertex(int x, int y) {
      this.x = x;
      this.y = y;
    }
    
    @Override
    public String toString() {
      return String.format("(%d,%d)",x,y);
    }
  }
  
  /**
   * 計算多邊形
   * 
   * @return 多邊形點集合
   */
  public static 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);
    
    // 往左找斜率最大的點 (一樣大的斜率取距離最長的點)
    // 1. 定義起始斜率 (無限大)
    // 2. 測試左邊所有的點
    //    a. 先計算斜率, 篩選斜率比起始斜率小的 (斜率遞減)
    //    b. 在這些點裡面取斜率最大的, 若斜率相同取距離最長的
    //    c. 最佳的點為多邊形的下一個點
    // 3. 找到的斜率作為下次的起始斜率
    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);
            //System.out.print(v);
            //System.out.printf(" mt=%d/%d mc=%d/%d ms=%d/%d",dyt,dxt,dyc,dxc,dys,dxs);
            //System.out.printf(" scmp2=%d\n",scmp);
            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;
    }
    
    // 往右找斜率最大的點 (一樣大的斜率取距離最長的點)
    // 1. 定義起始斜率 (無限大)
    // 2. 測試右邊所有的點
    //    a. 先計算斜率, 篩選斜率比起始斜率小的 (斜率遞減)
    //    b. 在這些點裡面取斜率最大的, 若斜率相同取距離最長的
    //    c. 最佳的點為多邊形的下一個點
    // 3. 找到的斜率作為下次的起始斜率
    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;
  }
  
  /**
   * 比較兩斜率的大小, 以分數形式處理無限的問題
   *   m2 = dy1/dx1
   *   m1 = dy2/dx2
   * 
   * @param dy2 第2組斜率的y差值
   * @param dx2 第2組斜率的x差值
   * @param dy1 第1組斜率的y差值
   * @param dx1 第1組斜率的x差值
   * 
   * @return m2>m1傳回1, m2=m1傳回0, m2<m1傳回-1
   */
  public static 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; // m1 無限大或無限小
        } else {
          return dy1>=0 ? -1 : 1; // m2 無限大或無限小
        }
      } else {
        // 兩個數都是無限大或無限小
        if(dy2>=0) {
          return dy1>=0 ? 0 : 1;  // m1 無限大
        } else {
          return dy1>=0 ? -1 : 0; // m1 無限小
        }
      }
    }
  }
  
  // 啟動點
  public static void main(String[] args) {
    final JFrame f = new JFrame("Convex Hull 演算法");
    f.setContentPane(new ConvexHullSwing());
    f.setSize(500,420);
    f.setVisible(true);
    f.addWindowListener(new WindowAdapter() {
      @Override
      public void windowClosing(WindowEvent e) {
        f.dispose();
      }
    });
  }
 
}


reply to postreply to post
話題樹型展開
人氣 標題 作者 字數 發文時間
4777 Convex Hull (凸包) 演算法 Swing 解說版 秒殺 7272 2010-04-15 11:04
» JWorld@TW »  Java 技巧文件 » Java與演算法

reply to postflat modego to previous topicgo to next topic
  已讀文章
  新的文章
  被刪除的文章
Jump to the top of page

JWorld@TW 本站商標資訊

Powered by Powerful JuteForum® Version Jute 1.5.8