ProcessingでDelaunay分割（ジェネリクス対応篇）

昨日まで、Processing のプログラムは、プログラマの性善説に基づいて組んでいた。

つまり、function(ArrayList pointList) とかいうメソッドがあったら、それを使う側は、間違いなく引数に PVector オブジェクトが格納されたリストを渡してくるだろうと想定していたのだ。

万一にもおかしなものが渡された場合、ClassCastException や NullPointerException が throw されるので、それを catch するようにプログラムしてはいたけれど、やはりコレクションフレームワークに何が入れられてくるのか判らない事に対する気持ち悪さは拭えずにいた。

さてさて、そんなうららかな金曜日の昼下がり。暇だったので、Processing の最新版（1.5.1）を落として遊んでいたら、ある事に気付いた。

なんと、Processing の言語仕様がジェネリクスに対応しているではないか。

これなら、明示的に List や Map などのコレクションフレームワークに格納できる型を明示的に指定する事が可能である。

というわけで、昨日の Delaunay 分割のうち、コレクションフレームワークを駆使した DelaunayTriangles クラスを、新仕様に合わせて改訂してみた。それ以外のクラスについてはいじる必要なし。

---

DelaunayTriangles クラス

view plainprint?

1. class DelaunayTriangles {  
2.   public HashSet<Triangle> triangleSet;  // 三角形リスト  
3.   
4.   // ======================================  
5.   // コンストラクタ  
6.   // 与えられた点のリストを基にDelaunay分割を行う  
7.   // ======================================  
8.   public DelaunayTriangles(List<PVector> pointList) {  
9.     triangleSet = new HashSet<Triangle>();  
10.     DelaunayTriangulation(pointList);  
11.   }  
12.     
13.   // ======================================  
14.   // 点のリストを与えて、Delaunay三角分割を行う  
15.   // ======================================  
16.   public void DelaunayTriangulation(List<PVector> pointList) {  
17.     // 三角形リストを初期化  
18.     triangleSet.clear();  
19.       
20.     // 巨大な外部三角形をリストに追加  
21.     Triangle hugeTriangle = getHugeTriangle();  
22.     triangleSet.add(hugeTriangle);  
23.   
24.     try {  
25.       // --------------------------------------  
26.       // 点を逐次添加し、反復的に三角分割を行う  
27.       // --------------------------------------  
28.       for(Iterator pIter = pointList.iterator(); pIter.hasNext();) {  
29.         Object element = pIter.next();  
30.         Point p = element instanceof Point ?   
31.             (Point)element : new Point((PVector)element);  
32.           
33.         // --------------------------------------  
34.         // 追加候補の三角形を保持する一時ハッシュ  
35.         // --------------------------------------  
36.         // 追加候補の三角形のうち、「重複のないものだけ」を  
37.         // 三角形リストに新規追加する  
38.         //          → 重複管理のためのデータ構造  
39.         // tmpTriangleSet  
40.         //  - Key   : 三角形  
41.         //  - Value : 重複していないかどうか  
42.         //            - 重複していない : true  
43.         //            - 重複している   : false  
44.         // --------------------------------------  
45.         HashMap<Triangle, Boolean> tmpTriangleSet   
46.           = new HashMap<Triangle, Boolean>();  
47.   
48.         // --------------------------------------  
49.         // 現在の三角形リストから要素を一つずつ取り出して、  
50.         // 与えられた点が各々の三角形の外接円の中に含まれるかどうか判定  
51.         // --------------------------------------  
52.         for(Iterator tIter=triangleSet.iterator(); tIter.hasNext();){  
53.           // 三角形リストから三角形を取り出して…  
54.           Triangle t = (Triangle)tIter.next();  
55.                 
56.           // その外接円を求める。  
57.           Circle c = getCircumscribedCirclesOfTriangle(t);  
58.                 
59.           // --------------------------------------  
60.           // 追加された点が外接円内部に存在する場合、  
61.           // その外接円を持つ三角形をリストから除外し、  
62.           // 新たに分割し直す  
63.           // --------------------------------------  
64.           if (Point.dist(c.center, p) <= c.radius) {  
65.             // 新しい三角形を作り、一時ハッシュに入れる  
66.             addElementToRedundanciesMap(tmpTriangleSet,  
67.               new Triangle(p, t.p1, t.p2));  
68.             addElementToRedundanciesMap(tmpTriangleSet,  
69.               new Triangle(p, t.p2, t.p3));  
70.             addElementToRedundanciesMap(tmpTriangleSet,  
71.               new Triangle(p, t.p3, t.p1));  
72.               
73.             // 旧い三角形をリストから削除  
74.             tIter.remove();              
75.           }  
76.         }  
77.           
78.         // --------------------------------------  
79.         // 一時ハッシュのうち、重複のないものを三角形リストに追加   
80.         // --------------------------------------  
81.         for(Iterator tmpIter = tmpTriangleSet.entrySet().iterator();  
82.             tmpIter.hasNext();) {  
83.   
84.           Map.Entry entry = (Map.Entry)tmpIter.next();  
85.           Triangle t = (Triangle)entry.getKey();  
86.             
87.           boolean isUnique =   
88.               ((Boolean)entry.getValue()).booleanValue();  
89.   
90.           if(isUnique) {  
91.             triangleSet.add(t);  
92.           }  
93.         }  
94.       }  
95.         
96.       // 最後に、外部三角形の頂点を削除  
97.       for(Iterator tIter = triangleSet.iterator(); tIter.hasNext();){  
98.         // 三角形リストから三角形を取り出して  
99.         Triangle t = (Triangle)tIter.next();  
100.         // もし外部三角形の頂点を含む三角形があったら、それを削除  
101.         if(hugeTriangle.hasCommonPoints(t)) {  
102.           tIter.remove();  
103.         }  
104.       }  
105.     } catch (Exception ex) {  
106.       return;  
107.     }  
108.   }  
109.   
110.   // ======================================  
111.   // 描画  
112.   // ======================================  
113.   public void draw() {  
114.     for(Iterator it = triangleSet.iterator(); it.hasNext(); ) {  
115.       Triangle t = (Triangle)it.next();  
116.       t.draw();  
117.     }  
118.   }  
119.     
120.     
121.   // ======================================  
122.   // ※ ここからprivateメソッド  
123.   // ======================================  
124.     
125.     
126.   // ======================================  
127.   // 一時ハッシュを使って重複判定  
128.   // hashMap  
129.   //  - Key   : 三角形  
130.   //  - Value : 重複していないかどうか  
131.   //            - 重複していない : true  
132.   //            - 重複している   : false  
133.   // ======================================  
134.   private void addElementToRedundanciesMap  
135.       (HashMap<Triangle, Boolean> hashMap, Triangle t) {  
136.     if (hashMap.containsKey(t)) {  
137.       // 重複あり : Keyに対応する値にFalseをセット  
138.       hashMap.put(t, new Boolean(false));  
139.     } else {  
140.       // 重複なし : 新規追加し、  
141.       hashMap.put(t, new Boolean(true));  
142.     }  
143.   }  
144.     
145.   // ======================================  
146.   // 最初に必要な巨大三角形を求める  
147.   // ======================================  
148.   // 画面全体を包含する正三角形を求める  
149.   private Triangle getHugeTriangle() {  
150.     return getHugeTriangle(new PVector(0, 0),   
151.                            new PVector(width, height));      
152.   }  
153.   // 任意の矩形を包含する正三角形を求める  
154.   // 引数には矩形の左上座標および右下座標を与える  
155.   private Triangle getHugeTriangle(PVector start, PVector end) {  
156.     // start: 矩形の左上座標、  
157.     // end  : 矩形の右下座標…になるように  
158.     if(end.x < start.x) {  
159.       float tmp = start.x;  
160.       start.x = end.x;  
161.       end.x = tmp;  
162.     }  
163.     if(end.y < start.y) {  
164.       float tmp = start.y;  
165.       start.y = end.y;  
166.       end.y = tmp;  
167.     }  
168.       
169.     // 1) 与えられた矩形を包含する円を求める  
170.     //      円の中心 c = 矩形の中心  
171.     //      円の半径 r = |p - c| + ρ  
172.     //    ただし、pは与えられた矩形の任意の頂点  
173.     //    ρは任意の正数  
174.     Point center = new Point( (end.x - start.x) / 2.0,  
175.                               (end.y - start.y) / 2.0 );  
176.     float radius = Point.dist(center, start) + 1.0;  
177.       
178.     // 2) その円に外接する正三角形を求める  
179.     //    重心は、円の中心に等しい  
180.     //    一辺の長さは 2√3･r  
181.     float x1 = center.x - sqrt(3) * radius;  
182.     float y1 = center.y - radius;  
183.     Point p1 = new Point(x1, y1);  
184.       
185.     float x2 = center.x + sqrt(3) * radius;  
186.     float y2 = center.y - radius;  
187.     Point p2 = new Point(x2, y2);  
188.       
189.     float x3 = center.x;  
190.     float y3 = center.y + 2 * radius;  
191.     Point p3 = new Point(x3, y3);  
192.   
193.     return new Triangle(p1, p2, p3);      
194.   }  
195.     
196.   // ======================================  
197.   // 三角形を与えてその外接円を求める  
198.   // ======================================  
199.   private Circle getCircumscribedCirclesOfTriangle(Triangle t) {  
200.     // 三角形の各頂点座標を (x1, y1), (x2, y2), (x3, y3) とし、  
201.     // その外接円の中心座標を (x, y) とすると、  
202.     //     (x - x1) * (x - x1) + (y - y1) * (y - y1)  
203.     //   = (x - x2) * (x - x2) + (y - y2) * (y - y2)  
204.     //   = (x - x3) * (x - x3) + (y - y3) * (y - y3)  
205.     // より、以下の式が成り立つ  
206.     //  
207.     // x = { (y3 - y1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)  
208.     //     + (y1 - y2) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1)} / c  
209.     //  
210.     // y = { (x1 - x3) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)  
211.     //     + (x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1)} / c  
212.     //  
213.     // ただし、  
214.     //   c = 2 * {(x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)}  
215.       
216.     float x1 = t.p1.x;  
217.     float y1 = t.p1.y;  
218.     float x2 = t.p2.x;  
219.     float y2 = t.p2.y;  
220.     float x3 = t.p3.x;  
221.     float y3 = t.p3.y;  
222.       
223.     float c = 2.0 * ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1));  
224.     float x = ((y3 - y1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)  
225.              + (y1 - y2) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1))/c;  
226.     float y = ((x1 - x3) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)  
227.              + (x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1))/c;  
228.     Point center = new Point(x, y);  
229.       
230.     // 外接円の半径 r は、半径から三角形の任意の頂点までの距離に等しい  
231.     float r = Point.dist(center, t.p1);  
232.       
233.     return new Circle(center, r);  
234.   }  
235. }  

