integergeometryplanerepresentationhash-function

Unambiguous hashable representation for plane defined by 3 points with integer coordinates


I need to be able to use planes as keys in a hash map. The planes are defined by three distinct points in 3d space. I have been unable to find a representation for a plane, that is the same no matter which points on it are used to construct it, so it can be hashed. The plane equation is out since it would lead to the usage of floating points, which are not precise.

Equality comparison can be implemented without such representation but ideally, there should be no need for special logic.

The question is how to obtain an unambiguous hashable representation for a plane defined by three points, which have integer coordinates; or failing that a hash function for such a plane. Other three points that represent the same plane should have the same hashcode.

I am using rust, but pseudo-code is ok. Performance is a concern.


Solution

  • Having three points P0, P1, P2, we can use two vectors

    P10 = P1 - P0
    P20 = P2 - P0
    

    and get normal using vector product:

    N = P10 x P20
    

    N components are integers. Then calculate GCD (greatest common divisor) of Nx, Ny, Nz and divide components to make them mutually prime (if this ter, is applicable to three values, perhaps "irreducible")

    G = GCD(GCD(Nx, Ny), Nz)
    A = Nx / G   //integer division
    B = Ny / G
    C = Nz / G
    

    and finally find 4th component of general plane equation substituting any point components (say P0) into equation

    A * P0x + B * P0y + C * P0z + D = 0
    D = - (A * P0x + B * P0y + C * P0z)
    

    Definitely D is integer, all coefficients are mutual prime/irreducible, so tuple (A,B,C,D) is a kind of "normalized" plane equation.

    Both this equation and any equation with proportional coefficients represents the same plane and might be used to check if some point P belongs to given plane.

    if (A * Px + B * Py + C * Pz + D == 0)...