想法是给定平面上的一组格点,确定给定集合中有多少“组”点。 一组点定义如下:
Given a set S of lattice points,
it is said that these points form a group of points if and only if:
for each a of S the distance of the nearest point(s) is 1
该函数必须返回一个包含所有点组的列表。
input: --> point: list
output: --> group: list
如果有可能获得更好的算法,因为我不确定这段代码是否适用于每组点。
我的代码是这样的
def walk_point_path(points):
groups = []
points_x = sorted(points, key=lambda x: x[1])
visited = [points_x[0]]
q = [points_x[0]]
while points_x:
while q:
x, y = q.pop()
for x, y in (x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y):
if [x, y] not in visited and [x, y] in points_x:
q.append([x, y])
visited.append([x, y])
groups.append(visited)
for point in visited:
points_x.remove(point)
if len(points_x) > 0:
q = [points_x[0]]
visited = [points_x[0]]
return groups
最佳答案
考虑一些很好的 connected-components labeling 实现算法。
您当前的方法利用填充算法(一次一个组件
类型)来获取组中的分数。
关于algorithm - 给定一组格点,有多少组点?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57995549/