Rambler's Top100  

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