Discrétisation d'un polygone

Bonjour,

Je travaille sur un projet d'automatique (automatisation d'un process, c'est de l'info indus avec automate programmable derrière).
Pour faire simple, j'ai une forme quelconque et le but du système est de la remplir.

J'ai déjà réfléchi à la stratégie concernant le système physique (modèle pour les trajectoires, commande des actionneurs pour distribuer du produit, etc.)

Pour pouvoir mener à bien le projet, il faut que mon polygone soit "compréhensible" par mon système (pour pouvoir justement générer les trajectoire de mon outil de remplissage, ce dernier
ne pouvant faire que des longueurs, de la gauche vers la droite, avec décalage vers le haut ou le bas à chaque bord).

Pour en venir à mon problème, mon polygone est défini par un ensemble de segments (chaque segment étant défini par 2 points, dans un plan donc uniquement du 2D).
A partir de cela, je voudrai réaliser une discrétisation de l'ensemble de l'espace occupé (on parle de maillage si j'ai bien compris, mais sur google cela renvoi sur des pages et des pages de math).
Pour cela je me suis dit que je peux prendre des cases de 1mm * 1mm (ce qui peut donner un tableau 2D de booléens au final), c'est suffisant pour mon problème.
Mon problème est que je ne sais absolument pas comment je peux faire pour passer d'une liste de segments à un modèle 2D, et cela de manière la plus simple possible (je parle en logique de process, concernant la performance du système on a un i5 derrière donc pas de problème en puissance de calcul même si c'est un automate et pas un PC).

J'ai mis en pièce jointe un exemple (tordu mais possible) de polygone pouvant être traité.
Mon idée était de partir du bord en haut à gauche ou démarre le polygone puis de suivre le contour vers le bas mais après je suis rapidement bloqué.
On peut également voir sur la droite 3 ouvertures qui ne doivent pas être couvertes, pour l'instant elles ne m'intéressent pas, je souhaite couvrir tout le polygone, puis utilisé la même méthode en local pour soustraire localement ces ouvertures...

Si quelqu'un à une idée je suis preneur parce que là mes méninges ne donnent rien.

Merci beaucoup

Si je comprend bien, ton polygone est la forme noire.

De plus, un polygone est fermé au contraire d'une ligne.

Donc ton dernier point doit être le premier aussi.

Ensuite, j'ai un peu de mal à comprendre : la machine doit remplir le polygone, c'est ça ? Si c'est bien ça, tu peux regarder les algos de remplissage , traitement d'images..

Tu as déjà ton polygone sous forme d'un tableau : Poly[n], où chaque point est Poly[i] {x,y}.


http://alienryderflex.com/polygon_fill/
https://www.cs.uic.edu/~jbell/Course...onFilling.html
http://cs.brown.edu/stc/summer/2View...Render_23.html
http://www.tutorialspoint.com/comput..._algorithm.htm

Bonjour,

Tout d'abord merci pour ta réponse!

Oui tu as bien compris mon problème.
En fait ma machine est une sorte de citerne avec différents clapets en dessous dans le sens de la largeur (illustré par la double bande en haut à gauche du cadre) qui forment une ligne. Mon idée pour remplir le polygone est donc de faire
des passages de la gauche vers la droite en décalant vers le bas (ou le haut, faut juste choisir un sens) à chaque fois qu'on atteint une extrêmité.

J'ai en entrée un polygone (structure que j'ai défini) qui contient un int donnant le nombre de segments, et un tableau de segments (struct aussi définie par moi même), chaque segment étant constitué de 2 points.

A l'idéal en sortie de mon process je voudrais des "trajectoires" pour ma machine. Une trajectoire étant une bande comme expliquée plus haut. Cette bande étant décomposée en une succession de sections. Chaque section prend une abscisse de début et de fin (l'ordonnée étant celle de la bande tout le long) et le nombre de clapets à ouvrir pour ladite section.

Etant donné qu'on travaille avec du béton, les effets de bords ne sont pas très importants, si on ne rempli pas pile l'espace (problème pouvant se poser avec un segment transversal comme on voit sur la gauche) au mm près et qu'en contrepartie on en met un peu plus dans le voisinage cela va se compenser quand le béton va s'étaler.

La discrétisation te parait-elle la plus efficace des solutions pour ensuite générer ces trajectoires, ou peut on faire mieux?

