Suppression des points inutiles dans un contour polygonal

Bonjour,

J'ai un polygone défini par minimum 4 côtés (rectangle au minimum donc) mais qui peut en avoir plus (le polygone définit une dalle de béton).
Normalement on a 2 points par côté, or il se trouve que les données issues d'un logiciel CAO ont des fois plus de 2 points pour définir un côté (un segment peut donc être défini par 3-4-5 points donc avec 1-2-3 points intermédiaires entre ses extrêmités par exemple).

Ces points intermédiaires me gêne pour un post traitement que je dois faire, je voudrais savoir si vous connaissez un algorithme prenant en entrée une liste de points et ressortant une liste avec les points seulement nécessaires pour définir un polygone (suppression des points intermédiaires donc)?

J'ai bien l'idée de tester la colinéarité des vecteurs portés par les segments et je vois le principe, mais j'ai peur de me planter dans la gestion des index et le marquage des points non nécessaires etc...

Merci

Une boucle comme ça :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Pour i = n-1 a 2 pas -1 Point_0 = tableau[i-1] Point_1 = tableau[i] Point_2 = tableau[i+1]   Si fff_alignés (Point_0, point_1, point_2) alors tableaussupprime( tableau, i ) fin   Avec la procédure fff_alignés() : Procedure fff_alignes( point_0, point_1, point_2 ) d01 = distance(point_0, point_1) d02 = distance(point_0, point_2) d12 = distance(point_1, point_2) si d12 = d01 + d12 alors renvoyer vrai renvoyer faux

---

En parcourant la boucle de la fin vers le début, ça simplifie énormément les choses, ça évite les décalages d'indices dès qu'on supprime un point.

Ici, je fais l'impasse sur le cas où le Premier Point ( ou le dernier) serait en trop.

Si Les valeurs traitées sont des nombres réels, si on est susceptible d'avoir des points quasiment-alignés, il faut adapter la fonction fff_alignés() , pour éventuellement avoir une petite tolérance.

Cette page peut t'aider : https://en.wikipedia.org/wiki/Parcours_de_Graham .

Non Trap D, je ne pense pas que ce soit une bonne piste.

Tevious a déjà le contour se son polygone. Ses n points sont ordonnés pour former le contour. Eventuellement, ce polygone n'est pas convexe.
Et ce qu'il veut, c'est supprimer le ou les points intermédiaires, quand il a 3 points alignés ou plus.

Merci pour votre réponse à chacun,

Le parcours de Graham ne semble effectivement pas adapté.
En fait ce que je veux faire c'est plus ou moins un filtre qui ne garde que le nombre minimal de points nécessaires pour définir mon polygone.
L'idée de tbc92 me semble bonne, l'approche par un calcul de distance ne m'a pas sauté aux yeux (comme dit je pensais faire un calcul de colinéarité entre les vecteurs portés par les segments), mais me semble tout à fait viable.

Je vais implémenter cette solution pour tester et voir ce que ça donne. Il n'y a normalement pas de points quasi allignés et travaillant avec des unités mm il n'y a pas de coordonnées à valeur réelle. Par contre il faudra peut être gérer la question d'arrondi dans le calcul des distances...

@+

Testé sur Scilab, fonctionne de manière parfaite!

Je vais l'implémenter sur un automate comme c'est la finalité!

Merci pour l'aide!

bonjour,

réponse un peu tardive, mais l'algorithme de Douglas-Peucker permet de simplifier un polygone en ne gardant que les points "saillants". Dans le cas d'un rectangle, et en prenant une distance égale à une fraction de la largeur du rectangle, ça devrait fonctionner assez bien.

A+