Skip to main content

A Geometry Problem in Scala

Posted by cayhorstmann on November 12, 2010 at 6:04 AM PST

I ran into this blog about making a pretty drawing in C# and F#.

The task is to draw all lines between n evenly spaced points on a circle.

The solution in C# is surprisingly hard to read because it intermixes control flow with the details of the graphics processing. The author's attempt at a “functional” version just translated the iterations to recursion, and it wasn't really any simpler. I figured that I could do better in Scala. (Someone else contributed a much more functional version, and it is along the same lines as my Scala solution.)

Here is how I approached it.

First, I figured that I needed a way of getting all pairs (i,j) of numbers 0 ≤ i < j < n. That's easy.

def pairs(n : Int) = for (i <- 0 until n; j <- 0 until n; if i < j) yield (i, j)

For example, pairs(4) is

Vector((0,1), (0,2), (0,3), (1,2), (1,3), (2,3))

I also need to get the actual points.

The ith point of an n-gon on a unit circle is (cos(2πi / n), sin(2πi / n). If we aren't on a unit circle but in a square of a given width, then we need to transform, like this:

def point(i : Int, n : Int, width : Int) = 
  (((cos(2 * Pi * i / n) + 1) * width / 2).toInt,
   ((sin(2 * Pi * i / n) + 1) * width / 2).toInt)

All points are

val points = for (i <- 0 until n) yield point(i, n, width)

To get the lines, I have to look up the first and second point for each pair.

val lines = for ((i, j) <- pairs(n)) yield (points(i), points(j))

Finally, I need to draw them all. Let's assume that we can draw lines with a draw function.

for (((x1, y1), (x2, y2)) <- lines) line(x1, y1, x2, y2)

In the nifty SPDE environment (a Processing clone for Scala), you can do just that. Here is the complete SPDE program:

import math._

size(400, 400)

def pairs(n : Int) = for (i <- 0 until n; j <- 0 until n; if i < j) yield (i, j)

def point(i : Int, n : Int, width : Int) =
  (((cos(i * 2 * Pi / n) + 1) * width / 2).toInt,
   ((sin(i * 2 * Pi / n) + 1) * width / 2).toInt)

def draw {
  val n = 19
  val points = for (i <- 0 until n) yield point(i, n, width)
  val lines = for ((i, j) <- pairs(n)) yield (points(i), points(j))
  for (((x1, y1), (x2, y2)) <- lines) line(x1, y1, x2, y2)
}

Very nice: Two helper functions and three lines of data transformations. (Note how pattern matching in the for loop is our friend.)

What does it all mean? Looking at the iterative solution, it seems as if the implementor was focused on getting the nested loops right. With Scala, I wanted to get the data right. I knew that, once I had the lines, I could call

for (... <- lines) line(...) 

How could I get all the lines? I needed to get all the points. Then I needed to join them into pairs. Each of these steps is an easy transformation. So, the entire computation comes down to a sequence of data transformations.

Is this a reason to switch from Java or C# to Scala or F#? By itself, of course, it is not.

But now look at the Processing web site and all the nifty drawings that you can make with a few lines of Processing code. Nice, but you have to learn yet another domain-specific language. That's a waste. With Scala, you just learn one language. Together with SPDE, Scala becomes your DSL for drawing, and your investment is repaid.

Related Topics >>

Comments

A Geometry Problem in Scala

Yes, well said aberrant. The same approach can be applied in all kinds of different languages. Please forgive me for posting a little C# on a Java site, but here is a fairly direct port of the Scala code to C#. I've formatted the code for brevity (it wouldn't pass the coding standards we use at work!). I could have made it a little more like the Scala code by using delegates, although I must admit that 'yield' in C# is quite limited and can't be used within closures (anonymous methods or lambda expressions). Also, I've omitted the type definitions for Size, Pair, Point and Line. I wrote the original code to draw onto a WPF canvas which took six more lines of code.
class CompleteGraph
{
private Size size = new Size(400, 400);
public void Draw(Canvas canvasPanel)
{
var n = 19;
foreach (var line in this.GetLines(n))
{
DrawLine(line); // assume we can draw lines with this method call
}
}
private IEnumerable<Pair> GetPairs(int n)
{
for (var i = 0; i <= n; i++)
for (var j = 0; j <= n; j++)
if (i < j)
yield return new Pair(i, j);
}
private IEnumerable<Point> GetPoints(int n)
{
for (var i = 0; i <= n; i++)
yield return NewPoint(i, n, size.B);
}
private IEnumerable<Line> GetLines(int n)
{
foreach (var pair in GetPairs(n))
foreach (var start in GetPoints(n))
foreach (var end in GetPoints(n))
yield return new Line(start, end);
}
private Point NewPoint(int i, int n, double width)
{
return new Point(Convert.ToInt32(((Math.Cos(2 * Math.PI * i / n ) + 1) * width / 2)),
Convert.ToInt32(((Math.Sin(2 * Math.PI * i / n ) + 1) * width / 2)));
}
}

A Geometry Problem in Scala

Yes, well said aberrant. The same approach can be applied in all kinds of different languages. Please forgive me for posting a little C# on a Java site, but here is a fairly direct port of the Scala code to C#. I've formatted the code for brevity (it wouldn't pass the coding standards we use at work!). I could have made it a little more like the Scala code by using delegates, although I must admit that 'yield' in C# is quite limited and can't be used within closures (anonymous methods or lambda expressions). Also, I've omitted the type definitions for Size, Pair, Point and Line. I wrote the original code to draw onto a WPF canvas which took six more lines of code.
class CompleteGraph
{
private Size size = new Size(400, 400);
public void Draw(Canvas canvasPanel)
{
var n = 19;
foreach (var line in this.GetLines(n))
{
DrawLine(line); // assume we can draw lines with this method call
}
}
private IEnumerable<Pair> GetPairs(int n)
{
for (var i = 0; i <= n; i++)
for (var j = 0; j <= n; j++)
if (i < j)
yield return new Pair(i, j);
}
private IEnumerable<Point> GetPoints(int n)
{
for (var i = 0; i <= n; i++)
yield return NewPoint(i, n, size.B);
}
private IEnumerable<Line> GetLines(int n)
{
foreach (var pair in GetPairs(n))
foreach (var start in GetPoints(n))
foreach (var end in GetPoints(n))
yield return new Line(start, end);
}
private Point NewPoint(int i, int n, double width)
{
return new Point(Convert.ToInt32(((Math.Cos(2 * Math.PI * i / n ) + 1) * width / 2)),
Convert.ToInt32(((Math.Sin(2 * Math.PI * i / n ) + 1) * width / 2)));
}
}

A Geometry Problem in Scala

I am not sure I understand GetLines--isn't it going to yield each line n * (n -1) times?

A Geometry Problem in Scala

Okay I'm just a little confused. Yes the original C# was verbose but I think we can attribute most of that to the AutoCAD api. In just about 11 lines of Java code (for the drawing logic) I can implement your example using just plain old Java2D. Also I'd like to point out to everyone that the magic number here is 19. That image with it's 'empty inner circle' is just an artifact of dividing the circle into an odd number of points and not any special programmatic behavior. If you ran the same code with 20 points it would certainly cross in the middle.Examples: 7 points,15 points,19 points, 20 points. I'm not really trying to bash Scala here, I just don't believe simple exercises like this can really give you any indication as to the power of a language. I'm still waiting for someone to write something trivial in Scala that's not also trivial in just plain old Java.

A Geometry Problem in Scala

Yes, but you draw every line twice :-)
In the functional program, it is perhaps more "in your face" how many lines are drawn. pairs(n) has n * (n - 1) / 2 elements, and so has lines.
So, perhaps the problem isn't quite as trivial as it appears. Still, I agree that one shouldn't make too much of it. I just wanted to ponder the difference between the nested loops and the functional approach in this simple example. Like I said, it's not a reason to switch to Scala.

A Geometry Problem in Scala

Ahh, you got me. I'll fix my attempt.
Fixed. Still not so bad.