计算几何求凸包算法的java实现

import java.awt.BorderLayout; import java.awt.Color; import java.awt.FlowLayout; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.Point; import java.awt.RenderingHints; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.event.MouseAdapter; import java.awt.event.MouseEvent; import java.awt.geom.Ellipse2D; import java.nio.ByteOrder; import java.util.ArrayList; import java.util.List; import javax.swing.JButton; import javax.swing.JFrame; import javax.swing.JPanel; import javax.swing.border.EmptyBorder; public class ConvexHull extends JFrame implements ActionListener { JButton jButton = new JButton("开始计算"); PointPanel pointPanel = new PointPanel(); static ConvexHull convexHull; public ConvexHull(){ JPanel contentPanel = (JPanel)getContentPane(); contentPanel.setLayout(new BorderLayout()); contentPanel.setBorder(new EmptyBorder(10, 10, 10, 10)); setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); contentPanel.add(pointPanel,BorderLayout.CENTER); JPanel p2 = new JPanel(); p2.add(jButton, BorderLayout.NORTH); jButton.addActionListener(this); contentPanel.add(p2,BorderLayout.SOUTH); setSize(400,400); setLocation(200,200); setVisible(true); } public static void main(String[] args) { convexHull = new ConvexHull(); } @Override public void actionPerformed(ActionEvent arg0) { List<MyVector> myVectors = convexHull.getTheConvexHull(convexHull.pointPanel.getPointList()); for (int i = 0; i < myVectors.size(); i++) { pointPanel.getGraphics().drawLine(myVectors.get(i).startPoint.x, myVectors.get(i).startPoint.y, myVectors.get(i).endPoint.x, myVectors.get(i).endPoint.y); } } public static List<MyVector> getTheConvexHull(List pointList){ int i = pointList.size(); if(i<3) return null ; List<MyVector>myVectors = new ArrayList<MyVector>(); for(int j=0;j<i;j++){ for(int k = 0;k<i;k++){ MyVector myvector = null; boolean valid = true; // if(k==j)continue; for(int m = 0;m<i;m++){ // if (m==k||m==j) continue; Ellipse2D A =(Ellipse2D) pointList.get(j); Ellipse2D B =(Ellipse2D) pointList.get(k); Ellipse2D C =(Ellipse2D) pointList.get(m); Point startPoint = new Point((int)A.getX(),(int)A.getY()); Point endPoint = new Point((int)B.getX(),(int)B.getY()); Point cPoint = new Point((int)C.getX(),(int)C.getY()); myvector = new MyVector(startPoint, endPoint); if(myvector.lieOnMyLeft(cPoint)){ valid = false; } } if(valid) myVectors.add(myvector); } } return myVectors; } } class PointPanel extends JPanel{ List pointList; Color selectedColor; Ellipse2D selectedPoint; public PointPanel(){ pointList = new ArrayList(); selectedColor = Color.red; addMouseListener(new PointLocater(this)); setBackground(Color.white); } protected void paintComponent(Graphics g) { super.paintComponent(g); Graphics2D g2 = (Graphics2D)g; g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); Ellipse2D e; Color color; for(int j = 0;j < pointList.size();j++){ e = (Ellipse2D)pointList.get(j); if (e == selectedPoint) color = selectedColor; else color = Color.blue; g2.setPaint(color); g2.fill(e); } } public List getPointList(){ return pointList; } public void setSelectedPoint(Ellipse2D e){ selectedPoint = e; repaint(); } public void addPoint(Point p){ Ellipse2D e = new Ellipse2D.Double(p.x, p.y, 3, 3); pointList.add(e); selectedPoint = null; repaint(); } } class PointLocater extends MouseAdapter{ PointPanel pointPanel; public PointLocater(PointPanel pp) { pointPanel = pp; } public void mousePressed(MouseEvent e) { Point p = e.getPoint(); boolean haveSelection = false; List list = pointPanel.getPointList(); Ellipse2D ellipse; for(int j = 0; j < list.size(); j++) { ellipse = (Ellipse2D)list.get(j); if(ellipse.contains(p)) { pointPanel.setSelectedPoint(ellipse); haveSelection = true; break; } } if(!haveSelection) pointPanel.addPoint(p); } }