Delaunay triangulation: hitting an impasse

During the recent weeks, I have been making slow but steady progress implementing Delaunay triangulation with the Bowyer-Watson algorithm. However, as I mentioned in the conclusion of my previous post, I spotted a bug, which I hoped would be an easy fix, but so far no such luck: it has me stumped. In this post, I will go over how I approached figuring out the problem, which is interesting in its own right. My hope is that by talking it through I might either get an idea, or perhaps someone else will spot what I am missing!

Anyways, let’s get into it. Per the Wikipedia entry:

a Delaunay triangulation […] of a set of points in the plane subdivides their convex hull into triangles whose circumcircles do not contain any of the points; that is, each circumcircle has its generating points on its circumference, but all other points in the set are outside of it. This maximizes the size of the smallest angle in any of the triangles, and tends to avoid sliver triangles.

The Bowyer-Watson algorithm seemed straightforward to implement, so that’s what I did. For those interested, my current code is here, and it mostly works. Starting from a list of 20 random points, I can generate a triangulation like so:

let points =
    let rng = Random 0
    List.init size (fun _ ->
        {
            X = rng.NextDouble() * 100.
            Y = rng.NextDouble() * 100.
        }
        )
points
|> BowyerWatson.delaunay

With a bit of tinkering, I can render the result using SVG:

This looks like what I would expect: all the points are connected in a mesh of triangles.

Delaunay triangulation: Bowyer-Watson algorithm

In my last two posts, I did a bit of prep work leading to an implementation of the Bowyer-Watson algorithm. Now that we have the geometry building blocks we need, we can attack the core of the algorithm, and perform a Delaunay triangulation on a list of points.

Rather than attempt to explain what a Delaunay triangulation is, I will leave that out, and simply illustrate on an example. Starting from a collection of 20 random points, like so:

let points =
    let rng = Random 0
    List.init 20 (fun _ ->
        {
            X = rng.NextDouble() * 100.
            Y = rng.NextDouble() * 100.
        }
        )

… their Delaunay triangulation produces something like this: a mesh of triangles connecting all the points, without any edges crossing each other, and where the triangles have “reasonably even” angles:

The Bowyer-Watson algorithm is one way to generate such a triangulation. In this post, I’ll go over implementing it in F#.

Delaunay triangulation with Bowyer-Watson: circumcircle

In my last installment, I started revisiting some old code of mine around Delaunay triangulation, the dual of a Voronoi diagram. My goal is to implement the Bowyer–Watson algorithm, and perhaps use it for procedural map generation at some point.

I will follow the pseudo-code outlined on the Wikipedia page, and work my way through it. Last time I took care of the initialization step, computing an initial super-triangle large enough to completely contain all the points:

function BowyerWatson (pointList)
    triangulation := empty triangle mesh data structure
    add super-triangle to triangulation

Today I will tackle the next step:

for each point in pointList do
    badTriangles := empty set
    for each triangle in triangulation do
        if point is inside circumcircle of triangle
            add triangle to badTriangles

Delaunay triangulation with Bowyer-Watson: initial super triangle

A while ago, I got interested in Delaunay triangulation, because it seemed to be a good building block for procedural map generation, city maps in particular. I started implementing the Bowyer–Watson algorithm, but ended up putting this side-project on ice, because, well, life got busy. I had something messy somewhat working back then, and figured it would be fun to revisit that code and try to get it into shape.

In this post, I’ll revisit one minor piece of the algorithm that seemed easy, but gave me some trouble: the calculation of the so-called “super triangle”.

The algorithm is quite interesting. The first step is to compute a triangle that contains all the points we want to triangulate, adding points one by one and updating the triangulation, until there is nothing left to add. At that point, the initial triangle and anything connected to it is removed, and the triangulation is done.

Super Triangle

What I am after here is fairly simple: given a collection of points on the plane, find 3 points (the super triangle) that enclose every point in the list.

Let’s illustrate with an example. Suppose we have 5 points, like in the example below. The triangle ABC in yellow is a valid super triangle:

Async Commands with Avalonia FuncUi

Another Avalonia FuncUI post this week! One problem I struggled with initially with Avalonia FuncUI is how to handle async calls. I had some familiarity with the Elmish Cmd.OfAsync module, and wanted to use that if possible (Maxime Mangel has a great post on Cmd and how to use them, if you are curious).

Anyways, using Cmd.OfAsync and its cousin Cmd.OfTask in Avalonia FuncUI is what we will cover in today’s installment!

Without further due, let’s dive in, starting with a very basic example, without anything async to begin with. Our example app will have just a TextBox, where the text of a “Request” can be entered, and a Button, which will send the “Request”, and return a “Response”, a string, which we will display back to our user.

We’ll start synchronous, and work our way up to asynchronous commands.