我正在尝试制作一种算法，用给定的点集找到最大可能的形状。每个点都可以垂直、水平（相差 1 个单位）或对角线连接到另一个点。形成一个形状，点之间的这种连接会创建一个形状（显然）
（不要关注颜色）
一个点有 x 和 y 索引，它们决定了它在板上的位置。
我已经尝试了什么？
- 我的第一个想法是使用寻路算法，专门配置为在点网格中寻路回到起点，唯一的不同之处在于它会尝试寻找最长的路径，而不是最短的路径。这个方法失败了，因为寻路算法遍历了所有可能的点，但实际上并没有找到最大的形状。
- 我的第二个想法是找到相同形状的点（不是找到形状本身，而是找到形状内部确认的点），然后找到点集的。凸包给了我一组点，我可以尝试从中寻找凸包中的下一个点，从而得到形状。我放弃了这个想法，因为它太复杂了，因为我已经迷失在这种方法的理论中了。
那么我可以尝试什么来实现我想要做的事情呢？
5
最佳答案
3
您对每个点簇形成凸包的直觉是一个好主意。但是，由于线段的最大距离为 1，我们将不得不修改凸包算法，因为在形成凸包时，添加此约束并不能保证所有内角都小于 180 度。
这是一个潜在的解决方案。
我们可以修改，用有序路径遍历代替排序。路径必须由任意两点之间的长度为 1 的边组成，并且必须是圆形的。
假设没有重叠的形状，我们可以为每个点找到最长的连接圆形路径。我们首先构建一个邻接表来表示图，具有逆时针偏差，其中每个点都连接到距离一个单位的相邻点。然后我们从每个点执行深度优先搜索以探索所有可能的路径。以下是此类的一种实现：
def dfs(point, graph, path, visited, start_point, longest_path, global_visited):
path.append(point)
visited.add(point)
for neighbor in graph[point]:
if neighbor == start_point and len(path) > 2:
if len(path) > len(longest_path[0]):
longest_path[0] = path.copy()
elif neighbor not in visited and neighbor not in global_visited:
dfs(neighbor, graph, path, visited, start_point, longest_path, global_visited)
path.pop()
visited.remove(point)
这可以被记忆为在线性时间内运行，并且还存在许多不同的方法来获取该路径。
对于这些points，取自 Timeless 的回答
points = [
(4, 11), (5, 10), (5, 11), (5, 12), (6, 10),
(6, 11), (8, 12), (11, 11), (12, 10), (12, 12),
(13, 10), (13, 11), (16, 9), (17, 7), (17, 8),
(17, 10), (18, 8), (18, 9), (19, 10), (21, 9),
(21, 10), (21, 11), (22, 10), (22, 11),
]
我们发现了以下路径。
然后，我们可以修改 Graham 扫描算法，通过确保点之间的线段有效来纳入邻接约束。这是因为所遵循的路径偏向于逆时针方向，因此cross > 0。
def is_valid_segment(p1, p2):
return (abs(p1[0] - p2[0]) == 1 and abs(p1[1] - p2[1]) == 0) or \
(abs(p1[0] - p2[0]) == 0 and abs(p1[1] - p2[1]) == 1) or \
(abs(p1[0] - p2[0]) == 1 and abs(p1[1] - p2[1]) == 1)
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
def build_hull(points):
hull = []
for p in points:
while len(hull) >= 2 and cross(hull[-2], hull[-1], p) > 0:
if is_valid_segment(hull[-2], p):
hull.pop()
else:
break
hull.append(p)
return hull
我们可以将找到的路径传递到修改后的 Graham 扫描中来形成船体。
这是。这只是一个草稿，还有一些优化空间。
不太清楚您是否想在所有点中找到最大可能的形状。但是，假设您现在有了每个形状的周长点，则可以使用鞋带定理在线性时间内计算每个形状的：
，找到最大的形状。
1
-
1您的解决方案非常容易遵循，现在我得到了一些按预期工作的东西！
–
|
和如果我理解正确的话，您可以基于度量构建一个，然后根据由 组成的s集合构建一个：
from libpysal import weights
from shapely import MultiPoint
db = weights.DistanceBand.from_array(
points,
p=float("inf"), # "chebyshev"
threshold=1,
silence_warnings=True,
)
shapes = [
MultiPoint([points[n] for n in cc]).convex_hull
for cc in nx.connected_components(db.to_networkx())
if len(cc) > 1
]
注意：点 17 和 18 是相连的（因为对角线=1），不像您的图所显示的那样。
输出 （shapes）：
[
<POLYGON ((5 10, 4 11, 5 12, 6 11, 6 10, 5 10))>,
<POLYGON ((12 10, 11 11, 12 12, 13 11, 13 10, 12 10))>,
<POLYGON ((17 7, 16 9, 17 10, 19 10, 18 8, 17 7))>,
<POLYGON ((21 9, 21 11, 22 11, 22 10, 21 9))>
]
通过动画来突出三种距离之间的区别：
用过的points：
points = [
(4, 11), (5, 10), (5, 11), (5, 12), (6, 10),
(6, 11), (8, 12), (11, 11), (12, 10), (12, 12),
(13, 10), (13, 11), (16, 9), (17, 7), (17, 8),
(17, 10), (18, 8), (18, 9), (19, 10), (21, 9),
(21, 10), (21, 11), (22, 10), (22, 11),
]
2
-
“点 17 和 18 是相连的，与图中所示不同。”它们没有相连，因为最终形状应该由相邻的点组成（形状是所有外部点）。点 15 和 18 相距 2 个单位，因此它们之间不可能连接，因此形状无效。此连接“15->17->18->17->16”在 17 和 18 之间建立两次连接，也不是有效的形状。也许我应该澄清最终形状没有重叠的点或连接。
–
-
不，17 和 18 在我的图中是相连的，而在你的图中不是。另外，不要关注点之间的边缘/链接，这只是制作最终多边形之前的中间步骤。你可以看看来了解我的意思。祝你好运 😉
–
|
您正在寻找的每个“形状”都是图中
首先使用链接的维基百科页面中的任何算法找到双连通分量。然后，对于每个分量，从左上角的顶点开始并描画其轮廓。
跟踪移动过程中的区域： 对于每个向下的轮廓边，area += x1+x2。 对于每个向上的轮廓边，area -= x1+x2。 最后area = abs(area)/2。
记住最大形状的面积。
|
biggest？–
–
–
–
–
|