I have some software which finds points along an arc.
The arc starts at (X1, Y1) and ends at (X2, Y2) and has radius R

The software evaluates the following expression and if it is true says that the arc is impossible.
How does this work, please?

4 * R ^ 2 < ((X2 - X1) ^ 2 + (Y2 - Y1) ^ 2)

 

Pythagoras. The two end points can't be further apart than the diameter of the circle of which the arc is part.

 

Easy to see now I know the answer.
Although it is this equation where the software falls out, I believe it is floating point rounding errors which are the actual cause.
I feel a fudge factor coming on. Rather than is A < B, use is (A - B) < 'some prety small positive number' (both A and B must be positive as they are squares).

Any better ideas?

 

look like a homework problem... ;-)

 

look like a homework problem... ;-)

No - a CNC software problem. A perfectly legal semicircle being rejected.

I gave up doing homework about 45 years ago!

 

what are the exact values you are working with? what is the accuracy?

 

If I view the values and use a calculator the two sides of that equation are exactly equal, but when the computer evaluates it they are not, though the difference is, and I quote, -2.27373675443232E-13

 

you did not answer the questions but... for "too exact" fit you may add some tolerance

a = 4 * R ^ 2
b = ((X2 - X1) ^ 2 + (Y2 - Y1) ^ 2)
tol = 0.0001 ; sufficiently small value

then change comparison to something like

(a<b) or (ABS(a-b)< tol )

 

then change comparison to something like

(a<b) or (ABS(a-b)< tol )

Is not the (a<b) part redundant if you remove the ABS from the second part?
If (a<b) is true then (a-b) will be negative and so must be less than tol.
Remember that both a and b must be positive as they are some value squared.

 

Is not the (a<b) part redundant if you remove the ABS from the second part?
If (a<b) is true then (a-b) will be negative and so must be less than tol.
Remember that both a and b must be positive as they are some value squared.

Ah right, maybe just a check for (a < (b - tol))?

***EDIT***

Sorry, it's late for me here. On second thought panic mode's solution looks correct. It's a short circuit evaluation, so if the first part of the test is true (a < b) then it's obviously an invalid arc. Otherwise we just need to make sure that the absolute difference is small. Right?

 

This is the code I have now tried, which seems to do the job.

  D2 = (X2 - X1) ^ 2 + (Y2 - Y1) ^ 2
  D = Sqr(D2)
  If D < FPtol Then
  FindCentre = False
  Exit Function
  End If
   
  H = R ^ 2 - D2 / 4
  If H < 0 Then
  If H < -FPtol Then
  FindCentre = False
  Exit Function
  Else
  H = 0
  End If
  End If
  H = Sqr(H)

 

Is not the (a<b) part redundant if you remove the ABS from the second part?
If (a<b) is true then (a-b) will be negative and so must be less than tol.
Remember that both a and b must be positive as they are some value squared.

well 3 and 4 are positive numbers but 3-4 is negative and different from ABS(3-4)

but you can do it any way you like, i was just proposing one approach.

you can accomplish same using something like this:

4 * (R - tol) ^ 2 <= ((X2 - X1) ^ 2 + (Y2 - Y1) ^ 2)

 

If I view the values and use a calculator the two sides of that equation are exactly equal, but when the computer evaluates it they are not, though the difference is, and I quote, -2.27373675443232E-13

Could you PLEASE give the actual input values you are using? What is R, X1, Y1, X2, Y2. Your calculator is not immune to roundoff errors, either.

Since this is for a CNC, then aren't there tolerances on all of those dimensions? If the nominal numbers work out exact, meaning that it is right on the edge of impossibility, then doesn't that mean for some large fraction (perhaps something like half) of the possible actual values of the parameters that the arc IS impossible?

 

The values given by viewing the variables in the software were:
X1: 1.27
X2: 33.02
Y1: -3.81
Y2: -3.81
R: 15.875

These values come from an eagle board layout, processed by PCBgcode into a gcode file and finally post-processed by the software in question (author me), so they've been through quite a few floating point operations.

 

The values given by viewing the variables in the software were:
X1: 1.27
X2: 33.02
Y1: -3.81
Y2: -3.81
R: 15.875

These values come from an eagle board layout, processed by PCBgcode into a gcode file and finally post-processed by the software in question (author me), so they've been through quite a few floating point operations.

I agree that the input data results in an exact equality.

