I'm looking for a solution to a seemingly simple mathematical problem. Please refer to the attached drawing to illustrate the following description.
- A sphere with radius R = 1
- Two circles on the surface of this sphere, described by two arbitrary vectors A and B as well as two angles alphaA and alphaB (0..PI/2)
To calculate for the following seven cases:
1. Circles lie side by side and do not touch or intersect: - nothing -
2. Circles touch outside in one point: vector coords for this point C
3. Circles intersect each other: vector coords of the two points C1 and C2
4. Circles touch inside in one point: vector coords of this point C
5. Circles lie inside each other and do not touch or intersect: - nothing -
6. Circles are identical, with A = B and alphaA = alphaB: - nothing -
7. Circles are identical, with A = -B and alphaA = alphaB = PI/2: - nothing -
The drawing does show case #3.
In addition to a formal mathematical solution, I'm also looking for its implementation. This implementation should be numerically stable and in form of a function which accepts A, B, alphaA and alphaB as parameters and returns the case number as well as either zero, one or two points of intersection. Delphi would be prefered as programming language, but any similar will do (C, Java, VB etc.).
- This is not home or course work. It's just a puzzle piece I need for a larger software project. I already posted this problem on various math help user boards, but nobody there seems to be able to point to a reasonably simple solution.
- I need just the bare-bone function, as stated in the project description. No gui of any kind is required.
- I already have a "solution" which is rather complex and computational expensive and does so not fit the apparent simplicity of the problem. There just has to be a better solution.
To give a better understanding of the context in which this function will be used:
- Image processing software, that computes certain information by analyzing source images
- Function has to be executed 256 times for every pixel in 5000x4000px source files (approx. 5,000,000,000 times per image) with no room for optimization.
- To achieve reasonable run times, the implementation has to be quite fast. My current implementation takes about 5s for 10,000,000 runs (2010 MacPro). Obviously, I'm looking for an implementation that is faster than that.
Décerné à :
Hi, i have a solution for the intersecting circles which uses only 12 arithmetic and 9 vectorial operations to get the points. I can give you a Delphi solution.