演算法 Term Project 實施要點

每個同學以Voronoi diagram 為題目，將 課本的Voronoi diagram 演算法撰寫程式，加以測試分析。若能改良演算法，則更佳。最後需繳交一份完整成果報告

題目：

全部同學均撰寫課本的Voronoi diagram 演算法

實施時程：

1. 2024年11月11日~11月15日：進行初步測試，查驗初步成果
2. 2024年12月2日~12月8日：進行完整測試，查驗最後成果
3. 2024年12月15日：繳交報告
4. 進行測試時，請至EC5013找助教進行測試。測試為每日之 10:00~ 19:00。

程式介面與輸出入規格：

1. 演算法須為課本之divide-and-conquer 方法。
2. 操作介面須為視窗介面，畫布大小至少為 600 x 600。
3. 有兩種執行模式 「Run」 與 「Step by step」，功能與 C++ / Java 的編譯器 IDE 類似。按下 「Step by step 」按鈕時，每次 merge 之前暫停，並以不同顏色畫出左右兩個Voronoi diagram ；按下「Run 」按鈕時，從當時的狀態(可能已經執行過數次「Step by step」)執行至最後，並將最終結果畫出。
4. 除了在視窗介面上，用滑鼠直接點出輸入點之外，程式必須能夠讀入「輸入文字檔案」，以便讀取測試資料。
   測試用的輸入文字檔案有統一格式，請按此    
   （下載測試資料文字檔，含有註解) 
   （下載測試資料文字檔，不含註解)         助教另有未公開之測試資料(格式相同)
5. 除了在視窗介面上，畫出Voronoi diagram 圖形外，程式必須能夠執行結果儲存為「輸出文字檔案」 (非圖檔)，其中包含輸入點的座標，與執行結果的所有線段。若為射線，則只需計算到畫布的邊界。輸出文字檔格式如下：
   
   輸入的座標點：P x y    // 每個點佔一行，兩整數 x, y 為座標。
   線段：E x1 y1 x2 y2      // (x1, y1) 為起點，(x2, y2) 為終點，其中 x1≦x2 或 x1=x2, y1≦y2
   座標點排列在前半段，線段排列在後半段。座標點以 lexical order順序排列（即先排序第一維座標，若相同，則再排序第二維座標；線段亦以 lexical order順序排列。
   
   輸出文字檔案範例：

   P 103 200 P 193 64 P 193 370 P 283 200 E 0 34 193 161 E 0 363 193 261 E 193 161 193 261 E 193 161 437 0 E 193 261 600 476

   線段的 lexical order (字典序)：
   5.1  線段E x1 y1 x2 y2，座標須滿足x1≦x2 或 x1=x2, y1≦y2。
   5.2 不同線段之間，依照x1, y1, x2, y2的順序進行排序(字典序)。以上述輸出文字檔案為例，比較x1時，因為0<193，x1為0的2條線段放前面，並繼續比較y1；後3條線段亦同理。

6. 顯示介面，除了可以畫出程式自己計算的Voronoi diagram 圖形外，也必須能夠讀入「輸出文字檔案」，並顯示其圖形。 例如，讀入檔案A，顯示圖形A；讀入檔案B，顯示圖形B。
7. 除了操作介面與輸出入介面需正確外，核心程式（演算法）必須能以divide-and-conquer方式執行四點（含）以上（特例（如四點共線）以外的一般情況大部分可以執行），此 term project 才能得到及格以上的分數。

注意事項：

• 此題目之資料結構較複雜，需花心思好好設計，亦可參考下列書籍 

Atsuyuki Okabe,    Barry Boots,    Kokichi Sugihara,   Sung Nok Chiu
Spatial Tessellations : Concepts and Applications of Voronoi Diagrams
索書號   QA278.2 O36 1992
Sec. 4.2 Data Structure for Representing a Voronoi Diagram, pp.215~pp.223

Vornoi Diagram資料結構下載 (若需列印，請在印表機選擇「橫向列印」)

