基于狄洛尼三角网生成算法的源代码

importjava.util.*;importjava.awt.*;publicclassMyEdge{publicstaticintcount=0;publicintid;privateintbegin;privateintend;privateintuseCount;publicMyEdge(intbegin,intend){this.id=++count;this.begin=begin;this.end=end;this.useCount=0;}publicMyEdge(MyPointbegin,MyPointend){this.id=++count;this.begin=begin.id;this.end=end.id;this.useCount=0;}publicintgetUseCount(){returnthis.useCount;}publicvoidaddUseCount(){this.useCount++;}/**下面这两个方法是得到边的来个顶点*若集合中没有指定的对象则返回空值*/publicMyPointgetBeginPoint(MapInteger,MyPointpointSet){MyPointtemp=pointSet.get(this.begin);returntemp;}publicMyPointgetEndPoint(MapInteger,MyPointpointSet){MyPointtemp=pointSet.get(this.end);returntemp;}/**下面是根据两个点的ID，在边集中找寻两点组成的边*返回的是边对象*若没找到，则返回空*/publicstaticMyEdgegetEdge(intbegin,intend,MapInteger,MyEdgeedgeSet){MyEdgetemp=null;for(inti=1;i=edgeSet.size();i++){temp=edgeSet.get(i);if(temp.begin==begin&&temp.end==end)break;}returntemp;}/**下面是根据两个点对象，在边集中找寻两点组成的边*返回的是边对象*若没找到，则返回空*/publicstaticMyEdgegetEdge(MyPointbegin,MyPointend,MapInteger,MyEdgeedgeSet){MyEdgetemp=null;for(inti=1;i=edgeSet.size();i++){temp=edgeSet.get(i);if(temp.begin==begin.id&&temp.end==end.id)break;}returntemp;}publicvoiddraw(Graphicsg,MapInteger,MyPointpointSet){MyPointbegin=pointSet.get(this.begin);MyPointend=pointSet.get(this.end);Colorc=g.getColor();g.setColor(Color.blue);g.drawLine(begin.x,begin.y,end.x,end.y);g.setColor(c);}/**下面这个方法是用来判断点在当前直线的左边还是右边*当然当前直线是有方向的*若点在直线的右边，则返回false*否则返回true*/publicbooleanisOnLeft(MyPointp,MapInteger,MyPointpointSet){booleanflag=false;MyPointbegin=pointSet.get(this.begin);MyPointend=pointSet.get(this.end);intLine=(begin.y-end.y)*p.x+(end.x-begin.x)*p.y-end.x*begin.y+end.y*begin.x;if(Line0)flag=true;returnflag;}/**比较两个边是否相等*这个方法排除了边的方向性*只要空间上是一条边*就是同一条边即相等*/publicbooleanequals(Objectedge){booleanflag=false;if(this.end==((MyEdge)edge).begin&&this.begin==((MyEdge)edge).end||this.begin==((MyEdge)edge).begin&&this.end==((MyEdge)edge).end)flag=true;returnflag;}/**下面这个方法是将边的方向翻转*/publicvoidturnBeginAndEnd(){inttemp=this.begin;this.begin=this.end;this.end=temp;}/**下面这个方法是找到当前边的左边最优点*采用外接圆的方法*如果该边有左边最优点则返回之*否则返回空*/publicMyPointfindGoodPointByCircle(MapInteger,MyPointpointSet,MapInteger,MyEdgeedgeSet,MapInteger,MyTriangletriangleSet){MyPointgoodPoint=null;for(inti=1;i=pointSet.size();i++){MyPointactivePoint=pointSet.get(i);if(this.isOnLeft(activePoint,pointSet))//判断当前活动点是不是在直线的左边{//在直线左边MyTriangleactiveTriangle=newMyTriangle(this.begin,i,this.end);intgood=i;for(intj=i+1;j=pointSet.size();j++){//对当前活动边的左边点进行空圆准则检验if(this.isOnLeft(pointSet.get(j),pointSet))//判断当前活动点是不是在直线的左边{if(activeTriangle.isInCircle(pointSet.get(j),pointSet)){activeTriangle=newMyTriangle(this.begin,j,this.end);good=j;}}}goodPoint=pointSet.get(good);/**下面是生成边后的后期处理*///生成的第一边MyEdgenewEdge1=newMyEdge(this.getBeginPoint(pointSet),goodPoint);newEdge1.addUseCount();if(edgeSet.containsValue(newEdge1)){MyEdge.count--;for(intk=1;k=edgeSet.size();k++){if(edgeSet.get(k).equals(newEdge1)){edgeSet.get(k).addUseCount();break;}}}elseedgeSet.put(newEdge1.id,newEdge1);//生成的第二边MyEdgenewEdge2=newMyEdge(goodPoint,this.getEndPoint(pointSet));newEdge2.addUseCount();if(edgeSet.containsValue(newEdge2)){MyEdge.count--;for(intk=1;k=edgeSet.size();k++){if(edgeSet.get(k).equals(newEdge2)){edgeSet.get(k).addUseCount();break;}}}elseedgeSet.put(newEdge2.id,newEdge2);//对第三边进行处理this.addUseCount();this.turnBeginAndEnd();//生成三角形，并加入到三角形集合中MyTrianglenewTriangle=newMyTriangle(this.getBeginPoint(pointSet),goodPoint,this.getEndPoint(pointSet),edgeSet);triangleSet.put(newTriangle.id,newTriangle);break;}}returngoodPoint;}/**下面是另一种找最优点的方法*基于角度的方法*用余弦值最小的那个点*/publicMyPointfindGoodPointByAngle(MapInteger,MyPointpointSet,MapInteger,MyEdgeedgeSet,MapInteger,MyTriangletriangleSet){MyPointgoodPoint=null;for(inti=1;i=pointSet.size();i++){MyPointactivePoint=pointSet.get(i);if(this.isOnLeft(activePoint,pointSet))//判断当前活动点是不是在直线的左边{//在直线左边doubleminCos=this.getCos(activePoint,pointSet);intgood=i;for(intj=i+1;j=pointSet.size();j++){//对当前活动边的左边点进行空圆准则检验if(this.isOnLeft(pointSet.get(j),pointSet))//判断当前活动点是不是在直线的左边{doublecos=this.getCos(pointSet.get(j),pointSet);if(cosminCos){minCos=cos;good=j;}}}goodPoint=pointSet.get(good);/**下面是生成边后的后期处理*///生成的第一边MyEdgenewEdge1=newMyEdge(this.getBeginPoint(pointSet),goodPoint);newEdge1.addUseCount();if(edgeSet.containsValue(newEdge1)){MyEdge.count--;for(intk=1;k=edgeSet.size();k++){if(edgeSet.get(k).equals(newEdge1)){edgeSet.get(k).addUseCount();break;}}}elseedgeSet.put(newEdge1.id,newEdge1);//生成的第二边MyEdgenewEdge2=newMyEdge(goodPoint,this.getEndPoint(pointSet));newEdge2.addUseCount();if(edgeSet.containsValue(newEdge2)){MyEdge.count--;for(intk=1;k=edgeSet.size();k++){if(edgeSet.get(k).equals(newEdge2)){edgeSet.get(k).addUseCount();break;}}}elseedgeSet.put(newEdge2.id,newEdge2);//对第三边进行处理this.addUseCount();this.turnBeginAndEnd();//生成三角形，并加入到三角形集合中MyTrianglenewTriangle=newMyTriangle(this.getBeginPoint(pointSet),goodPoint,this.getEndPoint(pointSet),edgeSet);triangleSet.put(