Re: [問題] 計算幾何 - stabbing line
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/12/04 15:35)推噓4(5推 1噓 11→)留言17則, 7人參與討論串3/3 (看更多)
※ 引述《DJWS (...)》之銘言：
: ※ 引述《FRAXIS (喔喔)》之銘言：
: : 我在網路上看到一個問題：
: : 給定n條垂直的線段，設計一個線性的演算法找出是否存在一條直線，
: : 使得此直線與此n條線段都相交。
: : 我的解法是基於二維線性規劃，感覺是比較不直接的方法。
: : 有沒有比較直接的方法呢？
: : 原文如下：
: : You are given a set of n vertical line segments in the plane.
: : Present an O(n) efficient algorithm to determine whether
: : there exists a line that intersects all of these segments.
: 重發一篇...
: 假設這些垂直線段已經由左到右排列好
: 線段有上端點和下端點
: 所有線段上端點，找往朝下凸包 O(N) (monotone chain)
: 所有線段下端點，找到朝上凸包 O(N)
: 朝下凸包和朝上凸包之間的區域，就是直線可能存在的區域
: 如果兩個凸包有內公切線，就存在一條直線穿過所有線段
: 如果兩個凸包不相交（交集的面積是零），就有內公切線，就存在一條直線穿過所有線段
: 要判斷兩個凸包是否相交是O(N)
嗯, 抱歉我看不懂你想說折麼.
你的朝上凹包 是 convex polygen 嗎?
朝下凹包是甚麼? concave polygen ?
要是只有三條線, 你永遠會找到 convext polygen
你的演算法怎麼辦?
--------
well, my intuition is..
Let's define the vertical line as (u, v)
u as the upper point, v as the lower point.
Assuem the lines are sorted from left to right.
Then, we only need to compare two lines:
u_1 - highest v_i
and
u_1 - lowest u_i , i \= 1
--
趙客縵胡纓，吾鉤霜雪明。銀鞍照白馬，颯沓如流星。
十步殺一人，千里不留行。是了拂衣去，深藏身與名。
閑過信陵飲，脫劍膝前橫。將炙啖朱亥，持觴勸侯贏。
三杯吐然諾，五嶽倒為輕。眼花耳熱後，意氣素霓生。
就趙揮金錘，邯鄲先震驚。千秋二壯士，烜赫大梁城。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 96.41.13.29
推
12/04 18:50, , 1F
12/04 18:50, 1F
推
12/04 19:17, , 2F
12/04 19:17, 2F
→
12/04 19:17, , 3F
12/04 19:17, 3F
→
12/04 19:18, , 4F
12/04 19:18, 4F
→
12/04 19:34, , 5F
12/04 19:34, 5F
→
12/04 19:36, , 6F
12/04 19:36, 6F
→
12/04 19:38, , 7F
12/04 19:38, 7F
推
12/04 20:49, , 8F
12/04 20:49, 8F
→
12/04 20:50, , 9F
12/04 20:50, 9F
推
12/04 22:00, , 10F
12/04 22:00, 10F
→
12/04 22:01, , 11F
12/04 22:01, 11F
→
12/04 22:01, , 12F
12/04 22:01, 12F
→
12/04 22:02, , 13F
12/04 22:02, 13F
→
12/04 22:03, , 14F
12/04 22:03, 14F
噓
12/04 22:26, , 15F
12/04 22:26, 15F
→
12/04 22:26, , 16F
12/04 22:26, 16F
推
12/06 10:44, , 17F
12/06 10:44, 17F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
