Discussion :

[thedante]

Bonjour,

je suis à la recherche d'un algorithme ou d'une bibliothèque qui est capable de prendre un cercle ou arc de cercle en entrée, et de la transformer en suite de segment.
Avec une précision de 25mm mais le mieux serais de pouvoir changer a volonté la précision.

Est ce que quelqu'un a déjà eu à faire à ce problème ?

Merci pour votre aide.

[souviron34]

Voir sur Google algo de Bresenham..

[plegat]

Salut,

je suis à la recherche d'un algorithme ou d'une bibliothèque qui est capable de prendre un cercle ou arc de cercle en entrée, et de la transformer en suite de segment.

Sous quelle forme est fourni l'arc ou le cercle?

Si tu veux approximer par n segments, tu prends n+1 points sur ton arc (n points pour le cercle), et tu as automatiquement tes segments. Non?

Avec une précision de 25mm mais le mieux serais de pouvoir changer a volonté la précision.

Qu'est-ce que tu appelles "précision" dans ton cas? La longueur des segments? l'écart max entre l'arc de cercle et le segment l'approximant?

Voir sur Google algo de Bresenham..

Euh... si je ne m'abuse, Bresenham c'est pour approximer un segment par des pixels. Donc là, même si on approxime le cercle par des pixels, ça ne semble pas répondre au besoin (sauf si je n'ai pas bien compris la question)

[souviron34]

Euh... si je ne m'abuse, Bresenham c'est pour approximer un segment par des pixels. Donc là, même si on approxime le cercle par des pixels, ça ne semble pas répondre au besoin (sauf si je n'ai pas bien compris la question)

Il t'abuse

Midpoint circle algorithm (Wiki)

The algorithm is a variant of Bresenham's line algorithm, and is thus sometimes known as Bresenham's circle algorithm, although not actually invented by Jack E. Bresenham

D'autres références :

http://www.eazynotes.com/notes/compu...-algorithm.pdf (PDF)

ou

http://www.ecse.rpi.edu/Homepages/wr...bresenham.html

Si tu veux approximer par n segments, tu prends n+1 points sur ton arc (n points pour le cercle), et tu as automatiquement tes segments. Non?

Tout à fait

[plegat]

Il t'abuse

Midpoint circle algorithm (Wiki)

Ouaaaah, tu chicanes là!
(en plus c'est marqué "The algorithm is a variant of Bresenham's line algorithm"...en plus c'est même pas lui qui l'a fait)

Bon, on verra bien la réponse de thedante pour voir ce qu'il veut exactement...

[thedante]

Je vous remercie d'avoir répondu aussi rapidement.

Je vais vous expliquer mon projet, je pilote une graveuse numérique.
Mais pour le moment je ne fais que des mouvements rectilignes.

Pour les segments, je n’ai donc aucun problème, mais je cherche à transformer mes cercle ou arc de cercle en polyligne.
C'est à dire un nombre indéfini de corde d'un cercle ou arc de cercle, d'une longueur définie.
J'ai dit 25mm, mais j'ai fait une erreur de calcule enfaite je suis a 4mm, mais il faudrait pouvoir faire évolué cette valeur.

4mm est la longueur des cordes, car ça correspond à la précision de ma graveuse.

J'ai pour un cercle les coordonnées du point central et le rayon, pour l'arc de cercle j'ai aussi les coordonnées du point central, le rayon aussi et aussi les coordonnées du point de départ et d'arriver.

Je viens de regarde les liens et fait qu'elle que recherche sur les aglo de Bresenham, bon j'avoue ne pas avoir réellement compris l'utilité, mais j'ai l'impression qu'il utilise les pixels donc surement un bitmap alors que moi je travail qu'avec des coordonnées donc une image matricielle.

[LinuxUser]

Pourquoi es tu restreint à ne tracer que des segments uniquement?

[plegat]

Chouette, j'ai gagné!

Je joins un bout de code pour de la segmentation d'arc de cercle (qui apparaîtra dans mon prochain article d'ailleurs...). C'est du java, mais ça doit se comprendre:

centre, c'est le centre de l'arc, pt1, le premier point décrivant l'arc de cercle, pt2, le second point (attention, description suivant sens anti-horaire), radius1, le rayon de l'arc

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
        double dx1 = this.pt1.getX() - this.centre.getX();
        double dy1 = this.pt1.getY() - this.centre.getY();
 
        double dx2 = this.pt2.getX() - this.centre.getX();
        double dy2 = this.pt2.getY() - this.centre.getY();
 
        double angle1 = Math.atan2(dy1, dx1);
        double angle2 = Math.atan2(dy2, dx2);
 
        while (angle2 <= angle1) {
            angle2 = angle2 + 2 * Math.PI;
        }
 
        this.nbPts = (int) Math.floor(Math.abs(angle2 - angle1) / (10. / 180 * Math.PI)) + 1; // à adapter, je fais des segments couvrant 10°
        double step = (angle2 - angle1) / (this.nbPts - 1);
 
        this.points = new PFEM2DPoint[this.nbPts];
 
        for (int i = 0; i < this.nbPts; i++) {
            this.points[i] = new PFEM2DPoint(0, this.centre.getX() + radius1 * Math.cos(angle1 + i * step), this.centre.getY() + radius1 * Math.sin(angle1 + i * step));
        }

Si ce n'est pas clair, j'essaierai de traduire en algo.

Le point à adapter, là où j'utilise un angle de 10°, toi tu vas devoir utiliser un angle de 2*asin(L/(2*R)), avec R rayon, et L longueur de tes segments, soit L=4mm

[thedante]

Pourquoi es tu restreint à ne tracer que des segments uniquement?

Pour le moment je fais les calcules sur le pc et non sur le microcontrôleur qui lui ne fait que piloter la graveuse
Vu le protocole que j'ai établi pour communiquer avec mon microcontrôleur, je ne peux faire que des mouvements rectilignes, mais je le ferais peut-être évolué suivant mes tests.

Je te remercie plegat ne t'embête pas je comprends le java.

Alors là c'est du sens antihoraire pour passer au sens horaire il me sufie d'inversé le point de départ et le point d'arriver ?

Et je pense que pour mes cercles je peux le découper en deux ou quatre arcs de cercle pour réutiliser ce code, si je ne me trompe pas ?

[plegat]

Alors là c'est du sens antihoraire pour passer au sens horaire il me sufie d'inversé le point de départ et le point d'arriver ?

Pas tout à fait...
Si tu inverses angle1 et angle2, il faudra sans doute retoucher la boucle à la fin. Celle-ci part de angle1, et ajoute un step angulaire à chaque itération. Si tu veux le faire en sens anti-horaire, il faut soit un step angulaire négatif (quoique... ça doit être ce qui doit se passer en inversant angle1 et angle2), soit un itérateur négatif.
A voir...

Il faut faire attention à comment tu définis tes arcs. Si tu n'as que des arcs couvrant moins de 180°, deux points suffisent. Mais si tu as des arcs <180° et >180°, il faut soit un troisième point pour définir de quel côté du cercle on passe, soit prendre une convention comme j'ai fait.

Et je pense que pour mes cercles je peux le découper en deux ou quatre arcs de cercle pour réutiliser ce code, si je ne me trompe pas ?

C'est faisable.
Sinon tu prends exactement le même code, avec angle2=angle1+PI (attention, si tu prends ce code, nbPts=nb segments+1 pour le calcul, même si on retombe sur le point de départ avec un cercle)

[thedante]

Pas tout à fait...
Si tu inverses angle1 et angle2, il faudra sans doute retoucher la boucle à la fin. Celle-ci part de angle1, et ajoute un step angulaire à chaque itération. Si tu veux le faire en sens anti-horaire, il faut soit un step angulaire négatif (quoique... ça doit être ce qui doit se passer en inversant angle1 et angle2), soit un itérateur négatif.
A voir...

Je pense qu'il serait plus simple de rester comme ça en sens anti-horaire et si je veux un résultat final en sans horaire, j'inverse tous les points trouver, le premier dénier, ect...

Par contre, je viens d'effectuer qu'elle que teste en c#,avec mes arcs, mes segments font environ 7mm et avec mes cercles, ils font 6.7mm(où je fais avec le même code, mais angle2=angle1+2*PI ) donc un petit écart, mais loin des 4 rechercher.

Je joins donc un le bout de code que je pense faux, car je n’ai rien touché d'autre.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

nbPts = (int) Math.Floor(Math.Abs(angle2 - angle1) / ( ((2 * Math.Asin(L / (2 * radius1)))*100)  /180 * Math.PI)) + 1;

Les variables sont les mêmes que les tiennes pour mieux comprendre.

[plegat]

Je joins donc un le bout de code que je pense faux, car je n’ai rien touché d'autre.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

nbPts = (int) Math.Floor(Math.Abs(angle2 - angle1) / ( ((2 * Math.Asin(L / (2 * radius1)))*100)  /180 * Math.PI)) + 1;

Les variables sont les mêmes que les tiennes pour mieux comprendre.

Normalement c'est bon, je viens de refaire le calcul sous excel...

On peut éventuellement remplacer le Math.Floor(...)+1 par un Math.Ceiling(...), mais ça revient au même numériquement (Math.ceil(...) en java)

Par contre fait attention, tu as un 100 codé en dur dans la ligne de code. C'est quoi d'ailleurs ce 100?

Tu pourrais nous mettre un jeu de données complet stp (valeurs R,L,angles en entrée et nbPts, L en sortie)

[thedante]

On peut éventuellement remplacer le Math.Floor(...)+1 par un Math.Ceiling(...), mais ça revient au même numériquement (Math.ceil(...) en java)

Je viens de teste à l’ instant ça ne bouge pas.

Par contre fait attention, tu as un 100 codé en dur dans la ligne de code. C'est quoi d'ailleurs ce 100?

C'est pour revenir à un pourcentage, vus que ton code utilise un l'ange en pourcentage

Tu pourrais nous mettre un jeu de données complet stp (valeurs R,L,angles en entrée et nbPts, L en sortie)

En entrée
pt1.X = 253.90214485
pt1.Y = 37.06219324
pt2.X = 108.94949659
pt2.Y = 158.2178481
centre.X = 174.1136028
centre.Y = 88.89156108
radius1 = 95.14459949
L=4

Pour info
angles_total =157.02863019

En sortie
angle1= -0.57608278858305184
angle2 = 2.3252565720637017
((2 * Math.Asin(L / (2 * radius1))) * 100) = 4.2044368867238866
nbPts = 40
step = 0.074393316939660351
Je te donne juste les deux premiers points
0 X 253.9021448453897 Y 37.062193242994788
1 X 257.53366021537539 Y 43.135809169142036

J'ai donc fait plusieurs calculs :
95.14Sqrt(2-2cos(.042)=3.99 avec les arrondie on tombe bien sur les 4mm rechercher avec l'angle de .042 et le rayon de 95.14 donc ça, c'est juste

Mais quand je calcule la distance entre les deux points, par exemple :
Sqrt((257.5-253.9)^2+(43.1-37)^2)=7.08 donc là même avec les arrondie je suis loin de mes 4mm recherché

[plegat]

C'est pour revenir à un pourcentage, vus que ton code utilise un l'ange en pourcentage

houla malheureux, un angle en pourcentage? non, non, j'utilise un angle en degrés, ce qui explique le facteur PI/180 pour le ramener en radians dans les calculs.

En fait, l'arcsin te retourne un angle en radians, donc j'ai besoin de convertir mes degrés en radians. Toi, dans ton cas, tu peux te contenter de toujours rester avec des radians, étant donné que tu ne fais intervenir aucun angle explicitement.

D'où en fait ton erreur, le fameux facteur 100:

((2 * Math.Asin(L / (2 * radius1))) * 100) = 4.2044368867238866

qui si tu l'enlèves te donne:

((2 * Math.Asin(L / (2 * radius1)))) = 0.042044368867238866

en radians, soit 2.409° (=0.042044*180/PI)

Pour le reste:

Pour info
angles_total =157.02863019 [166.2 chez moi]

En sortie
angle1= -0.57608278858305184 [OK]
angle2 = 2.3252565720637017 [OK, et donc 2.325-(-0.576)=2.901 rad=>166.2°]
((2 * Math.Asin(L / (2 * radius1))) * 100) = 4.2044368867238866 [facteur 100 à supprimer, donne donc 0.0420044
nbPts = 40 [70 avec la formule donnée précédemment, 71 si corrige en mettant +2 à la place de +1 (relation entre nb de points et nb de segments...
+1 pour avoir le nb de segments pour atteindre ta précision, et +1 supplémentaire pour avoir le nb de points)]
step = 0.074393316939660351 [0.041 avec 71 pts]

Pour les dix premiers points, on a:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
Pt	Angle		x		y		L
1	-0.576		253.9021449	37.06219324	
2	-0.535		255.9812131	40.4128112	3.943243036
3	-0.493		257.9196602	43.84669947	3.943243036
4	-0.452		259.7141564	47.35795979	3.943243036
5	-0.410		261.3616194	50.94056097	3.943243036
6	-0.369		262.8592195	54.58834931	3.943243036
7	-0.327		264.2043841	58.29505912	3.943243036
8	-0.286		265.3948029	62.05432352	3.943243036
9	-0.245		266.428431	65.85968533	3.943243036
10	-0.203		267.3034931	69.70460822	3.943243036

on est en-dessous des 4mm comme recherché.

[thedante]

houla malheureux, un angle en pourcentage? non, non, j'utilise un angle en degrés, ce qui explique le facteur PI/180 pour le ramener en radians dans les calculs.

En fait, l'arcsin te retourne un angle en radians, donc j'ai besoin de convertir mes degrés en radians. Toi, dans ton cas, tu peux te contenter de toujours rester avec des radians, étant donné que tu ne fais intervenir aucun angle explicitement.

D'où en fait ton erreur, le fameux facteur 100:

Oui un angle en pourcentage, j'ai fait fort là. l'élimine donc le "100" et "PI/180" pour rester en radian et la j'arrive a avoir qu'elle que chose de correcte.

Je te remercie donc pour ton aide et ton temps.

Je joins le code adapté pour segmenter les arcs de cercle ou les cercles, si ça peut aider une personne.
cercle à true pour faire un cercle ou cercle à false pour faire un arc de cercle

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
39
            double dx1 = pt1.X - centre.X;
            double dy1 = pt1.Y - centre.Y;
 
            double dx2 = pt2.X - centre.X;
            double dy2 = pt2.Y - centre.Y;
 
            double angle2;
            double angle1 = Math.Atan2(dy1, dx1);
            int nbPts = 0;
 
 
            if (cercle)
            {
                angle2 = angle1 + 2*Math.PI; //Cercle
                nbPts+=1;
            }
            else
            {
                angle2 = Math.Atan2(dy2, dx2); //Arc de cercle
            }
 
            while (angle2 <= angle1) {
                angle2 = angle2 + 2 * Math.PI;
            }
            double dd = ((2 * Math.Asin(L / (2 * radius1))) * 100);
 
            nbPts = nbPts + (int)Math.Floor(Math.Abs(angle2 - angle1) / (2 * Math.Asin(L / (2 * radius1)))) +2; 
 
            double step = (angle2 - angle1) / (nbPts - 1);
 
 
            for (int i = 0; i < nbPts; i++) 
            {
                point2d point;
                point.X = centre.X + radius1 * Math.Cos(angle1 + i * step);
                point.Y = centre.Y + radius1 * Math.Sin(angle1 + i * step);
                Lpoint2d.Add(point);
 
            }

Je te remercie encore plegat et bonne continuation à toi.