Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
16. March 2013 10:04

Mondrian is one of those modern painters whose work everyone recognizes, even though few people will quote his name. He also happens to be one of my favorite artists – in spite of their simple geometric structure, I find his pieces strangely beautiful:

“Composition II in Red, Blue, and Yellow”, from Wikipedia

I have been hard at work on some pretty dry stuff lately, and needed a bit of a change of pace, and ended up spending a couple of hours coding a simple Mondrianizer in F#: give it a picture, and it will transform it into something “in the style of Mondrian”.

For instance, starting from my Twitter avatar, here is what the Mondrianizer produces:

This was strictly quick-and-dirty hackery, so the code is not my best by any stretch of the imagination, but I was rather pleased by the results – you can find the current version of the Mondrianizer here on GitHub.

More...

7. April 2012 10:50

For no clear reason, I got interested in Convex Hull algorithms, and decided to see how it would look in F#. First, if you wonder what a Convex Hull is, imagine that you have a set of points in a plane – say, a board – and that you planted a thumbtack on each point. Now take an elastic band, stretch it, and wrap it around the thumbtacks. The elastic band will cling to the outermost tacks, leaving some tacks untouched. The convex hull is the set of tacks that are in contact with the elastic band; it is convex, because if you take any pair of points from the original set, the segment connecting them remains inside the hull.

The picture below illustrates the idea - the blue thumbtacks define the Convex Hull; all the yellow tacks are included within the elastic band, without touching it.

There are a few algorithms around to identify the Convex Hull of a set of points in 2 dimensions; I decided to go with Andrew’s monotone chain, because of its simplicity.

The insight of the algorithm is to observe that if you start from the leftmost tack, and follow the elastic downwards, the elastic turns only clockwise, until it reaches the rightmost tack. Similarly, starting from the right upwards, only clockwise turns happen, until the rightmost tack is reached. Given that the left- and right-most tacks belong to the convex hull, the algorithm constructs the upper and lower part of the hull by progressively constructing sequences that contain only clockwise turns.

More...

25. March 2012 10:53

In a previous post, I looked at creating a Sierpinski triangle using F# and WPF. One of the pieces I was not too happy about was the function I used to transform a Triangle into a next generation triangle:

type Point = { X:float; Y:float }
type Triangle = { A:Point; B:Point; C:Point }

let transform (p1, p2, p3) =
let x1 = p1.X + 0.5 * (p2.X - p1.X) + 0.5 * (p3.X - p1.X)
let y1 = p1.Y + 0.5 * (p2.Y - p1.Y) + 0.5 * (p3.Y - p1.Y)
let x2 = p1.X + 1.0 * (p2.X - p1.X) + 0.5 * (p3.X - p1.X)
let y2 = p1.Y + 1.0 * (p2.Y - p1.Y) + 0.5 * (p3.Y - p1.Y)
let x3 = p1.X + 0.5 * (p2.X - p1.X) + 1.0 * (p3.X - p1.X)
let y3 = p1.Y + 0.5 * (p2.Y - p1.Y) + 1.0 * (p3.Y - p1.Y)
{ A = { X = x1; Y = y1 }; B = { X = x2; Y = y2 }; C= { X = x3; Y = y3 }}

Per se, there is nothing wrong with the transform function: it takes 3 points (the triangle corners), and returns a new Triangle. However, what is being “done” to the triangle is not very expressive – and the code looks rather ugly, with clear duplication (the exact same operation is repeated on the X and Y coordinates of every point).

Bringing back blurry memories from past geometry classes, it seems we are missing the notion of a Vector. What we are doing here is taking corner p1 of the Triangle, and adding a linear combinations of the edges p1, p2 and p1, p3 to it, which can be seen as 2 Vectors (p2 – p1) and (p3 – p1). Restated that way, here is what the transform function is really doing:

A –> A + 0.5 x AB + 0.5 x AC

A –> A + 1.0 x AB + 0.5 AC

A –> A + 0.5 x AB + 1.0 x AC

In graphical form, the first transformation can be represented as follows:

