已知一个多边形所有顶点的坐标,这个图形的形状也有了
怎么来按照顺序输出这些坐标。
之前用了扫描法和固定一点求点到各顶点的角度,象限判断,但都存在一些漏洞。特此求问,要奔溃了

解决方案 »

  1.   

    因为如果只是一堆点,而且可以凹凸,这个定义是有歧义的。5个点:
    A    B
       C
    D    E
    你可以把AC CB连起来,也可以把CD CE连起来。所以不知道你是怎样在没有顺序的情况下画出图形的
      

  2.   

    有个固定的算法可以解决
    这可以看为一个convex hull 问题
    用Graham-­‐Scan 来求,记录下顶点顺序就好了。
      

  3.   

    或者既然你有了所有顶点
    先找到最左和最右的点,在这两点画一条虚拟的线,所有点在这条线之上的为A组,其他B组把A,B按X坐标分别排序,
    然后从最左开始添加A组的点(小从小到大),直到最右,然后在从最右开始添加B组的点(X从大到小)。
    这样就得到一个整多边形。
      

  4.   

    嗯,把点分为两种,一种是原始点,也就是三角形的顶点,一种是交叉点,针对每个交叉点生成一个小树,也就是两个原点为父,交叉点为子,没有交叉点的就两个原点成一个树
    然后就得到很多树放到set里,
    之后拿出一个树做基本的graph,找set里有相同顶点的树,添加进图,然后拿第二个树的不重复点去set里找相同
    直到set里的树都被拿出来。就成一个完整的图了。