python - 具有至少 k 个点的 Numpy 查找区间

Question

我在区间 [0,20] 中有一些点
我有一个大小为 window_size=3 的窗口我可以在上述区间内移动。因此窗口的开始 - 让我们调用 start被限制为 [0,17] .
假设我们有一些 points以下:

points = [1.4,1.8,   11.3,11.8,12.3,13.2,  18.2,18.3,18.4,18.5]

如果我们想要至少 min_points=4指出窗口的起始范围(我手动找到)的解决方案是:

suitable_starts = [[10.2,11.3],[15.5,17.0]]

即大小的开始 3窗口可以来自 10.2至11.3来自 15.5至17.0 .简单地说，窗口的对应端只是 +3的起始范围。
我正在寻找一种通过巧妙的算法快速解决此问题的方法 numpy或 scipy或其他功能。
我正在寻找的一般功能是:

get_start_windows(interval = [0,20],
    window_size = 3.0, 
    points = [1.4,1.8,11.3,11.8,12.3,13.2,18.2,18.3,18.4,18.5],
    min_points = 4

    return suitable_starts # suitable_starts = [[10.2,11.3],[15.5,17.0]]

笔记:
正如评论中的某个人指出的那样，有时在某些特殊情况下，点之间的距离正好是 window_size。然而实际上，这些点是双浮点数，它们不可能完全分开 window_size，因此可以忽略它们。
这些特殊示例包括:

points = [1.4,1.8,  11.3,11.8,12.3,13.2,14.2,15.2,16.2,17.2,18.2,18.3,18.4,18.5]

但这些可以安全地忽略。

Answer 1

经过一番挣扎，我想出了这个解决方案。
首先是一些解释和思路:

理想情况下，我们希望设置一个窗口大小并将其从最左边的可接受点滑动到最右边的可接受点，并在 min_points 时开始计数。在窗口中，并在 min_points 时完成计数不再在里面(想象一下它是一个抽搐操作者左右)

基本的陷阱是我们想要离散滑动，所以这里的技巧是只检查点的数量何时低于或高于 min_points ，这意味着每次出现元素或 window_size在它下面(如 optional_starts 反射(reflect))

然后迭代 optional_starts并采样第一次满足条件，以及每个间隔满足条件的最后一个

所以下面的代码是如上所述编写的:

def consist_at_least(start, points, min_points, window_size):
    a = [point for point in points if start <= point <= start + window_size]
    return len(a)>=min_points
    


points = [1.4,1.8,   11.3,11.8,12.3,13.2,  18.2,18.3,18.4,18.5]
min_points = 4
window_size = 3
total_interval = [0,20]
optional_starts = points + [item-window_size for item in points if item-window_size>=total_interval[0]] + [total_interval[0] + window_size] + [total_interval[1] - window_size] + [total_interval[0]]
optional_starts = [item for item in optional_starts if item<=total_interval[1]-window_size]
intervals = []
potential_ends = []
for start in sorted(optional_starts):
    is_start_interval = len(intervals)%2 == 0
    if consist_at_least(start, points, min_points, window_size):
        if is_start_interval:
            intervals.append(start)
        else:
            potential_ends.append(start)
    elif len(potential_ends)>0 :
        intervals.append(potential_ends[-1])
        potential_ends = []
if len(potential_ends)>0:
    intervals.append(potential_ends[-1])

print(intervals)

输出:

[10.2, 11.3, 15.5, 17]

每 2 个连续元素反射(reflect)区间的开始和结束