case class Point2D(x: Int, y: Int) {  
    def < (other: Point2D) = x < other.x || x == other.x && y < other.y;
    
    def isLeftOf(pt1: Point2D, pt2: Point2D): Boolean =
        (pt1.x - x) * (pt2.y - y) - (pt1.y - y) * (pt2.x - x) < 0
        // magic determinant courtest of Jonathan Richard Shewchuk
}

object Utility2D {
    var rand: scala.util.Random = new scala.util.Random()
    
    def randomPoint(maxX: Int, maxY: Int): Point2D =
        new Point2D(Utility2D.rand.nextInt(maxX), Utility2D.rand.nextInt(maxY))

    def randomPoint(minX: Int, minY: Int, maxX: Int, maxY: Int): Point2D =
        new Point2D(Utility2D.rand.nextInt(maxX) + minX, Utility2D.rand.nextInt(maxY) + minY)
    
    def randomPoints(n : Int) : List[Point2D] =
        for (i <- List.range(0, n)) yield randomPoint(100, 100, 200, 200)
}

object SlowConvexHull extends processing.core.PApplet {
  import processing.core._;

  def drawLine(pts: List[Point2D]): Unit = {
      def drawLines(p1: Point2D, p2: Point2D) : Point2D = { line(p1.x, p1.y, p2.x, p2.y); p2 }
      pts.reduceLeft(drawLines);
  }

  override def setup(): Unit = {
    size(400, 400, PConstants.P3D)
    noLoop
  }

  // runs in O(n^2). O(nlogn) is not much harder-- coming soon.
  def slowConvexHull(points: List[Point2D]) = {
      for (pt1 <- points)
        for (pt2 <- points)
            if (pt1 != pt2) {
                def ptLeftOfOrEqual(pt:Point2D) = pt == pt1 || pt == pt2 || pt.isLeftOf(pt1, pt2);
                if (points.forall(ptLeftOfOrEqual)) {
                    line(pt1.x, pt1.y, pt2.x, pt2.y);
                }
            }
  }

  override def draw(): Unit = {
    background(5)

    stroke(255)
    
    var points = Utility2D.randomPoints(50).sort(_<_);
    points foreach {
        case Point2D(x, y) => point(x, y)
    }
    slowConvexHull(points)
  }

  def main(args: Array[String]): Unit = {
    var frame = new javax.swing.JFrame("SlowConvexHull")
    var applet = ProcessingTest
    frame.getContentPane().add(applet)
    applet.init
    frame.pack
    frame.setVisible(true)
  }
}