Уменьшить количество очков в строке

Я ищу алгоритмы для уменьшения LOD полилиний, линий (петлевых или нет) узлов. Проще говоря, я хочу взять данные береговой линии с высоким разрешением и иметь возможность уменьшить их уровень детализации в сотни или тысячи раз, чтобы визуализировать их в мелком масштабе.

Я нашел алгоритмы сокращения полигонов (но они требуют треугольников) и лапласовское сглаживание, но это не совсем то, что мне нужно.


algorithm polygon level-of-detail
person culebrón    schedule 04.04.2010    source источник

Ответы (8)


arrow_upward
17
arrow_downward

Я изменил код в ответе Кулеброна, удалив потребность в классах 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:])
person dbr    schedule 07.06.2012
comment
Хороший. Здесь занятия были бесполезны. Прекратите писать курсы. :) Мне нравится, что кто-то обратил внимание на мой код. - person culebrón; 21.06.2012

arrow_upward
14
arrow_downward

Решение, которое я нашел и, вполне вероятно, буду использовать, это Ramer-Douglas-Peucker алгоритм. Он используется в PostGIS.

Я опубликовал мою собственную реализацию на Python (сайт в настоящее время недоступен, ниже было взято с archive.org)

#!/usr/bin/python
"""Ramer-Douglas-Peucker line simplification demo.
Dmitri Lebedev, [email protected]

http://ryba4.com/python/ramer-douglas-peucker
2010-04-17"""

def ramerdouglas(line, dist):
    """Does Ramer-Douglas-Peucker simplification of
    a line with `dist` threshold.
    `line` must be a list of Vec objects,
    all of the same type (either 2d or 3d)."""
    if len(line) < 3:
        return line

    begin, end = line[0], line[-1]
    distSq = [begin.distSq(curr) -
        ((end - begin) * (curr - begin)) ** 2 /
        begin.distSq(end) for curr in line[1:-1]]

    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:])

class Line:
    """Polyline. Contains a list of points and outputs
    a simplified version of itself."""
    def __init__(self, points):
        pointclass = points[0].__class__
        for i in points[1:]:
            if i.__class__ != pointclass:
                raise TypeError("""All points in a Line
                                must have the same type""")
        self.points = points

    def simplify(self, dist):
        if self.points[0] != self.points[-1]:
            points = ramerdouglas(self.points, dist)
        else:
            points = ramerdouglas(
                self.points[:-1], dist) + self.points[-1:]
        return self.__class__(points)

    def __repr__(self):
        return '{0}{1}'.format(self.__class__.__name__,
            tuple(self.points))

class Vec:
    """Generic vector class for n-dimensional vectors
    for any natural n."""
    def __eq__(self, obj):
        """Equality check."""
        if self.__class__ == obj.__class__:
            return self.coords == obj.coords
        return False

    def __repr__(self):
        """String representation. The string is executable as Python
        code and makes the same vector."""
        return '{0}{1}'.format(self.__class__.__name__, self.coords)

    def __add__(self, obj):
        """Add a vector."""
        if not isinstance(obj, self.__class__):
            raise TypeError

        return self.__class__(*map(sum, zip(self.coords, obj.coords)))

    def __neg__(self):
        """Reverse the vector."""
        return self.__class__(*[-i for i in self.coords])

    def __sub__(self, obj):
        """Substract object from self."""
        if not isinstance(obj, self.__class__):
            raise TypeError

        return self + (- obj)

    def __mul__(self, obj):
        """If obj is scalar, scales the vector.
        If obj is vector returns the scalar product."""
        if isinstance(obj, self.__class__):
            return sum([a * b for (a, b) in zip(self.coords, obj.coords)])

        return self.__class__(*[i * obj for i in self.coords])

    def dist(self, obj = None):
        """Distance to another object. Leave obj empty to get
        the length of vector from point 0."""
        return self.distSq(obj) ** 0.5

    def distSq(self, obj = None):
        """ Square of distance. Use this method to save
        calculations if you don't need to calculte an extra square root."""
        if obj is None:
            obj = self.__class__(*[0]*len(self.coords))
        elif not isinstance(obj, self.__class__):
            raise TypeError('Parameter must be of the same class')

        # simple memoization to save extra calculations
        if obj.coords not in self.distSqMem:
            self.distSqMem[obj.coords] = sum([(s - o) ** 2 for (s, o) in
                zip(self.coords, obj.coords)])
        return self.distSqMem[obj.coords]

class Vec3D(Vec):
    """3D vector"""
    def __init__(self, x, y, z):
        self.coords = x, y, z
        self.distSqMem = {}

class Vec2D(Vec):
    """2D vector"""
    def __init__(self, x, y):
        self.coords = x, y
        self.distSqMem = {}

