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

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

1 楼tomuno（特别行动组）回复于 2005-05-19 14:49:13 得分 0

如果在多边形的平面上存在一条直线，它与多边形的交点多于二个，则这个多边形为非凸多边形  
  初中的算术题  
  现在忘了  
  实现起来应该是不难Top

2 楼zhengy2003（尘封的传说）回复于 2005-05-19 15:07:25 得分 0

upTop

3 楼cuilichen（fjfjfjfj）回复于 2005-05-19 15:46:39 得分 50

对于N个点组成的多边形，连接其中的任意3个点，形成三角形，如果在N个顶点中，存在一个（一个以上的）点在这个三角形内，则这个多边形是凹多边形。如果遍历所有的情况，不存在这样的点，则这个多边形是凸多边形。  
   
  至于点在三角形内的算法，就比较简单了。Top

4 楼jihanzhong（逍遥）回复于 2005-05-19 17:02:13 得分 0

同意楼上的，２楼的直线没法遍历Top

5 楼jihanzhong（逍遥）回复于 2005-05-19 17:28:25 得分 50

我的新算法：  
  １：给所有点按X线轴排序：  
  N1（x1,y1）,N2（x2,y2）,N3（x3,y3）,...  
  x1<x2<x3...          
  2:建立上部集合top，下部集合buttom  
      遍历所有点：    
      if   Ni.y   比top中的元素都高，加入top;   判断top中后3点的夹角是不是向下（<180度）,是继续，否则返回false  
      if   Ni.y   比top中的元素都低，加入buttom;   判断top中后3点的夹角是不是向上（<180度）,是继续，否则返回false  
  3：剩下的点形成新集合right：  
        按y轴排序，依次判断夹角，都小于180度，则返回true，否则false      
  Top

6 楼potakaka（咔咔）回复于 2005-05-19 17:42:51 得分 0

关注。。。。Top

7 楼zhengy2003（尘封的传说）回复于 2005-05-19 17:53:20 得分 0

我用的是叉积，每相邻两条边做叉积，全部同号就为凸，但有时会判断错误  
   
  //   向量ab，向量ac   叉积ab×ac  
  private   int   getDirection(Point2D   a,   Point2D   b,   Point2D   c)   {  
          double   x1   =   b.getX()   -   a.getX();  
          double   y1   =   b.getY()   -   a.getY();  
          double   x2   =   c.getX()   -   a.getX();  
          double   y2   =   c.getY()   -   a.getY();  
          double   v   =     x1*y2   -   x2*y1;  
           
          if(v   >   0)  
                  return   1;     //   ab在ac顺时针方向  
          else   if(v   <   0)  
                  return   -1;   //   ab在ac逆时针方向  
          else  
                  return   0;     //   共线  
  }Top

相关问题

• 算法
• 凸多边形
• 多边形
• 三角形
• 存在

• 帖主：zhengy2003
• cuilichen
• jihanzhong

• CSDN Java频道
• Java类图书
• Java类源码下载