Success with Accord.NET for my geometric constraint solver

[Brad Phelan]

For example I can make a box tightly fit around a circle ensuring that the box has 

vertical sides and horizontal top and bottom and that the interior angles of the box are 90 degrees.

The declarative code to do this is

         [Test()]
        public void SquareAroundCircle()
        {
            var circle = new Circle() { center = new Point(0, 0, false), rad = new Parameter(10, false) };

            // We want a box around the circle where all lines touch the 
            // circle and line0 is vertical. We arrange the lines roughly
            // in the correct placement to get the search off to a good
            // start
            var line0 = new Line(new Point(-21,0), new Point(0, 23));
            var line1 = new Line(new Point(0,22), new Point(22, 0));
            var line2 = new Line(new Point(21,0), new Point(0, -29));
            var line3 = new Line(new Point(0,-27), new Point(-25, 0));

            var angle = new Parameter (Math.PI/2, false);

            var r = SketchSolve.Solver.solve
                ( true
                , line0.IsTangentTo(circle)
                , line1.IsTangentTo(circle)
                , line2.IsTangentTo(circle)
                , line3.IsTangentTo(circle)
                , line0.HasInternalAngle (line1, angle)
                , line1.HasInternalAngle(line2, angle) 
                , line2.HasInternalAngle(line3, angle)
                , line3.HasInternalAngle(line0, angle)
                , line0.p2.IsColocated(line1.p1)
                , line1.p2.IsColocated(line2.p1)
                , line2.p2.IsColocated(line3.p1)
                , line3.p2.IsColocated(line0.p1)
                , line0.IsVertical()
                );

            Console.WriteLine (line0);
            Console.WriteLine (line1);
            Console.WriteLine (line2);
            Console.WriteLine (line3);

            r.Should ().BeApproximately (0, 0.0001);


        }       

outputs

l -10.0001115077093 ; -10.0000042872393 : -10.0001009643498 ; 10.0007695944268

l -10.0001039993543 ; 10.0007775379925  : 10.000822346198   ; 9.9993514218465

l 10.0008234033545  ; 9.99932555026719  : 9.99938821899412  ; -10.0001897226096

l 9.99938502181062  ; -10.0001965026072 : -10.0001011598745 ; -10.0000102791518

l 0                 ; 0                 : -10.0001062362285 ; 5.27153176044237E-06

which you should be able to verify is indeed a box tangent to a circle of radius 10 

The number of free variables generated by the constraints is 16

If anybody is interested in the implementation of this with Accord.NET you can see

the source code at

https://github.com/bradphelan/SketchSolve.NET

under a BSD license and if there are some really nerdy Math types that would

like to suggest better way of doing things or add tests then I'd be really

happy.

Thanks Ceasaro for a neat optimization lib to get me started properly with this

Brad

[César]

I am glad you got it working! This a neat use of the framework. Please let me know if you discover any further issues, or if you have any suggestions for further improvements. Congrats on your working application!

Best regards,

Cesar

[Brad Phelan]

I've found that sometimes there is no convergence when there is only a single free variable. Is this a common problem with the solver?

[César]

It could be possible, specially when constraints are too tight. If you find more of these, would you mind collecting some of the data and, perhaps if that is not too much, providing a test case for those issues?

The Augmented Lagrangian code in Accord.NET uses the BroydenFletcherGoldfarbShanno class to do the heavily lifting. However, since I have manually adapted/translated the BFGS from FORTRAN and had to fill in some missing dependencies, it could be possible some bugs were introduced during this transition. If I had more test cases, I could check if the original FORTRAN code produces correct results and try to pin point where the issue might be.

By the way, which library you was using for the optimization before Accord.NET?

Best regards,

Cesar

[Brad Phelan]

I pulled the original code from https://code.google.com/p/sketchsolve/ which was a c++ lib. I first did a naive direct to c# translation then started writing a more fluent wrapper interface for it. The original solver wasn't very modular but it seemed to work. However it was a custom one off solver only for this library which I didn't feel like maintaining alone. The original c++ source can be found at

https://github.com/bradphelan/SketchSolve.NET/tree/master/src

for the time being and you can always find the changes I made in my git history. 

I'm also building test cases for my own library some of which are failing at the moment.

The test case that fails to converge has two local minimum quite close. It tries to find a line tangent to

a circle by moving only the second point of the line along the x axis. Obviously there are two solutions

but it seems to jump between the second and first one but without actually converging to them.

However it's not a realistic test just a unit test. When I used a set of 16 constraints to make the

box on the circle it worked fine. My general knowledge of solvers is not brilliant so I can't

say it's a bug in Accord.NET.

If you want to run this test then it is this test here

https://github.com/bradphelan/SketchSolve.NET/blob/master/SketchSolveC%23.NET.Spec/Test.cs#L195

The test is easy to run in Xamarin Studio.

Do you have a set of test cases for Accord.Net. I couldn't find a directory for them if

I wanted to add some specific failure cases if I found any?

[César]

Hi Brad,

Hmmm... If I recall correctly, in cases like this, the solver may throw a convergence exception. However, perhaps it could still had provided an useful answer. If you check the solution, even after the exception was thrown, perhaps it would still be close from one of the local minima... But I have to check this further!

Unit tests for the Math project are available at 

https://code.google.com/p/accord/source/browse/trunk#trunk%2FSources%2FAccord.Tests%2FAccord.Tests.Math

Hope it helps!

Best regards,

Cesar

[Brad Phelan]

Good to see all those tests. Nice work :)