if __name__ == '__main__':
    coast = Line([
    Vec2D( 6.247872 , 11.316756 ),
    Vec2D( 6.338566 , 11.316756 ),
    Vec2D( 6.633323 , 11.205644 ),
    Vec2D( 6.724018 , 11.205644 ),
    Vec2D( 6.792039 , 11.205644 ),
    Vec2D( 7.154817 , 11.372311 ),
    Vec2D( 7.313532 , 11.400089 ),
    Vec2D( 7.381553 , 11.344533 ),
    Vec2D( 7.336206 , 11.288978 ),
    Vec2D( 7.200164 , 11.288978 ),
    Vec2D( 7.154817 , 11.261200 ),
    Vec2D( 7.132143 , 11.233422 ),
    Vec2D( 7.154817 , 11.150089 ),
    Vec2D( 7.268185 , 11.177867 ),
    Vec2D( 7.313532 , 11.122311 ),
    Vec2D( 7.404227 , 11.150089 ),
    Vec2D( 7.472248 , 11.094533 ),
    Vec2D( 7.767005 , 10.900089 ),
    Vec2D( 7.758951 , 10.864989 ),
    Vec2D( 7.752684 , 10.837656 ),
    Vec2D( 7.426900 , 10.927867 ),
    Vec2D( 6.519955 , 10.927867 ),
    Vec2D( 6.429261 , 10.900089 ),
    Vec2D( 6.315893 , 10.955644 ),
    Vec2D( 6.270545 , 10.955644 ),
    Vec2D( 6.247872 , 10.927867 ),
    Vec2D( 6.111830 , 11.011200 ),
    Vec2D( 6.066483 , 11.066756 ),
    Vec2D( 5.862420 , 11.038978 ),
    Vec2D( 5.817073 , 10.955644 ),
    Vec2D( 5.771726 , 10.900089 ),
    Vec2D( 5.862420 , 10.761200 ),
    Vec2D( 5.975788 , 10.733422 ),
    Vec2D( 6.157177 , 10.566756 ),
    Vec2D( 6.247872 , 10.511200 ),
    Vec2D( 6.293219 , 10.427867 ),
    Vec2D( 6.315893 , 10.233422 ),
    Vec2D( 6.315893 , 10.177867 ),
    Vec2D( 6.542629 , 9.844533 ),
    Vec2D( 6.587976 , 9.761200 ),
    Vec2D( 6.610650 , 9.288978 ),
    Vec2D( 6.542629 , 9.066756 ),
    Vec2D( 6.565303 , 8.900089 ),
    Vec2D( 6.519955 , 8.816756 ),
    Vec2D( 6.542629 , 8.761200 ),
    Vec2D( 6.565303 , 8.733422 ),
    Vec2D( 6.429261 , 8.427867 ),
    Vec2D( 6.474608 , 8.316756 ),
    Vec2D( 6.724018 , 8.288978 ),
    Vec2D( 6.882733 , 8.538978 ),
    Vec2D( 6.973428 , 8.594533 ),
    Vec2D( 6.996101 , 8.622311 ),
    Vec2D( 7.200164 , 8.650089 ),
    Vec2D( 7.290859 , 8.650089 ),
    Vec2D( 7.426900 , 8.483422 ),
    Vec2D( 7.404227 , 8.455644 ),
    Vec2D( 7.245511 , 8.511200 ),
    Vec2D( 6.996101 , 8.427867 ),
    Vec2D( 7.041449 , 8.372311 ),
    Vec2D( 7.154817 , 8.455644 ),
    Vec2D( 7.200164 , 8.455644 ),
    Vec2D( 7.245511 , 8.455644 ),
    Vec2D( 7.381553 , 8.316756 ),
    Vec2D( 7.381553 , 8.261200 ),
    Vec2D( 7.404227 , 8.233422 ),
    Vec2D( 7.494921 , 8.205644 ),
    Vec2D( 7.767005 , 8.288978 ),
    Vec2D( 7.948394 , 8.233422 ),
    Vec2D( 8.016415 , 8.261200 ),
    Vec2D( 8.197804 , 8.094533 ),
    Vec2D( 8.084435 , 7.816756 ),
    Vec2D( 8.152456 , 7.733422 ),
    Vec2D( 8.175130 , 7.650089 ),
    Vec2D( 8.175130 , 7.511200 ),
    Vec2D( 8.311172 , 7.427867 ),
    Vec2D( 8.311172 , 7.372311 ),
    Vec2D( 8.651276 , 7.372311 ),
    Vec2D( 8.923360 , 7.316756 ),
    Vec2D( 8.900686 , 7.261200 ),
    Vec2D( 8.809991 , 7.261200 ),
    Vec2D( 8.472735 , 7.171122 ),
    Vec2D( 8.333845 , 7.038978 ),
    Vec2D( 8.282022 , 6.981100 ),
    Vec2D( 8.254778 , 6.848911 ),
    Vec2D( 8.265824 , 6.816756 ),
    Vec2D( 8.239206 , 6.711211 ),
    Vec2D( 8.219743 , 6.612067 ),
    Vec2D( 8.130227 , 6.433044 ),
    Vec2D( 8.084435 , 6.316756 ),
    Vec2D( 8.107109 , 6.288978 ),
    Vec2D( 7.948394 , 6.177867 ),
    Vec2D( 7.925720 , 5.983422 ),
    Vec2D( 7.857699 , 5.816756 ),
    Vec2D( 7.835026 , 5.788978 ),
    Vec2D( 7.857699 , 5.511200 ),
    Vec2D( 7.812352 , 5.400089 ),
    Vec2D( 7.812352 , 5.344533 ),
    Vec2D( 7.812352 , 5.177867 ),
    Vec2D( 8.084435 , 4.733422 ),
    Vec2D( 8.107109 , 4.622311 ),
    Vec2D( 7.857699 , 4.344533 ),
    Vec2D( 7.630963 , 4.261200 ),
    Vec2D( 7.540268 , 4.177867 ),
    Vec2D( 7.494921 , 4.150089 ),
    Vec2D( 7.449574 , 4.150089 ),
    Vec2D( 7.404227 , 4.150089 ),
    Vec2D( 7.336206 , 4.094533 ),
    Vec2D( 7.313532 , 4.066756 ),
    Vec2D( 7.041449 , 4.011200 ),
    Vec2D( 6.905407 , 3.955644 ),
    Vec2D( 6.950754 , 3.900089 ),
    Vec2D( 7.200164 , 3.927867 ),
    Vec2D( 7.630963 , 3.872311 ),
    Vec2D( 7.721657 , 3.872311 ),
    Vec2D( 7.948394 , 3.788978 ),
    Vec2D( 7.993741 , 3.705644 ),
    Vec2D( 7.971067 , 3.677867 ),
    Vec2D( 7.925720 , 3.622311 ),
    Vec2D( 8.175130 , 3.705644 ),
    Vec2D( 8.401866 , 3.650089 ),
    Vec2D( 8.492561 , 3.650089 ),
    Vec2D( 8.605929 , 3.538978 ),
    Vec2D( 8.651276 , 3.566756 ),
    Vec2D( 8.855339 , 3.372311 ),
    Vec2D( 8.900686 , 3.316756 ),
    Vec2D( 8.900686 , 3.150089 ),
    Vec2D( 8.787318 , 2.900089 ),
    Vec2D( 8.787318 , 2.844533 ),
    Vec2D( 8.946033 , 2.816756 ),
    Vec2D( 8.991380 , 2.788978 ),
    Vec2D( 9.014054 , 2.705644 ),
    Vec2D( 8.886928 , 2.524989 ),
    Vec2D( 8.832665 , 2.538978 ),
    Vec2D( 8.809991 , 2.455644 ),
    Vec2D( 8.923360 , 2.538978 ),
    Vec2D( 9.014054 , 2.400089 ),
    Vec2D( 9.308811 , 2.288978 ),
    Vec2D( 9.399506 , 2.261200 ),
    Vec2D( 9.512874 , 2.122311 ),
    Vec2D( 9.535548 , 1.983422 ),
    Vec2D( 9.512874 , 1.955644 ),
    Vec2D( 9.467527 , 1.816756 ),
    Vec2D( 9.036728 , 1.816756 ),
    Vec2D( 8.991380 , 1.927867 ),
    Vec2D( 8.946033 , 1.955644 ),
    Vec2D( 8.900686 , 1.983422 ),
    Vec2D( 8.946033 , 2.122311 ),
    Vec2D( 8.968707 , 2.150089 ),
    Vec2D( 9.195443 , 1.927867 ),
    Vec2D( 9.354158 , 1.955644 ),
    Vec2D( 9.376832 , 2.038978 ),
    Vec2D( 9.376832 , 2.094533 ),
    Vec2D( 9.240790 , 2.205644 ),
    Vec2D( 9.195443 , 2.205644 ),
    Vec2D( 9.263464 , 2.150089 ),
    Vec2D( 9.240790 , 2.122311 ),
    Vec2D( 9.195443 , 2.122311 ),
    Vec2D( 9.104749 , 2.122311 ),
    Vec2D( 8.900686 , 2.316756 ),
    Vec2D( 8.787318 , 2.344533 ),
    Vec2D( 8.696623 , 2.372311 ),
    Vec2D( 8.651276 , 2.427867 ),
    Vec2D( 8.719297 , 2.455644 ),
    Vec2D( 8.787318 , 2.650089 ),
    Vec2D( 8.832665 , 2.705644 ),
    Vec2D( 8.605929 , 2.677867 ),
    Vec2D( 8.537908 , 2.788978 ),
    Vec2D( 8.333845 , 2.788978 ),
    Vec2D( 7.925720 , 2.316756 ),
    Vec2D( 7.925720 , 2.261200 ),
    Vec2D( 7.903046 , 2.233422 ),
    Vec2D( 7.857699 , 2.233422 ),
    Vec2D( 7.857699 , 2.177867 ),
    Vec2D( 7.789678 , 1.983422 ),
    Vec2D( 7.812352 , 1.788978 ),
    Vec2D( 7.948394 , 1.538978 ),
    Vec2D( 7.971067 , 1.511200 ),
    Vec2D( 8.129783 , 1.511200 ),
    Vec2D( 8.243151 , 1.594533 ),
    Vec2D( 8.333845 , 1.594533 ),
    Vec2D( 8.424540 , 1.622311 ),
    Vec2D( 8.515234 , 1.566756 ),
    Vec2D( 8.673950 , 1.400089 ),
    Vec2D( 8.771174 , 1.291756 ),
    Vec2D( 8.828938 , 1.119878 ),
    Vec2D( 8.762504 , 0.972544 ),
    Vec2D( 9.238614 , 0.759633 ),
    Vec2D( 9.492323 , 0.627022 ),
    Vec2D( 9.820891 , 0.644711 ),
    Vec2D( 10.376567 , 0.800622 ),
    Vec2D( 10.651961 , 1.085978 ),
    Vec2D( 10.762173 , 1.132022 ),
    Vec2D( 10.943045 , 1.095989 ),
    Vec2D( 11.256739 , 0.999878 ),
    Vec2D( 11.576074 , 0.761611 ),
    Vec2D( 11.768247 , 0.425211 ),
    Vec2D( 11.960165 , 0.074778 ),
    Vec2D( 11.953907 , 0.000000 ),
    Vec2D( 11.629411 , 0.258767 ),
    Vec2D( 11.229920 , 0.582278 ),
    Vec2D( 11.001633 , 0.564300 ),
    Vec2D( 10.868476 , 0.447478 ),
    Vec2D( 10.633849 , 0.541833 ),
    Vec2D( 10.513370 , 0.672133 ),
    Vec2D( 11.188700 , 0.820078 ),
    Vec2D( 11.194014 , 0.859656 ),
    Vec2D( 11.118212 , 0.905822 ),
    Vec2D( 10.874860 , 0.930311 ),
    Vec2D( 10.427319 , 0.716522 ),
    Vec2D( 10.023620 , 0.374211 ),
    Vec2D( 9.434614 , 0.360144 ),
    Vec2D( 8.455131 , 0.859544 ),
    Vec2D( 8.180481 , 0.920500 ),
    Vec2D( 7.902529 , 1.115078 ),
    Vec2D( 7.823108 , 1.269800 ),
    Vec2D( 7.830482 , 1.403778 ),
    Vec2D( 7.791937 , 1.496744 ),
    Vec2D( 7.767005 , 1.538978 ),
    Vec2D( 7.676310 , 1.622311 ),
    Vec2D( 7.653637 , 1.650089 ),
    Vec2D( 7.585616 , 1.955644 ),
    Vec2D( 7.562942 , 1.983422 ),
    Vec2D( 7.562942 , 2.233422 ),
    Vec2D( 7.608289 , 2.400089 ),
    Vec2D( 7.630963 , 2.427867 ),
    Vec2D( 7.608289 , 2.538978 ),
    Vec2D( 7.585616 , 2.566756 ),
    Vec2D( 7.653637 , 2.705644 ),
    Vec2D( 7.630963 , 2.816756 ),
    Vec2D( 7.336206 , 3.011200 ),
    Vec2D( 7.290859 , 3.011200 ),
    Vec2D( 7.245511 , 3.011200 ),
    Vec2D( 7.041449 , 2.955644 ),
    Vec2D( 6.928081 , 2.816756 ),
    Vec2D( 6.928081 , 2.733422 ),
    Vec2D( 6.905407 , 2.622311 ),
    Vec2D( 6.860060 , 2.677867 ),
    Vec2D( 6.814712 , 2.677867 ),
    Vec2D( 6.678671 , 2.677867 ),
    Vec2D( 6.678671 , 2.733422 ),
    Vec2D( 6.769365 , 2.733422 ),
    Vec2D( 6.814712 , 2.733422 ),
    Vec2D( 6.792039 , 2.788978 ),
    Vec2D( 6.293219 , 3.066756 ),
    Vec2D( 6.225198 , 3.122311 ),
    Vec2D( 6.202525 , 3.233422 ),
    Vec2D( 6.134504 , 3.344533 ),
    Vec2D( 5.907767 , 3.261200 ),
    Vec2D( 5.862420 , 3.288978 ),
    Vec2D( 6.043809 , 3.427867 ),
    Vec2D( 6.021136 , 3.483422 ),
    Vec2D( 5.975788 , 3.483422 ),
    Vec2D( 5.930441 , 3.511200 ),
    Vec2D( 5.953115 , 3.566756 ),
    Vec2D( 5.975788 , 3.594533 ),
    Vec2D( 5.749052 , 3.788978 ),
    Vec2D( 5.703705 , 3.788978 ),
    Vec2D( 5.635684 , 3.788978 ),
    Vec2D( 5.703705 , 3.844533 ),
    Vec2D( 5.703705 , 4.011200 ),
    Vec2D( 5.499642 , 4.011200 ),
    Vec2D( 5.862420 , 4.372311 ),
    Vec2D( 5.975788 , 4.427867 ),
    Vec2D( 6.021136 , 4.427867 ),
    Vec2D( 6.089156 , 4.538978 ),
    Vec2D( 6.111830 , 4.566756 ),
    Vec2D( 6.089156 , 4.650089 ),
    Vec2D( 5.998462 , 4.650089 ),
    Vec2D( 5.817073 , 4.788978 ),
    Vec2D( 5.771726 , 4.816756 ),
    Vec2D( 5.681031 , 4.816756 ),
    Vec2D( 5.749052 , 4.927867 ),
    Vec2D( 5.749052 , 5.038978 ),
    Vec2D( 5.839747 , 5.177867 ),
    Vec2D( 5.998462 , 5.233422 ),
    Vec2D( 6.225198 , 5.233422 ),
    Vec2D( 6.270545 , 5.233422 ),
    Vec2D( 6.383914 , 5.288978 ),
    Vec2D( 6.406587 , 5.372311 ),
    Vec2D( 6.429261 , 5.400089 ),
    Vec2D( 6.587976 , 5.483422 ),
    Vec2D( 6.670626 , 5.490000 ),
    Vec2D( 6.700845 , 5.564100 ),
    Vec2D( 6.860060 , 5.927867 ),
    Vec2D( 6.860060 , 6.038978 ),
    Vec2D( 6.950754 , 6.205644 ),
    Vec2D( 6.973428 , 6.316756 ),
    Vec2D( 7.041449 , 6.344533 ),
    Vec2D( 7.064122 , 6.455644 ),
    Vec2D( 7.116072 , 6.541989 ),
    Vec2D( 7.114313 , 6.603667 ),
    Vec2D( 7.025305 , 6.741422 ),
    Vec2D( 6.736924 , 6.701367 ),
    Vec2D( 6.641658 , 6.741467 ),
    Vec2D( 6.500574 , 6.761389 ),
    Vec2D( 6.435410 , 6.733422 ),
    Vec2D( 6.224291 , 6.728556 ),
    Vec2D( 6.191759 , 6.738989 ),
    Vec2D( 6.099124 , 6.755000 ),
    Vec2D( 6.041805 , 6.749733 ),
    Vec2D( 6.001672 , 6.742967 ),
    Vec2D( 5.905382 , 6.718300 ),
    Vec2D( 5.817073 , 6.677867 ),
    Vec2D( 5.611713 , 6.686622 ),
    Vec2D( 5.401366 , 6.864333 ),
    Vec2D( 5.386274 , 6.927867 ),
    Vec2D( 5.356608 , 6.981811 ),
    Vec2D( 5.404095 , 7.111822 ),
    Vec2D( 5.561958 , 7.216133 ),
    Vec2D( 5.660643 , 7.244722 ),
    Vec2D( 5.366149 , 7.489478 ),
    Vec2D( 5.340927 , 7.511200 ),
    Vec2D( 5.114998 , 7.592867 ),
    Vec2D( 4.870667 , 7.692033 ),
    Vec2D( 4.746560 , 7.781856 ),
    Vec2D( 4.708060 , 7.760867 ),
    Vec2D( 4.692225 , 7.802500 ),
    Vec2D( 4.607090 , 7.849044 ),
    Vec2D( 4.481324 , 7.879711 ),
    Vec2D( 4.340031 , 8.093378 ),
    Vec2D( 4.181171 , 8.158044 ),
    Vec2D( 4.116415 , 8.200800 ),
    Vec2D( 4.081135 , 8.195278 ),
    Vec2D( 4.090912 , 8.272500 ),
    Vec2D( 4.032232 , 8.378311 ),
    Vec2D( 3.779566 , 8.791278 ),
    Vec2D( 3.769654 , 8.849022 ),
    Vec2D( 3.598177 , 8.955178 ),
    Vec2D( 3.576828 , 9.059633 ),
    Vec2D( 3.527037 , 9.066756 ),
    Vec2D( 3.498069 , 9.082022 ),
    Vec2D( 3.541865 , 9.174211 ),
    Vec2D( 3.542409 , 9.234411 ),
    Vec2D( 3.576275 , 9.262711 ),
    Vec2D( 3.582279 , 9.287744 ),
    Vec2D( 3.390995 , 9.316756 ),
    Vec2D( 3.209606 , 9.344533 ),
    Vec2D( 3.100836 , 9.367511 ),
    Vec2D( 2.957466 , 9.370756 ),
    Vec2D( 2.870844 , 9.366222 ),
    Vec2D( 2.777211 , 9.285222 ),
    Vec2D( 2.744851 , 9.285900 ),
    Vec2D( 2.775397 , 9.294867 ),
    Vec2D( 2.832661 , 9.341156 ),
    Vec2D( 2.868114 , 9.373300 ),
    Vec2D( 2.869502 , 9.400089 ),
    Vec2D( 2.794434 , 9.420178 ),
    Vec2D( 2.714423 , 9.440078 ),
    Vec2D( 2.641124 , 9.441944 ),
    Vec2D( 2.572096 , 9.428378 ),
    Vec2D( 2.548379 , 9.418600 ),
    Vec2D( 2.573130 , 9.388211 ),
    Vec2D( 2.563126 , 9.333567 ),
    Vec2D( 2.535855 , 9.320067 ),
    Vec2D( 2.517670 , 9.282778 ),
    Vec2D( 2.479488 , 9.260278 ),
    Vec2D( 2.483125 , 9.239067 ),
    Vec2D( 2.464034 , 9.224278 ),
    Vec2D( 2.468586 , 9.180556 ),
    Vec2D( 2.443129 , 9.168989 ),
    Vec2D( 2.439084 , 9.147456 ),
    Vec2D( 2.448389 , 9.129344 ),
    Vec2D( 2.444897 , 9.109600 ),
    Vec2D( 2.450720 , 9.097256 ),
    Vec2D( 2.444897 , 9.080389 ),
    Vec2D( 2.447808 , 9.045822 ),
    Vec2D( 2.424536 , 9.024011 ),
    Vec2D( 2.415811 , 9.000133 ),
    Vec2D( 2.442457 , 8.957422 ),
    Vec2D( 2.429887 , 8.946567 ),
    Vec2D( 2.455028 , 8.894556 ),
    Vec2D( 2.435936 , 8.879078 ),
    Vec2D( 2.413136 , 8.853411 ),
    Vec2D( 2.410805 , 8.836944 ),
    Vec2D( 2.412202 , 8.822133 ),
    Vec2D( 2.387533 , 8.789544 ),
    Vec2D( 2.386608 , 8.776044 ),
    Vec2D( 2.398706 , 8.757278 ),
    Vec2D( 2.373103 , 8.739511 ),
    Vec2D( 2.387070 , 8.769467 ),
    Vec2D( 2.375434 , 8.784611 ),
    Vec2D( 2.358674 , 8.785922 ),
    Vec2D( 2.337270 , 8.793167 ),
    Vec2D( 2.365195 , 8.790533 ),
    Vec2D( 2.399169 , 8.821478 ),
    Vec2D( 2.396376 , 8.837933 ),
    Vec2D( 2.408946 , 8.879078 ),
    Vec2D( 2.432218 , 8.894878 ),
    Vec2D( 2.414995 , 8.963022 ),
    Vec2D( 2.390961 , 8.983722 ),
    Vec2D( 2.340091 , 8.969389 ),
    Vec2D( 2.332091 , 8.946244 ),
    Vec2D( 2.340091 , 8.927722 ),
    Vec2D( 2.332091 , 8.912289 ),
    Vec2D( 2.316093 , 8.904067 ),
    Vec2D( 2.311730 , 8.874744 ),
    Vec2D( 2.288975 , 8.861244 ),
    Vec2D( 2.247727 , 8.856233 ),
    Vec2D( 2.233180 , 8.861889 ),
    Vec2D( 2.209436 , 8.859233 ),
    Vec2D( 2.231003 , 8.871144 ),
    Vec2D( 2.265911 , 8.873200 ),
    Vec2D( 2.277548 , 8.869600 ),
    Vec2D( 2.290635 , 8.873711 ),
    Vec2D( 2.299360 , 8.904578 ),
    Vec2D( 2.268088 , 8.909622 ),
    Vec2D( 2.247727 , 8.925256 ),
    Vec2D( 2.225734 , 8.920756 ),
    Vec2D( 2.208747 , 8.909622 ),
    Vec2D( 2.203768 , 8.921811 ),
    Vec2D( 2.214352 , 8.931822 ),
    Vec2D( 2.197138 , 8.933811 ),
    Vec2D( 2.148725 , 8.907478 ),
    Vec2D( 2.134577 , 8.904844 ),
    Vec2D( 2.113354 , 8.917222 ),
    Vec2D( 2.095107 , 8.918800 ),
    Vec2D( 2.079961 , 8.912944 ),
    Vec2D( 2.060761 , 8.913356 ),
    Vec2D( 2.034577 , 8.902656 ),
    Vec2D( 1.983589 , 8.895400 ),
    Vec2D( 2.033997 , 8.913356 ),
    Vec2D( 2.062502 , 8.918700 ),
    Vec2D( 2.092758 , 8.929811 ),
    Vec2D( 2.148090 , 8.928756 ),
    Vec2D( 2.168397 , 8.937878 ),
    Vec2D( 2.146421 , 8.965533 ),
    Vec2D( 2.182173 , 8.943933 ),
    Vec2D( 2.201537 , 8.951311 ),
    Vec2D( 2.239138 , 8.938400 ),
    Vec2D( 2.267063 , 8.944989 ),
    Vec2D( 2.284939 , 8.925767 ),
    Vec2D( 2.306887 , 8.926022 ),
    Vec2D( 2.311086 , 8.936356 ),
    Vec2D( 2.296312 , 8.952489 ),
    Vec2D( 2.317254 , 8.981122 ),
    Vec2D( 2.334939 , 9.003844 ),
    Vec2D( 2.374500 , 9.014044 ),
    Vec2D( 2.386136 , 9.034778 ),
    Vec2D( 2.401962 , 9.044656 ),
    Vec2D( 2.418723 , 9.044889 ),
    Vec2D( 2.426287 , 9.054878 ),
    Vec2D( 2.411739 , 9.063522 ),
    Vec2D( 2.426867 , 9.099311 ),
    Vec2D( 2.398362 , 9.125233 ),
    Vec2D( 2.373339 , 9.121944 ),
    Vec2D( 2.403595 , 9.134289 ),
    Vec2D( 2.417680 , 9.165778 ),
    Vec2D( 2.425860 , 9.192778 ),
    Vec2D( 2.423783 , 9.231400 ),
    Vec2D( 2.400330 , 9.237022 ),
    Vec2D( 2.419494 , 9.243567 ),
    Vec2D( 2.429815 , 9.246711 ),
    Vec2D( 2.449495 , 9.245489 ),
    Vec2D( 2.457676 , 9.289856 ),
    Vec2D( 2.481311 , 9.298211 ),
    Vec2D( 2.488585 , 9.334211 ),
    Vec2D( 2.520255 , 9.353822 ),
    Vec2D( 2.520400 , 9.369944 ),
    Vec2D( 2.494960 , 9.432511 ),
    Vec2D( 2.463671 , 9.469200 ),
    Vec2D( 2.406950 , 9.500578 ),
    Vec2D( 2.240907 , 9.536433 ),
    Vec2D( 2.129969 , 9.569467 ),
    Vec2D( 2.031530 , 9.607422 ),
    Vec2D( 1.932328 , 9.658044 ),
    Vec2D( 1.835167 , 9.695656 ),
    Vec2D( 1.746196 , 9.760744 ),
    Vec2D( 1.667446 , 9.789667 ),
    Vec2D( 1.575400 , 9.797622 ),
    Vec2D( 1.562104 , 9.828722 ),
    Vec2D( 1.531422 , 9.846800 ),
    Vec2D( 1.415859 , 9.888744 ),
    Vec2D( 1.315206 , 9.942167 ),
    Vec2D( 1.175573 , 10.083667 ),
    Vec2D( 1.147394 , 10.090267 ),
    Vec2D( 1.118064 , 10.086567 ),
    Vec2D( 0.990883 , 9.998400 ),
    Vec2D( 0.778930 , 9.990856 ),
    Vec2D( 0.592924 , 10.033144 ),
    Vec2D( 0.507490 , 10.125422 ),
    Vec2D( 0.419562 , 10.320811 ),
    Vec2D( 0.375403 , 10.344533 ),
    Vec2D( 0.276464 , 10.431189 ),
    Vec2D( 0.220170 , 10.534911 ),
    Vec2D( 0.181271 , 10.571000 ),
    Vec2D( 0.153745 , 10.620156 ),
    Vec2D( 0.114973 , 10.653889 ),
    Vec2D( 0.103274 , 10.707756 ),
    Vec2D( 0.097914 , 10.761511 ),
    Vec2D( 0.076256 , 10.811522 ),
    Vec2D( 0.061935 , 10.867833 ),
    Vec2D( 0.000000 , 10.960167 )
    ])

    distances = (0, .05, .1, .25) # threshold sizes in kilometres
    import csv
    for d in distances:
        simple = coast.simplify(d) if d > 0 else coast
        with open('poly-{0}.csv'.format(d), 'w') as output_doc:
            writer = csv.writer(output_doc, dialect='excel')
            for pt in simple.points:
                writer.writerow(pt.coords)