class DelaunayTriangles {
  public HashSet<Triangle> triangleSet;  // 三角形リスト

  // ======================================
  // コンストラクタ
  // 与えられた点のリストを基にDelaunay分割を行う
  // ======================================
  public DelaunayTriangles(List<PVector> pointList) {
    triangleSet = new HashSet<Triangle>();
    DelaunayTriangulation(pointList);
  }
  
  // ======================================
  // 点のリストを与えて、Delaunay三角分割を行う
  // ======================================
  public void DelaunayTriangulation(List<PVector> pointList) {
    // 三角形リストを初期化
    triangleSet.clear();
    
    // 巨大な外部三角形をリストに追加
    Triangle hugeTriangle = getHugeTriangle();
    triangleSet.add(hugeTriangle);

    try {
      // --------------------------------------
      // 点を逐次添加し、反復的に三角分割を行う
      // --------------------------------------
      for(Iterator pIter = pointList.iterator(); pIter.hasNext();) {
        Object element = pIter.next();
        Point p = element instanceof Point ? 
            (Point)element : new Point((PVector)element);
        
        // --------------------------------------
        // 追加候補の三角形を保持する一時ハッシュ
        // --------------------------------------
        // 追加候補の三角形のうち、「重複のないものだけ」を
        // 三角形リストに新規追加する
        //          → 重複管理のためのデータ構造
        // tmpTriangleSet
        //  - Key   : 三角形
        //  - Value : 重複していないかどうか
        //            - 重複していない : true
        //            - 重複している   : false
        // --------------------------------------
        HashMap<Triangle, Boolean> tmpTriangleSet 
          = new HashMap<Triangle, Boolean>();

        // --------------------------------------
        // 現在の三角形リストから要素を一つずつ取り出して、
        // 与えられた点が各々の三角形の外接円の中に含まれるかどうか判定
        // --------------------------------------
        for(Iterator tIter=triangleSet.iterator(); tIter.hasNext();){
          // 三角形リストから三角形を取り出して…
          Triangle t = (Triangle)tIter.next();
              
          // その外接円を求める。
          Circle c = getCircumscribedCirclesOfTriangle(t);
              
          // --------------------------------------
          // 追加された点が外接円内部に存在する場合、
          // その外接円を持つ三角形をリストから除外し、
          // 新たに分割し直す
          // --------------------------------------
          if (Point.dist(c.center, p) <= c.radius) {
            // 新しい三角形を作り、一時ハッシュに入れる
            addElementToRedundanciesMap(tmpTriangleSet,
              new Triangle(p, t.p1, t.p2));
            addElementToRedundanciesMap(tmpTriangleSet,
              new Triangle(p, t.p2, t.p3));
            addElementToRedundanciesMap(tmpTriangleSet,
              new Triangle(p, t.p3, t.p1));
            
            // 旧い三角形をリストから削除
            tIter.remove();            
          }
        }
        
        // --------------------------------------
        // 一時ハッシュのうち、重複のないものを三角形リストに追加 
        // --------------------------------------
        for(Iterator tmpIter = tmpTriangleSet.entrySet().iterator();
            tmpIter.hasNext();) {

          Map.Entry entry = (Map.Entry)tmpIter.next();
          Triangle t = (Triangle)entry.getKey();
          
          boolean isUnique = 
              ((Boolean)entry.getValue()).booleanValue();

          if(isUnique) {
            triangleSet.add(t);
          }
        }
      }
      
      // 最後に、外部三角形の頂点を削除
      for(Iterator tIter = triangleSet.iterator(); tIter.hasNext();){
        // 三角形リストから三角形を取り出して
        Triangle t = (Triangle)tIter.next();
        // もし外部三角形の頂点を含む三角形があったら、それを削除
        if(hugeTriangle.hasCommonPoints(t)) {
          tIter.remove();
        }
      }
    } catch (Exception ex) {
      return;
    }
  }

