Please bear with me as this is my first post after a long-time (unregistered) user of the site.
I have an image file where there are specific regions in the image of interest. These regions have be identified by testing each pixel/cell individually and determining if it is of interest - appending those of interest to a new list.
So I have a list of the form:
[[22,25], [22,29], [23,24], ...]
which contains the indices of all my special pixels where on a macro scale if I were to plot these images as white on an otherwise black image; I would have essentially two contiguous white masses. I want to sort this list into another nested list in which they are grouped by continuity. That is all of the pixels that are associate with a white mass will be grouped together in a nested list
My Thought process was to just grab the first point (fpoint) and then test all other points (pts) with respect to that point by testing the x and y index to see if the difference of the two points is not greater than one for both x and y. so each test would be something like this:
if ( (np.absolute(fpoint[0] - pts[0]) <= 1) and (np.absolute(fpoint[1] - pts[1]) <= 1) ):
#add this point to the same nested list as my fpoint
#remove this point from the initial list and continue to chisel down the original list until it is all sorted into my new list
Seeing as this method in one pass I may get up to 8 neighboring points I will need to keep track of those to test each of them individually as I have removed them from my old list.
So by the end of this I hope to have something like:
groupedList = [[[22,23], [21,24], [20,24], ...], [[102, 51], [102, 50], [100, 55]...]]
To reiterate in a 1-dimensional case:
let's say I have a list:
[1, 22, 5, 20, 3, 4, 21, 2]
At the end of my function I hope to have a list similar to:
[ [1, 5, 3, 4, 2], [22, 20, 21] ]
Because as a set, 1, 5, 3, 4, and 2 are 'contiguous' as are 22, 20, and 21. I do not care about the order of the numbers as long as they are separated.
Something about a recursive bit of code sounds like an elegant solution to my problem but I am just not able to produce it. Thank you for your time, Heath M.
Accredited to Anders Munch
Taking what Anders Munch had given me, I was able to come to this point which proved satisfactory!
def candidate_neighbors(node):
return ((node[0]-1, node[1]-1), (node[0]-1, node[1]), (node[0]-1, node[1]+1), (node[0], node[1]-1),
(node[0], node[1]+1), (node[0]+1, node[1]-1), (node[0]+1, node[1]), (node[0]+1, node[1]+1))
def neighboring_groups(nodes):
remain = set(nodes)
while len(remain) > 0:
visit = [remain.pop()]
group = []
while len(visit) > 0:
node = visit.pop()
group.append(node)
for nb in candidate_neighbors(node):
if nb in remain:
remain.remove(nb)
visit.append(nb)
yield tuple(group)
nodes = ((22, 23), (22, 24), (21, 23), (1, 5), (2, 6), (21, 22), (3, 5))
print(tuple(neighboring_groups(nodes)))
(((1, 5), (2, 6), (3, 5)), ((22, 24), (22, 23), (21, 22), (21, 23)))
A problem with your initial approach is that it O(n2). You are proposing to compare each point to every other point, which gets slow fast. You need a faster way to find the neighbors of a given point, and faster in Python usually means to use a dict, or in this case its close relative, the set.
This can be seen as a graph-theoretical problem: You have a set of nodes (points) that are connected to up to 8 neighboring nodes. In graph theory lingo, if I remember it correctly, the task is to find the connected subgraphs of this graph. The algorithm for that is quite simple: You start a subgraph by picking an arbitrary node, and then you keep visiting neighbors of the nodes already in the subgraph until there are no more neighbors left. Then you start over again with the next subgraph.
Long story short, here is the code for the 1-dimensional case:
def candidate_neighbors(node):
return [node-1, node+1]
def neighboring_groups(nodes):
remain = set(nodes)
while len(remain) > 0:
visit = [remain.pop()]
group = []
while len(visit) > 0:
node = visit.pop()
group.append(node)
for nb in candidate_neighbors(node):
if nb in remain:
remain.remove(nb)
visit.append(nb)
yield group
nodes = [1, 22, 5, 20, 3, 4, 21, 2]
print(list(neighboring_groups(nodes)))
The 2-dimensional case is simply a matter of replacing the candidate_neighbors function with something that yields the 8 candidate neighbors of your pixel positions. You will need to use a slightly different representation of points, one that is hashable and can be put in a set. But that's easy, just use 2-element tuples instead of 2-element lists.