Find arc center point if start point, end point and offset is given

Question

I want to find the center point of an arc. I have start point, end point, and offset of an arc.

I have tried the below code. With this code, I got the center point of arc in a 90% case. But for certain data its fail to find center point.

I have this definition of arc drawing

X169290Y2681101I90207J39371*
X267716Y2779527J98426*
X169290Y2877952I98425*
X79082Y2818897J98425*

The answer for all above four arc center coordinate is (4.299940599999999, 70.5999858)

This is an arc image, This arc is made from four single-quadrant arcs.

private Coordinate findCenter(Coordinate start, Coordinate end, Coordinate offset) {
        double twoPi = 2 * Math.PI;
        
        if (quadrantMode.equals("single-quadrant")) {
            // The Gerber spec says single quadrant only has one possible center,
      // and you can detect it based on the angle. But for real files, this
      // seems to work better - there is usually only one option that makes
      // sense for the center (since the distance should be the same
      // from start and end). We select the center with the least error in
      // radius from all the options with a valid sweep angle.
            
            double sqdistDiffMin = Double.MAX_VALUE;
            
            Coordinate center = null;
            
            List<Coordinate> qFactors = new ArrayList<Coordinate>();
            qFactors.add(new Coordinate(1, 1));
            qFactors.add(new Coordinate(1, -1));
            qFactors.add(new Coordinate(-1, 1));
            qFactors.add(new Coordinate(-1, -1));
            
            for (Coordinate factors : qFactors) {
                Coordinate testCenter = new Coordinate(start.getX() + offset.getX() * factors.getX(),
                        start.getY() + offset.getY() * factors.getY());
                // Find angle from center to start and end points
                double startAngleX = start.getX() - testCenter.getX();
                double startAngleY = start.getY() - testCenter.getY();
                double startAngle = Math.atan2(startAngleY, startAngleX);
                
                double endAngleX = end.getX() - testCenter.getX();
                double endAngleY = end.getY() - testCenter.getY();
                double endAngle = Math.atan2(endAngleY, endAngleX);
                
                // # Clamp angles to 0, 2pi
                double theta0 = (startAngle + twoPi) % twoPi;
                double theta1 = (endAngle + twoPi) % twoPi;
                
                // # Determine sweep angle in the current arc direction
                double sweepAngle;
                if (direction.equals("counterclockwise") ) {
                    theta1 += twoPi;
//                  sweepAngle = Math.abs(theta1 - theta0);
                    sweepAngle = Math.abs(theta1 - theta0) % twoPi;
                } else {
                    theta0 += twoPi;
                    sweepAngle = Math.abs(theta0 - theta1) % twoPi;
                }
                
                // # Calculate the radius error
                double sqdistStart = sqDistance(start, testCenter);
                double sqdistEnd = sqDistance(end, testCenter);
                double sqdistDiff = Math.abs(sqdistStart - sqdistEnd);
                
                // Take the option with the lowest radius error from the set of
                // options with a valid sweep angle
                // In some rare cases, the sweep angle is numerically (10**-14) above pi/2
                // So it is safer to compare the angles with some tolerance
                boolean isLowestRadiusError = sqdistDiff < sqdistDiffMin;
                boolean isValidSweepAngle = sweepAngle >= 0 && sweepAngle <= Math.PI / 2.0 + 1e-6;
                if (isLowestRadiusError && isValidSweepAngle) {
                    center = testCenter;
                    sqdistDiffMin = sqdistDiff;
                }
            }
            return center;
        }
        else {
            return new Coordinate(start.getX() + offset.getX(), start.getY() + offset.getY());
        }
    }

public static double sqDistance(Coordinate point1, Coordinate point2) {
    double diff1 = point1.getX() - point2.getX();
    double diff2 = point1.getY() - point2.getY();

    return diff1 * diff1 + diff2 * diff2;
}

Explaination graph for arc drawing

If the algorithm works for most cases, but not for some, it looks like an accuracy-based problem. Did you debug the code and find any unforeseen values? — Dominique
What if offset? What does X169290Y2681101I90207J39371 mean? Why another string contain only I or J? — MBo
Can you elaborate on the input format? Also, are the arcs always circular arcs, or are they arcs from arbitrary ellipses? — templatetypedef
@MBo I, J Characters indicating a distance or offset in the X or Y direction. If I or J is missing then a 0 distance is used. — Bhavin S.
@Dominique, Yes I have debug and found the problem in this line boolean isValidSweepAngle = sweepAngle >= 0 && sweepAngle <= Math.PI / 2.0 + 1e-6; Where I got these value "sweepAngle" =1.5708064868152167 and Value of "Math.PI / 2.0 + 1e-6" = 1.5707973267948965 For this minor difference, Its become isValidSweepAngle = false. — Bhavin S.

Dominique Dominique · Accepted Answer · 2020-09-15T08:52:48

You are dealing with an accuracy problem, caused by the value 1e-6. I'd advise you to do two things:

Check what happens when you replace this value by zero (any side-effects which might cause problems?)
In case zero value does not work, try to replace by a value, smaller than 1e-6, like 1e-9, 1e-12, ...

But most of all: you need to do some exhaustive testing while modifying that value (do you have a testlist that needs to be covered + invent some realistic testing cases).

Find arc center point if start point, end point and offset is given

1 Answers