我正在尝试复制找到的小程序here http://www.diku.dk/hjemmesider/studerende/duff/Fortune/作为练习的一部分。该小程序使用《财富》的算法来生成两者; Voronoi 图和 Delaunay 三角剖分。我只是对在平面上生成 Delaunay 三角剖分感兴趣,因此将使用增量算法,即一次添加 1 个点。我打算展示添加样本点时每个阶段生成的三角形。
我正在使用 SwingWorker 类创建包含算法的 Triangulate 类的实例。我在 for 循环中调用 triangulate 方法,当单击 GUI 上的开始按钮时,该循环会迭代采样点集。
这是代码:
JButton startButton = new JButton("Start");
startButton.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent ae) {
SwingWorker<List<Triangle>, Triangle> worker = new SwingWorker<List<Triangle>, Triangle>() {
@Override
protected List<Triangle> doInBackground() throws Exception {
Triangulate dt = new Triangulate(drawingPanel.pointsList());
dt.preTriangulate(); //Set-up a bounding triangle and obtain a random permutation of the points
List<PlanarPoint> pointsList = dt.pointsList();
for (int i = 0; i < pointsList.size(); i++) {
PlanarPoint sample = pointsList.get(i);
dt.triangulate(sample);
List<Triangle> list = dt.trianglesList(); //Obtaining the list of triangles at every stage. Good Idea??
for (int j = 0; j < list.size(); j++) {
publish(list.get(j));
}
Thread.sleep(500);
}
dt.removeTriangles(dt.trianglesList()); // Remove all the triangles containing bounding-triangle vertices
return dt.trianglesList();
}
protected void process(List<Triangle> triangles) {
for (Triangle triangle : triangles) {
g = drawingPanel.getGraphics();
PlanarPoint p1 = triangle.getVertex1();
PlanarPoint p2 = triangle.getVertex2();
PlanarPoint p3 = triangle.getVertex3();
g.drawLine((int) Math.ceil(p1.x), (int) Math.ceil(p1.y),
(int) Math.ceil(p2.x), (int) Math.ceil(p2.y));
g.drawLine((int) Math.ceil(p2.x),(int) Math.ceil(p2.y),
(int) Math.ceil(p3.x),(int) Math.ceil(p3.y));
g.drawLine((int) Math.ceil(p3.x),(int) Math.ceil(p3.y),
(int) Math.ceil(p1.x),(int) Math.ceil(p1.y));
}
}
};
worker.execute();
}
});
下面是 Triangulate 类,它计算一组点的 Delanuay 三角剖分:
public class Triangulate {
private List<PlanarPoint> pointsList;
private List<Triangle> triangleList;
private Triangle boundingTriangle;
private List<Edge> edgeList;
public Triangulate(List<PlanarPoint> pointsList) {
this.pointsList = pointsList;
this.triangleList = new ArrayList<Triangle>();
this.edgeList = new ArrayList<Edge>();
}
public List<Triangle> trianglesList() {
return triangleList;
}
public List<PlanarPoint> pointsList() {
return pointsList;
}
public void preTriangulate() {
boundingTriangle = getBoundingTriangle(pointsList);
triangleList.add(boundingTriangle);
randomPermutation(pointsList);
}
public void triangulate(PlanarPoint samplePoint) {
// A procedure implementing the Bowyer - Watson algorithm
// to calculate the DT of a set of points in a plane.
}
public void removeTriangles(List<Triangle> trianglesList) {
// A procedure to remove all triangles from the list sharing
// edges with the bounding-triangle
}
private Triangle getBoundingTriangle(List<PlanarPoint> pointsList) {
//Obtains a bounding-triangle for a set of points
}
public void randomPermutation(List<PlanarPoint> pointsList) {
//Obtains a random permutation of a set of points
}
}
我还有另外3节课
- PlanarPoint - Point2D.Double 的子类,它实现 Comparable 以提供基于 y 坐标的排序
- Triangle - 确定三角形的外接圆和外接半径并确定点是否位于三角形的外接圆内的类
- Edge - 将 Edge 表示为具有 2 个 PlanarPoints 作为其端点的类。
-
DrawingPanel - 充当表面的类,在单击事件时在其上添加点并在屏幕上绘制点。
现在,这是我所关心的一些问题
- 有没有更好的方法通过迭代一组点然后调用 Triangulate 类的函数来获取现有的外接圆和三角形来显示三角形和可能的外接圆
- 是否所有绘图都仅限于 DrawingPanel 类,因为在上面的代码片段中,我在扩展 JApplet/JFrame 的类中进行绘画,因此每当调整窗口大小时,绘制的三角形都会丢失?有我可以遵循的设计模式吗?
- 除了计算一组点的 DT 的时间是一项耗时的任务之外,使用 SwingWorker 来生成另一个线程是否合理?
如果我遗漏了任何细节,请告诉我
谢谢,
柴塔尼亚