Требуется консультация алгоритма упрощения графа
Мне нужно взять 2D-график из n точек и уменьшить его до точки r (где r - это конкретное число, меньшее n). Например, у меня может быть два набора данных с немного различным количеством общих точек, скажем, 1021 и 1001, и я бы хотел, чтобы оба набора данных имели 1000 точек. Мне известны несколько алгоритмов упрощения: упрощение Ланга и Дуглас-Пеккер. Я использовал Lang в предыдущем проекте с немного другими требованиями.
Конкретные свойства алгоритма, который я ищу:
1) необходимо сохранить форму линии
2) должен позволить мне уменьшить набор данных до определенного количества точек
3) относительно быстро
В этом посте обсуждаются достоинства различных алгоритмов. Я опубликую второе сообщение для совета относительно реализаций в Java или Groovy (зачем изобретать велосипед).
Я обеспокоен требованием 2 выше. Я не являюсь экспертом в этих алгоритмах, чтобы знать, могу ли я диктовать точное количество выходных точек. Реализация Lang, которую я использовал, взяла lookAhead, толерантность и массив Points в качестве входных данных, поэтому я не вижу, как диктовать количество точек в выходных данных. Это критическое требование моих текущих потребностей. Возможно, это связано с конкретной реализацией Lang, которую мы использовали, но я не видел много информации о Lang в сети. В качестве альтернативы мы могли бы использовать Дугласа-Пекера, но, опять же, я не уверен, можно ли указать количество точек в выводе.
Я должен добавить, что я не являюсь экспертом в этих типах алгоритмов или в любом другом виде математики, поэтому я ищу простой совет типа смертных:) Как мне удовлетворить требования 1 и 2 выше? Я бы пожертвовал производительностью ради правильного решения.
2 ответа
Вы можете найти мою реализацию C++ и статью об упрощении Дугласа-Пекера здесь и здесь. Я также предоставляю модифицированную версию упрощения Дугласа-Пекера, которая позволяет вам указать количество точек в полученной упрощенной линии. Он использует приоритетную очередь, как упомянуто Питером Тейлором. Хотя это намного медленнее, поэтому я не знаю, удовлетворит ли это требование "относительно быстро".
Я планирую предоставить реализацию для упрощения Ланга (и несколько других). В настоящее время я не вижу простого способа настроить Lang, чтобы уменьшить число фиксированных точек. Если бы вы могли жить с менее строгим требованием: "должен позволить мне сократить набор данных до приблизительного количества точек", то вы могли бы использовать итеративный подход. Угадайте начальное значение для lookahead: количество очков / желаемое количество очков. Затем медленно увеличивайте прогноз, пока не достигнете желаемого количества очков.
Надеюсь, это поможет.
PS: Я только что вспомнил, вы также можете попробовать алгоритм Visvalingam-Whyatt. Вкратце: - вычислить площадь треугольника для каждой точки с ее прямыми соседями - отсортировать эти области - удалить точку с наименьшей областью - обновить область ее соседей - восстановить - продолжить, пока не останется n точек
Я думаю, что вы можете адаптировать Дуглас-Пюккер довольно просто. Адаптируйте рекурсивный алгоритм так, чтобы он не создавал список, а создавал дерево, отражающее структуру рекурсивных вызовов. Корнем дерева будет однолинейное приближение P0-Pn; следующий уровень будет представлять собой двухстрочное приближение P0-Pm-Pn, где Pm - точка между P0 и Pn, наиболее удаленная от P0-Pn; следующий уровень (если он заполнен) будет представлять собой четырехстрочное приближение и т. д. Затем можно обрезать дерево либо по глубине, либо по расстоянию вставленной точки от родительской линии.
Изменить: на самом деле, если вы выберете последний подход, вам не нужно строить дерево. Вместо этого вы заполняете приоритетную очередь, где приоритет задается расстоянием вставленной точки от родительской линии. Затем, когда вы закончите, очередь скажет вам, какие пункты удалить (или сохранить, в соответствии с порядком приоритетов).