  // ======================================
  // 描画
  // ======================================
  public void draw() {
    for(Iterator it = triangleSet.iterator(); it.hasNext(); ) {
      Triangle t = (Triangle)it.next();
      t.draw();
    }
  }
  
  
  // ======================================
  // ※ ここからprivateメソッド
  // ======================================
  
  
  // ======================================
  // 一時ハッシュを使って重複判定
  // hashMap
  //  - Key   : 三角形
  //  - Value : 重複していないかどうか
  //            - 重複していない : true
  //            - 重複している   : false
  // ======================================
  private void addElementToRedundanciesMap
      (HashMap<Triangle, Boolean> hashMap, Triangle t) {
    if (hashMap.containsKey(t)) {
      // 重複あり : Keyに対応する値にFalseをセット
      hashMap.put(t, new Boolean(false));
    } else {
      // 重複なし : 新規追加し、
      hashMap.put(t, new Boolean(true));
    }
  }
  
  // ======================================
  // 最初に必要な巨大三角形を求める
  // ======================================
  // 画面全体を包含する正三角形を求める
  private Triangle getHugeTriangle() {
    return getHugeTriangle(new PVector(0, 0), 
                           new PVector(width, height));    
  }
  // 任意の矩形を包含する正三角形を求める
  // 引数には矩形の左上座標および右下座標を与える
  private Triangle getHugeTriangle(PVector start, PVector end) {
    // start: 矩形の左上座標、
    // end  : 矩形の右下座標…になるように
    if(end.x < start.x) {
      float tmp = start.x;
      start.x = end.x;
      end.x = tmp;
    }
    if(end.y < start.y) {
      float tmp = start.y;
      start.y = end.y;
      end.y = tmp;
    }
    
    // 1) 与えられた矩形を包含する円を求める
    //      円の中心 c = 矩形の中心
    //      円の半径 r = |p - c| + ρ
    //    ただし、pは与えられた矩形の任意の頂点
    //    ρは任意の正数
    Point center = new Point( (end.x - start.x) / 2.0,
                              (end.y - start.y) / 2.0 );
    float radius = Point.dist(center, start) + 1.0;
    
    // 2) その円に外接する正三角形を求める
    //    重心は、円の中心に等しい
    //    一辺の長さは 2√3･r
    float x1 = center.x - sqrt(3) * radius;
    float y1 = center.y - radius;
    Point p1 = new Point(x1, y1);
    
    float x2 = center.x + sqrt(3) * radius;
    float y2 = center.y - radius;
    Point p2 = new Point(x2, y2);
    
    float x3 = center.x;
    float y3 = center.y + 2 * radius;
    Point p3 = new Point(x3, y3);

    return new Triangle(p1, p2, p3);    
  }
  
