I have an irregular polygonal grid (basic scipy Voronoi cells) as shown below:
Thresholded to show a clearer picture (hopefully):

Although not exactly, this can be replicated by generating a voronoi cell distribution with an irregular grid of points and then assigning weights to the edges based on their length (or randomly)
Some code to generate the input:
from random import *
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import Voronoi, voronoi_plot_2d
def addnoise(a):
n1=random()
n2=choice([1,2])
noise=((-1)**n2)*n1
return a+noise
X=np.linspace(0,20,50)
Y=np.linspace(0,20,30)
gridspace_x=X[1]
gridspace_y=Y[1]
X,Y=np.meshgrid(X,Y)
X=[i for s in X for i in s]
Y=[i for s in Y for i in s]
X=[addnoise(x) for x in X]
Y=[addnoise(y) for y in Y]
points=tuple(zip(X,Y))
vor = Voronoi(points)
vertices=vor.vertices
edges=[i for i in vor.ridge_vertices if (i[0] and i[1])!=-1]
weights=[(vertices[e[0]]**2+vertices[e[1]]**2)**0.5 for e in edges]
This should give something somewhat similar to this. Grid spacing along y being higher will be closer.
Preferred output -
cables=[
[2,5,9,13], # the numbers correspond to the index of the edges in the edge array
[4,7,9,15,18,32]
]
I want to find "cables", or in other words, points connected by a line segment that has the edge color orange or above (each edge has a weight, and the color corresponds to the weight, and the color threshold is just a threshold of the weight) and the angle between the line segments is greater than some angle (120 degrees here for example). I have marked two examples of what I want to find. Basically I want to get a list/array or all of these cables. Each cable probably represented by an array of edges.
My initial attempt logic is somewhat like this -
- Find the edges surrounding every point
- Starting from some corner, check if any of the edges satisfy the weight threshold.
- If yes, and if there is already an edge before this one in the cable array.
- If yes, check the angle between this edge and the previous edge.
- If it satisfies the angle criteria, append it to the cable array.
- Recursively call this function on the other end of the last appended edge.
Keep track of the recursion level in the meanwhile and the number of qualifying edges, at every vertex. If number of qualifying edges is more than one, make a copy of the cable array until the recursion level. This should take care of any branching.
Apart from potential bugfixes, it seems to get caught in a loop where the edges are just edges of a polygon like a heptagon, where the angle at all edges is more than 120 but still it is a closed loop. Also I haven't been able to figure out a way to not have it go back on the way it came. So clearly there are flaws in this logic. I just need suggestions on what can be improved. I was thinking of perhaps computer vision techniques to reduce the complexity of the logic, but I have no idea how. Another idea I had was that instead of checking one edge at any time, check for two edges that qualify, with the angle measured between qualifying edges at the vertex instead of trying to compare it with a previous one.
Any suggestions on how to improve the algorithm are appreciated.The gist of the question is simple: How do I find these cables? I can add more clarification if required. Thanks!
