如何計算某一個座標點方圓N公里範圍？ (第3頁)

Wei_1144
個人積分：540分
文章編號：8307549

540分

21樓

2008-09-26 21:06

Haily wrote:
不知道兄臺有沒有研究過航跡包圍成的面積計算? 雖然很少人用, 但是拿來測量面積也不錯......(恕刪)

沒有耶，不過剛剛在網路上找到一個公式
http://blog.blueshop.com.tw/alexchen/archive/2004/11/03/677.aspx
這個也是一種解法，不過需要先轉成平面座標

另外，如果把多邊行視為多個三角形的組合，是可以把每個三角形的面積加起來就好了
而每個三角形的面積可以由三邊長求得，每個邊長又可以由上面幾樓所提到的測距公式算出，也就不需要先轉換成平面座標

不過我沒有做過啦，空想而已，數學不是我的強項

這種應用是很有趣的問題，上學術網應該有很多很棒的演算法

以前逛B&Q，看到有雷射測量儀器，不但可以量距離，還可以測房間的面積、體積，很神，應該也是這類演算法的應用吧

besthand

besthand
個人積分：0分
文章編號：8325586

0分

樓主

2008-09-28 3:09

謝謝各位大大的鼎力相助，我目前已經在網路上找到計算兩個坐標點之間的距離公式(已有考量所在地區的差異)，不過仍然不曉得如何反求回第二個座標點>"<

millerliu大提供的軟體很好用，可是我需要自己寫程式去計算那些東西，所以算法上我還是需要自己寫的...

硬是要學：http://www.soft4fun.net

millerliu

millerliu
個人積分：339分
文章編號：8329726

339分

23樓

2008-09-28 12:53

besthand wrote:
millerliu大提供的軟體很好用，可是我需要自己寫程式去計算那些東西，所以算法上我還是需要自己寫的......(恕刪)

PCTrans當作是驗證你自己寫的程式計算有無問題用吧, 該程式是荷蘭海軍部的, 精確性不會有問題的, 加油!!

Wei_1144

Wei_1144
個人積分：540分
文章編號：8331361

540分

24樓

2008-09-28 14:39

besthand wrote:
我目前已經在網路上找到計算兩個坐標點之間的距離公式(已有考量所在地區的差異)，不過仍然不曉得如何反求回第二個座標點...(恕刪)

應該不難吧，不過不知道你拿到的是什麼樣的公式，先深入了解原來公式的原理，才有辦法修改

或許你可以先說說看你對這個公式的了解，才能知道癥結在哪裡

millerliu

millerliu
個人積分：339分
文章編號：8334484

339分

25樓

2008-09-28 17:53

Wei_1144 wrote:
應該不難吧，不過不知...(恕刪)

http://www.navdog.com.tw/topic_detail.php?b_id=6&m_id=448有公式.

besthand

besthand
個人積分：0分
文章編號：8336357

0分

樓主

2008-09-28 19:47

Wei_1144 wrote:
應該不難吧，不過不知...(恕刪)

目前我所找到的公式應該是各種算法裡面較為精確的，目前我也已經用Java實做這個公式了：

r = t * acos( ( sin(lat1) * sin(lat2) + cos(lat1) * cos(lat2) * cos(lon2 - lon1)) )
where t = 6378.7

目前我的假設是已知distance、lat1、以及lon1，要求lat2及lon2。從這個式子看來，lat2及lon2的有無限多個解，如果要算的話似乎是算不完的，因此我從另外一個方向進行思考，先來個示意圖：

紅色的點是我假設現在的所在位置，首先要先計算出四個藍色(菱形)的點的座標，這四個點正好位於紅點的東、西、南、北方，接著再由這四個點計算出兩個對角線(綠三角)的座標，這樣就能框選出在這個範圍內所有的點。因為方型範圍內有些點是超出圓的涵蓋範圍，因此最後再將所有取出來的點一一與紅圓點進行距離的運算，如果距離大於r的話即表示超出範圍，便不列入選取範圍之內。

計算出四個藍色(菱形)的點的座標....就是我現在碰到的問題囉~~

硬是要學：http://www.soft4fun.net

Wei_1144

Wei_1144
個人積分：540分
文章編號：8351348

540分

27樓

2008-09-29 16:36

besthand wrote:
計算出四個藍色(菱形)的點的座標....就是我現在碰到的問題囉...(恕刪)

不懂耶，如果是要計算求出任一個藍色菱形的座標，未知數只有一個，簡單的代數，會有什麼問題?

不過如果航點超多的時候呢? 還要一個一個算效能會不會不理想?

我覺得導航機中的運算效能很高，表示應該有更好的演算法可以解決這類問題，好的演算法真是有趣啊

Haily

Haily
個人積分：3487分
文章編號：8362879

3487分

28樓

2008-09-30 9:55

我個人的猜測是: besthand 想實作導航時搜尋附近點的功能
所以應該要先求出以r為半徑的距離最大及最小的經緯度
再利用這組經緯度去過濾POI資料庫
此時得到的是方形的範圍所有的POI
再用距離公式計算所有的POI, 並顯示POI以及距離.
這樣的方法搜尋可能速度比較快

Wei_1144

Wei_1144
個人積分：540分
文章編號：8364500

540分

29樓

2008-09-30 11:40

Wei_1144 wrote:
我覺得導航機中的運算效能很高，表示應該有更好的演算法可以解決這類問題，好的演算法真是有趣啊...(恕刪)

舉個例子來說:

求距離 O點 r公尺內的所有航點
1. 求出以r為半徑的距離之最大及最小的經緯度
2. 再利用這組經緯度去過濾POI資料庫，此時得到的是方形A的範圍內所有的POI，我們稱為Set A
3. 求出以 (r / 2^0.5) 為半徑的距離之最大及最小的經緯度
4. 再利用這組經緯度去過濾Set A 之內的POI，此時得到的是方形B的範圍內所有的POI，我們稱為Set B
5. SetB 必定包含於 Set A，假設 Set A = Set B + Set C
6. 再用距離公式計算所有Set C 之內的POI，檢出與O點距離小於等於r的POI，我們稱為 Set D

Set B + Set D 即為所求

以O點為圓心，r為半徑的圓我們稱為圓O
方形A切圓O
方形B在圓O的裡面四個角剛好頂住圓O

這樣會更快，因為省下對Set B之內的POI計算距離的時間，
不過我想導航機中的演算法會更好一點，而且我猜很可能跟以上的演算法完全不相同...永遠都有更好的演算法

離題一下，一定要以圓形來劃分嗎? 正方形來區分也很好呀，也比較符合一般地圖介面的形狀啊

Wei_1144

Wei_1144
個人積分：540分
文章編號：8392578

540分

30樓

2008-10-01 23:28

Wei_1144 wrote:
舉個例子來說:求距離...(恕刪)

啊，我又想到一個更快的演算法

半徑為r的圓外面，其實可以試著用很多矩形來覆蓋圓的面積，如下圖

只要求出每個矩形的經緯度極值，再篩選POI，再求聯集即為所求

只要矩形分得夠細，誤差是很小的，容許多少誤差，就看取捨啦

這樣連計算距離都不用了，一定很快

例圖: 這是每隔兩度就劃一個矩形