4

I am looking for the correct term for a type of problem solver. Since its hard to google for something without knowing its name, I hope that the good people of this stackexchange may be able to help me.

When defining shapes in CAD systems based on constructive solid geometry, you start out with a (usually 2D) sketch, from which you extrude, rotate, or otherwise generate a 3D shape. You make this sketch by defining a set of curves (lines, arcs, bezier, etc.) and then defining a set of constraints. This is co-linear to that, this line is parallel to that line, the distance here is so and so.

If you define a valid combination of constraints, the CAD system can almost always find a configuration of the curves matching those constraints. What is the part of the CAD system called, that finds those solutions? Is there a good open-source implementation that I could use?

I tried search terms like "geometry solver" or "geometric solver", but I couldn't find anything relevant.

trichoplax is on Codidact now
  • 6,222
  • 2
  • 22
  • 67
Rikki-Tikki-Tavi
  • 195
  • 1
  • 5

1 Answers1

3

Its called a geometric constraints solver (a good primer on subject). You can find a open source solver as part of Open Cascade but its a bit convoluted to get going. A simpler solution for just solving, but also 3D solver capable, is geosolver.

Making your own (algebraic solution being easiest to write) is also not that hard, just a bit of work to make it automatically write the equations (and be efficient at solving). Take the following drawing as a example (made and solved with Mathematica):

enter image description here

You can simply conclude that its a sum of vectors that has to loop back at the origin thus:

$$ 7\begin{pmatrix}\sin(15^\circ)\\ \cos(15^\circ)\end{pmatrix}+5\begin{pmatrix}\sin(120^\circ)\\ \cos(120^\circ)\end{pmatrix}+2\begin{pmatrix}\sin(195^\circ)\\ \cos(195^\circ)\end{pmatrix}+4\begin{pmatrix}\sin(\delta)\\ \cos(\delta)\end{pmatrix}+x\begin{pmatrix}\sin(-90^\circ)\\ \cos(-90^\circ)\end{pmatrix}=0 $$

And solve the 2 unknowns from 2 equations, either algebraically or by using a gradient descent solver of some kind.

joojaa
  • 8,287
  • 1
  • 22
  • 46