作者firingmoon (小天)
站內Prob_Solve
標題[問題] 多點到直線的距離
時間Sat May 16 22:46:44 2015
各位版友好
今天我有n個點,求每一個點到直線L的距離,最終找出其中一點
且此點到直線L的距離最長
直觀的來講我只需要做n次並用max函數即可
但我希望速度能夠更快
所以想請教各位是否有演算法可以加速計算此部分 謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 113.61.182.113
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1431787607.A.711.html
1F：→ yr: 那就邊做算把 max 存著，這樣快了一些 :p 05/17 00:16
2F：→ firingmoon: 這部分我有做了 05/17 00:19
3F：推 RealJack: 我認為距離公式有乘除又有根號,計算量很大 05/17 00:25
4F：→ RealJack: 如果先做convex hull再對外圍頂點做距離公式,取其最大值 05/17 00:26
5F：→ RealJack: 這樣應該會比較快,但或許有更好的方式啦 05/17 00:27
6F：→ EdisonX: 分母部份應該可以省掉，只要算分子。 05/17 00:27
7F：推 Leeng: 是不是只要求哪個點就好，距離的值不care?其他的點也不care 05/17 00:35
對 值不care 所以我沒有計算分母
let ax+b-y = 0
for (i=1,i<10000,i++)
{
dis = abs(a*xpoint[i]+b-ypoint[i])
if (dis>dismax)
{
dismax = dis
point = i <-------這是我的目的 想要找哪一個點
}
}
這是我的程式碼
不知道是否有任何地方可以讓他計算速度變更快
8F：→ Leeng: 那就每次只要算|ax+by+c|；比前一個小就discard 05/17 00:36
9F：→ Leeng: 後面根號那一坨根本就不用算，或最後取完點後，算一次就好 05/17 00:37
※ 編輯: firingmoon (113.61.182.113), 05/17/2015 01:07:32
10F：推 Leeng: 不能先排序吧 一排序就是NlogN 除非你在輸入資料的時候 05/17 01:09
11F：→ firingmoon: 抱歉 剛剛才想到排序這樣做不行Orz 05/17 01:09
12F：推 Leeng: 就先建好，不過那也是要N量級 05/17 01:11
13F：→ Leeng: 想到一個啦 假如取index[i]會耗時的話 就用指標++ .... 05/17 01:12
14F：→ Leeng: 不過你的data可能是文件讀進來的吧 那可能連陣列都不用存 05/17 01:14
15F：→ firingmoon: 不好意思 這部分我不太懂你的意思是指? 05/17 01:14
16F：→ Leeng: 邊讀就能邊算、邊discard 05/17 01:14
17F：→ Leeng: 是寫C/C++ ? 05/17 01:14
18F：→ firingmoon: 對 data是從文件讀進來,再丟去陣列 但這部分比較 05/17 01:14
19F：→ firingmoon: 不care 05/17 01:14
20F：→ firingmoon: 我是用C# 05/17 01:15
21F：→ azureblaze: 指標++和index[i]最佳化開下去是一樣的東西 05/17 01:15
22F：→ azureblaze: 我不認為有O(N)以下的方法 05/17 01:16
23F：→ azureblaze: 平行處理吧 分k組個別求最大，在比較各組冠軍 05/17 01:17
24F：→ azureblaze: 再來就你真的嫌太慢還是只是想做? 05/17 01:18
25F：→ azureblaze: 這種狀況讀檔可能比計算慢 05/17 01:19
26F：→ firingmoon: 讀檔的部分在時間上我可以不在意,我只在意計算距離 05/17 01:19
27F：→ firingmoon: 找點的部分 05/17 01:20
28F：→ firingmoon: 我只是想試著看看沒有更快的方式 05/17 01:20
29F：推 Leeng: 如果還有其他幾何可能的話，只能有請高斯了 05/17 01:20
30F：推 RealJack: 只求一次的話就直接算吧,也會對其他線求最大值那做個 05/17 01:25
31F：→ RealJack: convex hull,第二次會快很多 05/17 01:26
32F：→ azureblaze: 你的n個點有任何特殊性質嗎?像照著某種順序給? 05/17 01:31
33F：推 RealJack: 還有你的檔案是文字格式還是可直接序列化的二進制格式 05/17 01:31
34F：→ RealJack: 這兩者速度會差上數百倍 05/17 01:32
35F：→ firingmoon: 我的n個點是時間序列,沒有甚麼特別性質 05/17 01:49
36F：→ firingmoon: RealJack抱歉 不太懂你的意思 05/17 01:51
37F：→ EdisonX: (1) 對 10K 個點找最近,是只會做一次還是會重覆做 ? 05/17 01:54
38F：→ EdisonX: (2) 你的來源資料是你可以讀得懂的文字檔嗎 ? 05/17 01:54
39F：→ EdisonX: (3) n個點是時間序列沒錯,已知是2維,還有沒有特殊性質 ? 05/17 01:55
40F：→ EdisonX: 結果上述的問題。然後平行化+1. 05/17 01:55
41F：→ EdisonX: 抱歉修正一下, 是對 10K 個點找最遠 @@ 05/17 01:56
(1)只做一次
(2)讀得懂 基本上這部分不用太在意
(3)沒有特殊,單純就a[1],a[2],a[3].........
※ 編輯: firingmoon (113.61.182.113), 05/17/2015 02:01:33
42F：→ azureblaze: 改用C 平行處理 SIMD 能用的方法大概就這些 05/17 02:04
43F：推 LiloHuang: 這類問題很適合用 GLSL 或者 OpenCL 來做平行計算 05/17 15:10
45F：推 FRAXIS: 依照我的經驗 dis 的計算和 if condition 會造成 delay 05/17 21:45
46F：→ FRAXIS: 你可以手動用類似 software pipeling 的方法加快一點 05/17 21:46
47F：→ FRAXIS: 你可以試著用 profiling tool 去觀察每個 instruction 05/17 21:47
48F：→ FRAXIS: 的時間 然後再思考怎麼改進 05/17 21:47
49F：→ FRAXIS: 你的問題 O(n) 的時間是不能避免的了 但是或許可以減少 05/17 21:48
50F：→ FRAXIS: outer loop 呼叫這 function 的次數.. 05/17 21:48
51F：→ firingmoon: 感謝各位版友的幫助 我會試著你們給的建議測試看看 05/18 10:39
52F：→ sulf: 矩陣旋轉，把直線當成新X軸，只要計算新的y座標比較 11/13 12:01