Текст исходников ConvexTest.java и R2Convex.java (все изменения выделены):
ConvexText.java :
/** * The ConvexTest applet is a graphic test of R2Convex class. * * <applet code="ConvexTest" width=420 height=455> * </applet> * * The applet nees JDK 1.1. * Tested in RedHat Linux 4.2 (JDK 1.1.3 and 1.1.5) and * under Win95, JDK 1.1.5. * */
// //------------------------------------------------------- This is the second programm for examination. It is made by VILenin (with the help of Arty & Cherry & RAF & Diman & Starosta). //------------------------------------------------------- //
import java.awt.*; import java.awt.event.*; import java.applet.Applet; import java.util.Enumeration; import R2Graphics.*; import R2Convex;
public class ConvexTest extends Applet { R2Convex convex; Label areaField; Label perimeterField;
// //----------------------------------------------------- Label massField; //----------------------------------------------------- //
Button addPointButton; Button initButton;
TextField inputPointX; TextField inputPointY;
Rectangle planeRect; Canvas plane;
R2Transformation mapping; // Real coordinates --> pixel coordinates R2Transformation inverseMapping;
// Layout constants static final int leftMargin = 5; static final int topMargin = 5; static final int vertSkip = 5; static final int horSkip = 5; static final int labelWidth = 200; static final int labelHeight = 30; static final int buttonWidth = 100; static final int numberWidth = 60; static final int numberLabelWidth = 20; static final int planeWidth = 2 * labelWidth + horSkip; static final int planeHeight = (planeWidth * 8) / 10;
// Coordinate mapping constants static final double XMIN = -10.; static final double XMAX = 10.; static final double YMIN = XMIN * 0.8; static final double YMAX = XMAX * 0.8;
public static void main(String[] args) { Frame f = new Frame("Convex");
WindowAdapter wa = new WindowAdapter() { public void windowClosing(WindowEvent e) { System.exit(0); } }; f.addWindowListener(wa);
f.setFont(new Font("Helvetica", Font.PLAIN, 14));
// Add menu bar final MenuBar mb = new MenuBar(); f.setMenuBar(mb); final Menu fileMenu = new Menu("File"); final MenuItem quitItem = new MenuItem("Quit"); fileMenu.add(quitItem); mb.add(fileMenu);
ActionListener al = new ActionListener() { public void actionPerformed(ActionEvent e) { // System.out.println("Action " + e); if (e.getActionCommand().equals("Quit")) { System.exit(0); } } }; fileMenu.addActionListener(al);
ConvexTest ct = new ConvexTest(); f.add("Center", ct);
// f.pack(); f.setSize( 2*leftMargin + planeWidth + 10, planeHeight + 3*labelHeight + 4*vertSkip + 2*topMargin + 50 // For menu bar ); f.setLocation(20, 60);
ct.init(); ct.start();
f.setVisible(true); }
public ConvexTest() { convex = new R2Convex(); }
public void init() { setLayout(null);
setFont(new Font("Helvetica", Font.PLAIN, 14)); setBackground(Color.lightGray);
int x = leftMargin; int y = topMargin;
areaField = new Label("Area: "); add(areaField); areaField.setBounds(x, y, labelWidth, labelHeight); x += labelWidth + horSkip;
perimeterField = new Label("Perimeter: "); add(perimeterField); perimeterField.setBounds(x, y, labelWidth, labelHeight); x = leftMargin; y += labelHeight + vertSkip;
// //----------------------------------------------------- massField = new Label("Mass Center:"); add(massField); massField.setBounds(x, y, 2*labelWidth + horSkip, labelHeight); y += labelHeight + vertSkip; //----------------------------------------------------- //
addPointButton = new Button("Add a point"); add(addPointButton); addPointButton.setBounds(x, y, buttonWidth, labelHeight); x += buttonWidth + 2*horSkip;
Label coord = new Label("X:"); add(coord); coord.setBounds(x, y, numberLabelWidth, labelHeight); x += numberLabelWidth + horSkip;
inputPointX = new TextField(); add(inputPointX); inputPointX.setBounds(x, y, numberWidth, labelHeight); x += numberWidth + 2*horSkip;
coord = new Label("Y:"); add(coord); coord.setBounds(x, y, numberLabelWidth, labelHeight); x += numberLabelWidth + horSkip;
inputPointY = new TextField(); add(inputPointY); inputPointY.setBounds(x, y, numberWidth, labelHeight); x += numberWidth + 2*horSkip;
initButton = new Button("Init"); add(initButton); int w = planeWidth + horSkip - x; initButton.setBounds(x, y, w, labelHeight);
x = leftMargin; y += labelHeight + vertSkip;
planeRect = new Rectangle(x, y, planeWidth, planeHeight); plane = new MyPlane(); add(plane); plane.setBounds(planeRect); plane.setBackground(Color.white);
MyMouseAdapter mouseAdapter = new MyMouseAdapter(); plane.addMouseListener(mouseAdapter);
MyActionListener al = new MyActionListener();
// Add action listener for "Add a point" button addPointButton.addActionListener(al); initButton.addActionListener(al); inputPointX.addActionListener(al); inputPointY.addActionListener(al);
// // Initialize the coordinate mapping // double xcoeff = ((double) planeWidth) / (XMAX - XMIN); double ycoeff = ( -((double) planeHeight) / (YMAX - YMIN) ); mapping = new R2Transformation( // Real coord. --> pixel coord. new R2Matrix( xcoeff, 0., 0., ycoeff ), new R2Vect( ((double) planeWidth) / 2., ((double) planeHeight) / 2. ) );
inverseMapping = mapping.inverse(); }
class MyPlane extends Canvas {
public void paint(Graphics g) { // Draw cells double x = 0.; while (x < XMAX) { if (x == 0.) g.setColor(Color.black); // Coord. axis else g.setColor(Color.lightGray);
R2Point p1 = new R2Point(x, YMIN); R2Point p2 = new R2Point(x, YMAX); R2Point q1 = mapping.map(p1); R2Point q2 = mapping.map(p2); g.drawLine( (int)q1.x, (int)q1.y, (int)q2.x, (int)q2.y );
if (x != 0.) { p1.x = (-x); p2.x = (-x); q1 = mapping.map(p1); q2 = mapping.map(p2); g.drawLine( (int)q1.x, (int)q1.y, (int)q2.x, (int)q2.y ); }
x += 1.; }
double y = 1.; while (y < YMAX) { if (y == 0.) g.setColor(Color.black); // Coord. axis else g.setColor(Color.lightGray);
R2Point p1 = new R2Point(XMIN, y); R2Point p2 = new R2Point(XMAX, y); R2Point q1 = mapping.map(p1); R2Point q2 = mapping.map(p2); g.drawLine( (int)q1.x, (int)q1.y, (int)q2.x, (int)q2.y );
if (y != 0.) { p1.y = (-y); p2.y = (-y); q1 = mapping.map(p1); q2 = mapping.map(p2); g.drawLine( (int)q1.x, (int)q1.y, (int)q2.x, (int)q2.y ); }
y += 1.; }
// Draw coordinate axes g.setColor(Color.black); R2Point p1 = new R2Point(0., YMIN); R2Point p2 = new R2Point(0., YMAX); R2Point q1 = mapping.map(p1); R2Point q2 = mapping.map(p2); g.drawLine( (int)q1.x, (int)q1.y, (int)q2.x, (int)q2.y );
p1.x = XMIN; p1.y = 0.; p2.x = XMAX; p2.y = 0.; q1 = mapping.map(p1); q2 = mapping.map(p2); g.drawLine( (int)q1.x, (int)q1.y, (int)q2.x, (int)q2.y );
drawConvex(g); }
private void drawConvex(Graphics g) { int x0 = planeRect.x; int y0 = planeRect.y; g.setColor(Color.red);
Enumeration vertices = convex.elements();
R2Point q0 = new R2Point(); R2Point qPrev = new R2Point();
// The first vertex if (vertices.hasMoreElements()) { R2Point p0 = (R2Point) vertices.nextElement();
// Draw the first point q0 = mapping.map(p0); qPrev = q0; g.drawLine( (int)q0.x, (int)q0.y, (int)q0.x, (int)q0.y ); } else { return; // Convex is empty }
while (vertices.hasMoreElements()) { R2Point p = (R2Point) vertices.nextElement();
// Draw the edge R2Point q = mapping.map(p); g.drawLine( (int)qPrev.x, (int)qPrev.y, (int)q.x, (int)q.y ); qPrev = q; }
// Close the convex g.drawLine((int)qPrev.x, (int)qPrev.y, (int)q0.x, (int)q0.y); g.drawLine( (int)qPrev.x, (int)qPrev.y, (int)q0.x, (int)q0.y ); } }
public void start() {
}
public void run() {
}
// Action listeners class MyActionListener implements ActionListener { public void actionPerformed(ActionEvent e) { Object source = e.getSource(); if (source == addPointButton) { onAddPoint(); } else if (source == initButton) { onInit(); } else if (source == inputPointX || source == inputPointY) { onAddPoint(); } } }
// Mouse listener class MyMouseAdapter extends MouseAdapter { public void mouseClicked(MouseEvent e) { if ((e.getModifiers() & MouseEvent.BUTTON1_MASK) != 0) { // Left mouse button is pressed Point q = e.getPoint(); R2Point p = inverseMapping.map(new R2Point(q)); addPoint(p); } } }
void onAddPoint() { String textX = inputPointX.getText(); String textY = inputPointY.getText();
try {
double x = Double.valueOf(textX).doubleValue(); double y = Double.valueOf(textY).doubleValue(); addPoint(new R2Point(x, y));
} catch (NumberFormatException e) { // System.out.println("Input number: Illegal format: " + e.toString()); return; } }
void addPoint(R2Point t) { convex.add(t); areaField.setText("Area: " + (float) convex.area()); perimeterField.setText("Perimeter: " + (float) convex.perimeter());
// //---------------------------------------------------------- massField.setText("Mass Center. X: " + (float) convex.mass().x + " Y: " + (float) convex.mass().y); //---------------------------------------------------------- //
inputPointX.setText(""); inputPointY.setText("");
plane.repaint(); inputPointX.requestFocus(); }
private void onInit() { convex.init();
areaField.setText("Area:"); perimeterField.setText("Perimeter:");
// //--------------------------------------------------------- massField.setText("Mass Center:"); //--------------------------------------------------------- //
inputPointX.setText(""); inputPointY.setText("");
plane.repaint(); } }
R2Convex :
import java.util.Enumeration; import java.util.NoSuchElementException; import java.util.Vector; import R2Graphics.*;
/** * The R2Convex class computes a convex of a point set on a 2-dimensional plane */ public class R2Convex extends Object { R2Point a; // First vertex of the line segment R2Point b; // Second vertex of line segment int numAngles; // Number of verteces: 0, 1, 2, many ConvexPolygon polygon; // Pointer to polygon
public R2Convex() { a = null; b = null; numAngles = 0; polygon = null; }
public void init() { a = null; b = null; numAngles = 0; polygon = null; }
public double area() { if (numAngles < 3) { return 0.; } else { return polygon.area(); } }
public double perimeter() { if (numAngles < 2) { return 0.; } else if (numAngles == 2) { return 2. * a.distance(b); } else { return polygon.perimeter(); } }
// //----------------------------------------------------------- public R2Point mass() { Enumeration points = elements(); int n = 0; //Quantity of points R2Point sum = new R2Point(0., 0.); //The summ of points
while(points.hasMoreElements()) { sum = sum.add((R2Point) points.nextElement()); n++; }
return new R2Point(sum.x/n, sum.y/n); } //----------------------------------------------------------- //
public void add(R2Point t) { if (numAngles == 0) { numAngles++; a = t; } else if (numAngles == 1) { if (!t.equals(a)) { numAngles++; b = t; } } else if (numAngles == 2) { if (!t.onLine(a, b)) { polygon = new ConvexPolygon(a, b, t); numAngles++; } else if (a.between(t, b)) { a = t; } else if (b.between(a, t)) { // b between a and t b = t; } } else { // Pass the request to polygon polygon.add(t); } }
// Enumeration of convex elements class R2ConvEnum extends Object implements Enumeration { private int curPoint = 0;
public boolean hasMoreElements() { return curPoint < numAngles; }
public Object nextElement() throws NoSuchElementException { R2Point p; if (curPoint < numAngles) { if (curPoint == 0) p = a; else p = b; curPoint++; return p; } else { throw new NoSuchElementException( "No more points in the convex" ); } } }
public final synchronized Enumeration elements() { if (numAngles <= 2) { return new R2ConvEnum(); } else { return polygon.elements(); } } }
class ConvexPolygon extends Object { double polygonArea; double polygonPerimeter; Deq deq;
public ConvexPolygon(R2Point a, R2Point b, R2Point c) { // Put point in deq in order (p1, p2, p3) such that // p3-->p1 is not lit from p2. It implies that // p1-->p2 is not lit from p3 and p2-->p3 is not lit from p1, // i.e. the triangle edges are not lit from triangle inner points. deq = new Deq(); deq.pushBeg(b); if (lit(a, c, b)) { deq.pushBeg(a); deq.pushEnd(c); } else { deq.pushBeg(c); deq.pushEnd(a); }
polygonPerimeter = a.distance(b) + b.distance(c) + c.distance(a); polygonArea = a.area(b, c); // Triangle area }
public double area() { return polygonArea; }
public double perimeter() { return polygonPerimeter; }
public void add(R2Point t) { int i; R2Point x;
// Look up the lit edge for (i = 0; i < deq.size(); i++) { if (lit((R2Point) deq.end(), (R2Point) deq.beginning(), t)) break; // Rotate the polygon deq.pushEnd( deq.popBeg() ); }
// If current edge is not lit, then nothing to do :-) if (!lit((R2Point) deq.end(), (R2Point) deq.beginning(), t)) return;
// Assertion: current edge is lit from the point t.
// Delete the current edge // (i.e. modify polygonArea and polygonPerimeter) deleteEdge((R2Point) deq.end(), (R2Point) deq.beginning(), t);
// Delete lit edges from the beginning of deq x = (R2Point) deq.popBeg(); while (lit(x, (R2Point) deq.beginning(), t)) { deleteEdge(x, (R2Point) deq.beginning(), t); x = (R2Point) deq.popBeg(); } deq.pushBeg(x);
// Delete lit edges from the end of deq x = (R2Point) deq.popEnd(); while (lit((R2Point) deq.end(), x, t)) { deleteEdge((R2Point) deq.end(), x, t); x = (R2Point) deq.popEnd(); } deq.pushEnd(x);
polygonPerimeter += t.distance((R2Point) deq.beginning()) + t.distance((R2Point) deq.end());
deq.pushBeg(t); }
/** * The edge a-->b is lit from a point t. * Returns true, if a triangle <a, b, t> is * counterclockwise oriented. */ private static boolean lit(R2Point a, R2Point b, R2Point t) { double triangArea = t.signedArea(a, b); return ( triangArea < (-R2Point.PRESIZION) || ( Math.abs(triangArea) <= R2Point.PRESIZION && ! t.between(a, b) ) ); }
/** * Modify the area and perimeter after deleting of the edge a-->b, * when adding a new vertex t. */ private void deleteEdge(R2Point a, R2Point b, R2Point t) { polygonPerimeter -= a.distance(b); polygonArea += t.area(a, b); }
/** * Enumeration of polygon vertices */ public final synchronized Enumeration elements() { return deq.elements(); } }
/** * DEQ (Double-Ended Queue) */ class Deq extends Object { static final int DEQ_INITIAL_SIZE = 1024; int numElements = 0; int beg = 0; // Index of beginning int end = (-1); // Index of end Vector elementsArray = null; int maxSize = 0;
public Deq() { maxSize = DEQ_INITIAL_SIZE; elementsArray = new Vector(maxSize); // Set initial max. size of Deq elementsArray.setSize(maxSize); removeAllElements(); }
public Deq(int initialMaxSize) { maxSize = initialMaxSize; elementsArray = new Vector(maxSize); // Set initial max. size of Deq elementsArray.setSize(maxSize); removeAllElements(); }
public void removeAllElements() { numElements = 0; beg = 0; end = maxSize - 1; }
public boolean empty() { return numElements == 0; }
public int size() { return numElements; }
private int nextIndex(int i) { if (i < maxSize - 1) return (i + 1); else return 0; }
private int prevIndex(int i) { if (i > 0) return (i - 1); else return maxSize - 1; }
private void extendDeq() { // Make maximal size of deq larger elementsArray.setSize(2 * maxSize); for (int i = 0; i < beg; i++) { elementsArray.setElementAt( elementsArray.elementAt(i), maxSize + i ); } end = beg + maxSize - 1; maxSize *= 2; }
public void pushBeg(Object p) { if (numElements >= maxSize) extendDeq(); beg = prevIndex(beg); elementsArray.setElementAt(p, beg); numElements++; }
public void pushEnd(Object p) { if (numElements >= maxSize) extendDeq(); end = nextIndex(end); elementsArray.setElementAt(p, end); numElements++; }
public Object popBeg() throws DeqException { if (empty()) { throw new DeqException("Deq is empty"); } Object p = elementsArray.elementAt(beg); beg = nextIndex(beg); numElements--; return p; }
public Object popEnd() throws DeqException { if (empty()) { throw new DeqException("Deq is empty"); } Object p = elementsArray.elementAt(end); end = prevIndex(end); numElements--; return p; }
public Object beginning() throws DeqException { if (empty()) { throw new DeqException("Deq is empty"); } return elementsArray.elementAt(beg); }
public Object end() throws DeqException { if (empty()) { throw new DeqException("Deq is empty"); } return elementsArray.elementAt(end); }
/* * Enumeration of DEQ elements */ class DeqEnum extends Object implements Enumeration { int curPoint; int elementNumber;
public DeqEnum() { curPoint = beg; elementNumber = 0; }
public boolean hasMoreElements() { return (elementNumber < numElements); }
public Object nextElement() throws NoSuchElementException { if (curPoint != nextIndex(end)) { Object p = elementsArray.elementAt(curPoint); curPoint = nextIndex(curPoint); elementNumber++; return p; } else { throw new NoSuchElementException( "No more points in the DEQ" ); } } }
public final synchronized Enumeration elements() { return new DeqEnum(); } }
class DeqException extends RuntimeException { public DeqException() {} public DeqException(String reason) { super(reason); } }