寻找最大凸多边形

某公司今年的技能鉴定考试是这样的:

给出一系列平面直角坐标系中的点的坐标,写一个程序,找出能够围住这些点的最大的凸多边形,按照顺时针的顺序,将这个最大凸多边形的顶点依次打印出来。如果某个点落在多边形的边上,该点不得打印。

想象一下在每一个点上定一个钉子,然后用一根线把这些钉子给全部围住,线绷直了之后,就是我们要找的凸多边形了。做出这道题的关键是找到算法,同时还必须有一些平面几何的知识。下面给出两个算法。

第一个算法描述如下:

1. 在所有点中,找出纵坐标最大的那个点(最高的点);如果有好几个点的纵坐标都是最大的,那么就从中选出最左边(横坐标最小)的那个点;可以从数学上严格证明,这个点一定是最大凸多边形的顶点;这里就不证明了,欢迎热血青年来补充。
2. 记录下这个点,记做A,从A出发按如下算法寻找下一个顶点B;
3. 连接A点和剩下的其它点,形成一系列的向量AB,从正向X轴出发顺时针旋转一个角度之后会和向量AB重合,记录下这个夹角为α。
4. 形成最小夹角α的那个点B,就是我们要寻找的下一个顶点B。如果有好几个点都形成相等的最小夹角,那么我们选择线段AB长度最长的那个B点。其它长度较短的点则要从原始点集合中删除掉。
5. 按照同样的算法,从B点出发寻找下一顶点C,使得BC向量和正向X轴的夹角最小β,但是β必须大于上一步的α。
6. 以此类推,从C出发寻找D……,直到找到下一个顶点和A点重合,那么寻找结束。

这个算法,实际上就是模拟拿一根棍子贴着多边形滚动了一周。它要求我们会计算两个点的距离,会计算两个向量的夹角。对于我大五百强的员工而言,这些应该都是小儿科了。

上面的这个算法虽然巧妙,但是却缺少了一些数学上和程序上的美感,显得简单而且粗暴。算法,也要讲究“性感”,下面是一个性感的解法:

从N个点里面找最大凸多边形,比较困难;但是如果我们已经知道了这里面的N-1个点形成的最大凸多边形的顶点,那么再加上第N个点A,根据A和原来凸多边形的位置关系,就可以进一步计算出这N个点形成的新凸多边形顶点了。

没错,我们用到递归,来将复杂问题简单化。递归到最简单的情况,就是三个点,这三个点要么是在一条直线上,要么一定形成一个最简单的凸多边形,那就是三角形。三个点能否形成三角形,是很好判断的J。

以图一为例:已有凸多边形 ABCDEFGHI,现在加入一个新的点 J,显然,加上J之后,最大凸多边形应该变成 ABJEFGHI,CD两顶点要删除,并且用顶点J替换掉C和D;

图一

以图二为例:E点在AB的延长线上,多边形ABCD加上E点后,新的凸多边形应该是AECD,原来的B点应该被E替换掉;但如果ABCD 加上 F 点之后,新的凸多边形应该是ABFCD,原来的凸多边形上没有点要被删除,但是要插入新的F点。如果F点在多边形内部,那么直接抛弃F点即可。多边形还是不变。

图二

问题演变为,如何判断一个孤立点和一个凸多边形的关系呢?知道它们的关系后,怎么来计算出新的凸多边形呢?这里要用到向量的叉乘的概念,两个向量a=(x1,y2)和b=(x2,y2)的叉乘结果:

|a| ^ |b| = |a| * |b| *sin<a,b> = x1*y2 - x2*y1 <a,b>夹角必须小于180°
a ^ b = - b ^ a

叉乘结果是矢量,有正负表示其方向。结果为正,表示叉乘结果指向屏幕外;结果为负,表示叉乘结果指向屏幕里,可以使用右手定则来判定结果方向:右手四指环绕方向从a向b,大拇指方向则是其结果的方向,如果a和b平行,那么其结果为0;

回到图二,多边形ABCD和点E,将多边形顶点按顺时针顺序排列好,从E点出发分别和各顶点连接成向量EA, EB, EC ,ED,放入一个数组,然后依次计算两个相邻向量的叉乘,最后的ED去和EA叉乘,结果如下:[EA ^ EB , EB ^ EC, EC ^ ED ,ED ^EA], 可以发现,每一个元素的正负符号依次是[0 , + , - , -]。0表示E和AB在同一条线上,正数表示E点在BC直线的另一侧(相对于多边形在BC那侧而言),负数则表示在同一侧。

可以判断,叉乘结果的数组中:

1. 如果元素全部是负数,那么这个单点肯定在已知多边形的内部;这个单点应该直接抛弃;
2. 如果只有一个零,其它都是负数,那么这个单点一定在对应的边上;这个单点也应该直接抛弃;
3. 如果有两个零,那这个点一定和原来的某个顶点重合;应该抛弃这个单点;
4. 如果有一个或者多个连续的正数或者0,那么这个单点一定在这几条连续边的外面,例如上面的EA ^ EB , EB ^EC是0 和 正数,那么对应的连续顶点A-B-C,应该保留起始点A和结束点C,中间的点B则应该删除,然后将单点E插入到A和C中间;从而形成新的凸多边形顶点列表AECD;
5. 如果只有一个单独的正数叉乘结果,那就不需要删除任何原来的顶点,而仅需要将新的单点插入即可。
6. 不可能出现多段分开的正数或零序列,比如[-1, -1, 0, 1, 1, 1, 0, -1] 是可能的,但是如下的[-1, -1, 0, 1, -1, 0, 1, -1]叉乘结果序列是绝不可能出现的。 

知道这个关键点之后,剩下的就好办了,下面来看看代码吧,用Ruby写成。分别实现了上面提到的两个算法,最后有用例:


童鞋们,你们考试用的什么算法呢?

 

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 194,670评论 5 460
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 81,928评论 2 371
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 141,926评论 0 320
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 52,238评论 1 263
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 61,112评论 4 356
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 46,138评论 1 272
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 36,545评论 3 381
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 35,232评论 0 253
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 39,496评论 1 290
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,596评论 2 310
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,369评论 1 326
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,226评论 3 313
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 37,600评论 3 299
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,906评论 0 17
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,185评论 1 250
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 41,516评论 2 341
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 40,721评论 2 335

推荐阅读更多精彩内容