01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
package algs91; // section 9.8
import stdlib.*;
import algs12.Point2D;
import algs13.Bag;
/* ***********************************************************************
 *  Compilation:  javac InteractiveConvexHull.java
 *  Execution:    java InteractiveConvexHull
 *  Dependencies: GrahamScan.java Point2D.java StdDraw.java Bag.java
 *
 *************************************************************************/

public class XInteractiveConvexHull {

  public static void main(String[] args) {
    StdDraw.setCanvasSize(800, 800);
    StdDraw.setXscale(0, 10000);
    StdDraw.setYscale(0, 10000);
    StdDraw.show(0);
    Bag<Point2D> bag = new Bag<>();

    while (true) {
      if (StdDraw.mousePressed()) {
        // mouse pressed so add point to list of points
        int x = (int) (Math.round(StdDraw.mouseX()));
        int y = (int) (Math.round(StdDraw.mouseY()));
        bag.add(new Point2D(x, y));

        // extract array of points
        int N = bag.size();
        Point2D[] points = new Point2D[N];
        int n = 0;
        for (Point2D p : bag) {
          points[n++] = p;
        }

        // compute convex hull
        GrahamScan graham = new GrahamScan(points);


        StdDraw.clear();

        // draw the points in black
        StdDraw.setPenRadius(.01);
        StdDraw.setPenColor(StdDraw.BLACK);
        for (int i = 0; i < N; i++)
          points[i].draw();

        // draw the hull points in red
        StdDraw.setPenColor(StdDraw.RED);
        for (Point2D p : graham.hull())
          p.draw();

        // draw the hull line segments in blue
        StdDraw.setPenRadius();
        StdDraw.setPenColor(StdDraw.BLUE);
        Point2D prev = null;
        for (Point2D p : graham.hull()) {
          if (prev != null) prev.drawTo(p);
          prev = p;
        }
        // hack to connect first and last points
        for (Point2D p : graham.hull()) {
          prev.drawTo(p);
          break;
        }
      }
      StdDraw.show(20);
    }

  }

}