102-2 PDSA HW4

HW4要讓大家畫畫圖，應該會很有趣!

1. 利用二維座標畫點

[goal]：利用StdRandom產生N個2D points (用Point2D的array來儲存)，再搭配StdDraw把這個N個點畫出來(radius= 0.01)

• 請大家練習使用Point2D這個物件，可以先宣告一個array來用

Point2D[] a = new Point2D[N];

• 利用for loop產生N個點的x,y座標：呼叫StdRandom.uniform();
• 練習用StdDraw畫圖 (把作者提供的StdDraw.java好好看看，有很多methods可以用來畫圖)，如：

StdDraw.filledCircle(a[i].x(), a[i].y(), 0.01);

• N=10的結果範例：

作者有幫大家寫一個存讀檔的功能：

按下File->Save，取檔名的時候加上合適的副檔名即可，如：e1.png

2. 將y座標最小的點用紅色標示

[goal]：練習使用compareTo，以及更換畫筆的顏色

• HW4的第二小題是要練習呼叫sort，請在Point2D物件中尋找合適的compareTo()或Comparator使用，目的是要找到y座標最小的點
• 改用紅色標示，可用StdDraw的setPenColor改顏色：

StdDraw.setPenColor(StdDraw.RED);

• 結果範例：

3. 將所有的點，用其與紅點的角度排序

[goal]：練習comparator的使用

• 參考作者投影片 p45-p47
• 輸出範例 (請注意此時的點編號，後續輸出繳交批改系統的時候，請用此時的點編號)

• 利用StdDraw.text()標數字的時候，可將y軸向上提高約0.03，避開黑點

4. 找出convex hull

• 參考作者投影片 p58, p59, p60, p61
• 畫圖範例

• 請將能產生上圖的程式(MyConvexHull.java)，繳交至ceiba
• MyConvexHull這個class的main function會從args[0]得到N，然後產生亂數 + 畫圖
• 上傳批改系統的MyConvexHull.java必須額外有以下function，這個function會吃進一個Point2D的陣列，回傳字串：0 1 2 4 7 9

public static String ConvexHullVertex(Point2D[] a) {}

Bonus

[goal]：Find the convex hull for each of the connected components (CC) in a set of N points

• 綠線：兩點之間的距離<0.1 (表示兩個點之間距離太窄，無法通過)
• 紅點：尋找convec hull時所用的p點 (y座標最小)
• 黑線：convex hull (只有CC內的點個數>=3的時候才需要找convex hull)