# 科展 <5G 路由器最佳化安置區>

# 壹、簡介
## 一、摘要
現今火熱的 5G 雖然是目前最厲害的 wifi ，但卻也有著非常明顯的缺點──
有效半徑太小，本作品中，我將要研究如何讓 5G 路由器放置在最佳的位置，透
過程式語言(C++)以及 Python 來算出最佳位置以及繪製出完整的示意圖。
本作品對於現今的 5G 半徑小的缺點進行最大化效益，並且研究如何在一堆點中，在 5G 的半徑範圍有限的狀況下，找出圓心且在能涵括最多的點。我用 C++
隨機生成 200 個點，再輸入直徑，找出最大群體，且此群體彼此之間的距離不大
於直徑。再透過最小圓覆蓋的方式最終找出圓心。再利用 ZMQ 傳送給 Python，利用 Python + openCV 繪製算出來的答案，方便觀察不過此效率不佳，時間複雜度在 O(n^3)，所以之後繼續研究如何優化此效率。

## 二、研究動機
隨著 5G 時代來臨，同學們也越來越多人更換 5G。老師在課堂上有說到「如果我要換 5G 的話，需要看一下我家那邊收訊好不好」，引起我的好奇心，查了一下才發現 5G 的路由器一般有效距離在 20 公尺至 30 公尺，如果要放置在公司這種很大的環境的話，想必需要不只一個路由器。於是本研究希望能夠研究出如何擺置能夠使其最佳化，節省不必要的浪費。

## 三、研究目的
本研究期望能最佳化 5G 路由器的放置位置，首先利用 C++以及演算法來找出路由器應該在的位置，再用 Python 搭配 openCV 來繪製出完整的地圖包含路由器的範圍和每個點的位置。最後希望能優化其效率，找出較快的方式來找出路由器應該的位置。並有機會應用在生活或軍事方面

# 貳、研究方法
## 一、研究器材
- 電腦 i7-10750H-CPU-8.00 GB，6 核 12 緒
- Visual Studio Code-1.65(編譯器)
- GCC 4.9.2 64-bit（c 語言）
- Python 3.9.10 (Python 版本)
- openCV-4.5.5 (繪圖程式版本)

## 二、討論環境定義
1. 賦予 n 個座標 P(X,Y)，並且 n=200
2. 座標 P(X,Y)，200<=X,Y<=400，並且為整數，方便繪圖
3. 5G 有效範圍 R，R >= 0

## 三、先備知識

### 最小圓覆蓋 (Smallest Enclosing Circle)
1. 定義:
平面上給定 n 個點，其中能包覆所有點以及使半徑最小的圓最小覆蓋圓
可使用 Randomized Incremental Construction 演算法在 O(n)時間內求得。演算法的想法是，從一個點 (半徑為 0 的圓) 出發，每次多考慮一個新的點時，伺機調整圓的半徑與圓心，使其成為能夠容納當前所有點的最小覆蓋
圓。

2. 性質：
性質一：最小覆蓋圓維一存在
反證法：假設存在兩個最小覆蓋圓 c1 跟 c2 皆包含點 p[1..n]。由於 c1 跟c2 包含相同的點群，該點群必存在於兩圓 的交集區域上。我們可以利用該交集區域製作出一個半徑更小的 c3 依然包含 p[1..n]，這導致 c1 跟 c2不是最小覆蓋 圓，與假設矛盾。所以最小覆蓋圓是唯一的。
性質二：最小覆蓋圓的邊界上至少有兩個點，且任兩點之間的弧必小於 180度。

證明：先建構一個包含所有點的圓，然後逐漸縮小到無可再小。根據性質一，這個無可再小的圓就是最小覆蓋圓。
1. 如果邊界上沒有點，可以縮小圓的半徑，直到邊界撞上一個點8
(見左下圖點 H)。
2. 如果只有一個點在邊界，可以藉由讓圓心往該點移動而縮小圓半徑 ，直到撞上第二點。(見右下圖圓心 A 往點 H 移動)。
3. 如果邊界上有兩個點，此兩點必需在圓直徑的兩端(兩極) 。否則可以藉由讓圓心向兩點的中點移動以縮小半徑，直到兩點處於兩極，或是邊界撞上第三點。
4. 如果圓上有多於等於三個點，但是存在弧大於 180 度，那可以藉由讓圓心向弧相反方向移動來縮小半徑，直到這個弧小於 180 度，或是撞上其它點把弧切斷。

## 四、實驗：路由器最佳位置(過程與結果)
### (一)實驗流程圖
主要就三個步驟+最後繪圖：

### (二)隨機產生 200 個點
丟入make_rand()取得隨機產生200個座標點(數值200~400間)
Python 繪圖如圖所示：

### (三)找出最大群體且彼此間距離小於直徑
我先把所有的點，只要彼此間小於直徑就存取起來，並且存放在g_map 以及 g_check，g_map 代表存放 i 點的所有有效點

g_check 是為了在找尋 i 點是否跟目前的點距離小於直徑而存放，不然每一次都要在算一次距離很浪費。g_map 則是在找到 i 點為有效點之後，找出 i 點的所有有效點，利用 DFS 的方式繼續找尋下一個。

