如何检查给定的点是否形成连续的图形？（蟒蛇）-解网

问：

我需要实现一个函数，该函数获取任意数量的点的坐标（在 3D 空间中），如果点形成连续图形，则返回 True。下面有三个图（为简单起见，在 2D 空间中）。对于前两种情况，必须返回 True。最后一个应返回 False。

假设数组中的所有点都位于方形网格的节点上，该网格的步骤由函数作为第二个参数。

该函数应如下所示：

def is_continuous(points, step): # points is a list of tuples with coordinates
    # if points form a continuous figure:
        return True
    # else:
        return False

python 数组算法数学几何 networkx

“如果数组中每个点都有一个相邻的点（换句话说，如果点形成一个连续的图形），则返回 True”——这些是完全不同的东西。仅包含单个点的数组将满足第二个条件，但不满足第一个条件，而第三个示例输入将满足第一个条件，但不满足第二个条件。

0赞 ae_fed 11/11/2023

@user2357112 你说得对，谢谢。我在第一个条件上犯了一个错误，我会删除它。

0赞 esqew 11/11/2023

您实际上并没有在这里提出问题 - 我们是否可以将您的代码视为一个最小的可重现示例，并解释您在该尝试中具体遇到困难的地方？如何提问

1赞 Kelly Bundy 11/11/2023

这不就是一个简单的DFS或BFS吗？清晰/测试的示例数据会很好。

1赞 Simon Goater 11/11/2023

您可以执行类似于泛洪填充算法的操作，然后只需将从任意起点访问的节点数与总数进行比较即可。

答：

2赞 Timeless 11/11/2023 #1

IIUC，如果你想使用networkx，你可以试试：

def as_grid(points):
    import matplotlib.pyplot as plt
    plt.grid(linewidth=4, color="black", zorder=1)
    plt.scatter(*points, color="red", zorder=2, s=300)
    plt.xticks(range(-1, 8)); plt.yticks(range(-1, 8))
    plt.show()
    
def is_conn(points):
    import networkx as nx
    from libpysal import weights
    ws = weights.KNN.from_array(list(zip(*points)), k=3)
    G = ws.to_networkx().to_undirected()
    return "Connected" if nx.is_connected(G) else "Not connected"
#https://networkx.org/documentation/stable/auto_examples/geospatial/plot_points

注意：边将根据 k 个最近邻而有所不同。例如，第三个数据集：

如果你想考虑一个 x-y ，也许你可以使用 DistandBrand ：step

def is_conn(points, stepx, stepy):
    import networkx as nx
    from libpysal import weights
    mdis = ((stepx)**2 + (stepy)**2)**0.5
    ws = weights.DistanceBand.from_array(list(zip(*points)), threshold=mdis)
    G = ws.to_networkx().to_undirected()
    return "Connected" if nx.is_connected(G) else "Not connected"

is_conn([x3, y3], 1, 1) #'Not connected'
is_conn([x3, y3], 2, 2) #'Connected'

输出：

for p in [(x1, y1), (x2, y2), (x3, y3)]:
    print(is_conn(p))
    as_grid(p)

使用的配置：

x1 = [1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5]
y1 = [4, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3]

x2 = [1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5]
y2 = [2, 3, 4, 5, 6, 2, 3, 5, 6, 2, 6, 2, 3, 4, 5, 6, 2, 3, 4, 5]

x3 = [1, 1, 2, 2, 3, 4, 4, 5, 5, 6]
y3 = [5, 6, 5, 6, 6, 2, 3, 2, 3, 2]

是的，没有注意到更新。似乎更像是他们想要的。不过，仍然不清楚他们想要什么。我向他们询问了数据以澄清问题，但他们忽略了我，我想现在他们有一个他们接受的答案，他们永远不会澄清。我希望人们不要再回答不清楚的问题，等到它们被修复......

1赞 ae_fed 11/13/2023

@Timeless 您的方法在 Python 3 中完美运行，包括 3D 空间！再次感谢！也许您知道 Python 2 有类似的方法吗？不幸的是，libpysal 库不适用于 Python 2，而替代的 Pysal 没有to_networkx方法......

1赞 gimix 11/12/2023 #2

我相信 OP 的目标只是知道是否只有一个连续的数字。如果是这种情况，没有外部库的可能解决方案是：

保留迄今为止发现的数字清单
对于每个点，检查它是否链接到前一个点（即对角线或垂直链接到上一行中的点，或水平链接到上一列中的点），然后如果该点：
- 没有链接，将其添加到新图形中
- 具有指向一个图中包含的点的一个或多个链接，将其添加到该图中
- 具有指向不同图形中包含的点的链接，合并该图形并添加点

def cont_figure(width, height, points):
    grid = [[0 for w in range(width)] for h in range(height)]
    for no, pt in enumerate(points, start=1):
        grid[pt[0]][pt[1]] = no
    figures = []
    for no, pt in enumerate(points, start=1):
        links = []
        if pt[0] > 0 and grid[pt[0]-1][pt[1]]:
            links.append(grid[pt[0]-1][pt[1]])
        if pt[1] > 0 and grid[pt[0]][pt[1]-1]:
            links.append(grid[pt[0]][pt[1]-1])
        if pt[0] > 0 and pt[1] > 0 and grid[pt[0]-1][pt[1]-1]:
            links.append(grid[pt[0]-1][pt[1]-1])
        if pt[0] < width-2 and pt[1] > 0 and grid[pt[0]+1][pt[1]-1]:
            links.append(grid[pt[0]+1][pt[1]-1])
        pt_figs = sorted({fig_no for fig_no, figure in enumerate(figures) for link in links if link in figure})
        if not pt_figs:
            figures.append([no])
        elif len(pt_figs) == 1:
            figures[pt_figs[0]].append(no)
        else:
            for fig_no in range(len(pt_figs)-1,0,-1):
                figures[fig_no-1] += figures[fig_no]
                figures[fig_no-1].append(no)
                del(figures[fig_no])
    return len(figures) == 1

上一个：如何在 GeoGebra 中重复旋转一个点

下一个：根据用户输入定义任何数学函数

如何检查给定的点是否形成连续的图形？（蟒蛇）

How to check if given points form a continuous figure? (Python)

评论

评论