图形、游戏高手请进，输入N个点的坐标,由程序判断该N个点是否能构成一个凸多边形

输入N个点的坐标,由程序判断该N个点是否能构成一个凸多边形  
   
  请高手讲出算法思路，贴出代码也可以。 问题点数：100、回复次数：5Top

1 楼flying_dancing（小混混-_-）回复于 2005-05-19 14:41:31 得分 0

判断点是不是在任何一条线的一边...Top

2 楼heroforyou（(骑蜗牛)）回复于 2005-05-19 14:46:18 得分 0

任意2点连线，其余点不再同一测Top

3 楼yahaha（呀哈哈）回复于 2005-05-19 14:47:28 得分 0

最简单的算法就是枚举两个点之间的直线，然后判断剩余的点是不是在直线的同一侧。不过这样的时间复杂度就是O（C(n,2)），感觉应该有简单的算法，但是不知道！呵呵！Top

4 楼flying_dancing（小混混-_-）回复于 2005-05-19 14:50:51 得分 100

用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。  
  若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。  
  多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。  
  Top

5 楼zhengy2003（尘封的传说）回复于 2005-05-19 15:24:50 得分 0

upTop

相关问题

• 算法
• 凸多边形
• 多边形
• vj
• n个点
• 弦
• vi

• 帖主：zhengy2003
• flying_dancing

• C/C++ Blog
• C/C++类图书
• C/C++类源码下载