求一个算法，多边形对角线的问题

[plan9]

问题是这样的

有一个多边形，有n个顶点，现在想取m个对角线，而行这m个对角线是不相交的，问最多有多少种取法

比如，5个顶点的多边形，取2个不相交的对角线，可以有5种取法

做interviewstreet的编程挑战，卡到这里了，求解惑

[plan9]

目前的想法是这样的

1，求所有对角线
2，从里面取m个对角线并查看是否相交，如果不相交则count加一
3，重复2，直到对角线都取了个遍

有其他更好的吗

[aa88kk]

简单想了下，应该是个排列组合问题， 先从n个点选m, m多边形再两两相连，找出不相交的两条线。

[plan9]

@aa88kk m是对角线的个数，2条对角线可能有2个顶点，也可能有4个顶点，而且可能我表达的不够清楚，要找的不是2条对角线，而是要找m条不相交的对角线的可能性有几种

比如有1，2，3，4，5这5个顶点，2条不相交的对角线为
13，14
24，25
31，35
42，41
52，52
因此有5种可能性

[txx]

@plan9 你的方法太暴力 明显订一个顺序写一个递归会更好

[chx007]

是正多边形吗？
如果不是，是凸多边形吗？
如果不是，多边形自身的边有没相交呢？

[chx007]

如果是凸多边形（包括正多边形）应该是吧
m = n * ( n - 3 ) / 2

[momou]

给多边型定义一个坐标系，就很容易解决了。。。

[leoleozhu]

@plan9 13,14不是会在1处相交吗

[luin]

想象成一维的就好解决了啊

[plan9]

@txx 是啊，我也感觉太暴力

[plan9]

@txx 求订一个顺序递归做的算法

[plan9]

@chx007 不是，但是求最大的可能性，最大可能性应该就是正多边形

[plan9]

@chx007 这个。。。不是求对角线的个数。。。

[plan9]

@momou 求解答

[plan9]

@leoleozhu 具有同一个顶点的不算相交

[zellux]

和 Catalan 数的算法有点类似。取一条对角线把多边形分成两个，接下来要在左右两个多边形中一共取 m - 1 条，可能的取法是左边 0 条，右边 m - 1 条；左边 1 条，右边 m - 2 条……；左边 m - 1 条，右边 0 条（这里有些取法可能不成立，比如左边是三角形的话就只能取 0 条对角线）。这样递归下去就能算出来了。

[Air_Mu]

请用严谨的语言描述数学问题。不相交具体到底上什么情况？是在图形内不相交还是完全不相交（平行）。或者说AB 和AC这两条线相交于点A 这算相交还是不相交？

还有，这多边形是什么样的多边形？这种变态的图形也是多边形哦：

[txx]

@plan9 见@zellux 不过要想清楚就是了 顺着时针 考虑好边界情况

[plan9]

@zellux
@txx
非常感谢，也想过类似的方法，不过觉得这样得到的结果是不全的

按照这种方法，要想求得所有可能性的话
每次再归都要知道所在多边形的所有对角线
然后要拿每条对角线进行分割
并且要记录下来每个可能性的对角线都是什么
每次再归要是发现新的可能性都有与之前所记录的每种可能性进行比较

这样反而感觉更加暴力了

[plan9]

@Air_Mu 问题上没有说是什么样的多边形。。。就是说你这种变态多边形的也是可能的
相交的话只说了是在多边形的内部相交，那么AB 和AC这两条线相交于点A应该不算相交了
其他的描述就什么也没有了，还没有我这里描述的详细。。。