Il s'agit d'un projet informatique, mais la question est plutôt mathématique et indépendante du langage utilisé, donc je pense que la section mathématique est plus appropriée.
J'ai deux lignes polygonales (ou polylignes), c'est à dire des lignes constituées d'une succession de segments. Elles sont représentées par deux tableaux contenant les coordonnées de chaque nœuds, dans l'ordre. Je cherche le point d'intersection lorsqu'il existe. L'intersection de deux segments, c'est facile à calculer, donc si je sais quels sont les segments des polylignes qui s'intersectent, le calcul prends quelques lignes de code. Par contre, comment trouver de quels segment il s'agit ? Pour le moment la seule solution que j'ai trouvée consiste à tester tous les segments de la première ligne avec tous les segments de la seconde. Ce qui donne un temps de calcul proportionnel à m×n, m et n étant les tailles respectives des lignes et pouvant être des valeurs relativement élevées.
Existe-t-il un algo qui permette de faire cela plus rapidement, par exemple en limitant la zone de recherche ?
Bonjour ! Voilà précisément le genre de problème qui m'intéresse ! Mais je soupçonne que c'est assez complexe et je n'ai pas le temps. À mon avis il y a déjà eu des études à ce sujet et j'espère que quelqu'un les connaît et te donnera des références. En attendant, je pense à une idée pour accélérer les choses, mais tu y as peut-être déjà pensé.
OK, il faut étudier l'intersection de chaque segment de la ligne 1 avec chaque segment de la ligne 2. Mais je pense que dans la plupart des cas, ça ne doit mener à un aucun calcul. Pour ça, il faut mémoriser avec chaque segment ses Xmin, Xmax, Ymin et Ymax. En examinant les valeurs pour deux segments donnés, on peut voir immédiatement qu'ils ne peuvent pas se couper (lorsque c'est le cas). De plus, la condition n'est pas un ET mais un OU : si les X sont incompatibles, ou si les Y sont incompatibles, il n'y a pas d'intersection, donc si un seul des deux tests est négatif, on peut conclure sans faire l'autre test.
Tu dis que le nombre de segments est relativement élevé, je m'attends à ce que dans la grande majorité des cas on ne fera que ce simple test (beaucoup moins long qu'un calcul d'intersection).
À vrai dire je ne m'attends aussi à ce que tu aies pensé à cette comparaison avant de faire les calculs, du coup mon intervention est inutile. C'est juste au cas où, parce qu'on ne sait jamais...
Pour chaque segment, on a Xmin, Xmax, Ymin, Ymax , mais on peut aussi regarder (X+Y)min ou (X-Y)min, et les max pour ces 2 indicateurs.
Si tu as vraiment beaucoup de segments, et que ces segments suivent une certaine logique, tu peux aussi faire des lots : sur la polyligne n°1, on fait des groupes de 100 segments consécutifs. Pour chaque groupe, on calcule le Xmin, Xmax, Ymin et YMax ; on fait la même chose sur l'autre polyligne.
Et ainsi, avec un seul test, tu vas pouvoir dire : entre tel groupe de 100 segments de la ligne 1, et tel groupe de 100 segments de la ligne 2, il n'y a aucun point d'intersection.
Par ailleurs, dans ton 1er message, on a l'impression que tu parles d'un UNIQUE point d'intersection. Si c'est bien le cas, on doit pouvoir exploiter cette information.
C'est pas mal l'idée de faire des groupe. Surtout que j'ai des polylignes de tailles très différentes, donc si je prends le rectangle circonscrit de la plus petite (O(m)), puis je regarde à partir de quand la plus grande rentre dans ce rectangle (O(n)), je travaille sur un un tronçon de polyligne à peut près de taille m, donc ça fait du O(m + n + m×m’) (je suis pas sûr pour les notations avec les O, c'est pas trop mon domaine, mais je pense que c'est assez clair pour comprendre l'idée.
Dans mon cas, je n'ai effectivement qu'un seul point d'intersection. Mais ça intéressera peut-être du monde d'avoir un cas plus général.
Qu'est-ce que tu veux dire avec les (x+y) et (x-y)min/max ?
La suggestion de Robun, c'était d'encadrer chaque segment dans un rectangle à bords verticaux/horizontaux. Et si entre 2 segments, les rectangles en question ne se superposent pas, alors c'est sûr, les segments ne se coupent pas.
L'idée des (x+y)minmax et (x-y)minmax, c'est exactement la même. Sauf qu'au lieu de prendre des rectangles à bords verticaux/horizontaux , on prend des rectangles à bords inclinés à 45°.
L'idée n'est pas mieux ni moins bien que celle des rectangles à bords verticaux/horizontaux ; mais en testant une méthode puis l'autre, on peut éliminer plus de cas, sans utiliser des calculs compliqués. Et ce sera d'autant plus efficace avec l'idée des groupes de 100 segments.
Si on sait qu'on a un seul point d'intersection, et si les lignes ne sont pas trop piégeuses, alors on peut tenter une espèce de dichotomie... Mais ça va être assez compliqué à programmer, pour un bénéfice faible. Si tu as absolument besoin que le traitement aille très vite, l'investissement est utile.
Lignes piégeuses, c'est quoi ? Ce serait par exemple une ligne en spirale.
Est-ce qu'une heuristique ou une solution approchée t'intéresse ? (si ça permet de diminuer le temps de calcul)
Est-ce que les points de ta demi-droite sont totalement quelconque ? S'il s'agit des points de la courbe d'une fonction par exemple, on peut avoir quelques propriétés sur le fait que la courbe ne boucle pas sur elle même, ou ne repasse pas deux fois par le même abscisse, ça peut aider).
Si je trouve des choses intéressantes je te dirais.
EDIT : Ce problème m'a vraiment piqué, et j'essaie de réfléchir à un maximum de possibilités. J'ai des idées d'algos qui pourraient être pas mal selon certaines hypothèses sur la régularité de tes courbes. Avant d'aller trop loin dans mon développement, j'aimerais avoir quelques informations supplémentaires sur l'origine de tes courbes polygonales. D'où viennent-elles ? Si tu me dis par exemple qu'il s'agit de courbes discrétisées, donc de points plus ou moins régulièrement espacées, j'ai déjà de bonnes idées en tête.
- Edité par gasasaa 26 mai 2020 à 23:22:02
Vous n'auriez pas un ptit calcul à me montrer ? :D
Tu veux dire une fonction qui va trouver « la plupart » des solution ? Ou une solution qui soit bonne « la plupart du temps » ? Non, pas vraiment dans mon cas.
> ou une solution approchée
Ça dépends du nombre de décimales. Faudrait être dans le millionième de la longueur des segments en ordre de grandeur.
> Est-ce que les points de ta demi-droite sont totalement quelconque ?
Les rayons de courbures sont relativement grands devant la taille des segments (de l’ordre de 30× au minimum). C’est la principales propriété notable.
> S'il s'agit des points de la courbe d'une fonction par exemple, on peut avoir quelques propriétés sur le fait que la courbe ne boucle pas sur elle même, ou ne repasse pas deux fois par le même abscisse, ça peut aider
Il me semble qu’elle ne peut pas boucler sur elle-même. Par contre, ce n’est pas une fonction, donc elle peut tout à fait revenir en arrière, être parcourue dans le sens des x décroissants, etc. Les points ne sont pas forcément régulièrement espacés. Ce ne sont que des segments de droites. il n’y pas de points reliés par des paraboles ou de courbes de Bézier, ou autre.
La question de la fonction, c'était au cas où les points proviendraient d'une courbe que l'on peut définir par une fonction. Par exemple si la courbe est un cercle, la ligne serait une succession de cordes (segments reliant deux points d'un cercle). Mais bien sûr que ça resterait des segments.
Bon, compte tenu de ce que tu dis, j'ai du mal à te proposer vraiment mieux que l'algorithme naïf que tu avais déjà trouvé toi-même. Je pense qu'il existe sûrement mieux, mais je trouve pas .
Je te propose quand même une idée qui "pourrait" être plus efficace que l'algo naïf, mais sans savoir d'où viennent tes courbes et la répartition des segments, ça paraît difficile à dire.
Tu peux facilement déterminer l'abscisse / ordonnée min, max de tes points, et donc déterminer une "fenêtre" (un rectangle) dans laquelle tous tes points se trouvent. (Toutes ces opérations sont en O(m+n)). Imaginons par exemple que tous tes points se trouvent dans [0,1]*[0,1].
Tu divises ce carré en petites sous-cellules, de taille 0.1*0.1. (un genre de quadrillage finalement. Je fixe arbitrairement à 100 le nombre de sous-cellules, mais on y reviendra). Pour chaque segment de chaque courbe, tu détermines le quadrillage dans lequel il se trouve. Tu remplis donc un tableau tel que case[n°i] = [{ensemble des segments qui appartiennent à la case i}]. (le tout se fait en O(m+n) également)
Sans hypothèse sur la nature de tes segments, on peut raisonnablement penser qu'il se répartisse assez naturellement dans les différentes cases. Tu as donc (grosso modo) 100 cases, avec un nombre de segments m/100, n/100 dedans. Tu appliques alors l'algo naïf à chaque cases. En effet, s'il existe une intersection entre tes deux courbes, elle est forcément au sein d'une case de ton quadrillage. Cette case de ton quadrillage contient donc les deux segments de droites qui se coupent. Ainsi, en effectuant l'algo naïf sur toutes les cases de ton quadrillage, tu t'assures trouver un point d'intersection s'il en existe un.
Tu te retrouves donc à effectuer 100 fois l'algo naïf, sur des tailles bien réduites. Soit un temps proportionnel à 100 * (m /100) * (n/100) = nm/100.
si m = n assez grand (j'imagine de l'ordre de 1 million pour qu'une recherche d'optimalité soit intéressante), on peut considérer que les premières opérations de quadrillage sont totalement négligeable par rapport au temps de calcul d'intersection de m*n segments. On a donc divisé le temps de calcul par 100. Si on est ambitieux, on peut même se dire qu'on peut réitérer le processus de manière récursive sur la recherche d'intersection au sein de nos sous-cellules, et obtenir un algorithme en O(nln(n)) (en supposant n = m).
Mais bien sûr, il y a un mais.
Ce que je n'ai pas pris en compte ici, c'est que nos segments ne vont à priori pas pouvoir se ranger gentiment dans une case de notre quadrillage. La plupart de nos segments vont en réalité être à cheval sur plusieurs cases. Ainsi, plusieurs possibilités s'offrent à nous pour gérer le problème.
1) Si un segment est à cheval sur plusieurs cases, on considère qu'il est présent dans toutes les cellules. Ca ne perturbe pas l'algorithme dans la suite de son fonctionnement.
2) Si un segment est à cheval sur plusieurs cases, on le segmente de manière à ce qu'il devienne un ensemble de segment propre à chaque case.
On va considérer dans la suite la première proposition, qui me paraît moins couteuse en calcul à première vue.
Au fond, les deux possibilités sont plus ou moins similaires. Mais elles induisent un temps de calcul supplémentaire, liée au fait qu'au final, dans chaque case, il n'y aura plus grosso modo n/100 segments. mais potentiellement beaucoup plus. L'optimisation de l'algorithme va donc consister à choisir un quadrillage de taille adéquate. On voit que pour un quadrillage de taille 100, on diminue grosso modo le temps de calcul par 100, en négligeant le problème de chevauchement. Mais, plus le quadrillage est petit, et plus le nombre de segment se chevauchant va être important, et moins ce phénomène sera négligeable.
Une première manière de choisir un quadrillage est le choisir de manière à ce que la largeur d'une case soit égale à la taille du segment le plus grand. Ainsi, un segment peut chevaucher au maximum 3 cases à la fois. Si vous aimez les probas, la vraie espérance du nombre de cases chevauchées par un segment de taille l dans un quadrillage l*l est calculable. Mais tout de suite, j'ai la flemme, donc on va approximer cette espérance par 2 (ce qui je pense est assez proche de la valeur théorique).
Ainsi, un quadrillage de taille 100 correspondrait à un dessin qui tient dans [0,1]*[0,1], dont le plus grand segment de taille 0.1. Franchement, si notre courbe de trait ne correspond pas un gribouillage immonde de truc qui bouclent sur eux-même, ça me paraît raisonnable de considérer qu'il n'y a pas de segment qui font toute la largeur de la zone de dessin. Mais encore une fois, je n'ai aucune idée la forme de tes courbes, c'est pour ça que je peux pas affirmer que l'algo représente une réelle optimisation. Avec ces hypothèses (plus grand segment de taille 0.1, tu te retrouves avec un quadrillage de 100 cases, et chaque case contient environ (2*n/100+2*m/100) segment. (le 2 correspond au chevauchement).
Tu as donc 100 opérations à faire sur chaque case, soit 100*(2*n/100*2*m/100)=4/100*n*m. Tu aurais donc quand même divisé le temps de calcul par 25, ce qui est déjà correct.
Bien sûr, le fait de choisir la taille du quadrillage en fonction du plus grand des segments n'est sûrement pas la meilleur des solutions. On s'en doute, si j'ai 999 999 segments de taille <= 0.01, et un segment de taille 0.5, le plus optimum aurait sûrement été de prendre un quadrillage de taille 0.01, quitte à devoir scinder l'unique grand segment dans plusieurs cases.
Trouver la solution optimale générale pour une distribution de segment quelconque se trouve sûrement en faisait des probas, et j'imagine que c'est une formule qui prend en compte l'espérance, et l'écart-type de la taille des segments (valeurs qui sont obtenables en O(m+n), c'est-à-dire en un temps négligeable.)
Je peux proposer au pif une valeur de l'ordre de \(E(l)+2\sigma(l)\), j'imagine encore une fois ne pas être très loin de la valeur optimale théorique, mais si ça t'intéresse je pourrais essayer de la calculer vraiment.
Ainsi, bien réaliser l'algorithme consiste à trouver cette valeur optimum du quadrillage. Le gain de temps précis que ça te rapportera reste très compliqué à évaluer, surtout sans hypothèses sur la nature de tes segments. Ce gain dépend majoritairement du rapport entre la taille de la zone de dessin et la longueur moyenne de tes segments. Ca me paraît raisonnable de considérer que si tu as une courbe qui comporte beaucoup de segment, donc une courbe de longueur totale E(l)*m, la zone de dessin associé soit grande (de l'ordre de \(\sqrt(mE(l)*)\), mais c'est vrai qu'en y réfléchissant, on peut trouver facilement des courbes alambiquées qui font des spirales sur elles-même, et qui, bien que très longues, n'occupent que peu de places. (et ce même si elles ne bouclent pas sur elles-même).
Sur ce, le temps me manque, j'espère au moins avoir pu te donner des idées. Si le concept de l'algo te semble prometteur vis-à-vis de la forme de tes courbes de segment, dis le moi et j'essaierai d’approfondir certains points.
- Edité par gasasaa 30 mai 2020 à 4:24:47
Vous n'auriez pas un ptit calcul à me montrer ? :D
Si les rayons de courbures sont relativement grands, tu peux envisager quelque chose comme ça :
Pour une ligne, tu prends un point sur 30 (sur 30, sur 50, sur 100 ? à toi de tâtonner)
Supposons que les points M0 et M30 aient pour coordonnées (0,0) et (100,0) ;
Tu peux bâtir un losange (-4,0), (50,15), (104,0), (50,-15) : je prolonge le segment M0 M30 de 4% de part et d'autre, et sur la médiatrice de M0 M30, je prends 2 points pas trop espacé (30% de la longueur du segment M0 M30)
En principe, tous les points de la courbe devraient être dans ce losange, si les rayons de courbure sont conformes à ce que tu annonces. Je pense même que j'ai prévu très large. Portion par portion, tu peux controler que tous les points sont dans le losange, et si ce n'est pas le cas, tu agrandis le losange en question.
Idem pour la 2ème courbe.
Et ensuite tu testes quel losange de la 1ère série a une intersection avec quel losange de la 2ème série.
Si 2 losanges ont une intersection, ça ne voudra pas dire que les courbes se coupent, mais si 2 losanges ne se coupent pas, c'est sûr que les portions de courbes correspondantes ne se coupent pas.
La 2ème étape du traitement, c'est : on a trouvé 2 losanges qui ont une intersection. On a donc 2 x 30 segments, et on veut voir si ils ont une intersection. Je pense qu'en trouvant un axe adéquat, et en jouant avec le TVI et une dichotomie, on doit pouvoir trouver assez vite, sans comparer brutalement les 30x30 segments.
Tbc92 Bon je sais que je suis un peu parti en couilles et que j'ai proposé un algorithme qui est efficacesous un certain nombre d'hypothèses, mais qui fonctionne tout le temps, mais le but n'est pas non plus de proposer n'importe quoi. Si t'as pas une estimation de la complexité de ce que tu proposes, et que t'es pas capable de proposer un procédé algorithmique complet, c'est que l'idée ne mérite pas d'être partagée. (On fait quoi on fixe des losanges de plus en plus grand pour être sûr que tous les points sont dedans ? Si tu prends des losanges trop gros ils vont tous s'intersecter et tu perdras tout l'intérêt de la chose. Sans compter que tu peux agrandir indéfiniement les losanges avant d'avoir les 30 points qui sont dedans, si tu n'agrandis pas correctement. Rien que ce découpage en losange peut déjà être plus long que l'algo de base. Dans l'idée ce que tu proposes pourrait peut-être marché, c'est le même concept que mon algo finalement (découper l'espace en plusieurs sous-espaces, et voir les points qui sont dedans), mais la démarche est totalement arbitraire.
Pourquoi des losanges ? pourquoi tous les 30 points ? pourquoi des marges de 4% et 30% ?
Pourquoi pas prendre un point sur 3^297 et essayer de l'encadrer par un dodécagone ?
- Edité par gasasaa 28 mai 2020 à 22:40:32
Vous n'auriez pas un ptit calcul à me montrer ? :D
Yo! Je viens lire le sujet, j'avoue ne pas avoir d'idée par rapport à ce qui a déjà été dit. Mais je viens répondre a @gasaaa
gasasaa a écrit:
[...] Si t'as pas une estimation de la complexité de ce que tu proposes, et que t'es pas capable de proposer un procédé algorithmique complet, c'est que l'idée ne mérite pas d'être partagée. [...]
J'aurai tendance a penser que ça c'est une connerie comme raisonnement. Même si c'est pas abouti, toutes les idées sont bonnes à être partagées, surtout dans un tel contexte où, semblerait-il, il n'y ai pas vraiment de solutions trouvées. Chaque idées, même incomplète, peut mené a une solution par la suite. Une personne qui a une idée aura toujours un peu le nez dans le guidon, et ce sera plus difficile pour cette personne de trouver une autre solution. Alors que si une autre personne lit ou étudie le début de solution, il peut penser a d'autres trucs et peut etre mené a la suite d'un raisonnement plus juste.
Voilà voilà, désolé de l'incruste. Si je trouve une idée intéressante, je la partagerai.
« Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. » D. Mendeleïev
Bon, de toute façon l'OP semble ne plus s'intéresser au sujet, donc pas la peine de débattre pendant des heures. Quant à la solution proposée par TBC, je suis désolé de le dire, mais c'était juste du grand n'importe quoi, je pense qu'il en a lui-même conscience. Mais c'est sûr que si on ne lit que la moitié du sujet, ça peut ne pas sauter aux yeux.
Vous n'auriez pas un ptit calcul à me montrer ? :D
Gasasaa, je ne sais pas pourquoi tu es agressif à ce point. J'ai laissé passer ta première attaque, je me suis dit que tu avais dû passer une mauvaise journée ou quelque chose comme ça, et que tu passais ta colère sur moi. Soit. Mais puisque tu remets le couvert, je vais te répondre.
Si ta proposition était plus pertinente que les autres pistes proposées, tu pourrais jouer sur ce registre : les autres sont nuls et je suis brillant. Et encore, ce ne serait pas très malin.
Mais comme ta proposition n'est vraiment pas efficace, évite de critiquer les autres.
Quelques points supplémentaires :
- tu dis que tu n'as aucune idée de la forme des courbes : fallait lire la réponse de Megalo à ta question : les rayons de courbure sont relativement grands.
- tu dis que déterminer des losanges suffisamment grands, ça peut être très long et très coûteux, et que ça peut donner des losanges extrêmement grands. Si tu avais lu la réponse de Megalo, tu aurais vu que ce n'est pas le cas. Et si tu avais voulu comprendre pourquoi je proposais cette idée originale de losanges, tu pouvais poser une question. Poser une question, c'est toujours un signe d'intelligence. alors que critiquer sans chercher à comprendre, c'est un signe de bêtise.
Tu n'as peut-être pas lu non plus mon message du 23 mai à 21h13.
Tu verras que je proposais de découper chaque polyligne en groupes de 100 segments à peu près. En gros plus ou moins l'idée que tu as reprise, sauf que tu as 'inversé' les dimensions. Au lieu de découper chaque polyligne en groupes de 100 segments, tu découpes l'espace en 100 rectangles.
En quoi est-ce mieux que la proposition originale ? Personnellement, je peux dire en quoi c'est moins bien, et je ne vois vraiment pas en quoi ta proposition aurait pu être une amélioration de cette idée.
Tu n'as pas vu non plus l'idée de créer non seulement des rectangles avec des bords horizontaux/verticaux, mais également de créer des rectangles avec des bords inclinés à 45° ; et ça peut se généraliser, on peut parfaitement créer 3 jeux de rectangles, avec des bords inclinés à 0°, 30° et 60°. Ainsi, on pourra éliminer de façon très rapide tout un tas d'hypothèses. Surtout quand on a l'information que les rayons de courbure sont grands, et donc que ces rectangles auront une longueur relativement grande, mais une largeur relativement petite.
Largeur petite ... tu vois l'intérêt ?
Pourquoi je propose des losanges, et pourquoi je les bâtis comme dans ma 1ère proposition ? Parce que, à partir d'une courbe avec des très grands rayons de courbure, le losange est la forme simple, facile à construire et avec une surface minimale. Et que tester si 2 losanges ont une intersection, c'est peu coûteux.
Pourquoi des losanges plutôt que des dodécagones ? Je te renvoie la question, pourquoi dans ta proposition as-tu choisi des rectangles, et pas des polygones de formes diverses ?
Pourquoi un point sur 30 ? Je te renvoie la question, pourquoi proposes-tu de découper l'espace en 100 rectangles ?
Si enfin tu avais lu correctement mon message, tu aurais vu que l'algorithme est complet. Je propose une première logique (ces losanges), qui permet de diviser le temps de traitement par 100 voire beaucoup plus. Vraiment beaucoup plus.
Ensuite, quand on a identifié un groupe de 30 segments de A et 30 segments de B où éventuellement, il y a une intersection, je dis qu'on peut utiliser la force brute ... tester les 30*30 combinaisons. Simple, facile, ça marche.
Ou peut-être, en cherchant un peu, on peut aussi optimiser cette 2ème phase, par une méthode plus ou moins dichotomique. Ce qui serait un 2ème axe d'optimisation, qui viendrait s'ajouter au 1er axe, celui obtenu avec les losanges (ou avec les rectangles inclinés...)
Megalo n'a pas demandé que je développe cette 2ème phase. Donc je n'ai pas développé. Mais je suis assez convaincu qu'il y a moyen de faire pas mal de choses sur cette 2ème phase. Le fait d'utiliser ou pas une optimisation dans cette 2ème phase n'enlève rien aux propositions faites sur la 1ère phase.
Ca pourrait juste influencer le choix de ce fameux facteur '30'. Si on trouve une bonne optimisation sur la 2ème phase, alors on a tout intérêt à faire des groupes plus gros ; 50 voire beaucoup plus au lieu de 30.
A ce niveau, il faudrait quelques jeux de données représentatifs pour avancer plus. En particulier sur cette question de rayon de courbure.
Ces fameux losanges ont un autre intérêt qui est énorme, et que je n'avais pas développé jusque là.
-1- on recense tous les couples de losanges qui se superposent.
-2- pour chaque couple de losanges, on peut déterminer une certaine probabilité : Si les grands-axes des losanges A et B forment plus ou moins un X, alors c'est à peu près sûr qu'on aura un point d'intersection. Par contre, s'ils forment un Y, ou si les grands axes des 2 losanges sont plus ou moins parallèles, on a une probabilité plus faible de trouver un point d'intersection. On calcule donc pour chaque couple de losanges un indicateur qu'on va appeler probabilité. C'est en gros un produit scalaire à calculer, ça ne coûte rien
-3- Et bien sûr, on analyse d'abord les couples de losange ayant la plus forte probabilité.
Comme on a un seul point d'intersection à rechercher, on n'aura pas à étudier tous les couples de losanges, mais uniquement les premiers.
Et du coup, ça aussi, ça incite à augmenter la taille des groupes (50 voire 100 voire 200 au lieu de 30)
On pourrait proposer encore d'autres optimisations sur cette base très prometteuse ! Si Megalo est intéressé...
Il me semble désormais évident que l'auteur a oublié ce topic, donc bon, que la méthode des losanges ou des carrés soit la plus efficace...
J'ai déjà une première remarque à faire sur la forme. En sciences, c'est toujours pareil. Un résultat donné sans justification n'a pas d'intérêt. La rigueur des démonstration n'est pas toujours aussi poussé en informatique qu'en maths, mais donner au moins des pistes, dire d'où vient tel résultat n'est pas quelque chose d'optionnel. Il n'est pas normal que tu nous donnes une méthode, sans aucune (ou presque) justification, puis que tu m'en donnes une 10 jours après parce que j'ai fait remarqué que tes méthodes paraissaient hasardeuses.
Pour le fond, je n'ai sincèrement pas envie d'en discuter. J'avais commencé à lire ta réponse avec intérêt, en pensant que tu développerai un peu cette idée farfelue que sont les losanges (et qui, je le répète, est sûrement aussi viable que faire des carrés en soi), mais l'accumulation de mauvaise foi, tes citations partiels et trompeuses de ce que j'ai dit et l'absence totale d'une rigueur scientifique dans tes propos m'en ont découragé. J'en suis à me demander si tu n'es pas un troll
- Edité par gasasaa 9 juin 2020 à 22:39:48
Vous n'auriez pas un ptit calcul à me montrer ? :D
Quand je vois un message que je considère comme 'bizarre', je regarde l'historique des contributions de la personne, je regarde quelques messages postés par la personne, et j'essaie de voir si cette personne contribue positivement, ou pas.
Mène cette petite enquête, et tu auras ta réponse.
Traînant assez souvent sur le forum, je sais bien que tu en es un des membres les plus actifs, et que tu as déjà aidé énormément de personnes ici. Bref, désolé d'avoir lancé cette querelle, rien ne justifiait autant d'agressivité dans mon premier message.
Vous n'auriez pas un ptit calcul à me montrer ? :D
Houla, je m'absente deux semaines et c'est le clash sur le topic.
Pour ce qui est de m'intéresser au sujet, j'avais besoin d'un truc qui marche, donc je suis parti sur une des premières solutions proposé (intersection de carrés. Ça marche pas mal dans mon cas dans la mesure ou j'ai à chaque fois l'une des deux polylignes de taille assez courte et c'est facile à coder). Aujourd'hui c'est codé et je n'ai pas le temps de me repencher dessus dans l'immédiat. J'ai donc passé le sujet en résolut et je risque de participer de façon assez irrégulière à l'avenir.
Cela dit, il est possible que je me retrouve à nouveau sur un cas similaire ou que je trouve le temps d’améliorer un peu mon algo dans un avenir plus ou moins proche. Il est aussi possible que ça serve à d'autre dans la mesure ou il y a vraiment pas grand chose qui traîne sur le net à ce sujet. Donc vos idées ne sont pas perdu.
Pour ce qui est des idée qui ont été proposée, encore une fois je ne me suis pas penché en détail sur ce qui a été proposé après mon dernier message, mais je peux donner une première impression.
− L'idée le dichotomie me plaît. En pratique, ça m'empêche d'utiliser une bête boucle for avec un itérateur. Faudrait accéder aux éléments par leur position, auquel cas, je n'ai accès qu'a une copie. Je ne crois pas que ça pose problème, mais il faudrait que je vérifie.
− L'idée du quadrillage me semble pouvoir marcher, avec quelques petites adaptations.
− L'idée des losange doit pouvoir marcher si les diagonales sont suffisamment petites devant le rayon de courbure. Plutôt que mettre une largeur aléatoire, on doit pouvoir simplement prolonger les segments d'entrées et de sortie jusqu'à qu'ils s'intersectent, de manière à être sûr que la polyligne ne sorte pas du losange. Par contre la solution me parait un peu usine à gaz à coder. D'i
Pour l'idée du quadrillage, une variante qui me parait réalisable :
1/ découpage en grille de la zone circonscrite au deux courbes ).
2/ création de deux tableaux (un pour chaque polylignes) dont les indices correspondent à ceux des cases de la grille. Chaque élément contient une polyligne construite sur l'ensemble des segments intersectant (c.a.d contenant au moins un point à l'intérieur) la case correspondante. Si la courbe sort et re-rentre dans la case, on vire simplement les segments intermédiaires ( O[m] + O[n] )
3/ On parcourt nos deux tableaux simultanément ( O[nbcase] ). Si l'une des deux polylignes est vide on passe, sinon
4/ On applique l'argorithme naif ( O[m[i]×n[i] ). Si le point trouvé est à l'intérieur de la case on garde, sinon on passe au suivant.
On peut approximer le résultat final à O[ m + n + nbcase_vide + nbcase_non_vide×m_moyen×n_moyen ] si je ne m'abuse. Les trois facteurs du dernier termes sont interdépendants. Si je fais un calcul approché avec deux courbes le long de l'axe x. Ça fait m_moyen = m/nb_case_non_vide + 2 (les segment dépasseront quasiment tout le temps. Si on suppose nb_case_vide = a×nb_case_non vide, on finit avec O[ mn/nb_case_non_vide + 3(m+n) + (4 + a)nb_case_non_vide ] avec un maximum pour nb = racine(mn / (4 + a)) soit un résultat final de O[ 2×racine(mn(4+a)) + 3(m+n) ] ce qui peut-être inférieur à O[ mn ] ou pas selon que a est plus ou moins grands par rapport à m et n et selon que je me soit planté dans mon calcul ou pas.
Je ne sais pas vraiment pourquoi tu parles de "variante" pour l'idée du quadrillage, puisque ce que tu proposes est exactement ce que j'avais en tête. J'ai sûrement dû mal m'exprimer
Pour les calculs de complexité, en effet, tu fais de "grosses approximations". A tel point que le résultat de complexité que tu annonces n'a aucune valeur. Le plus gros problème dans ce que tu fais, c'est que tu considères que ton nombres de cases peut-être fixé comme tu le veux sans conséquences sur l'algorithme. Mais si tu prends un quadrillage trop petit (donc un nombre de case trop grand), chacun de tes segments risque de se retrouver dans beaucoup de cases à la fois. (Imaginons des segments de 1M, dans un quadrillage de 1mm*1mm, chaque segment sera dans 1000 carrés minimum par exemple).
Donc tu n'auras pas m_moyen = m/nb_case_non_vide. Cette formule n'est valable que pour des quadrillages "grands", où les probabilités qu'un segment soient dans plusieurs cases sont faibles.
Je t'invite à relire mon post si tu veux approfondir un peu le calcul de la complexité et le choix du quadrillage, j'avais commencé une explication mais j'ai l'impression de me répéter.
Vous n'auriez pas un ptit calcul à me montrer ? :D
« Je n’ai pas besoin de preuve. Les lois de la nature, contrairement aux lois de la grammaire, ne permettent aucune exception. »
D. Mendeleïev