作者firingmoon (小天)
站内Prob_Solve
标题[问题] 多点到直线的距离
时间Sat May 16 22:46:44 2015
各位版友好
今天我有n个点,求每一个点到直线L的距离,最终找出其中一点
且此点到直线L的距离最长
直观的来讲我只需要做n次并用max函数即可
但我希望速度能够更快
所以想请教各位是否有演算法可以加速计算此部分 谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 113.61.182.113
※ 文章网址: https://webptt.com/cn.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