[問題] 多點到直線的距離

[firingmoon (小天)]

各位版友好

今天我有n個點,求每一個點到直線L的距離,最終找出其中一點

且此點到直線L的距離最長

直觀的來講我只需要做n次並用max函數即可

但我希望速度能夠更快

所以想請教各位是否有演算法可以加速計算此部分 謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 113.61.182.113
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1431787607.A.711.html
→ yr: 那就邊做算把 max 存著，這樣快了一些 :p
→ firingmoon: 這部分我有做了
推 RealJack: 我認為距離公式有乘除又有根號,計算量很大
→ RealJack: 如果先做convex hull再對外圍頂點做距離公式,取其最大值
→ RealJack: 這樣應該會比較快,但或許有更好的方式啦
→ EdisonX: 分母部份應該可以省掉，只要算分子。
推 Leeng: 是不是只要求哪個點就好，距離的值不care?其他的點也不care
對 值不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   <-------這是我的目的 想要找哪一個點
 }
}

這是我的程式碼

不知道是否有任何地方可以讓他計算速度變更快

→ Leeng: 那就每次只要算|ax+by+c|；比前一個小就discard
→ Leeng: 後面根號那一坨根本就不用算，或最後取完點後，算一次就好
※ 編輯: firingmoon (113.61.182.113), 05/17/2015 01:07:32
推 Leeng: 不能先排序吧 一排序就是NlogN 除非你在輸入資料的時候
→ firingmoon: 抱歉 剛剛才想到排序這樣做不行Orz
推 Leeng: 就先建好，不過那也是要N量級
→ Leeng: 想到一個啦 假如取index[i]會耗時的話 就用指標++ ....
→ Leeng: 不過你的data可能是文件讀進來的吧 那可能連陣列都不用存
→ firingmoon: 不好意思 這部分我不太懂你的意思是指?
→ Leeng: 邊讀就能邊算、邊discard
→ Leeng: 是寫C/C++ ?
→ firingmoon: 對 data是從文件讀進來,再丟去陣列 但這部分比較
→ firingmoon: 不care
→ firingmoon: 我是用C#
→ azureblaze: 指標++和index[i]最佳化開下去是一樣的東西
→ azureblaze: 我不認為有O(N)以下的方法
→ azureblaze: 平行處理吧 分k組個別求最大，在比較各組冠軍
→ azureblaze: 再來就你真的嫌太慢還是只是想做?
→ azureblaze: 這種狀況讀檔可能比計算慢
→ firingmoon: 讀檔的部分在時間上我可以不在意,我只在意計算距離
→ firingmoon: 找點的部分
→ firingmoon: 我只是想試著看看沒有更快的方式
推 Leeng: 如果還有其他幾何可能的話，只能有請高斯了
推 RealJack: 只求一次的話就直接算吧,也會對其他線求最大值那做個
→ RealJack: convex hull,第二次會快很多
→ azureblaze: 你的n個點有任何特殊性質嗎?像照著某種順序給?
推 RealJack: 還有你的檔案是文字格式還是可直接序列化的二進制格式
→ RealJack: 這兩者速度會差上數百倍
→ firingmoon: 我的n個點是時間序列,沒有甚麼特別性質
→ firingmoon: RealJack抱歉 不太懂你的意思
→ EdisonX: (1) 對 10K 個點找最近,是只會做一次還是會重覆做 ?
→ EdisonX: (2) 你的來源資料是你可以讀得懂的文字檔嗎 ?
→ EdisonX: (3) n個點是時間序列沒錯,已知是2維,還有沒有特殊性質 ?
→ EdisonX: 結果上述的問題。然後平行化+1.
→ EdisonX: 抱歉修正一下, 是對 10K 個點找最遠 @@
(1)只做一次
(2)讀得懂 基本上這部分不用太在意
(3)沒有特殊,單純就a[1],a[2],a[3].........
※ 編輯: firingmoon (113.61.182.113), 05/17/2015 02:01:33
→ azureblaze: 改用C 平行處理 SIMD 能用的方法大概就這些
推 LiloHuang: 這類問題很適合用 GLSL 或者 OpenCL 來做平行計算
→ LiloHuang: 我找到一個 GLSL 版本供你參考 http://goo.gl/SokaVC
推 FRAXIS: 依照我的經驗 dis 的計算和 if condition 會造成 delay
→ FRAXIS: 你可以手動用類似 software pipeling 的方法加快一點
→ FRAXIS: 你可以試著用 profiling tool 去觀察每個 instruction
→ FRAXIS: 的時間 然後再思考怎麼改進
→ FRAXIS: 你的問題 O(n) 的時間是不能避免的了 但是或許可以減少
→ FRAXIS: outer loop 呼叫這 function 的次數..
→ firingmoon: 感謝各位版友的幫助 我會試著你們給的建議測試看看
→ sulf: 矩陣旋轉，把直線當成新X軸，只要計算新的y座標比較