作者Leon (Achilles)
站内Prob_Solve
标题Re: [问题] 面试问到的问题...
时间Thu Dec 13 05:45:28 2012
※ 引述《Favonia (小西风最乖了*^^*)》之铭言：
: 用射影几何的对偶变换，原本问题
: 「给定一堆点求一条穿过最多点的线」
: 的对偶问题是知名问题
: 「给定一堆线求一个穿过最多线的点」
这篇文章值得一回.
上面说的, 是 Duality.
y - ax - b = 0.
你可以把 (x,y) 看成 point, (a,b) 看成 slope, distance for line
或是 (a,b) 看成 point, etc.
不过有一个小问题:
你下面提出的 Bentley-Ottmann, 我不熟悉
所以我去看了一下. 这似乎试用在 line segment.
如果用 duality 变换, 出来的应该为 line, 而不是 line segment.
在这个情况下, 要怎麽改?
我知道的作法, 试用 hough transform.
但这是一个 approximted algorithm
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 128.125.20.198
1F：推 Favonia:对耶我没有注意到！！！ 12/13 09:51
2F：推 yoco315:我想的也是 hough ... 12/14 00:11