找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1735|回复: 14

[研讨] 好久没看见@Highflybird 了,凸包多边形最小面积矩形的问题

[复制链接]

已领礼包: 488个

财富等级: 日进斗金

发表于 2017-1-20 23:43:20 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

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

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

论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

已领礼包: 40个

财富等级: 招财进宝

发表于 2017-1-21 01:31:38 | 显示全部楼层
去看看  旋转卡壳法的总结 http://bbs.xdcad.net/thread-706965-1-1.html
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 488个

财富等级: 日进斗金

 楼主| 发表于 2017-1-21 10:50:08 | 显示全部楼层
本帖最后由 aeo 于 2017-1-21 11:02 编辑

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



====================
还有:
高飞鸟的帖子
http://bbs.mjtd.com/thread-81308-1-1.html
求最大距离:第7楼
如果第一条线是蓝色线,找到对面的平行线的点。如果对面的平行线的点,再找回第一条蓝线,就应该结束了,foreach 好像有点过头了。
还没写代码测试
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 20个

财富等级: 恭喜发财

发表于 2017-1-21 13:06:38 | 显示全部楼层
本帖最后由 marting 于 2017-1-21 13:11 编辑

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

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

论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 488个

财富等级: 日进斗金

 楼主| 发表于 2017-1-21 15:56:01 | 显示全部楼层
本帖最后由 aeo 于 2017-1-21 17:01 编辑


论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 20个

财富等级: 恭喜发财

发表于 2017-1-21 16:34:23 | 显示全部楼层

这个图形,你找到的不贴边的最小矩形是哪个?
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 488个

财富等级: 日进斗金

 楼主| 发表于 2017-1-21 17:07:27 | 显示全部楼层

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

论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 40个

财富等级: 招财进宝

发表于 2017-1-21 17:19:36 | 显示全部楼层

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

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



搜狗截图20170121163132.png




搜狗截图20170121170316.png

(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)
)

论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 145个

财富等级: 日进斗金

发表于 2017-1-21 17:39:53 | 显示全部楼层

想了下,不用证明,既然前提是凸包,你要求凸包的最小面积矩形,所有的矩形的边一定要过凸包的两个点, 两个点就组成边了,所以,矩形是肯定包含一个边的。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 488个

财富等级: 日进斗金

 楼主| 发表于 2017-1-25 12:07:31 | 显示全部楼层

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



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

我猜这个理论里面有很多结论性的东西,最小矩形和某条边重合,应该也是里面的一个结论。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 20个

财富等级: 恭喜发财

发表于 2017-1-25 12:22:06 | 显示全部楼层

A版, 你不是要求外接矩形里面最小的吗?
在凸包点集条件下,你要外接矩形,就一定要过凸包里面的两个点吧? 而凸包的性质是:你要隔一个点连接线段,那么这个线段一定在凸包内部,这个没异议吧? 所以只能是相邻两点连接的线段才可能在外接矩形上,所以,外接矩形的边至少有一条一定要通过凸包相邻点。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 488个

财富等级: 日进斗金

 楼主| 发表于 2017-1-25 14:23:46 | 显示全部楼层
本帖最后由 aeo 于 2017-1-25 14:28 编辑

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

论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 20个

财富等级: 恭喜发财

发表于 2017-1-25 15:12:15 | 显示全部楼层

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

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

旋转卡壳就是把凸包每个边上的这些矩形一个一个都算出来,找出面积最小的。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 20个

财富等级: 恭喜发财

发表于 2017-1-25 15:14:21 | 显示全部楼层

不存在长,高变化,确定了一个边,外接矩形就是唯一的,其他方向受凸包的点夹住控制。 这个边方向上的最大包围盒。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

发表于 2017-4-20 13:03:42 | 显示全部楼层
有这个的相关证明
用反证法可以证明,具体可以看下面的文章
http://blog.csdn.net/mo229mo/article/details/4256086
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )

GMT+8, 2024-11-12 14:10 , Processed in 0.215947 second(s), 59 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表