## A sound simulation

The propagation of sound waves is governed by the following system of first order partial differential equations:

The mathematical symbols might be a bit intimidating, but once past that, these formulae are surprisingly simple.

Implementing them in computer code is quite a challenge, but I found an excellent online resource that explains how to do so in detail: Understanding the Finite-Difference Time-Domain Method, John B. Schneider, www.eecs.wsu.edu/~schneidj/ufdtd, 2010.

That work is quite old now, so I thought it worthwhile to re-implement it in modern C++17 and provide a GUI.

My code is available at https://github.com/JamesBremner/soundsim

## In Praise of Plodders

My brother is some sort of mathematical prodigy.

When I was in high school I would show him my toughest assignments.  Although he was two years junior to me, he would stare at the problem for some minutes and then pronounce the answer.

“That looks like it might be correct!” I’d say, “ How did you work it out?”

“Dunno,” was the reply.

Well, being the plodding sort of bloke that I am, once I knew the answer, I could work out how to get from the question to the answer.   So, I did fine.  Later, my brother not so much.  “Show your work!” the teachers always wrote in the margins of his homework.

Flash forwards several decades to the tech crunch in 2000, when it was impossible to hire experienced software engineers.  My company began hiring people who seemed bright and expressed a desire to write code.  My job included ‘onboarding’ the new hires.

So, I would wander over to their desks each morning.  “My code isn’t working,” they told me, “I cannot see the bug.”  In the afternoon I’d find them still staring at the piece of code.  So, I showed them how to code tests and run them under a debugger.

It was all too much work.  They truly preferred to sit staring at the code.  At the end of the probationary period they knew just as much as at the start and had accomplished very little, so we had to let them go.

The occasional plodder, hired by mistake, did much better.

## PathFinder

Several times a year I need to find a path through a graph.

The graphs might be representations of the layout of streets, the distances between cities, the connections between nodes, or they might be models of abstract relationships such as the concept of prerequisites – you need to finish A before you can start B.

Many of these path finding problems can, with some thought, be transformed into a modification of one of the standard graph theory problems ( travelling salesman, spanning tree, maze searching or most often Dijkstra’s shortest path ) Now all that remains is to find the relevant routine in a graph library such as boost::graph and adjust the data into a form that the library routine can process.

Well, not so easy. Graph theory libraries are complex beasts, powerful but hard to tame.

However, over the years I have developed several software tools for making the connection between the mundane world of city streets and university curricula and the magical mathematical world of graph theory. Now I am working on combining them into one easy to usepackage: PathFinder.

The package is really only easy to use if you code in C++. For certain standard problems PathFinder comes with a graphical user interface that allows it to be used by anyone unfamiliar with C++.

PathFinder can be found here

On a personal note: I am dedicating this work to my father, Taylor Bremner. In the early 1940s, during the second world war, my father designed, built and maintained the bombsights used by Path Finder Squadron. The planes in this squadron were crewed by the most experienced pilots, navigators and bombardiers the Royal Air Forces possessed. They flew ahead of the bomber fleets to pick out the target and mark it with flares, so that the raw recruits in the remaining planes could find their way in the darkness over Germany.

My father once showed my brother and me the inner working of one of his bombsights. Packed into a suitcase sized green metal box was a fascinating maze of eccentric cogs and twisty worm gears of brass and steel that whirled around solving in real time cascading sequences of differential equations that adjusted the moment of bomb release for velocity, height, wind speed and direction. Perhaps this was the moment my brother became a mechanical engineer and I a software engineer.

In an early form of extreme usability testing, my father also flew in the raids that carried his bombsights. Since the German air force knew all about Path Finder Squadron, and knew that destroying the squadron planes was the best chance of diverting the bombs from their cities, the enemy fighters concentrated their attacks on the aircraft carrying my father and his colleagues. The life expectancy of a member of Path Finder was measured in weeks.

Posted in Open Source, Projects, Software Engineering Tool | Leave a comment

## Ferrero Rocher Trees & Computational Geometry

This little hazelnut tree is growing in a farm in Northern Italy.

When mature, it will produce lots of these

But meantime it needs lots of tender loving care.

The care will be provided by a robot tractor driving carefully between the rows of trees, as seen from space

and converted to a mathematical guide

To ensure no tree is neglected because it grows in an awkward corner requires solving a notoriously challenging problem, the convex decomposition of a concave polygon, in computational geometry.

Here is a news story about a similar, but different, robot that also tends hazelnut trees in Italy. https://www.euronews.com/2019/09/02/robots-drones-and-the-future-of-farming

## Talking to People and Robots

