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(MappointSet){MyPointtemp=pointSet.get(this.begin);returntemp;}publicMyPointgetEndPoint(MappointSet){MyPointtemp=pointSet.get(this.end);returntemp;}/**下面是根据两个点的ID，在边集中找寻两点组成的边*返回的是边对象*若没找到，则返回空*/publicstaticMyEdgegetEdge(intbegin,intend,MapedgeSet){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,MapedgeSet){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,MappointSet){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,MappointSet){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(Line<0)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(MappointSet,MapedgeSet,MaptriangleSet){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).addUseCo...