• 助教測試的電腦環境為Windows 10系統。建議使用的程式語言： C/C++、C#、Java、Python。 亦可使用其他語言，但必須確保執行檔可於助教的電腦上執行。
• 撰寫程式，不得抄襲他人或放置於網路上的程式。若經發現，本學期本課程以不及格論。(將以相似度比對軟體檢查程式之間的相似度，檢查範圍將包含以前學長修課繳交的程式)

成果與報告格式、繳交方式：

1. 繳交完整之Term Project，包含軟體原始碼、軟體與報告文件。
2. 軟體原始碼：

   2.1 「軟體原始碼」為所有與軟體相關之原始檔，如程式原始碼、專案檔、環境設定檔、編譯說明檔等檔案。助教將依提供之「軟體原始碼」重新編譯軟體，並驗證之。

   2.2   程式原始碼需註解「版權宣告」資訊，至少需提供學號、中英文姓名。

   2.3. 若軟體由多個程式原始碼（物件）所組成，請再提供一「程式原始碼合併檔」，將所有程式原始碼併入此一合併檔，各原始碼間需以合適且明顯之註解（如分隔符號與檔名）加以區隔。並需於檔頭註明版權宣告資訊、使用之程式語言與編譯環境資訊。

   2.4「程式原始碼合併檔」需與程式原始碼一致，助教將據此驗證是否有抄襲之行為。檔案第一行以你所使用語言的註解方式，加入 $LAN=X$ (其中X為你所使用之語言)。例如，使用C/C++語言則加入：

   // $LAN=C$ 或 /* $LAN=C$ */

   若使用JAVA語言，則則加入：

   // $LAN=JAVA$

3. 軟體：

   3.1 「軟體」需注意包裝過程並請自行驗證。助教將在乾淨的電腦執行軟體。若出現缺library等錯誤，軟體部份將無成績。

   3.2.請提供合適之軟體執行指引（如.bat檔）與簡單說明，例如以java開發者若未包裝為.jar檔，請提供.bat檔以利執行。若因執行參數或缺檔導致軟體無法執行，此部份將無成績。

4. 報告文件：

   4.1 報告文件以 html 檔案為主，製作成一個網頁。並請注意，網頁連結不要使用絕對位址（除非必要）。報告中若有圖片，請加以適當處理，以免檔案過大。

   4.2 報告文件為所有Term Project有關之資訊，至少需包含下列項目：

   • 題目、系級、姓名、學號
   • 軟體規格書：包含「輸出與輸入（資料）規格」、「功能規格與介面規格」、「軟體測試規劃書」與其他有利於軟體開發之規格。
   • 軟體說明：為軟體安裝與使用之說明，請提供安裝與使用時需特別注意之要點，以減少評分之障礙。
   • 程式設計：將演算法於程式設計中，需要使用的資料結構，所需注意的細節或特別的技巧，在此部分講述。如果演算法有改良之處，亦在此描述。
   • 軟體測試與實驗結果：軟體之測試報告。包含測試的環境、使用的電腦硬體系統（CPU型號、記憶體容量等）、作業系統、編譯器名稱及版本。然後列出測試數據。必須列出程式可以執行之範例數據（最好列出程式可以執行之極限數據）。如果有些情況無法執行，請列出可能原因及可能解決之道。並請提供測試時之「測試輸入檔」與「測試輸出檔」。
   • 結論與心得：說明所得結論、可以改良之處與心得等。
   • 附錄：請連結「程式原始碼合併檔」、「測試輸入檔」、「測試輸出檔」等與報告相關之資料。
5. 繳交成果與報告時，請將所有檔案（程式原始碼、執行檔、自己測試用的輸入文字檔案、輸出文字檔案、報告）壓縮成一個 zip 或 rar 檔案。每一個「文件」檔案與「程式原始碼合併檔」均以自己的學號為檔名。壓縮檔以 不超過5MB為原則。

6. 將上述壓縮檔繳交至網路大學本課程

註：本要點若有未盡事宜，將在本課程網頁上修改之。