Traffic Wavelength

A while back I was heading back home from work, unfortunately during rush hour. The streets were crammed and packed with cars, all trying to squeeze in front of each other. Pretty soon, I was standing in a traffic jam originating in a remote traffic light. This gave me the leisure to consider more carefully my surroundings, and I happened to notice something peculiar. Most of the time the car was stationary, but when I did go forward, the far-away traffic light was always red.

Of course, I’m no culprit, and when I did finally pass the intersection, the light was green. But, given the nature of traffic jams – slowly moving forward a couple of meters, then stopping and waiting – a lot of driving was done when the light in front of me was red. A curious thought popped into my mind: in a way, the traffic light and I were in “opposite phases”. While I spied a far away green, I grimly stayed in place. But when I did move, the stoplight showed red. This led me to consider the idea that traffic jams have wavelengths, frequencies, and speeds, and in certain ways behave like regular waves.
The core idea is simple: suppose that there is long line of cars standing in front of an intersection. The light turns green, but only one car manages to pass before it goes red again. Now, the second car oozes forward a bit, to replace the car that managed to drive on. The third car, noticing that the second has now taken the lead, also advances slightly, and so on. This “disturbance” propagates throughout the long column of cars, just like a single wave is carried about by a slinky.

I devised a very simple mathematical model to discover some of the properties of this wave. I later implemented this model in the computer in C++ so I could see graphically what was going on. The model has a few parameters and basic assumptions, which I will now describe.
Suppose we have an infinite number of cars waiting in a line in front of a junction, when suddenly the light turns green. All drivers have a parameter called “reaction time”, which I denote by r. The reaction time is the time it takes for us to react to an event. Although we would like to think differently, we never react instantly to what’s happening around us. From the moment light reaches our eyes, we have to send the information to the brain, process it, decide what to do with it, and then send the appropriate commands to our muscles. The reaction time is different for different individuals; you can test yours here. If you are extremely alert, you might get 0.2 seconds, but most of the time people don’t devote all their attention to noticing changes in the environment, so the value will be considerably higher (say, half a second).
The light turns green, the first driver takes a while to notice it, and then starts moving. The second driver also takes a while to notice that the first driver moved, but before he can put the pedal to the metal, he has to wait until there is a considerable distance between the two cars. This “speedup time” I call k. Normally, this would actually be a parameter dependent on the speed in which the cars are driving (you have to keep a certain distance away from the car in front of you; it’s the law), but for simplicity’s sake, I treat this as a constant. So, even after you notice that the car in front of you have started moving, you still have to wait for about a second or two before you can move yourself.
Using this model, we can see how much time it takes until a certain car starts moving. I denote by n_i the time it takes for car number i in the line to start moving.

…

Lets say that the green light is only turned on for g seconds. Which cars can cross within this time frame? Only cars that satisfy:

So while the green light is on, cars have started going forward. Unfortunately for them, not all will make it to the intersection in this round. Think of the last car, number i: it has just started driving when the light turned from green to red, and cannot hope to reach the junction in time. It will have to wait for the next time. I will later look a bit into this phenomena, but for now lets continue to focus on the “traffic wavelength”.
An interesting question to ask is, “during this session of green happiness, how much distance did the cars manage to cover?”. We all ask ourselves this when we are in jams, although this is usually accompanied by loud swearing. In this model, I take all cars to be of certain length l. This length takes into consideration both the average length of cars on the road, and the fact that you have to keep a certain distance away from the car in front of you. l turns out to be about 5 meters. In this case, all we have to do is multiply the number of cars by the length of each car, and discover how much distance we gained in the green streak:

