Skip to content

Instantly share code, notes, and snippets.

@mmakowski
Created April 26, 2010 06:07
Show Gist options
  • Save mmakowski/379028 to your computer and use it in GitHub Desktop.
Save mmakowski/379028 to your computer and use it in GitHub Desktop.
// concepts:
// - functional style: higher-order functions, type aliases
// - testing in REPL
object AreaCalculatorApp {
def main(args: Array[String]) = println(area(readVertices(args(0))))
type Vertex = (Double, Double)
def area(vertices: Seq[Vertex]) = triangulate(vertices) map(triangleArea _) sum
def triangulate(vertices: Seq[Vertex]) = vertices match { case a :: b :: c :: t => t.foldLeft(List((a, b, c)))(nextTriangle _) }
type Triangle = (Vertex, Vertex, Vertex)
def nextTriangle(prevTriangles: List[Triangle], d: Vertex) = prevTriangles last match { case (a, b, c) => prevTriangles :+ (a, c, d) }
def triangleArea(triangle: Triangle) = triangle match {
case (a, b, c) => math.abs(a._1 * b._2 - a._1 * c._2 + b._1 * c._2 - b._1 * a._2 + c._1 * a._2 - c._1 * b._2) / 2
}
def readVertices(path: String) = toVertices(fileContentsAsSeqOfDoubles(path))
def fileContentsAsSeqOfDoubles(path: String) = (io.Source fromPath(path) mkString) split("\\s") filter(_.length > 0) map(_.toDouble)
def toVertices(coords: Seq[Double]) = coords grouped(2) map((p: Seq[Double]) => (p(0), p(1))) toSeq
}
@mmakowski
Copy link
Author

The Problem

A convex polygon is given by the list of the coordinates of it's vertices where the vertices appear in clockwise order; e.g.
0 0
0 1
1 0
1 1
represents a 1x1 square. We need to calculate the area of this polygon.

A convex polygon can be trivially triangulated [draw a picture]. There is a well-known formula for calculating the area of a triangle given it's vertex coordinates: http://en.wikipedia.org/wiki/Triangle#Using_coordinates

Compiling and running an app

[show how to compile a file using scalac and how to run it using scala]

App structure

a singleton object with a main(Array[String]): Unit method is an application

Higher-order methods

  • fileContentsAsSeqOfDoubles(): filter() takes a predicate
  • toVertices(): the argument to map is a function written as a literal: (args) => body
    The operator syntax allows to omit dots when calling methods.

Type aliases

Instead of writing (Vertex, Vertex, Vertex) we can write Triangle -- it refers to the same type

Methods as function values

area(): in triangleArea _ the underscore turns a method into a function value which can be passed to higher-order methods/functions (partial application)

Testing in REPL

  • :load AreaCalculator.scala
  • import AreaCalculatorApp._
  • val dl = fileContentsAsSeqOfDoubles("square1.txt")
  • val vs = toVertices(dl)
  • area(vs)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment