I'm trying to write a piece of code that packs circles of differing radii efficiently into a square-shaped sheet. With the algorithm I'm using, I need to find the tangent between:
- a circle with a known radius r and unknown coordinates (a, b) (on an x-y plane)
- 2 other circles ri (i = 1, 2) with known radii r1 and r2 along with coordinates (c1.x, c1.y) and (c2.x, c2.y) respectively
Equation being used (Distance between circle centers (ri and r) = ri + r):
((c1.x-a)**2 + (c1.y-b)**2)**(0.5) = r1 + r
((c2.x-a)**2 + (c2.y-b)**2)**(0.5) = r2 + r
I need to be able to solve this system of equations fast as it will need to be computed around 250 times per iteration.
Currently I'm using the solve() function from the SymPy library, since the system of equations has all non-linear elements. Currently it takes about 10 seconds to execute each solve() function call (way too long :( ).
Here's how I have the solve() function running in my program:
solve([((c1.x-a)**2 + (c1.y-b)**2)**(0.5) - c1.r - circle.r, ((c2.x-a)**2 + (c2.y-b)**2)**(0.5) - c2.r - circle.r], a,b)
*note that a and b are set to real numbers only (real=True)
I've been scrolling through the internet trying to find some linearization methods of circles or some kind of polynomial approximation to speed up the solving process but have found nothing and gotten nowhere.
Is there a faster and somewhat accurate way to solve a system of two circle equations in Python?
It sounds like you are not really using SymPy in the intended way here. The idea with using SymPy's symbolic
solvefunction is that you would use it to find a general formula and then substitute numeric values into the formula.First find the general formula:
Now you can use SymPy's
lambdifyfunction to turn the solution into something that can be evaluated efficiently numerically:Let's time how fast this function is:
So it takes 30 microseconds to compute the answer for a given value of the parameters x1, x2 etc. Doing that 250 times would take less than 10 milliseconds.
If you install
llvmlitethen you can compile this expression using LLVM which is faster. We have to flatten the solution list of tuples into a single list and use SymPy'scsefunction to prepare the input expression:Now it takes 1.5 microseconds to evaluate for a single value of the parameters so 250 evaluations would take less than 1 millisecond.
If you are restarting the program many times then it is better to save the expression for the general solution rather than calling
solveagain each time your program runs. In fact if you only need to evaluate the function 250 times then it is probably better not to bother withlambdifyorllvm_callablebecause just creating the fast callable will probably take longer than 250 calls to a simple Python function. You can usepycodeto print out the expression as Python code:Now make a function in your Python script and just paste in that code for the solution expressions:
Calling this function takes 18 microseconds:
That is not as fast as using LLVM but avoids the overhead of compiling the function at the start of your program. It takes around 250 milliseconds on this computer to import
llvm_callableand then use it to compile the function but it makes the functionfabout 10x faster than thepycodeoutput. Usingllvm_callablewould be faster then if you needed to evaluate the function more than 10000 times per process but otherwise it is faster just to use thepycodeoutput pasted into your Python script since it avoids import/compilation overhead at runtime.Another option for avoiding compiler overhead is to generate an extension module so you can use ahead of time compilation but I think that this is probably overkill in your case. The simplest option here is to use pycode which will be plenty fast enough if you only need to evaluate the function 250 times. Here is complete timings for running a program that calls the function 250 times:
This way takes about 40 milliseconds for a complete run of the process that computes the solution 250 times. Most of this time is actually not even spent calling the function
fbut just importing things at startup.