Michael Fogleman


Projects tagged "optimization"

Hopefully something here will catch your eye.

Table of Contents

3D Packing June 2017

171 Go 3D Optimization

Tightly pack 3D meshes into as small of a volume as possible.

Formlabs recently announced the Fuse 1, a 3D printer that works via Selective Laser Sintering. This technique uses a nylon powder which conveniently supports the structures as they are printed. No scaffolding or supports are needed, so we can print as many objects as we can pack into the volume.

This begs the question - how many 3DBenchy boats can the Fuse 1 print in a single batch? As soon as the printer was announced, I immediately gravitated toward this algorithmic challenge.

With naive bin packing, 82 boats can be packed into the printer volume. But with some more advanced packing algorithms, 113 boats can fit - a 37.8% improvement!

Read the article here.

Primitive September 2016

6,225 Go Objective-C 2D Vector Graphics Optimization

Recreate your photos with vector-based geometric primitives.

You provide an image as input. The app tries to find the most optimal shape that can be drawn to maximize the similarity between the target image and the drawn image. It repeats this process, adding one shape at a time. Using this process, the program can recreate a photo with surprisingly few shapes.

This project was originally inspired by the popular and excellent work of Roger Johansson - Genetic Programming: Evolution of Mona Lisa. Since seeing that article when it was quite new, I've tinkered with this problem here and there over the years. But only now am I satisfied with my results.

The core is written in Go and is open source. A native macOS app is also available in the App Store, providing a nice UI on top of the engine as well as some additional features like "drawing mode." To date, this has been my most successful paid app.

Traveling Pixel January 2016

22 Go Graphics Optimization

Applying the traveling salesman problem to pixel art.

This code uses simulated annealing to find the shortest path to visit all black pixels in an image. Then it generates an animated GIF showing the order of traversal.

Graph Layout February 2014

64 Python C Graphs Optimization

Experimenting with graph visualization using simulated annealing for layout.

Graphviz is the main player when it comes to graph visualization. But its output isn't very appealing, at least not by default. With this in mind, and being a fan of simulated annealing, I experimented with using annealing for graph layout. The results are pretty good, but it probably doesn't scale very well. The algorithm basically tries to minimize the following metrics, with different weights applied to each:

  • Node-Node Intersections
  • Node-Edge Intersections
  • Edge-Edge Intersections
  • Edge Lengths
  • Total Graph Area
  • Node Rank Violations