作者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