person culebrón    schedule 05.04.2010
comment
Просто добавлю, чтобы указать на эту быструю реализацию Python Visvalingam-Whyatt. Он создает список важности, а затем может возвращать полилинии любого разрешения с помощью одной операции numpy.mask. - person Permafacture; 27.07.2014

arrow_upward
4
arrow_downward

Когда я пытался превратить кривую Безье в отрезки прямой линии, в итоге я определил максимальное расстояние между кривой и прямой линией между двумя точками кривой. Начните с одной точки, являющейся одной конечной точкой, двигайте другой конец вдоль кривой, пока его дальнейшее перемещение не превысит максимальное расстояние. Затем сделайте это снова, используя вторую (и так далее) точку, пока не охватите всю кривую.

Вы должны иметь возможность генерировать несколько LOD, просто увеличивая допустимое расстояние между сегментами линии и полилинией.

person Vatine    schedule 04.04.2010

arrow_upward
2
arrow_downward

Я разработал очень простой алгоритм, используя расстояние от заданной точки до следующих точек, чтобы решить, имеет ли смысл включать их в рендеринг. В зависимости от текущего масштаба вы можете связать минимальное расстояние между точками, необходимое для преобразованной модели.

person stacker    schedule 04.04.2010
comment
Я тоже думал об этом. Рассматривали ли вы усреднение нескольких близких точек в одну? - person culebrón; 04.04.2010
comment
@culebrón нет, я просто пропустил все точки, которые находятся слишком близко к начальной точке, и использовал выбранную точку в качестве следующей начальной точки. - person stacker; 04.04.2010