  // ======================================
  // 三角形を与えてその外接円を求める
  // ======================================
  private Circle getCircumscribedCirclesOfTriangle(Triangle t) {
    // 三角形の各頂点座標を (x1, y1), (x2, y2), (x3, y3) とし、
    // その外接円の中心座標を (x, y) とすると、
    //     (x - x1) * (x - x1) + (y - y1) * (y - y1)
    //   = (x - x2) * (x - x2) + (y - y2) * (y - y2)
    //   = (x - x3) * (x - x3) + (y - y3) * (y - y3)
    // より、以下の式が成り立つ
    //
    // x = { (y3 - y1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)
    //     + (y1 - y2) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1)} / c
    //
    // y = { (x1 - x3) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)
    //     + (x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1)} / c
    //
    // ただし、
    //   c = 2 * {(x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)}
    
    float x1 = t.p1.x;
    float y1 = t.p1.y;
    float x2 = t.p2.x;
    float y2 = t.p2.y;
    float x3 = t.p3.x;
    float y3 = t.p3.y;
    
    float c = 2.0 * ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1));
    float x = ((y3 - y1) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)
             + (y1 - y2) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1))/c;
    float y = ((x1 - x3) * (x2 * x2 - x1 * x1 + y2 * y2 - y1 * y1)
             + (x2 - x1) * (x3 * x3 - x1 * x1 + y3 * y3 - y1 * y1))/c;
    Point center = new Point(x, y);
    
    // 外接円の半径 r は、半径から三角形の任意の頂点までの距離に等しい
    float r = Point.dist(center, t.p1);
    
    return new Circle(center, r);
  }
}