So this underscores one of the principle tenants of floating point operations -- never test for direct equality between floating point values because, most of the time, the result will be that they aren't equal since equality requires equality down to the last bit of the representation (which, for an IEEE-754 double-precision representation is about 15 sig figs, which is pretty much exactly what you are seeing).

It might not seem like you are testing for direct equality, but you are operating right at the edge of your inequality and thus (as you've keyed in on from the beginning) the boundary between "less than" and "not less than" has some fuzziness.

But it doesn't require a bunch of floating point operations to build up an error. The simple fact is that while 15.875 can be exactly represented, none of the other four values can. So even the starting data you have for X1 and X2 are not quite what you think they are.

For instance, 33.02 gets stored as 1.031875 x 2^5. The 1 is implied and the 0.031875 gets scaled by 2^52 which is 4647151865492930.56 but this has to be stored as an integer. I don't know if this is done by rounding or truncation. Since it is done in the processor's internal floating point representation (which, on an Intel machine, is 80 bits) I suspect it is via rounding. So this gets stored as

33.02 = [1 + (4647151865492931 / 2^52)] * 2^5

The difference between these two values is (0.44 / 2^52) * 2^5 which is ~3.13E-15.

1.27 = [1 + (1215971899390034/ 2^52)] * 2^0 which has an error of 1.776E-17 (it is close to being exactly representable).

The difference likely has an error that is about the same as the error in 33.02.

But when you square it, the error goes up by about a factor of 32 to somewhere around 1.0E-13.

So the difference you are seeing is quite within the realm of reasonable even without much accumulated round off error.

 

Ah right, maybe just a check for (a < (b - tol))?

***EDIT***

Sorry, it's late for me here. On second thought panic mode's solution looks correct. It's a short circuit evaluation, so if the first part of the test is true (a < b) then it's obviously an invalid arc. Otherwise we just need to make sure that the absolute difference is small. Right?

Not quite, this runs into the exact same problem as the original issue.

If (a < b) is true, the it MAY be an invalid arc. But it might also be true ONLY as an artifact of imprecision because either 'a' is artificially small or 'b' is artificially large when the true values would fail the test.

The "correct" way to do it depends on what the desired behavior is.

Which is better, to declare some impossible arcs as being possible, or to declare some possible arcs as being impossible?

It sounds like it is better to declare some impossible arcs as being possible on the premise that arcs that are exactly possible should not be declared impossible but that the set of impossible arcs that will get declared possible fall well within the precision limits of the tools in question and thus are arguably considered as "exact" arcs.

If that's the case, then you want to declare an arc to be impossible if (given that 'a' and 'b' are both positive values)

a < b - tol

where 'tol' is a small, positive value or, equivalently,

a + tol < b

Going back to the original equation, this becomes:

(4 * R ^ 2) + tol < ((X2 - X1) ^ 2 + (Y2 - Y1) ^ 2)

But this can be converted to a more meaningful form as

4 * (R + Rtol)^ 2 < ((X2 - X1) ^ 2 + (Y2 - Y1) ^ 2)

And now Rtol has the following meaning: We artificially increase the arc's radius to ensure that arcs that are too close to being exact circles will fail the 'impossibility' test.

You can probably set Rtol to something on the order of a micron.

 

well 3 and 4 are positive numbers but 3-4 is negative and different from ABS(3-4)

but you can do it any way you like, i was just proposing one approach.

you can accomplish same using something like this:

4 * (R - tol) ^ 2 <= ((X2 - X1) ^ 2 + (Y2 - Y1) ^ 2)

I think you need to add the tolerance to the radius. By subtracting it, you make it MORE likely that the inequality will hold and, thus, the arc be declared impossible.

 

It might not seem like you are testing for direct equality, but you are operating right at the edge of your inequality and thus (as you've keyed in on from the beginning) the boundary between "less than" and "not less than" has some fuzziness.

Yes, I know not to test for equality but I hadn't come across this problem with inequality.
You live and learn.

But this can be converted to a more meaningful form as

4 * (R + Rtol)^ 2 < ((X2 - X1) ^ 2 + (Y2 - Y1) ^ 2)

And now Rtol has the following meaning: We artificially increase the arc's radius to ensure that arcs that are too close to being exact circles will fail the 'impossibility' test.

You can probably set Rtol to something on the order of a micron.

I like that, thanks
I have now made a PCB with the modified software and all is well.

 

did we deserve picture...?

 

This isn't the one with the arc (that was one of my test patterns) and my photos are not the best you'll ever see.