python-3.x 求网格上整数点数组的凹船体

ccgok5k5 于 12个月前发布在 Python

关注(0)|答案(1)|浏览(157)

我在一个整数网格上有数千个点的数组。我正在寻找一种快速找到点的凹船体的方法。如果点在任何基本方向上相距1个单位，则它们是相邻的。我对边界是否应该对角移动感到矛盾（即从 [391，4036] -> [392，4037] 中偷工减料），而是优先考虑计算速度。没有内部漏洞。我正在使用Python。
x1c 0d1x的数据
我最初的想法是遍历每一个点，并查找它的基数邻居是否也在点集中，如果其中一个不在，那么将该点标记为在形状的边界上。然后我需要一些其他的算法来排序这些点以获得（顺时针或逆时针）边界。
这不会很好地与点的数量，因为对于每个点，我需要检查它的四个基本方向对其他点的成员资格。
查找边界点的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)
    )
]

字符串
我知道找到凹壳是一个困难的问题，但有一个解决方案时，点均匀分布在一个网格？

python-3.x

来源：https://stackoverflow.com/questions/77773403/find-a-concave-hull-of-an-array-of-integer-points-on-a-grid

1条答案

按热度按时间

k4aesqcs1#

有一个年轻的repo（concav_hull，* 依赖于JavaScript算法 *）。
你可能会觉得很有趣。如果是这样，这里有一个建议，你可以根据需要进行调整：

import matplotlib.pyplot as plt
from concave_hull import concave_hull_indexes

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)

型

赞(0）回复(0）举报 12个月前

我来回答

python-3.x 求网格上整数点数组的凹船体

1条答案

相关问题

热门标签

最新问答