在网格上找到整数点数组的凹壳

Question

我在整数网格上有数千个点的数组。我正在寻找一种快速找到点凹壳的方法。如果点在任何基本方向上相距 1 个单位，则它们是相邻的。我对边界是否应该沿对角线移动（即如下图所示从[391,4036] -> [392,4037]）感到矛盾，而是优先考虑计算速度。没有内部孔。我正在用 python 工作。

我最初的想法是循环遍历每个点，并查找它的主要邻居是否也在点集中，如果其中一个不在，则将该点标记为位于形状的边界上。然后我需要一些其他算法来对这些点进行排序以获得（顺时针或逆时针）边界。

这不会随着点数的变化而很好地扩展，因为对于每个点，我需要对照集合中的每个其他点来检查它的四个基本方向以获得成员资格。

寻找边界点的Python代码：

boundary_pixels = [
    (row_idx, col_idx)
    for (row_idx, col_idx) in full_pixels
    if not (
        ((row_idx+1, col_idx) in full_pixels) & 
        ((row_idx-1, col_idx) in full_pixels) &
        ((row_idx, col_idx+1) in full_pixels) & 
        ((row_idx, col_idx-1) in full_pixels)
    )
]

我知道找到凹壳是一个难题，但是当点在网格上均匀分布时有解决方案吗？

Answer 1

有一个年轻的存储库（

concav_hull

，依赖于 JavaScript 算法）。

你可能会觉得很有趣。如果是这样，这里有一个建议，您可以根据需要进行调整：

import matplotlib.pyplot as plt
from scipy.spatial import ConvexHull
from concave_hull import concave_hull, concave_hull_indexes

convex_hull = ConvexHull(points[:, :2])

idxes = concave_hull_indexes(points[:, :2], length_threshold=-0)

plt.plot(points[:, 0], points[:, 1], "rx")

for f, t in zip(idxes[:-1], idxes[1:]):
    seg = points[[f, t]]
    plt.plot(seg[:, 0], seg[:, 1], "k-.")

使用的输入：

import numpy as np

op = [
    (389, 4034), (389, 4035), (389, 4036),
    (390, 4035), (390, 4036),
    (391, 4034), (391, 4035), (391, 4036),
    (392, 4032), (392, 4033), (392, 4034), (392, 4035), (392, 4036), (392, 4037),
    (393, 4032), (393, 4033), (393, 4034), (393, 4035), (393, 4036), (393, 4037),
    (394, 4034), (394, 4035), (394, 4036), (394, 4037)
]

points = np.array(op)