algorithm - 减少直线上的点数

Question

我正在寻找算法来减少多段线、节点线(环路或非环路)的 LOD。 简单来说，我想获取高分辨率的海岸线数据，并能够将其 LOD 降低百倍或千倍以在小比例尺下进行渲染。

我找到了多边形缩减算法(但它们需要三角形)和拉普拉斯平滑，但这似乎并不是我所需要的。

Answer 1

我修改了 culebrón's answer 中的代码，不再需要 Vec2D/Line 类，而是将点作为元组列表处理。

代码稍微不太整洁，但更短，也更快(900 分，原始代码用了 2966 毫秒，这个版本用了 500 毫秒 - 仍然比我想要的慢一点，但有所改进)

def _vec2d_dist(p1, p2):
    return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2


def _vec2d_sub(p1, p2):
    return (p1[0]-p2[0], p1[1]-p2[1])


def _vec2d_mult(p1, p2):
    return p1[0]*p2[0] + p1[1]*p2[1]


def ramerdouglas(line, dist):
    """Does Ramer-Douglas-Peucker simplification of a curve with `dist`
    threshold.

    `line` is a list-of-tuples, where each tuple is a 2D coordinate

    Usage is like so:

    >>> myline = [(0.0, 0.0), (1.0, 2.0), (2.0, 1.0)]
    >>> simplified = ramerdouglas(myline, dist = 1.0)
    """

    if len(line) < 3:
        return line

    (begin, end) = (line[0], line[-1]) if line[0] != line[-1] else (line[0], line[-2])

    distSq = []
    for curr in line[1:-1]:
        tmp = (
            _vec2d_dist(begin, curr) - _vec2d_mult(_vec2d_sub(end, begin), _vec2d_sub(curr, begin)) ** 2 / _vec2d_dist(begin, end))
        distSq.append(tmp)

    maxdist = max(distSq)
    if maxdist < dist ** 2:
        return [begin, end]

    pos = distSq.index(maxdist)
    return (ramerdouglas(line[:pos + 2], dist) + 
            ramerdouglas(line[pos + 1:], dist)[1:])