arrow_upward
2
arrow_downward

Я поклонник сортировки точек на основе угла, который сегменты образуют по обе стороны от точки, а затем итеративного удаления точек с наименьшим углом, пока вы не достигнете некоторого порога. O (n log (n)) я думаю, по сравнению с O (n ^ 2) метода RDP, и с меньшими константами для загрузки. :)

Угол можно даже масштабировать по длине сегмента (на самом деле его проще вычислить таким образом), если вы хотите придать больший вес (желательность) более длинным сегментам.

Учитывая p0, p1, p2, вес p1 будет ((p0 - p1) точка (p2 - p1)), нормализуйте различия, если вы не хотите взвешивать по длине. (В отличие от расстояния до линии, это намного дешевле, и результаты могут быть идентичными.)

person dash-tom-bang    schedule 12.04.2010
comment
На самом деле - это может быть даже решение O (n), если вы просто маршируете спереди назад и удаляете точки, которые не соответствуют вашим критериям угла; просто посмотрите на одну или две точки вперед, где вы, возможно, удаляете точки, чтобы убедиться, что точки, которые лучше удалить, не появляются. - person dash-tom-bang; 12.04.2010
comment
Я вижу слабое место в этом алгоритме: если у вас есть прямоугольник с очень маленькой, но густой звездой в одном из углов (с острыми углами), этот алгоритм сначала сотрет прямоугольник. - person culebrón; 17.04.2010
comment
Возможно, вам придется настроить свой вес, например. так что вершина с двумя длинными ребрами будет рассматриваться как менее желательная для удаления. Однопроходный подход к этому алгоритму был бы менее полезен в подобных случаях. Однако мой последний абзац в исходном посте должен подтолкнуть в приличном направлении. - person dash-tom-bang; 23.04.2010