Although only a certain number of cars pass while the light is green, remember that even though the light is now red, cars further down the line keep advancing. They are indifferent to the state of the traffic light – all that the drivers care about is if there is room in front of them to move forward. In fact, the sole driver which really cares about the traffic light is the leader of the column, because it affects only him (and perhaps you will curse less if you remember this when you are stuck in heavy traffic). So even if the traffic light now malfunctions and stays red forever, there will still be cars in the middle of the line which move forward.
The interesting question to ask given this phenomenon is which cars move when the light is red, and which cars move when the light is green. For this I assume that the red and green lights are equal in duration [this cannot be true for more than two way junctions, but it is what allows us to treat the thing as a wave]. Lets look then at the time intervals [0, g], [g, 2g], [2g, 3g]…
During the first interval, [0,g], the light is green. The cars which move are those whose index is smaller than .
During the second interval, [g, 2g], the light is red. The cars at the front of the line have stopped moving, but disturbance still propagates backwards. The cars that move now are those from to .
During the third interval, [2g, 3g], the light is green. This means that the cars at the start of the line have started moving again, but this does not interest me. What’s more interesting is that the cars in the middle are still moving, due to the first appearance of the green light. The cars that move are those in the range from to , and they too all move while there is a green light (even though it’s not the same green light that started the moving process).
We can treat this phenomena as a square wave. Cars that started moving when there was a green light will be given the value “1”. Cars that started moving while the light was red will be given the value “-1”. The wavelength is defined as the distance between two peaks, e.g, between two “1”s. This means the difference, in length, between the cars that moved in the interval [0, g], and the interval [2g, 3g].

.

The period is, of course, . The speed of the wave is therefore:

.

Which is independent of the duration of the green light. If we take the following values for parameters:

l = 5 [m]; r = 0.3 [s]; k = 1 [s], we get:
c = 3.85 [m/s] = 13.8 [kph]

This is how fast the disturbance, the slow crawling of cars, propagates along the entire column.
To visualise this wave graphically, I built a small program that uses the above model in order to mimic the behavior of the traffic light. All cars start out white, and the moment they move forward, they are colored according to the color the light was when they just started moving.
Cars start out in a line to the middle, and generally try to drive to the right, if possible. The current stoplight color is shown in the top right. The junction where they stop is represented by the vertical line.
Here is an example of the program in action. WordPress doesn’t allow uploading videos without paying, so I uploaded an animated gif. Click on it to see the animation.

The following particular run has r = 0.5 [s]; k = 0.7 [s]; g = 5 [s], which means there should be 4.75 red or green cars each phase. Since only integer amounts of cars exist, we see mostly groups of four, but sometimes groups of 5, too.

Cool!
One last thing I would like to discuss, is how many cars actually cross the intersection before the light turns red. This is hard to compute analytically for repeated cycles, and that is what the model is good for. However, for the first green light, it is possible, since all cars start out stationary.
Remember that cars start moving during the first green light, but not all of them make it to the junction on time. Just how many of them do? In order to answer this, I assume that once a car starts going, it does so with a constant acceleration. This is not quite true – we switch gears quite often while driving, and certainly don’t reach infinite speeds – but for lower speeds, it’s a fair estimate. I will mark this acceleration by a. Just how large is it? Well, some Jaguars boast they can go from 0-90 [kph] in 4 seconds, but that’s a hell of a ride. Most cars, under normal conditions, would experience an acceleration somewhere between 2-3 meters per second per second.
Since the cars start stationary, the distance they cover against time of travel is . Lets consider some car, c, that is in such a position in the car column, so it will start driving after m seconds. If this is the last car that can actually pass while the light is still green, then the time it takes to cross the junction must be just equal to the time left to drive, which is g-m. So all we have to do is solve the equation:

The left hand side is the distance the car covers as a function of time. The right hand side is the distance of a car which moves only after m seconds from the intersection. The equation needs to be solved for m. I will not bother you with the actual calculations, but this is just a quadratic equation, so it’s easily solvable. As an example, taking:
l = 5 [m]; r = 0.2 [s]; k = 1 [s]; a = 2 [m/s²]; g = 10 [s], we get that 9.16 cars start moving while the light is green (according to ). However, plugging in the numbers in the equation above, we get that only 5 cars will actually pass before the light becomes red. This is indeed what happens when the parameters are adjusted in the model: as you can see, 9 cars are colored green, which means 9 have started driving while there was a green light, but only 5 managed to cross the intersection.

