作者iasm (I am Nobody)
看板Math
標題[幾何] 請問包含兩個點的最小圓
時間Mon May 23 00:25:09 2016
請教各位,我看到一題演算法smallest circle problem的一個特例
其題目如下
Give two planar points p1=(a1,b1) and p2=(a2,b2) and a line y=0,
design an algorithm to find the smallest circle that covers
both points such that its center (x*, 0) lies on y=0
由於本題的兩個點並不一定需要在圓周上,故跟原始問題不太像
例如有一點個是(2,5),另一個點是(2,3),由於限制圓心在x軸上
這兩個點又在同一條直線上,因此最小圓的圓心在(2,0),(2,5)在圓周上
(2,3)在"圓內",但如果兩個一個在x軸上,一個在x軸下,那情形又不一樣了
想請問各位,有沒有更為"一般"的演算可以涵蓋所有可能呢?
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.161.26.106
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1463934312.A.DEF.html
1F:推 Vulpix : if( abs(b1)>abs(b2) ) 05/23 00:46
2F:→ Vulpix : if( (a1-a2)^2+b2^2 <= b1^2 ) 05/23 00:49
3F:→ Vulpix : x*=a1; radius=abs(b1) 05/23 00:50
4F:→ Vulpix : else 05/23 00:52
5F:→ Vulpix : x*=( a1^-a2^2+b1^2-b2^2 )/2(a1-a2); 05/23 00:53
6F:→ Vulpix : radius自己算... 05/23 00:54
7F:→ Vulpix : else 就只是把p1跟p2對調而已 05/23 00:54
8F:→ Vulpix : 其實跟在x軸上下方沒有關係,因為圓是對稱的。 05/23 17:05
9F:推 suhorng : min_x max_i d(p_i,(x,0)) 也可硬解,比一樓方法麻煩 05/23 18:27