In order to achieve this, we need to define a few elements: a Vector, obviously, a way to create a Vector from two Points, to add Vectors, to scale a Vector by a scalar, and to translate a Point by a Vector. Let’s do it:

type Vector =
{ dX:float; dY:float }
static member (+) (v1, v2) = { dX = v1.dX + v2.dX; dY = v1.dY + v2.dY }
static member (*) (sc, v) = { dX = sc * v.dX; dY = sc * v.dY }

type Point =
{ X:float; Y:float }
static member (+) (p, v) = { X = p.X + v.dX; Y = p.Y + v.dY }
static member (-) (p2, p1) = { dX = p2.X - p1.X; dY = p2.Y - p1.Y }

type Triangle = { A:Point; B:Point; C:Point }

Thanks to operators overloading, the transform function can now be re-phrased in a much more palatable way:

let transform (p1:Point, p2, p3) =
let a = p1 + 0.5 * (p2 - p1) + 0.5 * (p3 - p1)
let b = p1 + 1.0 * (p2 - p1) + 0.5 * (p3 - p1)
let c = p1 + 0.5 * (p2 - p1) + 1.0 * (p3 - p1)
{ A = a; B = b; C = c }

… and we are done. The code (posted on fsSnip.net) works exactly as before, but it’s way clearer.

It can also be tweaked more easily now. I got curious about what would happen if slightly different transformations were applied, and the results can be pretty fun. For instance, with a minor modification of the transform function…

let transform (p1:Point, p2, p3) =
let a = p1 + 0.55 * (p2 - p1) + 0.5 * (p3 - p1)
let b = p1 + 1.05 * (p2 - p1) + 0.45 * (p3 - p1)
let c = p1 + 0.5 * (p2 - p1) + 0.95 * (p3 - p1)
{ A = a; B = b; C = c }

… we get the following, bloated “Sierpinski triangle”:

Add a bit of transparency, some more tweaks of the linear combinations,

let transform (p1:Point, p2, p3) =
let a = p1 + 0.3 * (p2 - p1) + 0.6 * (p3 - p1)
let b = p1 + 0.8 * (p2 - p1) + 0.3 * (p3 - p1)
let c = p1 + 0.6 * (p2 - p1) + 1.1 * (p3 - p1)
{ A = a; B = b; C = c }

and things get much wilder:

I don’t think these are really Sierpinski triangles any more, but I had lots of fun playing with this, and figured someone else might enjoy it, too… If you find a nice new combination, post it in the comments!

Source code: fsSnip.net

16. March 2012 08:33

In my last post, I looked into drawing a Sierpinski triangle using F# and WinForms, and noted that the rendering wasn’t too smooth – so I converted it to WPF, to see if the result would be any better, and it is. In the process, I discovered John Liao’s blog, which contains some F# + WPF code examples I found very useful. I posted the code below, as well as on FsSnip. The differences with the WinForms code are minimal, I’ll let the interested reader figure that part out!

One thing I noticed is that the starting point of the Sierpinski sequence is a single triangle – but nothing would prevent a curious user to initialize the sequence with multiple triangles. And while at it, why not use WPF Brush opacity to create semi-transparent triangles, and see how their superposition looks like?

We just change the Brush Color and Opacity, and add a second triangle to the root sequence…

let brush = new SolidColorBrush(Colors.DarkBlue)
brush.Opacity <- 0.6
let renderTriangle = render canvas brush

let triangle =
let p1 = { X = 190.0; Y = 170.0 }
let p2 = { X = 410.0; Y = 210.0}
let p3 = { X = 220.0; Y = 360.0}
{ A = p1; B = p2; C = p3 }

let triangle2 =
let p1 = { X = 290.0; Y = 170.0 }
let p2 = { X = 510.0; Y = 210.0}
let p3 = { X = 320.0; Y = 360.0}
{ A = p1; B = p2; C = p3 }

let root = seq { yield triangle; yield triangle2 }

… and here we go:

Granted, it’s pretty useless, but I thought it looked rather nice!

