好久没看见@Highflybird 了，凸包多边形最小面积矩形的问题

aeo

刚看到几年前 @Highflybird 的帖子，计算 凸包点集 最小面积矩形，
方法是按 凸包每条边 为矩形的边，求出矩形，找最小的那个。

我问的是，有谁证明过，最小矩形 肯定 有条边 和 凸包边 重合吗？
是不是可能有面积更小的，不和 凸包边 平行的状态

newer

去看看  旋转卡壳法的总结 http://bbs.xdcad.net/thread-706965-1-1.html

aeo

newer 发表于 2017-1-21 01:31

但是并没有证明就是最小了。
只是一圈每条边 的情况下最小的。
我的意思：不重合的情况下为什么没最小的，（只要包住这么多点就可以了）



====================
还有：
高飞鸟的帖子
http://bbs.mjtd.com/thread-81308-1-1.html。
求最大距离：第7楼
如果第一条线是蓝色线，找到对面的平行线的点。如果对面的平行线的点，再找回第一条蓝线，就应该结束了，foreach 好像有点过头了。
还没写代码测试

marting

aeo 发表于 2017-1-21 10:50

通俗的想，你往一个箱子里面放东西，肯定是把尽可能贴着箱边的放里面，这样能放入的东西最多不会有空间浪费。可以用反证法，极端的条件就是一个矩形的凸包，还有其他的比这个小吗？ 极端下是四个边贴合。矩形面积长X宽，就一定不存在不贴合的面积还小的。贴合的边越多，面积就更小，两个边贴合的矩形一定比一个边贴合的还小。

既然旋转卡壳法被证明可以用来求最小面积矩形的经典算法，那么就不会有不符合卡壳结果的 另外情形的。

aeo

marting

aeo 发表于 2017-1-21 15:56

这个图形，你找到的不贴边的最小矩形是哪个？

aeo

marting 发表于 2017-1-21 16:34

我不是想说明这个问题的，
凸包的最小矩形肯定和凸包边重合，这个证明我没看见。
网上都是说怎么求的，都是用结论证明结论

newer

aeo 发表于 2017-1-21 17:07

那就搜搜 旋转卡壳算法的由来，应该会有证明的。旋转卡壳的提出的背景材料应该有说明为什么是和一个边重合的。要不算法就没支撑了。
写个程序，可以画出所有的矩形，和面积比较。

下面图中，红色较粗的是卡壳算法找到的。图中的例子有两个面积相等的矩形。

(defun c:tt ()
  (defun _drawrec (pts clr)
    (xdrx_polyline_make pts t)
    (if (/= clr 1)
      (setq clr (xdrx_math_rand 255))
    )
    (xdrx_setpropertyvalue (entlast) "constantwidth" (/ (getvar "viewsize")
                                                        (if (= clr 1)
                                                          50
                                                          100
                                                        )
                                                     ) "color" clr
    )
  )
  (xdrx_begin)
  (if (setq e (car (xdrx_entsel "\n拾取多边形<退出>:" '((0 . "LWPOLYLINE")))))
    (progn
      (setq pts (xdrx_getpropertyvalue e "vertices")
            minbox (xdrx_points_minareabox pts)
      )
      (setq pts (xd::list:snakepair (xd::pnts:close pts))
            i 0
      )
      (mapcar
        '(lambda (x)
           (setq vec (mapcar
                       '-
                       (cadr x)
                       (car x)
                     )
                 vec (xdrx_vector_normalize vec)
                 box (xdrx_entity_box e vec)
           )
           (_drawrec box -1)
           (setq i (1+ i))
           (xdrx_prompt "\n面积" i " = " (xdrx_getpropertyvalue
                                                                (entlast)
                                                                "area"
                                         )
           )
         )
        pts
      )
      (_drawrec minbox 1)
      (xdrx_prompt "\n旋转卡壳计算最小面积" " = "
                   (xdrx_getpropertyvalue (entlast) "area")
      )
    )
  )
  (xdrx_end)
  (princ)
)

XDSoft

aeo 发表于 2017-1-21 17:07

想了下，不用证明，既然前提是凸包，你要求凸包的最小面积矩形，所有的矩形的边一定要过凸包的两个点， 两个点就组成边了，所以，矩形是肯定包含一个边的。

aeo

newer 发表于 2017-1-21 17:19

旋转卡壳 只是其中的一种比较快的算法，但并不是证明。你的证明只是说和某条边重合的情况，谁最小。
我的意思是会不会有包住这些点的更小的矩形。



凸包理论应该是很早以前某个数学家创立的理论吧（我猜的），证明肯定有，但翻遍网络，没有！

我猜这个理论里面有很多结论性的东西，最小矩形和某条边重合，应该也是里面的一个结论。

marting

aeo 发表于 2017-1-25 12:07

A版， 你不是要求外接矩形里面最小的吗？
在凸包点集条件下，你要外接矩形，就一定要过凸包里面的两个点吧？ 而凸包的性质是：你要隔一个点连接线段，那么这个线段一定在凸包内部，这个没异议吧？ 所以只能是相邻两点连接的线段才可能在外接矩形上，所以，外接矩形的边至少有一条一定要通过凸包相邻点。

aeo

marting 发表于 2017-1-25 12:22

你这么说并没有说服我，面积是长*宽，你长变短了，不能证明高怎么变化。 可能长小了一些，高大了更多呢。
我是说包住这么多点的矩形，不管怎么作图，重不重合。
现实是：凸包最小矩形，就是这么多点的最小矩形。我想不出反例，不然就是数学家了。
但就是找不到这个结论出自哪里，只能找到作图方法。

marting

aeo 发表于 2017-1-25 14:23

在试试说说， 现在外接矩形 肯定要在凸包的一个边上没问题了吧？

在一个凸包的边，然后是矩形，那么这个矩形在这个方向上是唯一的，因为另外几个边对要过凸包的点。也就是两条垂直边被这个方向上的凸包最边上的点夹住，也就是这个方向上的最大包围盒。

旋转卡壳就是把凸包每个边上的这些矩形一个一个都算出来，找出面积最小的。

marting

aeo 发表于 2017-1-25 14:23

不存在长，高变化，确定了一个边，外接矩形就是唯一的，其他方向受凸包的点夹住控制。 这个边方向上的最大包围盒。

robocky

有这个的相关证明
用反证法可以证明，具体可以看下面的文章
http://blog.csdn.net/mo229mo/article/details/4256086