Текст исходников 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);
}
}