[幾何] 一個封閉區塊的2D平面求其中最大塊的矩形?

看板Math作者 (Silence)時間15年前 (2011/01/30 01:31), 編輯推噓4(4010)
留言14則, 2人參與, 最新討論串1/1
各位好, 想請問一個問題,它的描述大致上是這樣: 我今天有一個不規則的封閉平面區塊,而我想從裡面取出它所包含的矩形. 其中這個矩形包含最大面積. 而我想得知這個舉行的四個點座標. 想請問: 1.數學領域是否有研究在解這個問題? 2.若有的要找哪個數學方面的關鍵字? 我並非本科系的,對數學領域的認識薄弱. 因此上來求個關鍵字好做打算. 若描述上若有不周,煩請給點指教,我再加強描述. 謝謝! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 134.208.3.187

01/30 02:00, , 1F
這應該是屬於計算幾何 (Computational Geometry)
01/30 02:00, 1F

01/30 02:01, , 2F
我不確定在那個區塊太不規則時這個問題會有好的解答
01/30 02:01, 2F

01/30 02:02, , 3F
不過在區塊為凸多邊形且要求矩形跟坐標軸垂直時,
01/30 02:02, 3F

01/30 02:03, , 4F
n-凸多邊形有個 O(log n) time 的演算法.
01/30 02:03, 4F

01/30 02:05, , 5F
謝謝樓上H大的資訊
01/30 02:05, 5F

01/30 02:05, , 6F

01/30 02:07, , 7F
這個 project 網頁也可以參考:
01/30 02:07, 7F

01/30 02:07, , 8F

01/30 02:07, , 9F
哇,還有paper再好不過了,我正需要coding. :)
01/30 02:07, 9F

01/30 02:11, , 10F
ok, 找到 general polygon 的了,
01/30 02:11, 10F

01/30 02:11, , 11F

01/30 02:12, , 12F
上下界似乎是 O(n log^2 n) 跟 Ω(n log n).
01/30 02:12, 12F

01/30 02:15, , 13F
好熱心,你真是個好人
01/30 02:15, 13F

01/30 02:16, , 14F
Google 是好物啊 :P
01/30 02:16, 14F
文章代碼(AID): #1DH4xnSA (Math)