Как упростить маршрутизируемую сеть?

У меня есть сетевой график, который мне нужно упростить в смысле уменьшения количества ребер . Идея состоит в том, чтобы объединить узлы, которые расположены близко друг к другу, и удалить короткие соединительные ребра.

Как этого достичь в PostGIS или GRASS? Или есть ли лучшие подходы для автоматического упрощения такой сети?

Я уже попробовал функцию ST_SnapToGrid, но я не доволен результатами (серый = оригинальный, черный = привязанный):

Самое близкое, что я зашел, это:

v.clean input=roads output=snap5rmline tool=snap,rmline thresh=5 

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

Вы пробовали GRASS v.generalize ?

v.generalizeпозволяет выбрать алгоритм обобщения с атрибутом метода . Существует множество: douglas, douglas_reduction, lang, Reduction, Reumann, Boyle, Sliding_averaging, distance_weighting, Chaiken, Hermite, Snakes, Network, смещения .

И дополнительные параметры , как threshold, degree_thresh, angle_thresh( в зависимости от выбранного алгоритма) может помочь вам получить точный результат.

Здесь идет учебник .

Я этого не делал, но думаю, что могу предложить направление.

1. Создайте топологию с PostGIS для вашего графика.
2. Найти все узлы только с двумя ребрами.
3. Исцели края.

ST_ModEdgeHeal объединит одно ребро с другим. ST_NewEdgeHeal заменит оба с новым ребром.

Руководство по топологии PostGIS

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

Выберите отрезки, от которых вы хотите избавиться, исходя из их длины.

Для каждого из этих сегментов создайте точку в средней точке

Удалить маленький сегмент

Теперь вы можете использовать ST_Snap в PostGIS (см. Пример здесь )

РЕДАКТИРОВАТЬ: обратите внимание, что в вашем случае, вы также могли бы сначала использовать v.net для удаления псевдо-узлов (узел, который соединяет только две линии)

Расскажите, как Микаэль Мишо проанализировал это в списке разработчиков OpenJUMP:

> Interesting question. There has been so much research works about
> generalization that it is surely not a simple task. I have tested the
> following approach with mitigated results :
> - make the layer planar with the noder plugin
> - detect small cycles with the graph plugin
> - merge adjacent cycles
> - create a point inside each cycles surface
> - remove network segments along these cycles (query + DE-9IM)
> - detect roads touching the cycles
> - project the center points of cycles to the road endpoints ==> replace small roundabout by simple nodes
> 
> Possible improvements (probably need a dedicated plugin)
> - make it work on non planar graph (or just remove bridges/tunnels from the graph)
> - replace small edges between two nodes with degree 3+ by a single node,    not only small cycles
> - process iteratively starting with smallest edges/cycles