c++algorithmadjacency-list

How to find adjacent points in a 3D space in c++


I have a couple of points in a 3D space, and I want to write a condition to determine whether two points are adjacent: are they only a single unit apart in the integer lattice?

I have a struct named Point that holds x,y and z coordinates. Then in the main function, I set the values for points a,b,c,d,e and push them into a vector. Then in the for loop I want to check if two points are adjacent or not. Currently I'm just checking if they are on the same axis, but I do not know how to proceed.

struct Point {
   int x;
   int y;
   int z;
};
bool adjacent(Point a, Point b) { ??? }

int main() {
    struct Point a = {0, 0, 0};
    struct Point b = {0, 0, -1};
    struct Point c = {1, 0, -1};
    struct Point d = {1, -1, -1};
    struct Point e = {2, -1, -1};

    assert(adjacent(a, b));
    assert(adjacent(b, c));
    assert(adjacent(c, d));
    assert(adjacent(d, e));
    assert(!adjacent(a, c));
}

By adjacent I mean something like in this photo: enter image description here


Solution

  • Very briefly:

    for each pair of points:
        if two of the three coordinates are equal AND
                  the other coordinate differs by 1:
            then mark the pair as adjacent.
    

    Iterating through point pairs is simple enough: the first point a walks through indices 0-(n-2); the second point b walks through indices from a's position through the end, n-1.

    Checking adjacency is also easy, given integer coordinates.

    diff = abs(a.x - b.x) + 
           abs(a.y - b.y) + 
           abs(a.z - b.z)
    

    diff = 1 iff the points are adjacent.