Andrew, all,
First some inversion basics:
- When a circle crosses the center of a circle of inversion, its inverse shape is an endless line perpendicular on the central axis.
- The size of the inversion circle doesn’t really matter, but there are good sizes, bad and better ones.
Because of the identity |OP’| = Rinv² / |OP| a small distance OP can inverse to huge distance OP’ and large values can become very small.
When three circles have a common intersection point and a circle of inversion is centered at that point …
… The inverse shapes of the three given circles are three endless lines.
For these three lines:
- All 3 can intersect at 3 different points, creating some sort of triangle between the points.
- Two lines can run parallel, with the third crossing both parallel lines once, creating a sort of ‘H’ shape.
- All three can intersect in one single point.
- All three can be parallel.
To solve for 3-fold tangent circles (CT3), the task is reduced to finding the tangent circles of the 3 lines and inverse these circles back.
By case:
- 4 circles will be tangent to the 3 lines forming a triangle, one Incircle and 3 Excircles … Hence 4 solutions for CT3.
- 2 circles are tangent to the 3 lines forming a ‘H’, one above and one below the middle segment … Hence 2 solutions for CT3.
- No real or unique circle can be tangent in a singularity or to 3 parallel lines … Hence NO solutions for CT3.
The size and order of the given circles are not important.
The code related to a common intersection should therefore be executed earlier.
After 2 concentric circles because these never have a common intersection point.
The solutions are ‘All inclusive’ and can be returned immediately.
Essential is a relative sized inversion circle (FS#2590), not too big and not too small, but certainly not of a fixed size = 10 units.
The average of the radii is a good choice.
As is, the code relies on 3D information although QCAD and Apollonius’s problem is basically 2D.
With 3D information the method(s) may fail.
Because circles can only exist as flat I tend to project everything to the Z=zero plane.
The code that evaluates for a common intersection of circles is limited in its search algorithm. (Apollonius.getCommonIntersectionPoint())
As is, circle 1 must cross 2 and 3 twice, each. Nowhere in the above is that a requirement.
Two circles may merely ‘kiss’ as long as the third circle goes through the point of tangency.
getCommonIntersectionPoint() must be re-conceived to return ‘A common intersection point of 3 circles’.
Note that there can be 2 such points and that does not really matter. It will always be a type 3.
Updated code to handle a common intersection point:
To insert between the concentric case and the equal sized circle case.
The old code must be removed.
// Special case: All three circles intersect in one point:
// Exploits an enhanced algorithm by CVH
var commonIP = Apollonius.getCommonIntersectionPoint(c1, c2, c3);
if (!isNull(commonIP)) {
// # Remark by CVH # Better results with appropriate circle of inversion
// Relative sized inversion circle (FS#2590), opted for the local average radius:
var rInv = (Math.abs(c1.radius) + Math.abs(c2.radius) + Math.abs(c3.radius)) / 3;
var inversionCircle = new RCircle(commonIP, rInv); // In 2D by default
// Construct inversion shapes:
var shapesInverse = Apollonius.getInverseShapes([c1, c2, c3], inversionCircle);
// Expecting nothing else than 3 line segments:
if (shapesInverse.length === 3 &&
isLineBasedShape(shapesInverse[0]) &&
isLineBasedShape(shapesInverse[1]) &&
isLineBasedShape(shapesInverse[2])) {
// Handle as LLL and get results (0-4):
var res = Apollonius.getSolutions(shapesInverse);
// Inverse the results back to solutions:
ret = Apollonius.getInverseShapes(res, inversionCircle);
}
// Return final results for any common intersection point case:
return ret; // 0-4 solutions
}
EDIT # Had some issues with the occurrence of QSharedPointer objects … Should be fixed. 
Replacement code for Apollonius.getCommonIntersectionPoint(c1, c2, c3):
The old code is incorrect/incomplete and must be removed.
/**
* \author Original by Andrew Mustun, bug fixing, hardened and enhanced by CVH © 2024.
* \return A common intersection point (1) of all three circles or undefined.
*/
Apollonius.getCommonIntersectionPoint = function(c1, c2, c3) {
var cA, cB, cC;
var ips = [];
var i, j, k;
var pos1, pos2, pos3;
var common;
// Reject incorrect shape types:
if (!isCircleShape(c1) ||
!isCircleShape(c2) ||
!isCircleShape(c3)) {
return undefined; // Failed, incorrect data
}
// Handle as normalized new circle shape in 2D, validate and reject when invalid:
cA = new RCircle(c1.center.get2D(), Math.abs(c1.radius));
if (!cA.center.isValid() || !isNumber(cA.radius) || cA.radius < RS.PointTolerance) {
return undefined; // Failed, invalid circle shape
}
cB = new RCircle(c2.center.get2D(), Math.abs(c2.radius));
if (!cB.center.isValid() || !isNumber(cB.radius) || cB.radius < RS.PointTolerance) {
return undefined; // Failed, invalid circle shape
}
cC = new RCircle(c3.center.get2D(), Math.abs(c3.radius));
if (!cC.center.isValid() || !isNumber(cC.radius) || cC.radius < RS.PointTolerance) {
return undefined; // Failed, invalid circle shape
}
// Collect all mutual intersection points:
ips = ips.concat(cA.getIntersectionPoints(cB, false)); // Unlimited, avoids RBox test
ips = ips.concat(cA.getIntersectionPoints(cC, false)); // Unlimited, avoids RBox test
ips = ips.concat(cB.getIntersectionPoints(cC, false)); // Unlimited, avoids RBox test
// Fail on no 3 intersection points:
if (ips.length < 3) {
return undefined;
}
// Process all intersection points:
for (i=0; i<ips.length-2; i++) {
pos1 = ips[i];
// Skip to next when invalid:
if (!pos1.isValid()) {
continue;
}
// Process all next intersection points:
for (j=i+1; j<ips.length-1; j++) {
pos2 = ips[j];
// Skip to next when invalid or when not (almost) equal with pos1:
if (!pos2.isValid() || !pos2.equalsFuzzy2D(pos1)) {
continue;
}
// Process all remaining intersection points:
for (k=j+1; k<ips.length; k++) {
pos3 = ips[k];
// Skip to next when invalid or when not (almost) equal with pos2:
if (!pos3.isValid() || !pos3.equalsFuzzy2D(pos2)) {
continue;
}
// Found a common intersection point, return average or undefined when invalid:
common = RVector.getAverage([pos1, pos2, pos3]);
return (common.isValid()) ? common : undefined;
}
}
}
// No common intersection point:
return undefined;
};
Regards,
CVH