CODEWITHSUNDEEP
pythonmultidimensional-array
TheTask1337
TheTask1337

Reputation: 409

Checking if two points are connected in boolean 2D list

Is there any quick way to find out, if two points on 2D boolean area are connected and you can mobe only up, down, left and right on a square with value True? Let's say you would have following 6x6 2D list:

2D array

In code, that would be:

bool2DList = [6][6]
bool2DList = { True,  True,  False, False, True,  True,
               False, True,  True,  False, True,  True,
               False, True,  True,  False, False, True,
               False, False, False, False, False, True,
               False, False, False, False, True,  True,
               False, True,  True,  True,  True,  True }

Green squares have value True and blue ones False. I was thinking about function( it would probably need to be recursive ), in which you would put a 2D list as a argument alongside with a list of tuples ( coordinates ) of several points and finaly one tuple of special point, it could have header like this:

def FindWay( bool2DList,listOfPoints,specialPointCoord )

In this example the special point would be the point P with coordinates 5;1. Let's imagine you would start walking from that special points. What points could you reach without stepping on the blue squares? In this example, only points P4 and P5 ( the output could be let's say the coordinates of those points, so 0;5 and 5;3 ). It would probably need to be recursive, but I have no idea, how the body should look like.

Thank you.

Upvotes: 0

Views: 1177

Answers (2)

Katerina
Katerina

Reputation: 2600

Here is an option how you can code it:

A = np.array([[0, 1, 1, 0], [1, 0, 1, 1], [1, 0, 1, 0], [0, 1, 0, 0]]).astype(bool)
print A

[[False  True  True False]
 [ True False  True  True]
 [ True False  True False]
 [False  True False False]]

We can upgrade standard dfs function for our needs:

def dfs_area(A, start):
    graph = {}
    res = np.zeros_like(A)
    for index, x in np.ndenumerate(A):
        graph[index] = x
    visited, stack = set(), [start]

    while stack:
        vertex = stack.pop()
        x, y = vertex[0], vertex[1]
        if vertex not in visited and graph[vertex] == True:
            visited.add(vertex)
            if x < A.shape[0]-1:
                stack.append((x+1, y))
            if x > 1:
                stack.append((x-1, y))
            if y < A.shape[1]-1:
                stack.append((x, y+1))
            if y > 1:
                stack.append((x, y-1))
    res[tuple(np.array(list(visited)).T)] = 1

    return res

Assume that we want points connected to (1, 2) - second row, third value: 

mask = dfs_area(A, (1,2))

>> mask

array([[0, 1, 1, 0],
       [0, 0, 1, 1],
       [0, 0, 1, 0],
       [0, 0, 0, 0]])

Upvotes: 1

Prune
Prune

Reputation: 77847

I'm afraid there is no trivial way to do this. It's a graph traversal problem, and Python doesn't have built-in functions supporting that. I expect that you'll want a simple implementation of a breadth-first graph search.

Very briefly, you keep a list of nodes you've visited, but not handled; another list of nodes you've handled. The steps look like this:

handled = [] visited = [P] while visited is not empty: remove a node A from the visited list for each node B you can reach directly from A: if B is new (not in visited or handled list): put B on the visited list put A on the handled list

This will find all nodes you can reach. If you're worried about a particular node, then inside the loop, check to see whether B is your target node. When you put B on the visited list, put it on the front for depth-first, on the back for breadth-first.

In this application, "all the nodes you can reach" consists of the bordering ones with the same Boolean label.

Upvotes: 5

Related Questions