Merci

Citation:

---

Envoyé par tevious

En fait ma machine est une sorte de citerne avec différents clapets en dessous dans le sens de la largeur (illustré par la double bande en haut à gauche du cadre) qui forment une ligne.
...
A l'idéal en sortie de mon process je voudrais des "trajectoires" pour ma machine. Une trajectoire étant une bande comme expliquée plus haut. Cette bande étant décomposée en une succession de sections. Chaque section prend une abscisse de début et de fin (l'ordonnée étant celle de la bande tout le long) et le nombre de clapets à ouvrir pour ladite section.
...
La discrétisation te parait-elle la plus efficace des solutions pour ensuite générer ces trajectoires, ou peut on faire mieux?

---

On peut sans doute trouver des méthodes complexes, mais celle-là est très efficace - et courante : ce qui est utilisé pour tracer sur les écrans d'ailleurs.. (la plupart du temps du moins)

Maintenant, quand je lis :

Citation:

---

Envoyé par tevious

Pour en venir à mon problème, mon polygone est défini par un ensemble de segments (chaque segment étant défini par 2 points, dans un plan donc uniquement du 2D).
A partir de cela, je voudrai réaliser une discrétisation de l'ensemble de l'espace occupé ...
...
Pour cela je me suis dit que je peux prendre des cases de 1mm * 1mm (ce qui peut donner un tableau 2D de booléens au final), c'est suffisant pour mon problème.
Mon problème est que je ne sais absolument pas comment je peux faire pour passer d'une liste de segments à un modèle 2D, et cela de manière la plus simple possible

---

je me pose plusieurs questions :

• Je suppose que tes clapets à béton doivent faire plus de 1mm, car je pense que les cailloux du béton au minimum doivent faire dans les 2-3 cm, non ? Pourquoi donc ne pas faire ton "découpage" à la taille minimale de l'ouverture de tes trous de déversement ?
  
  
• Il y aussi forcement une limite au déplacement de la machine, non ? ça ne sert a rien de prendre un découpage plus petit..
  
  
• Enfin je ne comprend pas ce que tu veux dire entre "liste de segments" et "modèle 2D".. Chaque segment contient 2 points. Ces points, d'après ton schéma, ont des coordonnées entières. Il y a donc une liste finie d'entiers faisant passer de l'un à l'autre..
  
  [4,8 - 4,5] => [4.8 - 4,7 - 4,6 - 4,5]
  

Bonjour,

Tes réflexions sont intéressantes et tout à fait exacts. En fait je découpe mon espace en bande qui font la largeur de ma machine.
Chaque bande est ensuite découpée en une série de portions où la machine avancera avec le même nombre de clapets ouverts, comme cela je peux réaliser mon motif.
Le maillage que je vais réaliser me permettra "juste" de connaitre l'espace occupé afin de générer ces bandes.

A partir de là, la résolution du maillage me permet de travailler avec plus ou moins de précision. On peut mailler avec des points de 1mm*1mm comme avec des dalles de plusieurs centimètres, il faut juste que cela soit "potable" pour ma génération de trajectoire plus tard (on voit déjà des problèmes d'aliasing se pointer avec le segments en biais, mais au final vue l'application cela se corrige facilement en en mettant plus que prévu dans le voisinage et en en mettant pas sur la zone frontière, car après le remplissage, la table vibre pendant un petit moment et donc le béton s'étale remplissant les espaces vacants...).

Du coup, l'algo du premier lien que tu donnes est très satisfaisant, j'adapterai le pas de discrétisation de mes mailles en fonction de mes besoins et des performances du système.

Merci beaucoup pour ton aide, ce point était assez pointu à résoudre, il y en aura d'autre notamment en ce qui concerne la commande de mes actionneurs pour respecter les trajectoires, mais cela relève de l'automatique au sens pur, et cela tombe bien, je suis ingénieur dans ce domaine!

Suppose que ta première passe soit à y=7.8. La droite y=7.8 coupe deux de tes segments, le premier et l'avant dernier à x1= 4 et x2= . Il faut tracer de l'un à l'autre. Pour d'autre y tu peux avoir plus d'intersections. Il faut alors les trier en ordre croissant, puis tracer de x1 à x2, de x3àx4, etc.