Projects tagged "optimization"
This page highlights several of my personal software projects.
Table of Contents
3D Packing June 2017
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!
Primitive September 2016
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.
Links: GitHub • Website • App Store • Twitter Bot
Traveling Pixel January 2016
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.
Links: GitHub
Graph Layout February 2014
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
Links: GitHub
