Поиск хороших отправных точек для алгоритма Дугласа-Пекера для замкнутых многоугольников

Question

Я пытаюсь уменьшить вершины многоугольника, используя алгоритм Дугласа-Пекера - который прекрасно работает для линий и путей.

Моя проблема в том, что полигоны, которые я хочу оптимизировать, закрыты.При выборе 2 случайных соседних точек оптимизация работает хорошо - за исключением начальной и конечной точек - поскольку они фиксированы и не могут быть оптимизированы.

Есть ли хороший способ выбрать отправную точку?

Answer 1

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

Answer 2

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

Это может быть шумно, если все ваши точки расположены близко друг к другу.В этом случае, вместо того, чтобы просто рассматривать последовательные наборы из трех вершин, вы можете работать наружу в обоих направлениях от каждой входной вершины, используя Дугласа-Пекера, чтобы пропустить ненужные вершины в каждом направлении.Это приведет к большим, более широко расставленным тройкам.Снова найдите две вершины, наиболее удаленные от линий, соединяющих вершины предшественника / преемника, исправьте их и примените Дугласа-Пекера к промежуточным вершинам.

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

Answer 3

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

Вот фрагмент, который, я уверен, вы можете адаптировать к любому языку, который вы используете:

function polygonPeuckerReduce(path, tolerance) {
    var points = [];
    if (path.length < 3) {
        return points.concat(path);
    } else {
        var widest = 0.0, startIndex = 0;
        // find the widest part of the polygon (only start index is necessary)
        for (var i = 0, l = path.length; i < l; i++) {
            var point = path[i];
            for (var j = i + 1; j < l; j++) {
                var distance = point.distanceTo(path[j]);
                if (distance > widest) {
                    startIndex = i;
                    widest = distance;
                }
            }
        }

        // re-order the points with the new starting point (faster method)
        points = path.splice(startIndex, path.length).concat(path);

        return PEUCKER_INTERNAL(points, tolerance); // the magic
    }
}

Answer 4

Я, возможно, полностью неверно истолковываю проблему здесь, но похоже, что вы просто хотите адаптировать алгоритм Дугласа-Пекера (http://en.wikipedia.org/wiki/Ramer–Douglas–Peucker_algorithm) к полигонам. И единственная причина, по которой вы не можете просто рассматривать свой многоугольник как линию сНачальная и конечная точки одинаковы, потому что алгоритм требует, чтобы эти две точки были различны.

Поэтому я бы рекомендовал выбрать две произвольные точки на вашем многоугольнике, которые находятся далеко друг от друга, и затем запустить Дуглас-Алгоритм Peucker дважды, один раз для пути между вашими точками, которые идут по часовой стрелке, и один раз для пути между вашими точками, которые идут против часовой стрелки.

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

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