遇到一个棘手的算法问题,多边形(可能凸也可能是凹)顶点的顺序问题 已知一个多边形所有顶点的坐标,这个图形的形状也有了怎么来按照顺序输出这些坐标。之前用了扫描法和固定一点求点到各顶点的角度,象限判断,但都存在一些漏洞。特此求问,要奔溃了 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 因为如果只是一堆点,而且可以凹凸,这个定义是有歧义的。5个点:A B CD E你可以把AC CB连起来,也可以把CD CE连起来。所以不知道你是怎样在没有顺序的情况下画出图形的 有个固定的算法可以解决这可以看为一个convex hull 问题用Graham-‐Scan 来求,记录下顶点顺序就好了。 或者既然你有了所有顶点先找到最左和最右的点,在这两点画一条虚拟的线,所有点在这条线之上的为A组,其他B组把A,B按X坐标分别排序,然后从最左开始添加A组的点(小从小到大),直到最右,然后在从最右开始添加B组的点(X从大到小)。这样就得到一个整多边形。 嗯,把点分为两种,一种是原始点,也就是三角形的顶点,一种是交叉点,针对每个交叉点生成一个小树,也就是两个原点为父,交叉点为子,没有交叉点的就两个原点成一个树然后就得到很多树放到set里,之后拿出一个树做基本的graph,找set里有相同顶点的树,添加进图,然后拿第二个树的不重复点去set里找相同直到set里的树都被拿出来。就成一个完整的图了。 关于打印输出程序自身代码 JAVA面试题解惑系列(十一)——这些运算符你是否还记得? 关于JList的添加删除 关于System.currentTimeMillis(); JDBC出错以前还好的 服务器是否支持开多个端口,如果不用多线程.详细问题是…… 高手帮忙看看,是哪里的问题 ? 谁知道如何用java做soap? 关于调用import com.borland.jbcl.layout.*;,的问题,高手帮忙 java新手小白求教(救救孩子吧!) 新手求教 求大神发一下java基础的练习题给我
A B
C
D E
你可以把AC CB连起来,也可以把CD CE连起来。所以不知道你是怎样在没有顺序的情况下画出图形的
这可以看为一个convex hull 问题
用Graham-‐Scan 来求,记录下顶点顺序就好了。
先找到最左和最右的点,在这两点画一条虚拟的线,所有点在这条线之上的为A组,其他B组把A,B按X坐标分别排序,
然后从最左开始添加A组的点(小从小到大),直到最右,然后在从最右开始添加B组的点(X从大到小)。
这样就得到一个整多边形。
然后就得到很多树放到set里,
之后拿出一个树做基本的graph,找set里有相同顶点的树,添加进图,然后拿第二个树的不重复点去set里找相同
直到set里的树都被拿出来。就成一个完整的图了。