Quoi de mieux pour commencer cette nouvelle année 2024 que de remettre les méninges en route avant d'aller à l'atelier ?
Dans le cadre du développement de la prochaine version d'OpenCutList, il se trouve que j'ai bien envie de profiter de l'intelligence collective pour résoudre un problème de géométrie.
Le contexte
OpenCutList va permettre d'exporter une projection 2D des pièces au format DXF.
Mais comme chacun le sait SketchUp ne connait pas la courbe et dessine seulement des segments. Afin d'aller plus loin qu'un simple export de polygones, avec Martin Müller, on a écrit un algorithme qui tente de retrouver les portions de polygones qui seraient des arcs de cercle ou d'ellipses. (les autres types de courbure ne sont pas détectés ... un autre défi ?).
Le système marche plutôt bien, mais on se heurte à un nouveau défi.
Limites du format DXF
Le format DXF est né à une époque ou la puissance des ordinateurs n'était celle d'aujourd'hui. Il a donc parfois certaines limitations par rapport à l'usage que l'on veut en faire aujourd'hui.
En effet, un "chemin" continu en DXF se dessine avec une Polyline.
Une polyline est une série de sommets (points) ordonnées et reliés par des segments ou des arcs de cercle. La forme crée par la polyline peut être ouverte ou fermée.
Et c'est là que la limitation intervient. Il n'est pas possible ici de relier deux sommets par un arc d'ellipse. Pour ça, il faudra dessiner un arc d'ellipse non connecté au reste du chemin ... ce qui, avec les divers arrondis, peut apporter des discontinuités dans le "chemin". Bref, ça ne va pas.
Le problème à résoudre
L'option est donc de convertir les arcs d'ellipse en une série d'arcs de cercle le plus approchant possible. En limitant tout de même leur nombre pour garder des fichiers légers à manipuler une fois sur les machines.
Ce que nous avons
Soit un arc d'ellipse défini par :
- Rx, son grand rayon
- Ry, son petit rayon
- C, son centre (point 2D)
- a, son angle d'inclinaison
- a1, l'angle de début d'arc (dans le repère de l'ellipse) ou E1, son point de début
- a2, l'angle de fin d'arc (dans le repère de l'ellipse) ou E2, son point de fin
Ce que nous voulons
Une liste ordonnée d'arcs de cercle approximants l'arc d'ellipse rouge avec pour chacun :
- P1, son point de début
- P2, son point de fin
- C, son centre
A vos copies
Mis à jour11 réponses
C'est top, vous m'avez bien aidé avec vos réponses ! Voici la solution que j'ai finalement utilisée.
Comme toutes les solutions d'approximation, c'est une affaire de compromis...
La stratégie
- Je crée un tableau d'échantillonnage de points répartis tous les 1° sur 1/4 d'ellipse. Il y a donc déjà plus de points dans les parties aplaties de l'ellipse.
- Je parcours ce tableau pour trouver l'équation d'un cercle avec les 3 premiers points (en commençant du côté du petit rayon de l'ellipse). Puis je compare avec le 4 ième pour savoir s'il peut faire partie du même cercle avec un décalage maximal de 0.001 pouce. Si oui, je regarde le suivant. Si non, je re-calcul un cercle avec 3 points. Et je répète l'opération jusqu'à plus avoir de points. S'il me reste moins de 3 points, j'utilise la formule pour trouver le cercle oscultateur pour les 1 ou 2 points qui me reste. De là, j'ai donc une liste de portions avec un angle de début et de fin et le centre du cercle associé.
- Je duplique ce résultat sur autant de quarts d'ellipse qu'il en faut pour couvrir l'arc d'ellipse que je veux approximer.
- Je trouve dans cette liste avec l'angle de début et de fin de mon arc les différentes portions qui m'intéressent. Et je recoupe celle de début et de fin pour correspondre précisément aux angles de l'arc.
- Je n'ai plus qu'à parcourir les portions pour dessiner la polyline comme succession d'arc de cercle.
Besoins remplis
- L'approximation étant toujours calculé sur une ellipse complète, j'ai toujours des points clés coïncidents peu import les angles de début et de fin de l'arc.
- Il y a toujours des points aux extrémités des rayons de l'ellipse.
- Dans la limite du premier échantillonnage à 1°, l'approximation s'affine plus si les valeur sont grandes. L'écart à la courbe étant exprimé en unité absolue.
En vrai, ça fait quand même toujours pas mal de points quand l'ellipse s'aplatie. Mais c'est aussi le prix à payer pour avoir la précision voulue.
Pour les plus curieux, le code est là.
Sans trop réfléchir...
Une ellipse a une équation cartésienne ou polaire. On peut facilement trouver cette équation à partir des paramètres que tu donnes, Rx, Ry, C, a, etc.
A partir de cette équation, tu prends 3 points sur l'ellipse.
On peut facilement trouver un arc de cercle passant par ces 3 points (la encore à partir de l'équation cartésienne ou polaire d'un cercle).
ici, les équations permettant de trouver l'arc de cercle passant par 3 points:
cral-perso.uni...cercle_3pts.pdf
Sur les parties où la courbure de l'ellipse est faible, on peut prendre des points relativement éloignées.
Là où la courbure est plus accentuée, il faudra réduire la distance entre les points (pour définir la courbure, il suffit de prendre le rapport entre la corde et la flèche définies par ces 3 points).
On doit pouvoir trouver une petite formule permettant d'optimiser la distance entre les points de manière à minimiser l'écart type entre les points de l'ellipse et le cercle.
Autre piste plus "puissante": Pour "lisser" une courbe définie par un nuage de points, il y a les techniques de régression non paramétrique. Ce sont des maths, mais une fois les formules programmées, cela devrait tourner tout seul.
A noter que mon petit logiciel de dessin 2D produisant des dxf, Deltacad, me résoud ce genre de probleme tout seul: trouver l'arc de cercle passant par 3 points définis, et donne des courbes non segmentées.
Une approche analytique (non itérative) fournissant une discrétisation continue sur [E1, E2] et accessoirement à dérivée continue en E1 et E2 (à supposer que ce soit le cas avant discrétisation), avec une évolution régulière des longueurs d'arcs de cercle entre E1 et E2 fonction de la courbure locale (plus d'arcs de cercle là où il faut afin d'approcher au plus près le profil elliptique à moindre coût).
Définition du problème
Via les transformations appropriées, on exprime le problème dans le repère de l'ellipse : axes principaux alignés avec x et y, centre en (0,0), et on normalise le rayon selon x ; le rayon selon y devient "a" (histoire de ne pas se promener des rapports de rayons dans les équations). Pour cela, on applique les transformations successives : translation en (0,0), rotation de l'ellipse (des points E1 et E2), puis normalisation (il faudra appliquer les transformations inverses, en sens inverse après la résolution afin de se replacer dans la configuration réelle : "dé-normalisation", rotation inverse, translation en C). Les points E1 et E2 deviennent e1 et e2.
On définit également une "erreur" (maxi) pour la discrétisation, "e", comme la distance maximale entre la discrétisation en arcs de cercles et l'arc d'ellipse.
Résolution
(On peut travailler en coordonnées polaires dans un premier temps, mais les coordonnées curvilignes semblent plus appropriées.)
- On calcule la courbure le long de l'arc d'ellipse (solution analytique)
- On distribue des points le long de ce profil en fonction de C, avec une densité proportionnelle à la courbure (une approche exacte existe).
Les points définissent les lieux d'intersection entre l'arc d'ellipse et les arcs de cercle. - En chaque point, on calcule le cercle de courbure (solution analytique)
- On calcule les points d'intersection des cercles de courbure voisins (solution analytique, il y en à 2, il faut prendre le bon)
Les arcs de cercle définissent la discrétisation de l'arc d'ellipse. On remarque que puisque les rayons des cercles de courbure sont d'autant plus petits que la courbure est localement importante, les intersections sont "du côté" où la courbure locale est la plus grande, ce qui donne bien une discrétisation plus fine là où la courbure est la plus grande. - Pour chaque point d'intersection, on calcule la distance minimale à l'arc d'ellipse (il doit aussi y avoir une solution analytique), c'est l'"erreur" en ce point, qui est localement le plus éloigné de l'arc d'ellipse ; c'est donc bien l'erreur maximale. Grâce à l'étape 2, les points devraient avoir des erreurs similaires, ce qui est ce que l'on recherche.
Si l'erreur est supérieure à l'erreur maximale fixée (e), alors c'est qu'il n'y a pas assez de points. On recommence avec un nombre plus grand. Sinon, on peut diminuer le nombre de points.
En creusant, il doit être pouvoir de connaître l'erreur (et donc le nombre de points) a priori. Sinon, on commence avec un ou quelques points internes.
La méthode implique qu'il y aura au moins un point intermédiaire. Le cas d'un seul arc de cercle est à traiter séparément... Sinon, réviser l'approche pour considérer les points comme les extrémités des arcs de cercle plutôt que leurs points d'intersection avec l'arc d'ellipse.
Je n'ai pas une réponse directe mais le problème est super intéressant. A brûle pourpoint je pense à la façon dont fonctionne un ellipsographe et je me dis qu'on doit pouvoir s'en inspirer. Car tel que je le vois à chaque instant il décrit justement un arc de cercle dont le centre varie... bref il faudrait transformer cette intuition en équation.
Voilà un problème interessant ! Ce qui est certain c'est qu'on ne trouvera pas ici une unique bonne réponse puisque tout est affaire de compromis entre le suivi parfais de l'élipse et la simplificiation de sa description en arcs.
Je manque un peu de temps pour suivre jusqu'au bous chacun des raisonnements mathématiques qui ont déjà été décris dans les précédents commentaires. C'est d'ailleurs toujours en plaisir de constater à quel point la communauté de l'Air du Bois est impliqué dans la résolution de sujets aussi variés que complexes.
De mon coté, je ne prétend pas apporter grand chose sur la description en équation du problème, surtout par manque de temps. Mais j'ai une intuition à la lecture de "l'énoncé" du Professeur Beaulant :
Pourquoi ne pas revenir au principe d'une anse de panier ?
Intuitivement j'ai toujours vu ce principe comme étant une méthode pour construire un "ovale" à partir d'arcs de cercle simples.
Alors c'est sur qu'un arc à 3 anses sera un peu approximatif, au risque de dénaturer la forme de l'éclipse initiale :
Mais qu'est ce qui empêcherait alors de voir le nombre de cercles de l'anse de panier comme un paramètre ? (un peu comme on choisi le nombre de segment lors du dessin d'un cercle dans sketchup)
Dans ce cas, en réglant le nombre de cercle à 5, 7 (...voir en peu plus ?), on tenderait de plus en plus vers l'élipse parfaite non ?
Dans cette hypothèse, en plus de garder un principe de description d'élipse plutôt simple et compréhensible, on garderait ainsi toujours les points essentiels de l'ellipse initiale comme intersections entre nos arcs.
Enfin voilà mon point de vue intuitif, malgré que je n'ai pas le temps d'aller au bout d'une vraie démonstration. J'espère que cela peux ajouter un peu d'eau au moulin
Pierre
PS : quelques infos sur les anses de panier 1
quelques infos sur les anses de panier 2
PPS : Pas tout à fait la même technique mais si ça peux aider
A voir
- least square arc fitting
- le paragraphe 4.3.2 de
researchgate.n...lement_Analysis
du projet feasy
engineering.pu...ement-analysis/
math dispo, pourrait etre codé pas trop difficilement
- le paragraphe 4.3.2 de
axes de recherche :
- least squares fitting of circles and lines (chernov); code dispo, quali a revoir
- levenberg-marquardt method
- landau algo
- spath algo
- svm circle fitting
- ransac arc fitting
en ouvrant le pb
- spline fitting / cubic spline fitting
- polygonalization / curvature estimation
PS: ~pas reussi a indenter les listes. dsl~ corrigé
Salut,
Il y a peut-être quelque chose a faire du côté de la courbe développée (lieu des centres de courbures, ou enveloppe des normales, ce qui est pareil)
Si tu veux une belle courbe (continue a dérivée continue, ie avec des cercles qui se raccordent sans angles) il faut diviser L'ellipse en tronçons Pour chaque extrémité d'un tronçon tu calcules les normales, le centre du cercle approché est l'intersection des normales. Une methode par 3 pts sur la courbe risque de te donner des "angles" même si tu n'avances que d'un point a la fois
Il y a une équation générale assez simple de la développée d'une ellipse quelconque en fonction de ses petits et grands axes ( serge.mehl.fre...x/developp.html ). J'ai pas creusé plus les formules mais si les "t" de l'équation sont les mêmes, on calcule très facilement autant de portions de cercles qu'on veut.
Si tu prends un pas assez important il faut peut-être avoir recours a des techniques détournés types faire la moyenne entre les deux centres de courbures.
En cherchant un peu, j'ai retrouvé le moyen de connaitre le cercle tangent en un point d'une ellipse.
Les Ref sont les suivantes :
Ref 1
Ref 2
On peut ensuite recalculer le centre du cercle tangent avec le calcul suivant. J'ai juste vérifier le cas trivial d'un cercle, mais il serait intéressant de le tester graphiquement.
Après, la stratégie pourrait être de
- Calculer en coordonnées polaires les points des extrémités E1 et E2 (ie. calcul des t1 et t2 dans l'équation ci-dessus).
- définir un nombre d'arcs à tracer
- itérer sur le nombre d'arcs
- calculer les tn, tn+1 (ie. chaque P1 et P2)
- calculer le point sur l'ellipse avec l'angle (tn + tn+1)/2 - (ie. point entre P1 et P2)
- retrouver le centre du cercle tangent en ce point milieu avec les formules ci-dessus
On devrait alors avoir les points P1, P2 et le centre pour chaque arc.
Autre stratégie, peut-être plus fine graphiquement: on itère sur les rayons de courbure (attention, il y aura peut-être un extremum à passer), on recalcule l'angle polaire correspondant et on en déduit les points intermédiaires correspondant à ce rayon.
En lisant ceci en diagonale, ça ressemble pas mal à ce que vous cherchez à faire. En plus le pseudo-code est fourni, ça ne devrait pas être bien dur à tester rapidement (modulo les transformations de repère à faire, toujours facile de s’y emmêler les pinceaux) !
si cela peu vous aidai voici la photo d'une élipse tel qu'elle est générée en polylignes transformable en DXF par mon logiciel machine Masterwork
elle a un rayon horizontal de 300 et 200 en vertical
la sorte de d'aile d'oiseau en dessous représente les différents centre des différents arcs de cercles
les segments de camembert sont respectivement à 12.38 °22.5° 31.99° 45° 59.96° 90°
si cela peut aidai je peu le transmettre en DXF ou PDF
j'ai ajouté cette photo car je n'arrive pas à suivre tout vos résonnements(je n'ai qu'un niveau de 3°) mais j'ai l'impression que que vous vous posez la question de la répartition des secteurs et donc là vous avez 2 cas de figure à droite un découpage sur une élipse plus ronde découpé en 6 secteurs à gauche une élipse plus plate découpée en 8 secteurs toujours avec Masterwork
1ère étape : exprimer le problème dans le repère de l'ellipse (axes coïncidant à x et y : a = 0, C = (0,0)). Au moins dans un premier temps, il vaut mieux chercher à résoudre le problème dans ce repère et appliquer les transformations adéquates avant et après .
ourea Une petite matrice de rotation du repère, et hop, on peut le faire à n'importe quel moment du calcul. Cela ne change rien au processus.
Avant de résoudre analytiquement un problème mathématique, quand on a l'habitude, on commence par l'exprimer dans sa forme la plus simple. Ca fait partie du "processus" de résolution...
Tu ne verras jamais un mathématicien traiter le problème (ou y réfléchir) directement sous cette forme.
D’où ma suggestion à Boris Beaulant...
ourea Oui, bien sur, c'est un truc de base. Mais cela ne change pas grand chose au problème... Le repère, on le change quand on veut, c'est une question marginale.
Ca permet de réduire le nombre de variables et supprimer les couplage avant de commencer à réfléchir.
Sinon Kentaro, je peux encore en placer une sans que tu viennes m'emmerder ? T'as que ça à faire de tes journées ?
ourea Oui, comme déjà dit, c'est un truc évident, cette histoire du repère. Mais c'est pas ça qui résoud la question.
Faut pas prendre la mouche comme ça, je ne vois pas en quoi je suis venu t'emmerder... J'ai simplement dit qu'une petite matrice de rotation, et hop, la question était réglée. Je l'ai dit très gentiment, et sans aucune animosité.
Est-ce qu'on est dans la section réponses ?
Personne n'est dupe...
Hey les gars commencez pas l'année en vous bouffant le nez. Paix et amour . Restons-en là !
ourea, ta remarque est fondée. Mais, j'ai posé le problème ainsi, parce que c'est ainsi qu'il est à résoudre. En occulter un bout (même s'il parait évident) produit pas un résultat valable. C'est toujours dans les trucs faciles qu'on écarte qu'on fera le plus d'erreur.
Pour preuve, mon algo actuel donne des effets de bord que j'explique mal pour les ellipses qui ont justement ... un angle...
Par ailleurs, cette question étant destinée à survivre dans le temps à mon besoin, je serais content qu'elle apporte une réponse générale.
Kentaro, chacun ses évidences.
Bonne année Boris Beaulant, je te souhaite le meilleur (et moins d'échanges comme ceux-là - j'en suis désolé).
Justement, si ton algo actuel opère dans ce repère général, une résolution dans le repère de l'ellipse (avec transformations appropriées avant et après) éviterait les "effets de bord" que tu observes, puisque le découpage en arcs de cercle serait indépendant de l'orientation / position de l'ellipse (lorsqu'observé dans le repère de l'ellipse, s'entend). C'est une solution.
Transformation avant : translation en (0,0) puis rotation.
Transformation après : rotation inverse puis translation en C.
Meilleurs voeux ourea !
Non, ce qui semble donner des résultats incohérants, c'est la recherche d'un point (dans le repère général) sur l'ellipse (code ici)
Les formules m'ont l'air bonnes... Par contre, tu peux essayer de remplacer ellipse_def.angle par -ellipse_def.angle (et/ou angle par -angle, dans une moindre mesure), car il dépend de la convention utilisée (que j'ignore).
Boris Beaulant, en complément, voici ce que j'obtiens avec tes formules, pour
ellipse_def.center.x = 3
ellipse_def.center.y = 2
ellipse_def.xradius = 0.8
ellipse_def.yradius = 0.2
ellipse_def.angle = 0.2
et angle qui varie par pas de 0.1.
En somme, ça fonctionne... Ton problème doit donc venir d'ailleurs.
ourea merci d'avoir regardé. J'ai trouvé mon problème ! Il venait en effet d'ailleurs. J'ajoutais 2 fois l'angle d'inclinaison ...
Voilà un problème de réglé...
Et au fait, Martin Müller n'a pas d'idées sur une méthode ? Il parait pourtant plutôt bien armé pour ça...
J'ai bien peur que la détermination d'une solution optimale nécessite une approche itérative, ce qui n'est pas ce que vous voulez, j'imagine ?
Plus il y a de gens, plus il y a d'idées
J'ai pas de frein à ça tant que ça fait pas des calculs de 10min.
j'ai un reste de frustration a propos au fait que le format standard natif créé par autodesk n'est pas évolutif! il manque un chainon? pourquoi dxf pour tout par tout , si il ne coche pas toutes les cases de l'esquisse 2d? que dit autodesk a ce propos? si c'est ce qu'autocad propose de mieux, autocad est il mort ou faut il militer pour l'apparition un dxf+courbecomplexe ???
il n'existe rien d'autre ou les pistes existantes ne sont pas suffisament reprises globalement pour être supporté par les cadors du market? OCL va t'il renverser la vapeur? (yes)
mofran le SVG supporte très bien tout ça et OCL exporte aussi en SVG.
Le DXF reste malheureusement un standard universel dans les logiciels métier et autres machines d’usinage.
DXF supporte les splines, mais à ma connaissance ça ne mixe que des courbe de Béziers sans cassure de courbe.
Oui DXF n’est pas le format qui va bien. Je le comparerai bien au système impérial qui rend les américains fiers et qui est merdique à implémenter dans du code. Grosse perte de temps.
Bref, vive le système métrique et les standards ouverts !
Bonjour Boris Beaulant et meilleurs voeux pour cette nouvelle année !
J'ose tenter un ping à Toutenbois qui aura peut-être le temps et je l'espère les compétences en Maths adéquates !
Salut Je suis passé voir le sujet hier, cependant il faut bien admettre que les maths c'est pas comme le vélo... 20ans à enseigner en collège, conjuguer avec des années de menuiserie, plus passionné par les épures que par les méthodes analytiques pour obtenir les angles et autre information necessaires , m'ont bien ramolli le cerveau. D'autant plus que j'ai toujours été passionné de pédagogie, c'est a dire la manière de bien enseigner plutôt que math pour le plaisir de faire des maths... et je crois pouvoir dire que mes élèves ne s'en sont que mieux porté.
Belle année à toi Sam.
Toutenbois on en aurait tous voulu des profs avec cette approche au collège
Bonjour et bonne année à tous
Je n'ai pas de réponse à donner par contre si je comprend prend l'idée reviens à transformer une spline en polyline
Bon bah sa ne va pas te plaire les autocad-like que je connais (nanocad - acad-draftsight) ont éludés la réponse et transforment la spline en succession de droites
là ou ils sont capable de le faire avec une ellipse ils ont semble t'il jeter l'éponge pour les splines ....
bonjour avez vous trouvé une solution ?
Il y en a plusieurs et avec chacune avantages et inconvénients du différents.
Je vais panachez ce qui a été proposé ici et je vous donnerai la solution retenue.