package yi.graph.polygon;

import java.util.*;

import java.awt.*;
import yi.util.io.*;

/**
 * The main algorithm is translated from:
 * Andrew's Convex Hull Algorithm:
 * http://nms.lcs.mit.edu/~aklmiu/6.838/convexhull/
 * Given some vertex, return the minimum convex polygon covers all the vertex
 */

public class ConvexPolygon{

  /**
   * The last vertex is the same as the first one (closed contour)
   */
  protected Vertexes m_vertexes =  new Vertexes();

  public ConvexPolygon() {
  }

  /**
   * Check if last 3 nodes (r, p, q) makes a right turn.  User is responsible
   * for making sure that there are at least 3 elements in the passing-in
   * vertexes.
   * @param n
   * @return
   */
  private boolean rightTurn(Vertexes n) {
    Point r = (Point) n.elementAt(n.size() - 3);
    Point p = (Point) n.elementAt(n.size() - 2);
    Point q = (Point) n.elementAt(n.size() - 1);

    int det = (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x);
    return det < 0;
  }

  public ConvexPolygon(Vertexes input) {
    input = input.sort();

    if (input.size() == 0) {
      return;
    }

    Vertexes upper = new Vertexes();
    upper.addElement(input.elementAt(0));

    if (input.size() < 2) {
      m_vertexes = upper;
      return;
    }

    upper.addElement(input.elementAt(1));

    if (input.size() < 3) {
      m_vertexes = upper;
      return;
    }

    for (int i = 2; i < input.size(); i++) {
      upper.addElement(input.elementAt(i));
      while (upper.size() > 2 && rightTurn(upper)) {
        upper.removeElementAt(upper.size() - 2);
      }
    }

    Vertexes lower = new Vertexes();
    lower.addElement(input.elementAt(input.size() - 1));
    lower.addElement(input.elementAt(input.size() - 2));
    for (int i = input.size() - 3; i >= 0; i--) {
      lower.addElement(input.elementAt(i));
      while (lower.size() > 2 && rightTurn(lower)) {
        lower.removeElementAt(lower.size() - 2);
      }
    }
    // return
    lower.removeElementAt(0);
    //lower.removeElementAt(lower.size()-1);
    for (int i = 0; i < lower.size(); i++)
      upper.addElement(lower.elementAt(i));

    m_vertexes = upper;

  }

  public Vertexes getVertexes() {
    return m_vertexes;
  }

  public String toString() {
    StringBuffer buf = new StringBuffer();

    buf.append("vertics = " + (m_vertexes.size()));
    buf.append(" {");
    for (int i=0; i<m_vertexes.size(); i++) {
      Point p = (Point)m_vertexes.elementAt(i);
      if (i!=0) buf.append(" ,");
      buf.append("(" + p.x + ", " + p.y + ")");
    }
    buf.append("}");

    return buf.toString();
  }

  public static void main(String[] args) {
    Vertexes vertexes = new Vertexes();
    vertexes.add(new Point(0,0));
    vertexes.add(new Point(5,0));
    vertexes.add(new Point(0,5));
    vertexes.add(new Point(6,6));
    vertexes.add(new Point(4,4));
    ConvexPolygon poly = new ConvexPolygon(vertexes);
    System.out.println(poly);
    GenericContour gpoly = new GenericContour(poly);
    System.out.println(gpoly);
    System.out.println("area = " + gpoly.getArea());
    System.out.println("area = " + gpoly.getCentroid());
  }
}