arrow_upward
1
arrow_downward

Поздно на вечеринку, но вот Java-реализация алгоритма Дугласа Пекера.

https://github.com/MKergall/osmbonuspack/blob/0310258c53244a485fda0ff0dd7829e5557b531b/OSMBonusPack/src/main/java/org/osmdroid/bonuspack/utils/DouglasPeuckerReducer.java

person spy    schedule 15.12.2015

arrow_upward
1
arrow_downward

Добавление к множеству ответов. Я нашел реализацию javascript в этом репозитории github: https://github.com/mourner/simplify-js< /а>

Также есть список различных реализаций алгоритма Рамера-Дугласа-Пекера на разных языках.

person derickito    schedule 01.05.2017

arrow_upward
0
arrow_downward

Что касается ответа culebron, правильный ли рекурсивный вызов? Насколько я понимаю, RDP разбивает строку на две разные строки: от начала до максимума и от максимума до конца.

Но глядя на вызов, где pos - это индекс максимального расстояния в списке...

return (ramerdouglas(line[:pos + 2], dist) + 
        ramerdouglas(line[pos + 1:], dist)[1:])

вместо этого выполняет start to max+1, max+1 to end. Разве не должно быть...

return (ramerdouglas(line[:pos + 1], dist) + 
        ramerdouglas(line[pos:], dist)[1:])
person selfname    schedule 22.05.2017