圍凸包(Convex Hull)

泰勞最近在做一件無聊的事，就是把座標上所有的點，沿著最外圍連成一個多邊形，多邊形內部必須包含所有剩餘的點，同時內部任意兩點的連線不會經過圖形外部，這樣的圖形稱為凸殼(Convex Hull)，也有人稱為凸包。

參考資料：
[演算法筆記]Convex Hull
[Wiki]Algorithm Implementation/Geometry/Convex hull/Monotone chain 

泰勞參考了上方網頁的介紹，選了一個自己「喜歡」的方式來實作，代表這絕對「不是最佳解法」，只是其中一個可以解決此問題的方法。如果你有特別的點子，歡迎在下方留言討論，讓泰勞長長知識喔！

泰勞主要參考了 Andrew's Monotone Chain，詳細定義請看上方參考資料，大致上的流程如下所示：
1.將所有點依 X 座標由左至右，再依 Y 座標由下而上排序
2.從最左下方的點開始尋找下半部的凸殼，直到最右上方
3.從最右上方的點開始尋找上半部的凸殼，直到最左下方

下圖是 WikiBooks 提供的 Gif 圖檔，這樣應該比較容易理解。

從程式的角度切入，我們必須先準備兩個物件：點(Node)和線(Line)，先來定義這兩個物件所需的內容。

Node類別，包含整數 x 和整數 y，代表座標 (x,y)。

class Node{
    private int x;
    private int y;
    //Setter and Getter
    public void setX(int x){
      this.x = x;
    }
    public void setY(int y){
      this.y = y;
    }
    public int getX(){
      return this.x;
    }
    public int getY(){
      return this.y;
    }
} 

Line類別，包含兩個 Node 物件，代表線的兩個端點。

class Line{
    private Node node1;
    private Node node2;
    //Setter and Getter
    public void setNodeOne(Node one){
      this.node1 = one;
    }
    public void setNodeTwo(Node two){
      this.node2 = two;
    }
    public Node getNodeOne(){
      return this.node1;
    }
    public Node getNodeTwo(){
      return this.node2;
    }
}

接著宣告一個 Node 陣列，並且初始化這些 Node 資料，我們先把座標範圍設定在 1~100 之間，方便做測試。

private void initNodes(Node[] nodes){
    for(int i = 0; i < nodes.length; i++){
      nodes[i] = new Node();
      nodes[i].setX((int)(Math.random()*100+1));
      nodes[i].setY((int)(Math.random()*100+1));
    }
}

依照上述步驟，必須先將這些 Node 依 X 座標由左至右並且依 Y 座標由下而上排序。排序之後的 Node 陣列，第 0 個 Index 就會是最左下方的點，最後一個 Index 就會是最右上方的點囉！

private void sortNodes(Node[] nodes){
    //For Andrew's Monotone Chain
    //Sort from left to right and from bottom to top
    for(int i = 0; i < nodes.length; i++){
      for(int j = i+1; j < nodes.length; j++){
        if(nodes[j].getX() < nodes[i].getX()){
          swap(nodes, i, j);
        }else if(nodes[j].getX() == nodes[i].getX()){
          if(nodes[j].getY() < nodes[i].getY()){
            swap(nodes, i, j);
          }
        }
      }
    }
}

再來就要進入圍凸殼最核心的階段，從最左下方的點開始尋找下半部的凸殼，直到最右上方。如何知道連接哪一個點才會符合凸殼呢？判斷的依據是斜率，每一次向最右上方走的過程，找出斜率最小的點連接，同時將這些在凸殼上的點儲存在 ArrayList 裡，方便最後印出完整的結果。

private void findLowerHull(Node[] nodes, ArrayList<Node> convexList){
    //From left to right ==> Lower Hull
    int nextIndex = 0;
    do{
      float minSlope = 101;
      int mainIndex = nextIndex;
      for(int i = nextIndex; i < nodes.length-1; i++){
        float tmpSlope = getSlope(nodes[mainIndex], nodes[i+1]);
        if(tmpSlope < minSlope){
          minSlope = tmpSlope;
          nextIndex = i+1;
        }
      }
      //Store each next node in ArrayList
      convexList.add(nodes[nextIndex]);
    }while(nextIndex < nodes.length-1);
}

上半部的凸殼從最右上方(陣列的最後一個 Index)開始往左下方(陣列的第 0 個 Index)走，一樣判斷最小斜率依序找出 next node。

private void findUpperHull(Node[] nodes, ArrayList<Node> convexList){
    //From right to left ==> Upper Hull
    int nextIndex = nodes.length-1;
    do{
      float minSlope = 101;
      int mainIndex = nextIndex;
      for(int i = nextIndex; i > 0; i--){
        float tmpSlope = slope(nodes[mainIndex], nodes[i-1]);
        if(tmpSlope < minSlope){
          minSlope = tmpSlope;
          nextIndex = i-1;
        }
      }
      //Store each next node in ArrayList
      convexList.add(nodes[nextIndex]);
    }while(nextIndex > 0);
}

到這邊算是完成圍凸殼的任務了，接下來只需要將 convexList 裡面儲存的點，用稍早定義的 Line 類別依序轉成線，並存到一個 ArrayList 裡面。

private void nodeToConvex(ArrayList<Node> convexList, ArrayList<Line> lineList){
    for(int i = 0; i < convexList.size()-1; i++){
      Line line = new Line();
      line.setNodeOne(convexList.get(i));
      line.setNodeTwo(convexList.get(i+1));
      lineList.add(line);
    }
}

最後只要將 lineList 裡面的資料打印出來，就可以看見最終結果囉！

GitHub:
https://github.com/Kuanlin-Chen/Practice/tree/master/ConvexHull