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

import java.util.*;import java.awt.*;public class MyEdge public static int count=0;public int id;private int begin;private int end;private int useCount;public MyEdge(int begin,int end)this.id=+count;this.begin=begin;this.end=end;this.useCount=0;public MyEdge(MyPoint begin,MyPoint end)this.id=+count;this.begin=begin.id;this.end=end.id;this.useCount=0;public int getUseCount()return this.useCount;public void addUseCount()this.useCount+;/* * 下面这两个方法是得到边的来个顶点 * 若集合中没有指定的对象则返回空值 */public MyPoint getBeginPoint(Map pointSet)MyPoint temp=pointSet.get(this.begin);return temp;public MyPoint getEndPoint(Map pointSet)MyPoint temp=pointSet.get(this.end);return temp;/* * 下面是根据两个点的ID，在边集中找寻两点组成的边 * 返回的是边对象 * 若没找到，则返回空 */public static MyEdge getEdge(int begin,int end,Map edgeSet)MyEdge temp=null;for(int i=1;i=edgeSet.size();i+)temp=edgeSet.get(i);if(temp.begin=begin&temp.end=end)break;return temp;/* * 下面是根据两个点对象，在边集中找寻两点组成的边 * 返回的是边对象 * 若没找到，则返回空 */public static MyEdge getEdge(MyPoint begin,MyPoint end,Map edgeSet)MyEdge temp=null;for(int i=1;i=edgeSet.size();i+)temp=edgeSet.get(i);if(temp.begin=begin.id&temp.end=end.id)break;return temp;public void draw(Graphics g,Map pointSet)MyPoint begin=pointSet.get(this.begin);MyPoint end=pointSet.get(this.end);Color c=g.getColor();g.setColor(Color.blue);g.drawLine(begin.x, begin.y, end.x,end.y );g.setColor(c); /* * 下面这个方法是用来判断点在当前直线的左边还是右边 * 当然当前直线是有方向的 * 若点在直线的右边，则返回false * 否则返回true */public boolean isOnLeft(MyPoint p,Map pointSet)boolean flag=false;MyPoint begin=pointSet.get(this.begin);MyPoint end=pointSet.get(this.end);int Line=(begin.y-end.y)*p.x+(end.x-begin.x)*p.y-end.x*begin.y+end.y*begin.x;if(Line0) flag=true;return flag;/* * 比较两个边是否相等 * 这个方法排除了边的方向性 * 只要空间上是一条边 * 就是同一条边即相等 */public boolean equals(Object edge)boolean flag=false;if(this.end=(MyEdge)edge).begin&this.begin=(MyEdge)edge).end|this.begin=(MyEdge)edge).begin&this.end=(MyEdge)edge).end) flag=true;return flag;/* * 下面这个方法是将边的方向翻转 */public void turnBeginAndEnd()int temp=this.begin;this.begin=this.end;this.end=temp;/* * 下面这个方法是找到当前边的左边最优点 * 采用外接圆的方法 * 如果该边有左边最优点则返回之 * 否则返回空 */public MyPoint findGoodPointByCircle(Map pointSet,Map edgeSet,Map triangleSet)MyPoint goodPoint=null;for(int i=1;i=pointSet.size();i+) MyPoint activePoint=pointSet.get(i); if(this.isOnLeft(activePoint, pointSet)/判断当前活动点是不是在直线的左边 /在直线左边 MyTriangle activeTriangle=new MyTriangle(this.begin,i,this.end); int good=i; for(int j=i+1;j=pointSet.size();j+) /对当前活动边的左边点进行空圆准则检验 if(this.isOnLeft(pointSet.get(j), pointSet)/判断当前活动点是不是在直线的左边 if(activeTriangle.isInCircle(pointSet.get(j), pointSet) activeTriangle=new MyTriangle(this.begin,j,this.end); good=j; goodPoint=pointSet.get(good); /* * 下面是生成边后的后期处理 */ /生成的第一边 MyEdge newEdge1=new MyEdge(this.getBeginPoint(pointSet),goodPoint); newEdge1.addUseCount(); if(edgeSet.containsValue(newEdge1) MyEdge.count-; for(int k=1;k=edgeSet.size();k+) if(edgeSet.get(k).equals(newEdge1) edgeSet.get(k).addUseCount(); break; else edgeSet.put(newEdge1.id, newEdge1); /生成的第二边 MyEdge newEdge2=new MyEdge(goodPoint,this.getEndPoint(pointSet); newEdge2.addUseCount(); if(edgeSet.containsValue(newEdge2) MyEdge.count-; for(int k=1;k=edgeSet.size();k+) if(edgeSet.get(k).equals(newEdge2) edgeSet.get(k).addUseCount(); break; else edgeSet.put(newEdge2.id, newEdge2); /对第三边进行处理 this.addUseCount(); this.turnBeginAndEnd(); /生成三角形，并加入到三角形集合中 MyTriangle newTriangle=new MyTriangle(this.getBeginPoint(pointSet),goodPoint,this.getEndPoint(pointSet),edgeSet);triangleSet.put(newTriangle.id, newTriangle); break; return goodPoint;/* * 下面是另一种找最优点的方法 * 基于角度的方法 * 用余弦值最小的那个点 */public MyPoint findGoodPointByAngle(Map pointSet,Map edgeSet,Map triangleSet)MyPoint goodPoint=null;for(int i=1;i=pointSet.size();i+) MyPoint activePoint=pointSet.get(i); if(this.isOnLeft(activePoint, pointSet)/判断当前活动点是不是在直线的左边 /在直线左边 double minCos=this.getCos(activePoint, pointSet); int good=i; for(int j=i+1;j=pointSet.size();j+) /对当前活动边的左边点进行空圆准则检验 if(this.isOnLeft(pointSet.get(j), pointSet)/判断当前活动点是不是在直线的左边 double cos=this.getCos(pointSet.get(j), pointSet); if(cosminCos) minCos=cos; good=j; goodPoint=pointSet.get(good); /* * 下面是生成边后的后期处理 */ /生成的第一边 MyEdge newEdge1=new MyEdge(this.getBeginPoint(pointSet),goodPoint); newEdge1.addUseCount(); if(edgeSet.containsValue(newEdge1) MyEdge.count-; for(int k=1;k=edgeSet.size();k+) if(edgeSet.get(k).equals(newEdge1) edgeSet.get(k).addUseCount(); break; else edgeSet.put(newEdge1.id, newEdge1); /生成的第二边 MyEdge newEdge2=new MyEdge(goodPoint,this.getEndPoint(pointSet); newEdge2.addUseCount(); if(edgeSet.containsValue(newEdge2) MyEdge.count-; for(int k=1;k=edgeSet.size();k+) if(edgeSet.get(k).equals(newEdge2) edgeSet.get(k).addUseCount(); break; else edgeSet.put(newEdge2.id, newEdge2); /对第三边进行处理 this.addUseCount(); this.turnBeginAndEnd(); /生成三角形，并加入到三角形集合中 MyTriangle newTriangle=new MyTriangle(this.getBeginPoint(pointSet),goodPoint,this.getEndPoint(pointSet),edgeSet);triangleSet.put(newTriangle.id, newTriangle); break; return goodPoint;/* * 此方法是将某一点与当前边的顶点角的余弦值返回 */private double getCos(MyPoint p,Map pointSet)Point OA=new Point(pointSet.get(this.begin).x-p.x,pointSet.get(this.begin).y-p.y);Point OB=new Point(pointSet.get(this.end).x-p.x,pointSet.get(this.end).y-p.y);double OALength=Math.sqrt(OA.x*OA.x+OA.y*OA.y);double OBLength=Math.sqrt(OB.x*OB.x+OB.y*OB.y);return (OA.x*OB.x+OA.y*OB.y)/(OALength*OBLength);import java.util.*;import java.io.*;public class MyPoint public static int count=0; public int id; public int x; public int y; private String info; public MyPoint(int x,int y) this.id=+count; this.x=x; this.y=y; public void setInfo(String info) =info; public String getInfo() return ; public double distance(int x,int y) int tempx=(this.x-x)*(this.x-x); int tempy=(this.y-y)*(this.y-y); return Math.sqrt(tempx+tempy); public double distance(MyPoint p) int tempx=(this.x-p.x)*(this.x-p.x); int tempy=(this.y-p.y)*(this.y-p.y); return Math.sqrt(tempx+tempy); /* * 下面这个方法是找寻主叫点在点集中与之最近的点 * 返回的是与之最近点的引用 */ public MyPoint getMinDistancePoint(Map pointSet) int minID=this.id; double minDistance=Double.MAX_VALUE; for(int i=1;itemp) minDistance=temp; minID=i; return pointSet.get(minID); /* *下面的方法是将点集中的点全部输出到文件中 */ public static boolean savePoints(Map pointSet) boolean flag=false; File file=new File(point.txt); try PrintStream ps=new PrintStream(file); PrintStream temp=System.out; System.setOut(ps); for(int i=1;i=pointSet.size();i+) System.out.println(pointSet.get(i).id+t+pointSet.get(i).x+t+pointSet.get(i).y); flag=true; System.setOut(temp); /temp.close(); ps.close(); catch(IOException e) flag=false; return flag; /* * 下面的方法是将文件中的点加载到内存中 */ public static boolean readPoints(Map pointSet,String filename) boolean flag=false; File file=new File(filename); try FileInputStream in=new FileInputStream(file); Scanner fromfile=new Scanner(in); while(fromfile.hasNextInt() fromfile.nextInt(); MyPoint point=new MyPoint(fromfile.nextInt(),fromfile.nextInt(); pointSet.put(point.id, point); flag=true; in.close(); catch(IOException e) return flag; return flag; import javax.swing.*;import java.awt.*;import java.awt.event.*;import java.util.*;public class MyTin extends JFramepublic static void main(String agrs)MyTin tin=new MyTin(三角网的生成);private MyPanel show;private JButton begin; public MyTin(String title) super(title); this.setSize(500, 580); this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); this.getContentPane().setLayout(null); this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); this.show=new MyPanel(); this.show.setBounds(0,0,this.getWidth(),this.getHeight()-80); this.begin=new JButton(开始绘制); this.begin.addActionListener(new MyButtonMonitor(); this.begin.setBounds(this.getWidth()/2-70, this.getHeight()-75,100,30); this.getContentPane().add(show); this.getContentPane().add(begin); /this.pack(); this.setVisible(true); public class MyPanel extends JPanel public HashMap pointSet; public HashMap edgeSet; public HashMap triangleSet; public MyPanel() this.setBackground(Color.LIGHT_GRAY); this.pointSet=new HashMap(); this.edgeSet=new HashMap(); this.triangleSet=new HashMap(); this.addMouseListener(new MyMouseMonitor(); /* * 总的绘制方法 */ public void paint(Graphics g) Color c=g.getColor(); g.setColor(Color.LIGHT_GRAY); g.fillRect(0, 0, 500, 500); g.setColor(Color.red); for(int i=1;i=this.pointSet.size();i+) g.fillOval(this.pointSet.get(i).x-2,this.pointSet.get(i).y-2,5,5); if(!edgeSet.isEmpty() for(int i=1;i=this.edgeSet.size();i+) this.edgeSet.get(i).draw(g, pointSet); class MyMouseMonitor implements MouseListener public void mouseClicked(MouseEvent e) Point temp=e.getPoint(); MyPoint p=new MyPoint(temp.x,temp.y); pointSet.put(p.id,p); repaint(); public void mousePressed(MouseEvent e) public void mouseReleased(MouseEvent e) public void mouseEntered(MouseEvent e) public void mouseExited(MouseEvent e) class MyButtonMonitor implements ActionListener HashMap pointSet=MyTin.this.show.pointSet; HashMap edgeSet=MyTin.this.show.edgeSet; HashMap triangleSet=MyTin.this.show.triangleSet; public void actionPerformed(ActionEvent e) /* * 将点集中的点全部输出到文件中 */ MyPoint.savePoints(pointSet); /MyPoint.readPoints(pointSet, point.txt); /* * 点击“开始绘制”按钮后就会开始绘制 * 这里假定以点集中的第一个点为初始点进行绘制 */ MyPoint firstPoint=pointSet.get(1); MyPoint secondPoint=firstPoint.getMinDistancePoint(pointSet);/找距初始点最近的点 MyEdge firstEdge=new MyEdge(firstPoint,secondPoint);/生成的第一个边 edgeSet.put(firstEdge.id, firstEdge);/将第一个边加入到边集中 MyTin.this.show.repaint(); int i=1; while(!edgeSet.isEmpty() MyEdge activeEdge=null; for( ;i=edgeSet.size();i+) activeEdge=edgeSet.get(i); if(activeEdge.getUseCount()edgeSet.size()break; /这是采用外接圆的方法找最优点 / MyPoint goodPoint=activeEdge.findGoodPointByCircle(pointSet, edgeSet, triangleSet); /这是采用余弦值的方法找最优点 MyPoint goodPoint=activeEdge.findGoodPointByAngle(pointSet, edgeSet, triangleSet); if(goodPoint=null) activeEdge.addUseCount(); MyTin.this.show.repaint(); import java.util.*;import java.awt.*;public class MyTriangle public static int count=0; public int id; private int pID;/记录三角形中的点，按顺时针顺序排列 private int eID;/记录三角形中的边，按顺时针顺序排列 /* * 下面这个构造方法是简单三角形构造法，其中没有边的信息 * 可以用它来做判断 * 建议最后生成的三角形不要用此构造方法 */ public MyTriangle(int p1ID,int p2ID,int p3ID) this.pID=new int3; this.pID0=p1ID; this.pID1=p2ID; this.pID2=p3ID; /* * 注意此构造方法中的三点要满足顺时针的顺序 */ public MyTriangle(MyPoint p1,MyPoint p2,MyPoint p3,Map edgeSet) this.id=+count; this.pID=new int3; this.pID0=p1.id; this.pID1=p2.id; this.pID2=p3.id; this.eID=new int3; this.eID0=MyEdge.getEdge(p1, p2, edgeSet).id; this.eID1=MyEdge.getEdge(p2, p3, edgeSet).id; this.eID2=MyEdge.getEdge(p3, p1, edgeSet).id; /* *此构造方法也是根据点来确定三角形 *但是传入的点是按照顺时针的顺序传入点的ID号 */ public MyTriangle(int p1ID,int p2ID,int p3ID,Map edgeSet) this.id=+count; this.pID=new int3; this.pID0=p1ID; this.pID1=p2ID; this.pID2=p3ID; this.eID=new int3; this.eID0=MyEdge.getEdge(p1ID, p2ID, edgeSet).id; this.eID1=MyEdge.getEdge(p2ID, p3ID, edgeSet).id; this.eID2=MyEdge.getEdge(p3ID, p1ID, edgeSet).id; /* * 下面这个构造方法是按照边对象来构造三角形的 * 注意，边的顺序也要是按照顺时针的顺序进入 */ public MyTriangle(MyEdge e1,MyEdge e2,MyEdge e3,Map pointSet) this.id=+count; this.pID=new int3; this.pID0=e1.getBeginPoint(pointSet).id; this.pID1=e2.getBeginPoint(pointSet).id; this.pID2=e3.getBeginPoint(pointSet).id; this.eID=new int3; this.eID0=e1.id; this.eID1=e2.id; this.eID2=e3.id; /* * */ public MyTriangle(int e1ID,int e2ID,int e3ID,Map edgeSet,Map pointSet) this.id=+count; this.pID=new int3; this.pID0=edgeSet.get(e1ID).getBeginPoint(pointSet).id; this.pID1=edgeSet.get(e2ID).getBeginPoint(pointSet).id; this.pID2=edgeSet.get(e3ID).getBeginPoint(pointSet).id; this.eID=new int3; this.eID0=e1ID; this.eID1=e2ID; this.eID2=e3ID; /* * 下面这个方法是私有方法 * 它的作用是找到三角形的外界圆圆心坐标 */ private Point findCenter(Map pointSet) MyPoint p1=pointSet.get(this.pID0); MyPoint p2=pointSet.get(this.pID1); MyPoint p3=pointSet.get(this.pID2