Just Around the Riverbend

A while ago I read in some dubious piece that beloved and wonderful π can be found everywhere in nature. In circles, in spheres, in electrical circuits, when dropping needles over the American flag. It was stated that one of the places where π loves to appear is in rivers. Specifically, meandering rivers – rivers that twist and coil and snake about, definitely not taking the shortest route towards the sea. Here is a nice example of such a river, the Rio Cauto in Cuba:

Supposedly, it was found that the ratio between the path that the river takes, and the actual distance between its starting and ending point is π. This ratio is called “sinuosity”. Amazing, is it not?
This statement bugged me. Why should the ratio be π, and not any other magical number? In fact, I was skeptic on whether this ratio should be constant at all. While there are some beautiful pictures of meandering rivers out there, I have seen plenty of water streams which are rather straight. It turns out that the snakiness of a river depends on the slope of the hill down which it slides. Gravity is a pretty strong force, which doesn’t give the river much choice as to where it will go. As they say, “obey gravity, it’s the law”. Rivers that run in plains and flatlands are much windier than those on mountains.
Further, water, like any other object when influenced by gravity, tends to take the shortest route possible. The fact that it swirls and curves around is because there are obstacles which prevent it from heading straight on. The river may overcome these obstacles by either overflowing them, going around them, or by cutting out a new path. This means that the actual shape of the river strongly depends on the ground conditions – how tall the rocks are, how hard it is to erode them, what type of soil is found there. Even if π does exist somewhere in there, I expect different geographical situations to yield different ratios.
So shall I let this issue pass silently? Of course not. Python to the rescue!
I took on the task of writing a small program that, when given an aerial view of a river, can tell me its sinuosity – the ratio between its winding length, and the actual distance it covers.
How it does so is fairly simple. Calculating the distance between the starting and ending points is rather easy – that’s just the regular, good ol’ Euclidian distance. What’s more difficult is to calculate the actual winding length. Doing so requires going along the river, and measuring its length. Computerwise, this means that we have to create “internal sampling points” inside the river itself. We will then play “connect the dots” and measure the length by summing up the distances between these internal points.
We start with a picture of a river. In this example, I used GoogleMaps and homed in on a small section of minor channel in South America, which eventually merges with the Amazon.

The first step is for the computer to find out where the river is. Humans have a rather easy time at it – any child could come up to the screen and yell “look, the river is right there!”. But alas, computers are dumb and have to be told what to do – currently, the computer just sees a bunch of raw pixel data. The classic way of doing so is by computing gradients in order to find edges. But I wanted something quick and easy, so I chose instead to filter by color. The picture was scanned pixel by pixel, and everything not blue enough was deleted. Afterwards, the picture was scanned again, and individual blue pixels – which might have evaded the previous filter by chance – were deleted. Only sufficiently large groups of blue were allowed to stay. In the end, we are left with something that is clean enough for the computer to work with, if we give it a few hints on what to do. This filter worked fine for me in the above example, but it is very picture specific. When dealing with the Nile, for example, the blue intensity doesn’t work, and something else is needed.

