Algorithme de simplification des graphes Conseil nécessaire

Question

J'ai besoin de prendre un graphe 2D de n points et de réduire les points r (où r est un nombre spécifique inférieur à n). Par exemple, je peux avoir deux ensembles de données avec un nombre légèrement différent de points totaux, disons 1021 et 1001 et je voudrais forcer les deux ensembles de données à avoir 1000 points. Je connais deux algorithmes de simplification: Lang Simplification et Douglas-Peucker. J'ai utilisé Lang dans un projet précédent avec des exigences légèrement différentes.

Les propriétés spécifiques de l'algorithme Je cherche est:

1) doit conserver la forme de la ligne

2) doit me permettre réduis ensemble de données à un certain nombre de points

3) est relativement rapide

Ce post est une discussion sur les mérites des différents algorithmes. Je posterai un second message pour des conseils sur les implémentations en Java ou Groovy (pourquoi réinventer la roue).

Je suis préoccupé par l'exigence 2 ci-dessus. Je ne suis pas assez expert dans ces algorithmes pour savoir si je peux dicter le nombre exact de points de sortie. L'implémentation de Lang que j'ai utilisée a pris lookAhead, tolérance et le tableau de Points en entrée, donc je ne vois pas comment dicter le nombre de points dans la sortie. C'est une exigence critique de mes besoins actuels. Peut-être que cela est dû à la mise en œuvre spécifique de Lang que nous avions utilisé, mais je n'ai pas vu beaucoup d'informations sur Lang sur le web. Alternativement nous pourrions utiliser Douglas-Peucker mais encore une fois je ne suis pas sûr si le nombre de points dans la sortie peut être spécifié.

Je devrais ajouter que je ne suis pas un expert sur ces types d'algorithmes ou n'importe quel genre de calcul mathématique, ainsi je recherche de simples conseils de type mortel :) Comment est-ce que je satisfais aux conditions 1 et 2 ci-dessus? Je sacrifierais la performance pour la bonne solution.

Answer 1

Vous pouvez trouver mon implémentation C++ et mon article sur la simplification Douglas-Peucker here et here. Je fournis également une version modifiée de la simplification de Douglas-Peucker qui permet de spécifier le nombre de points de la ligne simplifiée résultante. Il utilise une file d'attente prioritaire comme mentionné par 'Peter Taylor'. C'est beaucoup plus lent cependant, donc je ne sais pas si cela satisferait à l'exigence 'relativement rapide'.

Je prévois fournir une implémentation pour la simplification de Lang (et plusieurs autres). Actuellement, je ne vois pas de façon simple comment ajuster Lang pour réduire à un nombre de points fixes.Si vous pourrait vivre avec une exigence moins stricte: «doit me permettre de réduire l'ensemble de données à nombre approximatif de points ', alors vous pouvez utiliser une approche itérative. Deviner une valeur initiale pour lookahead: nombre de points/nombre de points souhaités. Ensuite, augmentez progressivement l'apparence jusqu'à ce que vous atteigniez approximativement le nombre de points souhaité.

J'espère que cela aide.

p.s .: Je viens juste de me souvenir de quelque chose, vous pouvez aussi essayer l'algorithme de Visvalingam-Whyatt. En bref: -compute la zone triangulaire pour chaque point avec ses voisins directs -sort ces zones -remove le point avec la plus petite zone -update la zone de ses voisins -resort -Continuer jusqu'à n points restent

Answer 2

Je pense que vous pouvez adapter Douglas-Pücker assez simplement. Adaptez l'algorithme récursif de sorte que, plutôt que de produire une liste, il produise un arbre reflétant la structure des appels récursifs. La racine de l'arbre sera l'approximation sur une seule ligne P0-Pn; le niveau suivant représentera l'approximation à deux lignes P0-Pm-Pn où Pm est le point entre P0 et Pn qui est le plus éloigné de P0-Pn; le niveau suivant (s'il est plein) représentera une approximation à quatre lignes, etc. Vous pouvez ensuite découper l'arbre soit en fonction de la profondeur, soit en fonction de la distance du point inséré par rapport à la ligne parente. Edit: en fait, si vous prenez cette dernière approche, vous n'avez pas besoin de construire un arbre. A la place, vous remplissez une file d'attente prioritaire où la priorité est donnée par la distance du point inséré par rapport à la ligne parente. Ensuite, lorsque vous avez terminé la file d'attente vous indique les points à supprimer (ou à conserver, selon l'ordre des priorités).