看板 [ Prob_Solve ]
討論串[問題] 計算幾何 - stabbing line
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 計算幾何 - stabbing line
推噓3(3推 0噓 4→)留言7則，0人參與, 最新作者FRAXIS (喔喔)時間11年前 (2013/12/03 22:43), 編輯資訊
1
0
0
內容預覽:
我在網路上看到一個問題：. 給定n條垂直的線段，設計一個線性的演算法找出是否存在一條直線，. 使得此直線與此n條線段都相交。. 我的解法是基於二維線性規劃，感覺是比較不直接的方法。. 有沒有比較直接的方法呢？. 原文如下：. You are given a set of n vertical lin
(還有44個字)
#2
Re: [問題] 計算幾何 - stabbing line
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者DJWS (...)時間11年前 (2013/12/04 13:09), 編輯資訊
1
0
0
內容預覽:
重發一篇.... 假設這些垂直線段已經由左到右排列好. 線段有上端點和下端點. 所有線段上端點，找往朝下凸包 O(N) (monotone chain). 所有線段下端點，找到朝上凸包 O(N). 朝下凸包和朝上凸包之間的區域，就是直線可能存在的區域. 如果兩個凸包有內公切線，就存在一條直線穿過所有
#3
Re: [問題] 計算幾何 - stabbing line
推噓4(5推 1噓 11→)留言17則，0人參與, 最新作者Leon (Achilles)時間11年前 (2013/12/04 15:35), 編輯資訊
0
0
0
內容預覽:
嗯, 抱歉我看不懂你想說折麼.. 你的朝上凹包 是 convex polygen 嗎?. 朝下凹包是甚麼? concave polygen ?. 要是只有三條線, 你永遠會找到 convext polygen. 你的演算法怎麼辦?. --------. well, my intuition is..
(還有256個字)
首頁
上一頁
1
下一頁
尾頁