1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| Soit L un tableau (pré-remplis) dont chaque élément est un point.
Chaque point contient ses coordonnées X et Y.
Soit S un tableau de segment.
Chaque segment contient deux point p1 et p2 et une "normale" (qui n'en est pas réellement une). Cette normale ne sert qu'à donner le sens vers lequel on sort du polygône ; elle peut être "H", "B", "D", "G", "HD", "HG", "BG", "BD". (abréviations pour "haut", "bas" etc...)
Éliminer les doublons du tableau L.
Si il n'existe pas dans L au moins trois points non alignés, alors il n'existe pas de surface.
Déterminer les points min_x, max_x, min_y, max_y qui ont respectivement l'abscice la plus petite, la plus grande, et l'ordonnée la plus petite et la plus grande.
Si min_x et max_y ne sont pas confondus, alors on ajoute un segment dans S dont la normale est déterminée par direction_normale(min_x, max_y, "HG").
Si max_y et max_x ne sont pas confondus, alors on ajoute un segment dont la normale est déterminée par direction_normale(max_y, max_x, "HD").
Idem pour max_x/min_y et pour min_y/min_x.
// À ce point là on a un polygône de base qui n'est pas forcément l'enveloppe convexe du nuage de point.
faire
Pour chaque segment seg de S
Pour chaque point p de L
Si la normale du segment est "G" et que p.X = seg.p1.X alors
on rajoute deux segment dans S tel qu'ils soient le résultat du découpage de seg par le point p.
On enlève seg de S.
sinon si la normale est "HG" alors
si p.X = seg.p1.X alors
on découpe seg par p et la deuxième partie du segment aura une normale "H".
sinon si p.Y = seg.p2.Y alors
on découpe seg par p et la première partie du segment aura une normale "G".
sinon si (seg.p2.Y-seg.p1.Y)/(seg.p2.X-seg.p1.X) <= (p.Y-seg.p1.Y)/(p.X-seg.p1.X) alors
on coupe seg par p et les deux morceaux de segment auront une normale "HG"
fin si;
sinon si la normale est "H" alors
[...]
// Pareil pour les 8 valeurs possibles de la normale.
fin si;
fin pour chaque; // pour chaque point de L
fin pour chaque; // pour chaque segment de S
recommencer tant qu'on a découpé au moins un segment; |
Partager