求凸包java演示程序:
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.border.*;
import java.util.*;
/*
* 直线类
*/
class Line {
Point p1, p2;
Line(Point p1, Point p2) {
this.p1 = p1;
this.p2 = p2;
}
void draw(Graphics g) {
g.drawLine(p1.x, p1.y, p2.x, p2.y);
}
public String toString() {
return "(" + p1.x + ", " + p1.y + ") -> (" + p2.x + ", " + p2.y + ")";
}
}
/*
* 凸包接口
*/
interface TuBao {
void setPointList(java.util.List< Point> pts);
java.util.List< Line> eval();
}
/*
* 暴力法求凸包
*/
class BaoLiTuBao implements TuBao {
java.util.List< Point> pts = null;
java.util.List< Line> lines = new ArrayList< Line>();
public void setPointList(java.util.List< Point> pts) {
this.pts = pts;
}
public java.util.List< Line> eval() {
lines.clear();
if (pts == null) { return lines; }
int n = pts.size();
int a, b, c, cc, l, r;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
a = pts.get(j).y - pts.get(i).y;
b = pts.get(i).x - pts.get(j).x;
c = pts.get(i).x * pts.get(j).y -pts.get(i).y * pts.get(j).x;
l = r = 0;
int k;
for (k = 0; k < n; k++) {
cc = a * pts.get(k).x + b * pts.get(k).y;
if (cc > c) l++;
else if (cc < c) r++;
if (l * r != 0) break;
}
if (k == n) {
lines.add(new Line(pts.get(i), pts.get(j)));
}
}
}
return lines;
}
}
/*
* 分治法求凸包
*/
class QuickTuBao implements TuBao {
java.util.List< Point> pts = null;
java.util.List< Line> lines = new ArrayList< Line>();
public void setPointList(java.util.List< Point> pts) {
this.pts = pts;
}
//求凸包，结果存入lines中
public java.util.List< Line> eval() {
lines.clear();
if (pts == null || pts.isEmpty()) { return lines; }
java.util.List< Point> ptsLeft = new ArrayList< Point>();
java.util.List< Point> ptsRight = new ArrayList< Point>();
//按x坐标对pts排序
Collections.sort(pts, new Comparator< Point>() {
public int compare(Point p1, Point p2) {
return p1.x-p2.x;
}
});
Point p1 = pts.get(0); //最左边的点
Point p2 = pts.get(pts.size()-1); //最右边的点
Point p3 = null;
int area = 0;
for (int i = 1; i < pts.size(); i++) {
p3 = pts.get(i);
area = getArea(p1, p2, p3);
if (area > 0) {
ptsLeft.add(p3);
} else if (area < 0) {
ptsRight.add(p3);
}
}
d(p1, p2, ptsLeft);
d(p2, p1, ptsRight);
return lines;
}
private void d(Point p1, Point p2, java.util.List< Point> s) {
//s集合为空
if (s.isEmpty()) {
lines.add(new Line(p1, p2));
return;
}
//s集合不为空，寻找Pmax
int area = 0;
int maxArea = 0;
Point pMax = null;
for (int i = 0; i < s.size(); i++) {
area = getArea(p1, p2, s.get(i));
if (area > maxArea) {
pMax = s.get(i);
maxArea = area;
}
}
//找出位于(p1, pMax)直线左边的点集s1
//找出位于(pMax, p2)直线左边的点集s2
java.util.List< Point> s1 = new ArrayList< Point>();
java.util.List< Point> s2 = new ArrayList< Point>();
Point p3 = null;
for (int i = 0; i < s.size(); i++) {
p3 = s.get(i);
if (getArea(p1, pMax, p3) > 0) {
s1.add(p3);
} else if (getArea(pMax, p2, p3) > 0) {
s2.add(p3);
}
}
//递归
d(p1, pMax, s1);
d(pMax, p2, s2);
}
// 三角形的面积等于返回值绝对值的二分之一
// 当且仅当点p3位于直线(p1, p2)左侧时，表达式的符号为正
private int getArea(Point p1, Point p2, Point p3) {
return p1.x * p2.y + p3.x * p1.y + p2.x * p3.y -
p3.x * p2.y - p2.x * p1.y - p1.x * p3.y;
}
}
/*
* 绘制点及凸包的面板
*/
class DrawPanel extends JPanel {
public static final int WIDTH = 640;
public static final int HEIGHT = 480;
public static final int BORDER = 100;
java.util.List< Point> pts = new ArrayList< Point>();
TuBao tuBao = null;
int n;
public DrawPanel() {
setPreferredSize(new Dimension(WIDTH, HEIGHT));
setBorder(new LineBorder(Color.RED));
n = 100;
}
public void setN(int n) { this.n = n; }
public void setTuBao(TuBao tuBao) {
this.tuBao = tuBao;
tuBao.setPointList(pts);
}
public void randPoints() {
pts.clear();
Random rd = new Random(new Date().getTime());
for (int i = 0; i < n; i++) {
pts.add(new Point(rd.nextInt(WIDTH-BORDER*2)+BORDER,
rd.nextInt(HEIGHT-BORDER*2)+BORDER));
}
}
public void paintComponent(Graphics g) {
super.paintComponent(g);
Color c = g.getColor();
g.setColor(Color.red);
for (Point pt : pts) {
g.fillOval(pt.x, pt.y, 5, 5);
}
g.setColor(c);
if (tuBao == null) return;
for (Line line : tuBao.eval()) {
line.draw(g);
}
tuBao = null;
}
}
/*
* 主窗体
*/
public class GetTuBao extends JFrame {
DrawPanel drawPanel;
JSlider sd;
JLabel lb;
TuBao baoLiTuBao = new BaoLiTuBao();
TuBao quickTuBao = new QuickTuBao();
public GetTuBao() {
setTitle("凸包问题演示");
JPanel menu = new JPanel();
menu.setLayout(new FlowLayout(FlowLayout.LEFT));
sd = new JSlider(JSlider.HORIZONTAL, 0, 100, 100);
sd.setMajorTickSpacing(20);
sd.setMinorTickSpacing(10);
sd.setPaintTicks(true);
lb = new JLabel("100");
JButton btnRand = new JButton("随机点");
JButton btnBaoLi = new JButton("暴力法");
JButton btnQuick = new JButton("快包法");
menu.add(sd);
menu.add(lb);
menu.add(btnRand);
menu.add(btnBaoLi);
menu.add(btnQuick);
drawPanel = new DrawPanel();
add(BorderLayout.NORTH, menu);
add(BorderLayout.CENTER, drawPanel);
pack();
setResizable(false);
sd.addChangeListener(new ChangeListener() {
public void stateChanged(ChangeEvent e) {
lb.setText(String.valueOf(sd.getValue()));
drawPanel.setN(sd.getValue());
}
});
btnRand.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
drawPanel.randPoints();
repaint();
}
});
btnBaoLi.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
drawPanel.setTuBao(baoLiTuBao);
repaint();
}
});
btnQuick.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
drawPanel.setTuBao(quickTuBao);
repaint();
}
});
setVisible(true);
}
public static void main(String[] args) {
try {
UIManager.setLookAndFeel("com.sun.java.swing.plaf.windows.WindowsLookAndFeel");
} catch(Exception e) {
e.printStackTrace();
}
EventQueue.invokeLater(new Runnable() {
public void run() {
GetTuBao getTuBao = new GetTuBao();
}
});
}
} |