As an aside, here is something I noted when working in F#: I often end up looking at the code, thinking “can I use this to do something I didn’t think about when I wrote it”? In C#, I tend to think in terms of restrictions: write Components, with a “containment” approach – figure out what the component should do, and enforce safety by constraining the inputs/outputs via an interface. By contrast, because of type inference and the fact that a function doesn’t require an “owner” (it is typically not a member of a class), I find myself less “mentally conditioned”, and instead of a world of IWidgets and ISprockets, I simply see functions that transform elements, and wonder what else they could apply to.

The case we saw here was trivial, but pretty much from the moment I wrote that code, I have been mulling over other extensions. What is the transform function really doing, and what other functions could I replace it with? generateFrom is simply permuting the triangle corners and applying the same transformation – could I generalize this to an arbitrary sequence and write Sierpinski Polygons? Could I even apply it to something that has nothing to do with geometry?

// Requires reference to
// PresentationCore, PresentationFramework,
// System.Windows.Presentation, System.Xaml, WindowsBase

open System
open System.Windows
open System.Windows.Media
open System.Windows.Shapes
open System.Windows.Controls

type Point = { X:float; Y:float }
type Triangle = { A:Point; B:Point; C:Point }

let transform (p1, p2, p3) =
let x1 = p1.X + 0.5 * (p2.X - p1.X) + 0.5 * (p3.X - p1.X)
let y1 = p1.Y + 0.5 * (p2.Y - p1.Y) + 0.5 * (p3.Y - p1.Y)
let x2 = p1.X + 1.0 * (p2.X - p1.X) + 0.5 * (p3.X - p1.X)
let y2 = p1.Y + 1.0 * (p2.Y - p1.Y) + 0.5 * (p3.Y - p1.Y)
let x3 = p1.X + 0.5 * (p2.X - p1.X) + 1.0 * (p3.X - p1.X)
let y3 = p1.Y + 0.5 * (p2.Y - p1.Y) + 1.0 * (p3.Y - p1.Y)
{ A = { X = x1; Y = y1 }; B = { X = x2; Y = y2 }; C= { X = x3; Y = y3 }}

let generateFrom triangle = seq {
yield transform (triangle.A, triangle.B, triangle.C)
yield transform (triangle.B, triangle.C, triangle.A)
yield transform (triangle.C, triangle.A, triangle.B)
}

let nextGeneration triangles =
Seq.collect generateFrom triangles

let render (target:Canvas) (brush:Brush) triangle =
let points = new PointCollection()
let polygon = new Polygon()
polygon.Points <- points
polygon.Fill <- brush

let win = new Window()
let canvas = new Canvas()
canvas.Background <- Brushes.White
let brush = new SolidColorBrush(Colors.Black)
brush.Opacity <- 1.0
let renderTriangle = render canvas brush

let triangle =
let p1 = { X = 190.0; Y = 170.0 }
let p2 = { X = 410.0; Y = 210.0}
let p3 = { X = 220.0; Y = 360.0}
{ A = p1; B = p2; C = p3 }

let root = seq { yield triangle }
let generations =
Seq.unfold (fun state -> Some(state, (nextGeneration state))) root
|> Seq.take 7
Seq.iter (fun gen -> Seq.iter renderTriangle gen) generations

win.Content <- canvas
win.Show()

do
let app =  new Application() in
app.Run() |> ignore
11. March 2012 11:29

I am midway through the highly-recommended “Real-world functional programming: with examples in C# and F#”, which inspired me to play with graphics using F# and WinForms (hadn’t touched that one in a long, long time), and I figured it would be fun to try generating a Sierpinski Triangle.

The Sierpinski Triangle is generated starting from an initial triangle. 3 half-size copies of the triangle are created and placed outside of the original triangle, each of them having a corner “touching” the middle of one side of the triangle.

That procedure is then repeated for each of the 3 new triangles, creating more and more smaller triangles, which progressively fill in an enclosing triangular shape. The figure below uses the same starting point, stopped after 6 “generations”:

The Sierpinski Triangle is an example of a fractal figure, displaying self-similarity: if we were to run the procedure ad infinitum, each part of the Triangle would look like the whole “triangle” itself.

So how could we go about creating this in F#?