In these days of COVID19 and AI, when face to face communication is avoided and Alexa lurks in the corner of every room, people are beginning to sound like robots and robots sound ever more like humans.  Still, sometimes a translator is needed.

Over the years I have developed many applications that “talk” to devices attached to  a Windows desktop computer.  The devices range from half a dozen different sensors on a racing sailboat to an infra-red spectrometer the size of a pinhead. For a list, see.

Such applications have two essential tasks, talking to the human user and talking to the device.  Neither the human nor the device are very patient – they expect an instant response no matter what else is going on.   So the application must be split into two separate threads of computation, one looking after the user and one looking after the device.  The trick is synchronizing the two threads so that whatever is said by the user is translated and sent to the device, while anything communicated from the device is displayed to the user, without descending into confusion and chaos.

Developing multithreaded applications is a challenge.  Ideally, the application developer should be able to concentrate on the translation tasks, employing a well tested library to keep track of the different threads and their inter-dependencies.  The application code should run in exactly one thread, and the communications library should create and run the required threads so that the robots do not block communications with the user, or vice versa.

This week I added a class called com to the windex framework which does just this for robots that are connected to a serial port ( USB, COM, RS232, etc ).  If this sounds like it might be useful, check it out

Posted in Open Source, Software Engineering Tool | Leave a comment

## Bin Packing

For many years I have maintained open source code to optimize the arrangement of small items in larger bins in two and three dimensions.

My interest in this problem has been maintained by requests from several clients to provide front and back ends that adapt the bin packing engine for their particular needs.

• Cutting panels from plywood sheets with minimum waste.  2D problem. Client in the Philippines .
• Packing ECCO shoe boxes into cartons to minimize shipping costs.  3D problem. Client in the USA.
• Packing Canon camera boxes into cartons to minimize shipping costs. 3D problem.  Client in Italy.
• Cutting panels from plywood sheets with minimum waste. 2D problem. Client in India.

The Indian client was kind enough to share test results comparing my results with those from a commercially available system ( Cut Rite ).  The test involved 32 unique packing problems requiring in total  926 panels to be cut from 124 sheets. On 26 of the 32 packs the results were identical, requiring the same number of sheets to cut the panels. For 4 packs the Cut Rite arrangement needed fewer sheets, and for 2 my packing engine gave a better result.

As always with optimization problems, my focus is on providing answers that are good enough in an extremely short time.  The Cut Rite bin packer required several seconds to generate a solution, my engine delivered in 300 milliseconds or about 10 times faster.

Bin Packing Engine code.

## A little intelligence, artificially.

KMeans is a windows console application to find clusters in data with any number of columns ( attributes ) using the KMeans algorithm ( https://en.wikipedia.org/wiki/K-means_clustering )

`Usage: KMeans <data dimension> <data file path> <number of clusters>`

The iris data set ( http://archive.ics.uci.edu/ml/datasets/Iris ) has 4 attributes

```1. sepal length in cm
2. sepal width in cm
3. petal length in cm
4. petal width in cm```

The application outputs

KMeans.exe 4 ..\data\bezdekIris.data 3

Total distance 103.982
Total distance 97.249
Total distance 97.2046

Cluster 0 means 5.006 3.428 1.462 0.246
mins: 4.3, 2.3, 1, 0.1,
maxs: 5.8, 4.4, 1.9, 0.6,
sds: 0.348947, 0.375255, 0.171919, 0.104326,

Cluster 1 means 5.90161 2.74839 4.39355 1.43387
mins: 4.9, 2, 3, 1,
maxs: 7, 3.4, 5.1, 2.4,
sds: 0.462633, 0.293885, 0.504774, 0.295091,

Cluster 2 means 6.85 3.07368 5.74211 2.07105
mins: 6.1, 2.5, 4.9, 1.4,
maxs: 7.9, 3.8, 6.9, 2.5,
sds: 0.48761, 0.28625, 0.482118, 0.276165,

I have used this code to locate servers among clients to minimize the total distance between clients and their nearest server, when there was too many clients to calculate the absolute optimal locations directly.

The open source code for this can be seen at https://github.com/JamesBremner/KMeans

## Talking to satellites

Starting work on SpaceCom  to enable error free communication between satellites and the ground using the  NASA TC SPACE DATA LINK PROTOCOL CCSDS 232.1-B-2

## New Mexico Senate Webcaster

Every session of the New Mexico state senate since 2009 has been webcast using a computer application designed and coded by SpeakerToRobots.

The chair recognizes one of the senators. When the senator begins to speak, one of three cameras has already swung into position and is webcasting the perfect image. The application stores over 50 preset positions for each camera, automatically selecting and moving the cameras into position whenever the speaker changes, using the VISCA protocol over RS232.