Требуется консультация алгоритма упрощения графа

Question

Мне нужно взять двухмерный график из n точек и уменьшить его до r точек (где r - это конкретное число, меньшее n).Например, у меня может быть два набора данных с немного различным количеством общих точек, скажем, 1021 и 1001, и я бы хотел, чтобы оба набора данных имели 1000 точек.Мне известны несколько алгоритмов упрощения: упрощение Ланга и Дуглас-Пеккер.Я использовал Lang в предыдущем проекте с немного другими требованиями.

Особые свойства алгоритма, который я ищу:

1) должны сохранять форму линии

2) должен позволить мне сократить набор данных до определенного количества точек

3) сравнительно быстро

В этом посте обсуждаются достоинства различных алгоритмов.Я опубликую второе сообщение с советами по реализации на Java или Groovy (зачем изобретать велосипед).

Я обеспокоен требованием 2 выше.Я не являюсь экспертом в этих алгоритмах, чтобы знать, могу ли я диктовать точное количество выходных точек.Реализация Lang, которую я использовал, взяла lookAhead, допуск и массив Points в качестве входных данных, поэтому я не вижу, как диктовать количество точек в выходных данных.Это критическое требование моих текущих потребностей.Возможно, это связано с конкретной реализацией Lang, которую мы использовали, но я не видел много информации о Lang в Интернете.В качестве альтернативы мы могли бы использовать Дугласа-Пекера, но, опять же, я не уверен, можно ли указать количество точек в выходных данных.

Я должен добавить, что я не являюсь экспертом в этих типах алгоритмов или в любом другом виде, поэтому я ищу простой совет типа смертных :) Как мне удовлетворить требования 1 и 2 выше?Я бы пожертвовал производительностью ради правильного решения.

Answer 1

Я думаю, что вы можете адаптировать Дугласа-Пюккера довольно просто.Адаптируйте рекурсивный алгоритм так, чтобы он не создавал список, а создавал дерево, отражающее структуру рекурсивных вызовов.Корнем дерева будет однолинейное приближение P0-Pn;следующий уровень будет представлять собой двухстрочное приближение P0-Pm-Pn, где Pm - точка между P0 и Pn, наиболее удаленная от P0-Pn;следующий уровень (если он заполнен) будет представлять собой четырехстрочное приближение и т. д. Затем можно обрезать дерево либо по глубине, либо по расстоянию вставленной точки от родительской линии.Изменить: на самом деле, если вы выберете последний подход, вам не нужно строить дерево.Вместо этого вы заполняете приоритетную очередь, где приоритет определяется расстоянием вставленной точки от родительской линии.Затем, когда вы закончите, очередь скажет вам, какие пункты удалить (или сохранить, в соответствии с порядком приоритетов).

Answer 2

Вы можете найти мою реализацию на C ++ и статью об упрощении Дугласа-Пекера здесь и здесь . Я также предоставляю модифицированную версию упрощения Дугласа-Пекера, которая позволяет вам указать количество точек полученной упрощенной линии. Он использует приоритетную очередь, как упомянуто «Питером Тейлором». Хотя это намного медленнее, поэтому я не знаю, удовлетворит ли это требование ' относительно быстро '.

Я планирую предоставить реализацию для упрощения Ланга (и несколько других). В настоящее время я не вижу простого способа настроить Lang, чтобы уменьшить число фиксированных точек. если ты может соответствовать менее строгому требованию: « должно позволить мне уменьшить набор данных до приблизительного количества точек », тогда вы можете использовать итеративный подход. Угадайте начальное значение для lookahead: количество очков / желаемое количество очков. Затем медленно увеличивайте взгляд, пока не достигнете желаемого количества очков.

Надеюсь, это поможет.

с .: Я только что кое-что вспомнил, вы также можете попробовать алгоритм Visvalingam-Whyatt. Короче: - вычислить площадь треугольника для каждой точки с ее прямыми соседями сортировать эти области - удалить точку с наименьшей площадью -Обновить район своих соседей -resort -продолжить, пока не останется n баллов