CODEWITHSUNDEEP
algorithmgriditeration
Tyler Durden
Tyler Durden

Reputation: 11532

Efficiently list every unique pair of points in a grid

Seemingly an easy problem, I am looking for an algorithm to list every unique pair of points in a grid that are not collinear with the origin. The trick is to somehow avoid all the different symmetries and coincidences. This is what I have so far:

for( int x1 = 0; x1 <= s; x1++ ){
    for( int y1 = 0; y1 <= s; y1++ ){
        if( x1 == 0 && y1 == 0 ) continue; // P1 is coincident with origin
        for( int x2 = x1; x2 <= s; x2++ ){
            for( int y2 = 0; y2 <= s; y2++ ){
                if( x1 == x2 && y2 >= y1 ) continue;
                if( x1 * y2 == x2 * y1 ) continue; // points are collinear with origin
                // this is a valid point
            }
        }
    }
}

Upvotes: 1

Views: 78

Answers (1)

user1196549
user1196549

Reputation:

Enumerate all unique pairs (by defining an order on the grid points) and disregard those that are aligned with the origin.

def Pair(X0, Y0, X1, Y1):
    if X0 * Y1 != X1 * Y0:
        # Non collinear with the origin
        Accept(X0, Y0, X1, Y1)

# Enumerate all (X0, Y0)
for X0 in range(NX):
    for Y0 in range(NY):
        # Enumerate all (X1, Y1) > (X0, Y0) in the lexicographical sense

        # 1) X1 == X0, Y1 > Y0
        X1= X0
        for Y1 in range(Y0 + 1, NY):
            Pair(X0, Y0, X1, Y1)

        # 2) X1 > X0
        for X1 in range(X0 + 1, NX):
            for Y1 in range(NY):
                Pair(X0, Y0, X1, Y1)

Or, better:

# Enumerate all (X0, Y0)
for X0 in range(NX):
    for Y0 in range(NY):
        # Enumerate all (X1, Y1) > (X0, Y0) in the lexicographical sense
        for X1 in range(X0, NX):
            for Y1 in range(0 if X1 > X0 else Y0 + 1, NY):
                if X0 * Y1 != X1 * Y0:
                    # Non collinear with the origin
                    Accept(X0, Y0, X1, Y1)

Upvotes: 1

Related Questions