為了找尋最大群體，我定義了 member 以及 endmember，分別代表暫時找尋群體，以及目前最大群體

之後 200 個點跑迴圈，假設目前的點為群體中的點，在進行推算，筆者
使用的方法是 DFS 深度優先搜尋，建立一個回傳 int 的函數 find_big_round()，
10把點丟進去此函數進行判斷，在去尋找此點的所有有效點是否和目前的暫時群體彼此間距離小於直徑，如果是就把那個點加入群體，最後回傳暫時群體大小。

#### (三) - 測試結果：
因為點的座標 x,y 落在 200~400 間，所以兩點之間最遠的距離為 200√2所以假設直徑為 500，500>200√2，所以理論上全部點都在群體內。

如果直徑為 20：

如果直徑為 0，代表一個點：

以上測試結果，確認每個點彼此間的距離確實落在其直徑範圍內，下一步就是把這些點用圓來包起來，就能夠找到最後的結果了。

### (四) 找尋最大群體的圓心
目的是將剛剛的最大群體，用最小覆蓋圓的方式找出其圓心。主要的方式就
是利用最小圓覆蓋的性質 1 及性質 2，最小圓唯一以及如果點>=3 的話，就
是 3 個點以上在圓周上。如果找尋的點在圓周外，則代表圓應該要在擴大。
例如圖 14 上的 F 點在外圈上 S，所以假設 FAB 點在圓周上，發現還有 D 點
在外面，所以再假設 D 點在圓周上，沒有任何點在外面，最小覆蓋圓就得
到了。

程式碼執行如下:
P[x]存放 pair<double,double>的最大群體的所有座標點。Judge 是判斷是否在
圓外。而最後找到圓周上的點後，再利用三點做圓的方式求出圓心。

#### (四) - 測試結果
假設有效半徑為 30，最大母群體算出來 14 個點，可以看出果然最小覆蓋圓
的半徑小於有效半徑。

假設有效半徑為 250，代表所有點都要都是最大群體，可以看出雖然半徑賦
予 250，但是真正卻不需要這麼多。

假設點只有兩個，(0,0)以及(10,10)

以上這些測試可以看出算出圓心座標以及半徑是沒問題的，那怕座標只有兩
個也能準確算出來。

### (四) Python 繪圖
利用 ZMQ 的方式把結果傳到 python，總共會傳送三個東西：原本的 200
個點座標，最大群體的座標，以及最後算出的圓心和半徑。而因為最後算出
來的圓心為小數點，但是圖片像素只有整數，所以四捨五入。

在 Python 收到三組座標後，利用 numpy 建立全白圖片，再利用 openCV 中的 cv2.circle 把傳入的點賦予黑色

## 實驗結果

1. 200 個座標點
2. 找到解為 直徑 30，最大群體 10 個

3. python將群體中的 10 個點換成紅色

4. 把最小覆蓋圓算出來的圓心座標繪製成圓

## 附錄
### 凸包:
##### 演算法 :
包裹法（Jarvis步進法）
時間複雜度為O(kn)。

葛立恆（Graham）掃描法 O(nlogn) 缺點是不能推廣到二維以上的情況

單調鏈 時間複雜度O(nlogn)

分治法 時間複雜度O(nlogn)

快包法 時間複雜度O(nlogn~n^2)

### 包裹法

#include <iostream>
#include <algorithm>
using namespace std;

static const auto Initialize = [] {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	return nullptr;
}();

struct point {
	int x, y;

	bool operator<(const point& other) {
		if (this->x != other.x)
			return this->x < other.x;
		return this->y < other.y;
	}

} points[200000], convex[200005];

inline long long CrossProduct(point center, point a, point b) {
	return (long long)(a.x - center.x) * (long long)(b.y - center.y) - (long long)(a.y - center.y) * (long long)(b.x - center.x);
}

void FindConvexHull(int pointAmount, int &convexSize) {
	for (int i = 0; i < pointAmount; ++i) {
		while (convexSize >= 2 && CrossProduct(convex[convexSize - 2], convex[convexSize - 1], points[i]) < 0)
			--convexSize;
		convex[convexSize] = points[i];
		++convexSize;
	}
	for (int i = pointAmount - 2, j = convexSize + 1; i >= 0; --i) {
		while (convexSize >= j && CrossProduct(convex[convexSize - 2], convex[convexSize - 1], points[i]) < 0)
			--convexSize;
		convex[convexSize] = points[i];
		++convexSize;
	}
	--convexSize;
}

int main() {
	int pointAmount, convexSize = 0;
	cin >> pointAmount;
	for (int i = 0; i < pointAmount; ++i)
		cin >> points[i].x >> points[i].y;
	sort(points, points + pointAmount);
	FindConvexHull(pointAmount, convexSize);
	sort(convex, convex + convexSize);
	cout << convexSize << '\n';
	for (int i = 0; i < convexSize; ++i)
		cout << convex[i].x << ' ' << convex[i].y << '\n';
}

###### tags: `旺宏`
{%hackmd aPqG0f7uS3CSdeXvHSYQKQ %}