I figured this would be a good case for Seq.unfold: given a state (the triangles that have been produced for generation n), and an initial state to start from, provide a function which defines how the next generation of triangles should be produced, defining a “virtual” infinite sequence of triangles – and then use Seq.take to request the number of generations to be plotted.

Here is the entire code I used; you’ll need to add a reference to System.Windows.Forms and System.Drawings for it to run:

open System
open System.Drawing
open System.Windows.Forms

type Point = { X:float32; Y:float32 }
type Triangle = { A:Point; B:Point; C:Point }

let transform (p1, p2, p3) =
let x1 = p1.X + 0.5f * (p2.X - p1.X) + 0.5f * (p3.X - p1.X)
let y1 = p1.Y + 0.5f * (p2.Y - p1.Y) + 0.5f * (p3.Y - p1.Y)
let x2 = p1.X + 1.0f * (p2.X - p1.X) + 0.5f * (p3.X - p1.X)
let y2 = p1.Y + 1.0f * (p2.Y - p1.Y) + 0.5f * (p3.Y - p1.Y)
let x3 = p1.X + 0.5f * (p2.X - p1.X) + 1.0f * (p3.X - p1.X)
let y3 = p1.Y + 0.5f * (p2.Y - p1.Y) + 1.0f * (p3.Y - p1.Y)
{ A = { X = x1; Y = y1 }; B = { X = x2; Y = y2 }; C= { X = x3; Y = y3 }}

let generateFrom triangle = seq {
yield transform (triangle.A, triangle.B, triangle.C)
yield transform (triangle.B, triangle.C, triangle.A)
yield transform (triangle.C, triangle.A, triangle.B)
}

let nextGeneration triangles =
Seq.collect generateFrom triangles

let render (target:Graphics) (brush:Brush) triangle =
let p1 = new PointF(triangle.A.X, triangle.A.Y)
let p2 = new PointF(triangle.B.X, triangle.B.Y)
let p3 = new PointF(triangle.C.X, triangle.C.Y)
let points = List.toArray <| [ p1; p2; p3 ]
target.FillPolygon(brush, points)

let form = new Form(Width=500, Height=500)
let box = new PictureBox(BackColor=Color.White, Dock=DockStyle.Fill)
let image = new Bitmap(500, 500)
let graphics = Graphics.FromImage(image)
let brush = new SolidBrush(Color.FromArgb(0,0,0))
let renderTriangle = render graphics brush

let p1 = { X = 190.0f; Y = 170.0f }
let p2 = { X = 410.0f; Y = 210.0f}
let p3 = { X = 220.0f; Y = 360.0f}
let triangle = { A = p1; B = p2; C = p3 }

let root = seq { yield triangle }
let generations =
Seq.unfold (fun state -> Some(state, (nextGeneration state))) root
|> Seq.take 7
Seq.iter (fun gen -> Seq.iter renderTriangle gen) generations

box.Image <- image

do
Application.Run(form)

A few comments on the code. I first define 2 types, a Point with 2 float32 coordinates (float32 chosen because that’s what System.Drawing.PointF takes), , and a Triangle defined by 3 Points. The transform function is pretty ugly, and can certainly be cleaned up / prettified. It takes a tuple of 3 Points, and returns the corresponding transformed triangle, shrunk by half and located at the middle of the p1, p2 edge. We can now build up on this with the nextGeneration function, which takes in a Sequence of Triangles (generation n), transforms each of them into 3 new Triangles and uses collect to “flatten” the result into a new Sequence, generation n+1.

The rendering code has been mostly lifted with slight modifications from Chapter 4 of Real-world functional programming. The render function retrieves the 3 points of a Triangle and create a filled Polygon, displayed on a Graphics object which we create in a form.

Running that particular example generates the following Sierpinski triangle; you can play with the coordinates of the root triangle, and the number of generations, to build your own!

As an aside, I was a bit disappointed by the quality of the graphics; beyond 7 or 8 generations, the result gets fairly blurry. I’ll probably give a shot at moving this to XAML, and see if it’s any better.

As usual, comments, questions or criticisms are welcome!