Graham’s Scan in Scala

Sometimes my job throws an interesting problem my way.  This week I was presented with a very odd geometry problem 🙂

I needed to generate KML files from geographic data and one of my requirements was to represent certain geographic areas as polygons, the vertices of which would be supplied (along with the rest of the data) by another OSGi service running elsewhere.  Seems fairly straightforward — In KML, the vertices of a polygon are usually specified as follows:


The coordinates tag requires at least four longitude/latitude/altitude triples to be specified, with the last coordinate being the same as the first.   Here is where the problem comes in — The order in which these coordinates are specified matters (they must be specified in counter-clockwise order).  To mix up the order of the coordinates would have unpredictable results (e.g. crazy geometric shapes) when the data is later displayed via Google Earth (or some other application that supports KML files).  However, the area vertices are indeed fed to my KML generator in no particular order (and the services providing the data cannot be changed to guarantee a particular ordering).

So… how do I put the points in order?  “Surely this is a solved problem.”  I thought, turning to the all-knowing internet.  A bit of searching turned up an algorithm called Graham’s Scan.  Basically, this algorithm takes a bag of random coordinates and generates a convex hull with vertices defined in counter-clockwise order (Note: This may not be suitable if you’re trying to faithfully recreate complex geometries, fortunately I’m mostly concerned with rectangular areas).  Roughly, the algorithm works as follows:

  1. Find the coordinate with the lowest y-value.
  2. Sort the remaining points by the polar angle between the line defined by the current point and the point found in step 1, and the x-axis.
  3. Go through the list, evaluating 3 points at a time (you’re concerned with the angle of the turn made by the two resulting line segments).  Eliminate any non counter-clockwise turns (i.e., non-convex corners).

I found several example implementations for this algorithm in various languages: C++, Java, etc.  Since I’m coding this up in Scala, I wasn’t too happy with any of those, and I couldn’t find an example in Scala to rip off draw inspiration from.  However, I did manage to find an implementation in Haskell which I used as a rough guide.  Anyway, here’s my attempt at Graham’s Scan in Scala:

type Coordinate = (Double, Double) //Longitude, Latitude

  protected def processArea(coords: List[Coordinate]): List[Coordinate] = {
      //returns > 0 if points form a counter clockwise turn, 
      // < 0 if clockwise, and 0 if collinear
      def ccw(p1: Coordinate, p2: Coordinate, p3: Coordinate) =
        (p2._1 - p1._1)*(p3._2 - p1._2) - (p2._2 - p1._2)*(p3._1 - p1._1)

      //Scan the List of coordinates and find our vertices
      def scan(theCoords: List[Coordinate]): List[Coordinate] = theCoords match {
        case xs if xs.isEmpty => List()
        case xs if xs.size == 2 => theCoords
        case x::y::z::xs if ccw(x,y,z) > 0 => x::scan(y::z::xs)
        case x::y::z::xs => scan(x::z::xs)
      //find the coordinate with the lowest latitude
      val origin = coords.minBy(_._2)
      //sort the rest of the points according to their polar angle (the angle between the line
      //defined by the origin and the current point, and the x-axis)   
      val coordList = origin :: coords.filterNot(_ == origin).
        sortBy(point => atan2(point._2 - origin._2, point._1 - origin._1))
      //do the graham scan

I think you’ll find that’s a bit shorter than some of the imperative language implementations out there 🙂

4 thoughts on “Graham’s Scan in Scala

  1. Interesting. Don’t believe I noted that in my testing, but then I’m not having to deal with a very large number of points for my particular problem. But I’m definitely curious now, so I’m looking at it.

    In my final implementation, I did have to make some changes to this for geometries that straddled the anti-meridian (-180/180 longitude). This algorithm definitely did not deal well with that situation, but that’s a special case that people using a normal, cartesian coordinate system wouldn’t run into.


  2. You mean points with the same X? That should be taken care of with the isLeft function, you only take the middle point if there is a left angle, ditch it otherwise…


  3. No, the issue came up when displaying areas in something like google earth. An area that straddled the anti-meridian (roughly the international date line), wouldn’t display correctly, because the coordinate system abruptly went from -180.0 to 180.0 at that line. The solution was to split such polygons into two smaller ones, which was quite involved code-wise and involved calculating and adding new points.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s