Now we are left with a collection of blue pixels, most of which represent the river. However, we are still dealing with raw data – the pixels of the picture itself. The next step is to find out what path the river takes.
We start with some point that we know is inside the river; this point is given manually, and has to be inputted to the program. From this point on, we look around us at a certain distance r, and ask: which points that are a distance r from us are river points? The identification, of course is done by color, now that everything is blue. We then continue the process, but now with the new points we just found out about as our starting points. This way, we traverse across the entire river, going about jumps of size r.
Another way to picture it is like this: whenever we find a point that we know is inside the river, we draw a circle of radius r around that point. If we happen to draw parts of the circle on blue pixels, we assume that those parts are in the river, and we can repeat the process again.
There are several things to consider when implementing this naive algorithm. First, we must be careful not to return to where we already looked: we want to avoid the case where we say, “oh, the point 10 steps to the left is a river point”, go there, and then say “oh, the point 10 steps to the right is a river point” – because that is where we started from. This may seem trivial, but calculation errors mean that you have to be careful with what you consider as “two identical points”.
Second, the distance r must be chosen carefully. If it is smaller than the width of the river, then instead of going along the length of the river, we may find ourselves going back and forth along the width. On the other hand, r cannot be too big, otherwise we might miss acute twists and turns in the river, or even accidentally skip an entire section of the river, when it bends too close to itself. The ideal would be to use an adaptive radius, which changes based on how thick the river is, and if there is any river beside it. However, this would require much more complicated image analysis, and I chose to remain with the simple algorithm.
Another factor to consider is that we cannot draw a perfect circle – we are dealing with a pixelated environment. The circle must be drawn in discrete angle steps. Again we have a dependence on the step size – if it is too large, then we will skip slender curves in the river. If it is too small, then two adjacent points on the circle will go along the width of the river, and not its length, and this requires correction. Again, an adaptive model would have been ideal, but for the rivers used, constant step size worked with reasonable results.
Speaking of results, here is the same picture after processed by the algorithm (on top: with dots, on bottom: with shown circles).

Now we have a bunch of points which we assume are inside the river. Unfortunately, the circle algorithm doesn’t guarantee that they are generated in proper order. In order to play “connect the dots”, and go along the entire river, we must go from start to finish. Jumping around between random points in the river will give us an incorrect value for distance travelled. Again, we use a naive algorithm for finding the correct path. Assuming we know either the starting or the ending position, we go from point to point by always going to the closest next point we have. This simple method works elegantly when there are no branches in the river, meaning, the river doesn’t diverge into two different channels. If it does, then the algorithm is hopeless can cannot aim to be correct – after it finishes processing one channel, it abruptly jumps to the next, generating an artifact in the path.
The algorithm can be fixed by recognizing when there are large jumps – too large to be in adjacent parts of the river. These jumps are caused when the path taken by the algorithm jumps from channel to channel. When we recognize these, we can treat the two channels as two different rivers, applying the algorithm separately to each channel. This partially solves the problem of divergence, but not of convergence – what if the river splits up, then joins back again? This problem was not addressed here; for the program to deal with it, manual editing has to be performed. Overall, the algorithm gave decent, although not perfect, results (there are some bends which it could have included but missed).
Path with branch correction:

Path without branch correction:

Now that all the dots are connected in the right order, we can start actually measuring. The program ran over the river, and saved the aerial distance, as well as the actual distance covered. So, we can see how the ratio changes along the river itself. The result? Hardly π.

This is a nice looking graph. At first, every twist and turn in the river changes the ratio dramatically – this is because of the relative size of the meanders themselves, when compared with the length we have already traversed along the river. As we go further and further, the value stabilizes to about 2.56.
Could I be missing something here? Maybe. Perhaps I need to look at the entire river in order to get π, although this seems unlikely, since the river in the picture is several dozens of kilometers long. Perhaps this is an exception to the π rule. Or perhaps π just doesn’t play a theoretical part in this river game. Whichever case it is, I’m glad I started this project. I had a lot of fun coding and playing around with various river pictures – the python PIL module made it extraordinarily easy. Perhaps one day I will take a look at the geophysics which govern the true behavior of meanders. Until then – happy image processing, everybody!

Just for fun: remember when I said that if the circle radius r is too big, and the angle step is just so, that it may happen that we sometimes skip river bends and twists by accident? Here is a test case I made to demonstrate the effect: