Re: [問題] 計算幾何 - stabbing line

[Leon (Achilles)]

※ 引述《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
推 ZanFu5566:what if lines are not sorted at start?
推 neutrino:我想他說的是 找上端點們的lower hull, 下端點們的upper
→ neutrino:hull
→ neutrino:如此理解的話, 他的方法好像會對
→ DJWS:我的意思如樓上所言  朝下凸包lower hull 朝上凸包upper hull
→ DJWS:英翻中翻譯的不好請多見諒
→ DJWS:再來回覆一樓   如果一開始沒排序，那麼我也不知道怎麼做
推 FRAXIS:LEON的解法應該不用排序吧 因為可以用O(n)的時間找出u_1
→ FRAXIS:不過我有點懷疑正確性.. 為什麼只要判斷u_1?
推 seanwu:原po應該是假定會過u_1所以這樣做吧...不過當然不一定會
→ seanwu:再說，就算是要求過u_1的直線也不對，例如
→ seanwu:垂直線 (0,2)-(0,5), (1,1)-(1,4), (3,0)-(3,3)
→ seanwu:這樣只會看到 (0,5)-(3,3) 和 (0,5)-(1,1)
→ seanwu:應該要以u_1為中心照角度排，不是y座標
噓 scwg:莫明其妙. DJWS 的做法解釋簡單明瞭也被你嫌. 你的做法最左邊
→ scwg:那條延長到正負無限大才不知道要怎麼辦咧
推 yoco315:的確是簡單明瞭，不能理解以 Leon 的程度怎麼可能會看不懂