修改numpy中的Ramer–Douglas–Peucker（RDP）算法以返回掩码而不是值

Question

我试图修改numpy implementation of the Ramer–Douglas–Peucker (RDP) algorithm，以返回筛选值的掩码，而不是包含值的筛选数组。在

问题是如何递归地返回正确的掩码。在

Answer 1

它有助于正确理解算法。如果每个递归调用中第一段和最后一段之间的所有点都在epsilon内，那么这些点应该标记为False，而start和end应该为True。我的解决方案是：

import numpy as np

def pldist(x0, x1, x2):
    return np.divide(np.linalg.norm(np.linalg.det([x2 - x1, x1 - x0])),
                     np.linalg.norm(x2 - x1))

def rdp_index(M, epsilon=0, dist=pldist):

    dmax = 0.0
    index = -1

    for i in xrange(1, M.shape[0]):
        d = dist(M[i], M[0], M[-1])

        if d > dmax:
            index = i
            dmax = d

    if dmax > epsilon:
        r1 = rdp_index(M[:index + 1], epsilon, dist)
        r2 = rdp_index(M[index:], epsilon, dist)

        return np.vstack((r1[:-1], r2))
    else:
        part_mask = np.empty_like(M, dtype = bool)
        part_mask.fill(False)
        part_mask[0] = True
        part_mask[-1] = True
        return part_mask

注意，这个实现使用递归，这个解决方案给出了大数据集https://stackoverflow.com/a/2401520/2082968的问题。一、 e.超过了递归调用的最大数量。下面是一个使用堆栈和while循环而不是递归调用的解决方案。此外，计算距离的效率更高一些。在

^{pr2}$