/Convex-hull-Algorithm

NUU CSIE Junior Algorithm Homework 1 in Home Teaching

Primary LanguageC++

Convex hull Algorithm

NUU CSIE Junior Algorithm Homework 1 in Home Teaching

JS

程式碼

  • 搭配網頁製作，將js寫在html裡面。
  • 程式碼如上面的js的資料夾裡的graphforjs.html所示。

課堂練習1

  • 現在有個問題，最高點計算凸包後都會消失 你的目標將會是，解決這個問題。

  • 參考解法：

  1. 在排序時，除了按照與起點的角度排序，如果角度相同（即點共線），則應該按照與起點的距離進行進一步排序。
  2. 在構建凸包的循環中，當遇到共線的情況，你應該繼續彈出堆疊中與新點共線的點。
  • 修改點應包括：
  1. 極角相同的點按與起點的距離進行排序，最遠的點排在前面。
  2. 在構建凸包的過程中，當新的點和堆疊頂端的兩點共線時，我們將繼續彈出堆疊頂部的點，直到發現一個有效的左轉為止。 這樣可以保證所有共線點中最遠的點被包括在凸包中。
  3. 堆疊初始只包含起點。

C++

程式碼與配置說明

  • 需要載這個CImg.h 會直接提供連結。

  • 打開dev-C++，並開新專案

  • 將cpp的資料夾裡的CImg.h 加入到專案

# include "CImg.h"

  • 點開cpp資料夾裡的main.cpp的程式碼並複製。

  • 接著點進工具，編譯選項。 在呼叫編譯器時打入以下的指令打以下的指令：

-O2 -lgdi32 -std=c++11
  • 按下編譯執行的按紐

課堂練習2

執行完後，你突然會發現雖然程式都沒問題，但似乎好像啥都沒有看到？ 你的任務就是，去解決這個問題。 提示：平移跟放大。

Python

程式碼說明

如同python資料夾的程式碼所示。

課堂練習3

老師似乎是希望你們手刻，所以你現在的任務就是用PYTHON 手刻 Convex Hull的函式。

程式碼在4.6的課堂講義那邊，會順便說明一下4.6當時上的其實不是分治，而是貪婪算法。