Skip to content

Instantly share code, notes, and snippets.

@Didericis
Last active April 18, 2020 02:34
Show Gist options
  • Save Didericis/7e6487afcbabacfc1254f3ac8cb7f8cb to your computer and use it in GitHub Desktop.
Save Didericis/7e6487afcbabacfc1254f3ac8cb7f8cb to your computer and use it in GitHub Desktop.
def get_cluster(cluster, point, traversed_points):
cluster.add(point)
traversed_points = traversed_points - {point}
untraversed_neighbors = point["neighbors"] - traversed_points
while untraversed_neighbors:
next_point = untraversed_neighbors.pop()
custer = get_cluster(cluster, next_point, traversed_points)
return cluster
def get_clusters(x_y_vectors, epsilon, min_connections):
points = []
clusters = []
for coords in x_y_vectors:
points.append({
"coords": coords,
"neighbors": set()
})
for i, point in enumerate(points):
for other_point in points[i+1:]:
if calculate_distance(point["coords"], other_point["coords"]) < epsilon:
point["neighbors"].add(other_point)
other_point["neighbors"].add(point)
clusters = set()
untraversed_points = set()
while untraversed_points:
point = untraversed_points.pop()
cluster = get_cluster(set(), point, traversed_points)
untraversed_points = untraversed_points - traversed_points
if (len(cluster) >= min_connections):
cluster.add(cluster)
return clusters
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment