ref: e0bb6d3b8546ea67e79cb190a96c26961ddacdf6
parent: 628cc6785b2cfa3d4ee6101667e4bb9e11095eec
author: Simon Tatham <anakin@pobox.com>
date: Mon May 1 10:24:56 EDT 2023
Untangle: add a 'snap to grid' user preference. Requested by a user who otherwise found themself spending too much time struggling to get lines nicely horizontal or vertical. The implementation is easy, but the question is what size of grid is appropriate. Untangle's own generated games are constructed by making a planar graph drawn on an extremely coarse grid - but snapping to _that_ grid would give away information about the puzzle solution, and also, Untangle wouldn't know any similar information about graphs generated by any other method. So a better approach is to choose a size of grid that guarantees that _any_ graph with n vertices can be drawn on it with nonintersecting straight edges. That sounds like a tricky maths problem - but happily, the solution is given in a book I already had a copy of. References in a comment (plus a proof of a pedantic followup detail about multiple planar embeddings).