作者sonico (Silence)
看板Math
標題[幾何] 一個封閉區塊的2D平面求其中最大塊的矩形?
時間Sun Jan 30 01:31:25 2011
各位好,
想請問一個問題,它的描述大致上是這樣:
我今天有一個不規則的封閉平面區塊,而我想從裡面取出它所包含的矩形.
其中這個矩形包含最大面積.
而我想得知這個舉行的四個點座標.
想請問:
1.數學領域是否有研究在解這個問題?
2.若有的要找哪個數學方面的關鍵字?
我並非本科系的,對數學領域的認識薄弱.
因此上來求個關鍵字好做打算.
若描述上若有不周,煩請給點指教,我再加強描述.
謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 134.208.3.187
1F：推 hcsoso :這應該是屬於計算幾何 (Computational Geometry) 01/30 02:00
2F：→ hcsoso :我不確定在那個區塊太不規則時這個問題會有好的解答 01/30 02:01
3F：→ hcsoso :不過在區塊為凸多邊形且要求矩形跟坐標軸垂直時, 01/30 02:02
4F：→ hcsoso :n-凸多邊形有個 O(log n) time 的演算法. 01/30 02:03
5F：→ sonico :謝謝樓上H大的資訊 01/30 02:05
7F：推 hcsoso :這個 project 網頁也可以參考: 01/30 02:07
9F：→ sonico :哇,還有paper再好不過了,我正需要coding. :) 01/30 02:07
10F：推 hcsoso :ok, 找到 general polygon 的了, 01/30 02:11
12F：→ hcsoso :上下界似乎是 O(n log^2 n) 跟 Ω(n log n). 01/30 02:12
13F：→ sonico :好熱心,你真是個好人 01/30 02:15
14F：推 hcsoso :Google 是好物啊 :P 01/30 02:16