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.

 print by Paul Couper

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.

Posted in Projects | Leave a comment

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.


Posted in Projects | Leave a comment

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 ( )

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

The iris data set ( ) 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\ 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

Posted in Uncategorized | Leave a comment

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


Posted in Uncategorized | Leave a comment

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.

Posted in Projects | Leave a comment


In the 1980s this Canso flying boat was photographed over the Gatineau Hills searching for ore deposits using a new electromagnetic system called SWEEPEM.  Built in the 1940s to hunt submarines under the North Atlantic, the aircraft’s ability to flow low, slow and long was ideal for detecting metallic ores buried deep underground.  I developed the signal processing and real time control software for SWEEPEM and operated the system aboard the Canso for the calibration flights.  In this article written for Survey Magazine and published in 1985 I described the work.



Posted in Uncategorized | Leave a comment


A showcase for some recent work on real time signal processing

There are five applications comprising the heart of the software in this system:

  1.  Mixer which does the signal processing
  2.  GUI which helps the user to edit the 100 plus configuration parameters
  3.  PDG which produces the pretty graphs seen in the showcase video
  4.  WV ( waveform visualizer ) which enables user to monitor and “teach” the Mixer how to identify cardiac signals.
  5.  Unit Tester

Added together these have 40,000 lines of pure code, excluding comments and white space.


Posted in Projects | 1 Comment


Nana is a cross-platform library for GUI programming in modern C++ style.

v1.5.5 was released this week and includes a small contribution from me that allows application code to set the default width of text entry fields.

Posted in Uncategorized | Leave a comment