typescriptfloating-pointgeometrylineprecision

Is it correct and consistent to check two vertex points for equality?

I am writing a Typescript game where there are vertexes drawn to a canvas, and some edges coming from them. I want to determine if some of edges from different vertexes intersect. For this, I am using a generic doLinesIntersect function to determine if two edges intersect.

However, the problem is that it shows all lines as intersecting, because if two edges share a vertex, they compute as always intersecting, but I do not want this. I was able to get it "working" by checking manually to see if they share a vertex like so:

function doLinesTrulyIntersect(aX1: number, aY1: number, aX2: number, aY2: number, bX1: number, bY1: number, bX2: number, bY2: number): boolean {
  const sharesVertexes = (aX1 === bX1 && aY1 === bY1) || 
                         (aX1 === bX2 && aY1 === bY2) || 
                         (aX2 === bX1 && aY2 === bY1) || 
                         (aX2 === bX2 && aY2 === bY2);

  return !sharesVertexes && doLinesIntersect(
    aX1, aY1, aX2, aY2,
    bX1, bY1, bX2, bY2
  );
}

Basically, if two edges share a vertex, then they do not intersect.

But, will this always work? The logic is that since if two edges have the same vertex, then (because they're the same point), floating point equality testing should work, right? It's the exact same bits under the hood, after all.

However, I know that in general testing two floating points for equality is incorrect and inconsistent, but does that apply in this case?

Solution

  • If an endpoint X in one edge and an endpoint Y in another edge are set equal to the same point P, then X equals Y. Floating-point entities are not mystical entities that vary spontaneously, and testing for equality reports two things are equal if and only if they are equal.

    When you see cautions about comparing floating-point numbers for equality, the actual problem is about comparing any kind of approximations, not anything particular to floating-point arithmetic. Suppose there is some ideal number N and we have two approximations A and B to N. Will A and B be equal? Quite possibly not, because preparing two approximations in different ways will often produce different results. To estimate the percentage of the US population that has blue eyes, you might go out and sample 1,000 people and come up with some percentage A, and another person might go out and sample 1,000 other people and come up with some percentage B. Even though both of these are approximations of N, they are quite likely not equal.

    The reason this arises as a problem in floating-point arithmetic is that floating point was primarily designed to approximate real-number arithmetic, and it is primarily used for that. Note that it is floating-point arithmetic that approximates real-number arithmetic. Floating-point numbers are actual real numbers (a subset of them). There is nothing approximate or otherwise wonky about the numbers: Each floating-point number is exactly one real number. When you set a floating-point variable to a floating-point number, it retains that number. It does not change or become approximate.

    It is the process of calculating with floating-point numbers that introduces approximations and rounding errors: Most floating-point operations, including addition and other arithmetic, scientific functions, and converting to a floating-point format from decimal (including decimal numerals in source code or program input) are operations that may round their results to fit in the floating-point format.

    Note that the above is actually true of any numerical format. Calculations with fixed-point numbers also produce rounded results, when the exact mathematical result does not fit in the format. And calculations with integers are also adjusted to fit in the integer format. 7/3 in integer arithmetic produces 2, an error greater than 1 part in 10, whereas 7./3. in “double precision” floating-point has an error less than 1 part in a quadrillion. So integer arithmetic can be much worse for rounding errors than floating-point arithmetic. The reason people caution about floating-point rounding and not integer rounding is due to the predominant ways we use these formats, not due to their intrinsic susceptibility to errors.

    Further, once you are working with approximations, all of your results are approximate. You can get very large relative errors by subtracting two nearly equal numbers. People warn about comparison because it is one operation that novices may misuse. But anytime you are working with approximations, in any format, you should be aware of what errors can happen and how large they can be.

    All of the above is to give you context for determining what operations you can rely on. If you set two endpoints to the same point and later compare them, they will compare as equal.

    Some things that could go wrong in the problem you describe are: