Correcting an additive correction model

As part of a project I am working on, I ran into a small issue that, while not of consequence, bothered me. Being prone to obsessing over details, I ended up digging into it to figure out if I could address the issue. In this post, I will go over the solution I ended up with.

In a nutshell, here is the problem. Suppose you are working on an application where you need information such as “how long does it take to go from point A to point B”. You have an external service available, which you can call to get estimates. So far, so good.

Now suppose that you look at the data, and realize that the time it takes to go from A to B depends on when the trip takes place. This is not entirely unexpected. Roads are typically busier at certain times of the day, or certain days of the week.

To avoid getting bogged down in unimportant details, let’s simplify a bit, and ignore the time of the day part. You look at the data, and notice that trips taking place on different days of the week behave differently.

As an example, you might observe something like “on Mondays, trips take 1 extra minute on average than what the service predicts; on Sundays, trips take 2 minutes less on average.”

An easy way to model this would be to layer a simple correction on top of the estimate you obtain from the service, adding an error correction value (a bias term), based on the day of the week, along these lines:

let driveTime (origin, destination, dateTime) =
    // use the external service to get a baseline
    let estimate = averageDriveTime(origin, destination)
    // get a correction for the day of the week
    let correction = dayCorrection dateTime
    // apply the correction
    estimate + correction

So for instance, a trip predicted to last 7 minutes taking place on a Sunday would end up being corrected to 7 minutes - 2 minutes = 5 minutes. Converserly, the same trip happening on a Monday would be predicted to take 7 minutes + 1 minute = 8 minutes. Simple enough.

Drawing mountains: shadows

After a couple of weeks of hiatus (sometimes, actual work needs to get done), we are back to our pointless but fun weekend project: drawing mountains in a style similar to topographic maps, using shadows to hint at the relief. We are pretty certain that this must be a solved problem. We aren’t particularly interested in the result: this is more of an excuse to understand lights, and do a bit of geometry.

As a recap and a teaser, we left off with a simple illumination model, where the tiles that represent our terrain were lighter or darker, depending on how much direct light they received:

This isn’t too bad, but it misses an important element: the shadow cast by the mountains. After our latest changes, this is how things look - much more satisfying:

Drawing mountains: direct light

Now that we have are setup to draw SVG on a page with Bolero, we can go back to our main quest: drawing mountains in a style similar to topographic maps, using shading to hint at the relief. In this post, I will go over how I approached computing the effect of light on a terrain.

This post will be heavy on geometry, so let’s start with a teaser, showing the result first:

Drawing mountains: setting up Bolero

With a return to dungeon master duties, making maps has made a come back in my weekend activities, and I started revisiting an old side-project of mine, drawing mountains in a style similar to topographic maps. The aspect I am mostly interested in is not the contour lines, but rather the usage of shadows to visualize the relief.

My goal here is as follows: given a grid of altitudes describing a terrain, can I draw it and suggest the relief by rendering the shadows of mountains?

I am pretty certain that there must exist solutions to this. I am less interested in the result than in understanding lights and shadows. In other words, this project is entirely pointless, except as an exploration exercise!

In aprevious series of posts, I used SVG to draw geometric figures and found it reasonably enjoyable, so that’s what I decided to use.

One aspect of that previous project wasn’t very pleasant, though: the process of generating documents by manually running a scripts to create a html file, and opening it it the browser to see the results. So I figured I would try something different, and use this as an excuse to give Bolero, the F# WebAssembly library, a spin.

Initial setup

The setup of Bolero was completely straightforward:

• install the template,
• create a project, using the --minimal option,
• start the server with dotnet watch run,
• go to the browser, a basic elmish app is running, with hot-reload.

Attempting to auto-tune RANSAC, take 2

This post is a continuation of my exploration of the RANSAC algorithm. In my previous post, I began investigating if I could auto-tune some of the input parameters. The first attempt was not a success, but gave me an idea, which will be today’s post.

As a quick recap, RANSAC is a method to estimate a model in the presence of noisy data (so-called outliers). The method requires 2 input parameters:

• t, “A threshold value to determine data points that are fit well by the model (inlier)”,
• d, “The number of close data points (inliers) required to assert that the model fits well to the data”.

Rather than having to specify myself these 2 arguments, I would like the model to figure out good values by itself. In my initial attempt I tried to directly estimate the proportion of inliers in the dataset. This time, I will try a different angle: what if I started from pessimistic estimates, assuming many outliers and very high noise, and progressively tightened up the estimates?