> geometric constraint solving
Uh oh, that's my trigger word! I've been grappling with this problem recently and have a lot to say on the matter. I've been trying to build a simple geometric constraint solver for laying out 2D diagrams of optics in laser systems. The idea is not to be optically rigorous (for which CAD tools already exist, like Zemax), but to lay things out in a nice way for publications, such that lengths and angles can be constrained programmatically. This stems from when I was writing my PhD thesis and had to edit some 2D optical diagrams. By changing the angle of one mirror, I had to then move a whole bunch of other optics around to keep the incidence angle equal to the reflected angle.
I eventually wrote Optivis [1], which was my first attempt at solving the optical layout problem, but I quickly realised that my simple algorithm didn't work for cyclicly connected optics, i.e. optics connected back to themselves in some way. This is the case for any triangular cavity, or e.g. a Mach-Zehnder interferometer [2]. The problem is that by simply defining length and angle constraints between lines and optics, you overconstrain the problem when you connect something back to itself: you are setting an angle or length which is already implicitly defined by all the other (constrained) angles and lengths. To properly solve such problems, you must use a geometric constraint solver - one which can tell whether the problem is under-, well-, or over-constrained.
With a little research, I found that the traditional CAD approach to solving this type of problem is to write a bunch of non-linear equations representing the lengths and angles, and then use a minimiser to solve it based on some cost function. I wrote a simple library to do this [3], but I found that the problem had to be drawn with an initial guess close to its final solution in order for the solver to converge on the solution. Ideally, I wanted to be able to programmatically draw an optical layout based solely on a set of length and angle definitions from a file, rather than a prototype drawn e.g. by the user.
I found an academic paper [4] which described a wonderful approach to solving such a problem. It is based on the idea of "cluster rewriting" instead of solving non-linear equations. This approach represents constraints as "clusters", or sets of points, and the relations between them. The algorithm in the paper supports three types of cluster innately: "rigid" clusters, which are points with fixed positions with respect to each other; "radial" clusters, where a set of points are defined to have some fixed length from a central, rigid point; and "scalable" clusters, which are points whose vertices have well defined angles but no defined lengths. The algorithm identifies groups of points that fall into these definitions, and tries to merge them together until there is only one rigid cluster left. Or, in other words, it starts out with the initial set of constraints defined by the user, then derives a whole bunch of implicit constraints on the other points that are consistent with the initial constraints, provided that the problem is well constrained. What's awesome about this paper is that the authors provide a Python library [5]. It was written between about 2009 and 2013 for use with Python 2.5, so I spent a few weeks over summer porting it to Python 3 [6]. I managed to get it to work, and it was managing to solve fairly complicated problems, but I found that it had a few latent bugs which I could not fix easily without really taking time to understand the full algorithm. For example, when adding a new constraint to a relatively simple set of points, it would spontaneously move everything back to the origin. I think I somewhat understand which part of the code is causing this, but I don't understand it well enough to really fix it.
That's where I left the problem. Recently I have again been looking at constraint solving using non-linear solvers, particularly with SolveSpace [7], because its (C++ based) library was recently exposed via Python [8], but this will again be susceptible to the problem that the user must provide a close-to-optimal prototype for the system to converge. I am disappointed I couldn't get the paper's algorithm to work fully, because it is an excellent approach to this problem. Perhaps someone here has some more experience in this domain and can help?
I also plan to use whatever I come up with to draw electrical diagrams around optics. In my field we frequently draw diagrams of optical layouts with the electrical signals included. For electrical problems you would probably be more interested in having "neat" signals with 90 degree angles, and parallel lines, but this would probably be quite straightforward to implement.
[1] https://github.com/SeanDS/optivis
[2] https://en.wikipedia.org/wiki/Mach%E2%80%93Zehnder_interfero...
[3] https://github.com/SeanDS/pygeosolve
[4] https://www.sciencedirect.com/science/article/pii/S001044850...
[5] http://geosolver.sourceforge.net/
[6] https://github.com/SeanDS/cluster/tree/feature/import-new
[7] http://solvespace.com/
[8] https://github.com/KmolYuan/python-solvespace