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

更新时间：2024-06-24 21:01:02 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

python狄洛尼三角网算法推荐度：
相关推荐

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(Line<0) 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); /*

* 下面是生成边后的后期处理 */

newEdge1=new

在直线的左边

//生成的第一边 MyEdge

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(cos

goodPoint=pointSet.get(good); /*

* 下面是生成边后的后期处理 */

newEdge1=new

在直线的左边

//生成的第一边 MyEdge

edgeSet.put(newEdge1.id, newEdge1);

newEdge2=new

//生成的第二边 MyEdge

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) { this.info=info; }

public String getInfo() { return this.info; }

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;i<=pointSet.size();i++) { if(i==this.id) continue; double temp=this.distance(pointSet.get(i)); if(minDistance>temp) { minDistance=temp; minID=i; } } return pointSet.get(minID); } /*

*下面的方法是将点集中的点全部输出到文件中 */

public static boolean savePoints(Map pointSet) { boolean flag=false; File file=new File(\ 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+\ 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 JFrame { public 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, \ /*

* 点击“开始绘制”按钮后就会开始绘制

* 这里假定以点集中的第一个点为初始点进行绘制 */

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()<2) break; } if(i>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 int[3]; this.pID[0]=p1ID; this.pID[1]=p2ID; this.pID[2]=p3ID; } /*

* 注意此构造方法中的三点要满足顺时针的顺序 */

public MyTriangle(MyPoint p1,MyPoint p2,MyPoint p3,Map edgeSet) { this.id=++count; this.pID=new int[3]; this.pID[0]=p1.id; this.pID[1]=p2.id; this.pID[2]=p3.id; this.eID=new int[3]; this.eID[0]=MyEdge.getEdge(p1, p2, edgeSet).id; this.eID[1]=MyEdge.getEdge(p2, p3, edgeSet).id; this.eID[2]=MyEdge.getEdge(p3, p1, edgeSet).id; } /*

*此构造方法也是根据点来确定三角形

*但是传入的点是按照顺时针的顺序传入点的ID号 */

public MyTriangle(int p1ID,int p2ID,int p3ID,Map edgeSet) { this.id=++count; this.pID=new int[3]; this.pID[0]=p1ID; this.pID[1]=p2ID; this.pID[2]=p3ID; this.eID=new int[3]; this.eID[0]=MyEdge.getEdge(p1ID, p2ID, edgeSet).id; this.eID[1]=MyEdge.getEdge(p2ID, p3ID, edgeSet).id; this.eID[2]=MyEdge.getEdge(p3ID, p1ID, edgeSet).id; } /*

* 下面这个构造方法是按照边对象来构造三角形的 * 注意，边的顺序也要是按照顺时针的顺序进入 */ public MyTriangle(MyEdge e1,MyEdge e2,MyEdge e3,Map pointSet) { this.id=++count; this.pID=new int[3]; this.pID[0]=e1.getBeginPoint(pointSet).id; this.pID[1]=e2.getBeginPoint(pointSet).id; this.pID[2]=e3.getBeginPoint(pointSet).id; this.eID=new int[3]; this.eID[0]=e1.id; this.eID[1]=e2.id; this.eID[2]=e3.id; } /* * */ public MyTriangle(int e1ID,int e2ID,int e3ID,Map edgeSet,Map pointSet) { this.id=++count; this.pID=new int[3]; this.pID[0]=edgeSet.get(e1ID).getBeginPoint(pointSet).id; this.pID[1]=edgeSet.get(e2ID).getBeginPoint(pointSet).id; this.pID[2]=edgeSet.get(e3ID).getBeginPoint(pointSet).id; this.eID=new int[3]; this.eID[0]=e1ID;

this.eID[1]=e2ID; this.eID[2]=e3ID; } /*

* 下面这个方法是私有方法

* 它的作用是找到三角形的外界圆圆心坐标 */

private Point findCenter(Map pointSet) { MyPoint p1=pointSet.get(this.pID[0]); MyPoint p2=pointSet.get(this.pID[1]); MyPoint p3=pointSet.get(this.pID[2]); double x1=p1.x,y1=p1.y; double x2=p2.x,y2=p2.y; double x3=p3.x,y3=p3.y; double tempx1=(y2-y1)*(y3*y3-y1*y1+x3*x3-x1*x1)*1.0; double tempx2=(y3-y1)*(y2*y2-y1*y1+x2*x2-x1*x1)*1.0; double tempx3=2*(x3-x1)*(y2-y1)-2*(x2-x1)*(y3-y1); double centerX=(tempx1-tempx2)/tempx3; double tempy1=(x2-x1)*(x3*x3-x1*x1+y3*y3-y1*y1)*1.0; double tempy2=(x3-x1)*(x2*x2-x1*x1+y2*y2-y1*y1)*1.0; double tempy3=2*(y3-y1)*(x2-x1)-2*(y2-y1)*(x3-x1); double centerY=(tempy1-tempy2)/tempy3; return new Point((int)centerX,(int)centerY); } /*

* 下面这个函数是判断一个自定义点是否在三角形的外接圆内 * 若在圆内，则返回true * 否则返回false */

public boolean isInCircle(MyPoint p,Map pointSet) { boolean flag=false; Point center=this.findCenter(pointSet); MyPoint first=pointSet.get(this.pID[0]); double tempr1=(center.x-first.x)*(center.x-first.x); double tempr2=(center.y-first.y)*(center.y-first.y); double r=Math.sqrt((tempr1+tempr2)); double distance=p.distance(center.x,center.y); if(distance

}

} /*

* 下面这个方法是按顺时针顺序得到构成三角形的三个顶点 * 三个顶点将存储在一个数组中返回 */

public MyPoint[] getPoints(Map pointSet) { MyPoint[] temp=new MyPoint[3]; for(int i=0;i<3;i++) temp[i]=pointSet.get(this.pID[i]); return temp; } /* *

* 下面这个方法是按照顺时针的顺序得到构成这个三角形的三边 * 三条边存在一个一维数组中返回 */

public MyEdge[] getPoints(Map edgeSet) { MyEdge[] temp=new MyEdge[3]; for(int i=0;i<3;i++) temp[i]=edgeSet.get(this.pID[i]); return temp; }

本文来源：https://www.bwwdw.com/article/za53.html

相关文章：