/* Calcul de l'enveloppe convexe avec l'algorithme de Graham
 */

package amphis;

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

import javax.swing.JFrame;
import javax.swing.JPanel;

class Point {
  double x, y;
  
  Point(double x, double y) {
    this.x = x;
    this.y = y;
  }

  static int sign(double d) {
    return Math.abs(d) < 1e-9 ? 0 : d < 0 ? -1 : +1;
  }
  
  // de quel côté de la droite orientée (p1p2) se trouve le point p3 ?
  // renvoie -1 : p3 est à droite de (p1p2)
  //          0 : p3 est sur (p1p2)
  //         +1 : p3 est à gauche de (p1p2)
  static int crossProduct(Point p1, Point p2, Point p3) {
    double r = (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
    return sign(r);
  }
  
}

// comparer deux points selon l'angle qu'ils font avec un point p
class AngleComparator implements Comparator<Point> {

  private Point p;
  
  public AngleComparator(Point p) {
    this.p = p;
  }
  
  @Override
  public int compare(Point p1, Point p2) {
    if (p1.y == p.y)
      return p2.y == p.y ? Point.sign(p1.x - p2.x) : -1;
    else if (p2.y == p.y)
      return 1;
    else
      return Point.crossProduct(p, p2, p1);
  }
  
}

// algorithme de Graham pour l'enveloppe convexe

public class ConvexHull {

  static LinkedList<Point> convexHull(Point[] points) {
    assert points.length >= 3;
    // trouver le pivot p = le point le plus bas et le plus à gauche
    Point p = points[0];
    for (Point q: points)
      if (q.y < p.y || q.y == p.y && q.x < p.x)
        p = q;
    // trier les points selon l'angle fait avec le pivot p
    AngleComparator c = new AngleComparator(p);
    Arrays.sort(points, c);
    assert points[0] == p;
    // on ajoute les points
    LinkedList<Point> h = new LinkedList<Point>();
    h.addFirst(p);
    h.addFirst(points[1]);
    for (int i = 2; i < points.length; i++) {
      while (h.size() >= 2 && Point.crossProduct(h.get(1), h.get(0), points[i]) <= 0)
        h.removeFirst();
      h.addFirst(points[i]);
    }
    return h;
  }
    
}

// test, avec affichage graphique

class TestConvexHull extends JFrame {
  private static final long serialVersionUID = 1L;
  
  static final int width = 800, height = 800;
  static final double w = width - 40;
  static final int radius = 10;
  
  private Point[] points;
  LinkedList<Point> hull;
  
  private class Window extends JPanel {
    private static final long serialVersionUID = 1L;

    void drawPoint(Graphics2D g, Point p) {
      int x = (int)(width/2 + p.x);
      int y = (int)(height/2 - p.y);
      g.fillOval(x - radius/2, y - radius/2, radius, radius);
    }
    
    void drawLine(Graphics2D g, Point p1, Point p2) {
      int x1 = (int)(width/2 + p1.x);
      int y1 = (int)(height/2 - p1.y);
      int x2 = (int)(width/2 + p2.x);
      int y2 = (int)(height/2 - p2.y);
      g.drawLine(x1, y1, x2, y2);
    }
    
    @Override
    public void paintComponent(Graphics g) {
      super.paintComponent(g);
      Graphics2D g2d = (Graphics2D) g;
      g.setColor(Color.red);
      for (Point p: points) drawPoint(g2d, p);
      g.setColor(Color.blue);
      for (Point q: points)
        drawLine(g2d, points[0], q);
      g.setColor(Color.red);
      Point p0 = hull.getFirst();
      Point p = p0;
      for (Point q: hull) {
        drawLine(g2d, p, q);
        p = q;
      }
      drawLine(g2d, p, p0);
    }

  }
  
  TestConvexHull(int n) {
    this.points = new Point[n];
    for (int i = 0; i < n; i++)
      points[i] = new Point(-w/2 + Math.random() * w,
                            -w/2 + Math.random() * w);

//    points = new Point[] { new Point(0,0), new Point(0,300), new Point(300,0), new Point(300,300),
//                           new Point(150, 0), new Point(0, 150) };
    
    this.hull = ConvexHull.convexHull(this.points);
    
    this.setTitle("enveloppe convexe");
    this.add(new Window());
    this.setSize(width, height+20);
    this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    this.setLocationRelativeTo(null);
  }
  
  public static void main(String[] args) {
    int n = 42; // Integer.parseInt(args[0]);
    TestConvexHull gui = new TestConvexHull(n);
    gui.setVisible(true);
  }
}