Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Candidat au Club
    Homme Profil pro
    Développeur Web
    Inscrit en
    janvier 2018
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 24
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : janvier 2018
    Messages : 4
    Points : 3
    Points
    3

    Par défaut Répartition lissée de points sur un cercle

    Bonjour,

    Dans le cadre d'un projet d'application mobile j'ai besoin d'afficher sur un cercle des points d'intérêt (le centre du cercle représente la position de l'utilisateur). J'ai créé un système qui affiche les points d'intérêt le long du cercle en fonction de la position de ces derniers par rapport à la position de l'utilisateur. Ce qui nous donne ceci :

    Nom : 01-ConvertImage.jpg
Affichages : 64
Taille : 43,3 Ko

    Cela marche parfaitement pour des points éloignés les uns des autres mais si les angles des points sont trop proches alors ça devient très moche :

    Nom : 02-ConvertImage.jpg
Affichages : 64
Taille : 41,4 Ko

    J'aurais besoin d'un algorithme pour "lisser" les angles des différents points (espacer les angles de façon harmonieuse), de manière à ce qu'il y ait toujours un angle minimum entre les différents points (disons par exemple 5°).

    Nom : 03-ConvertImage.jpg
Affichages : 65
Taille : 51,5 Ko

    La liste des points est dynamique et après plusieurs essais je n'arrive pas à trouver le bon algorithme, auriez vous des pistes ?

    Merci d'avance pour votre aide.

  2. #2
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 225
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 225
    Points : 7 551
    Points
    7 551

    Par défaut

    Bonjour

    Pas sûr de ce qui bloque.
    • Si tu veux faire un partage égal, il suffit de diviser 2*Pi par le nombre de points d'intérêts.
    • Si tu veux garder une position proche de la position naturelle (que le point sera obligé de quitter définitivement), tu fixes un point d'intérêt comme étant la référence qui ne bouge pas, et tu parcours à droite et à gauche pour repousser les autres points du minimum considéré comme "élégant".


    Si tu as plus de 72 points d'intérêts et que ton angle minimum est 5°, le problème n'a pas de solution.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  3. #3
    Membre expérimenté

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    724
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 72
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 724
    Points : 1 426
    Points
    1 426
    Billets dans le blog
    5

    Par défaut Répartition lissée de points sur un cercle

    Bonjour,

    Une solution consisterait à

    1°) Lister les (N) points selon l'ordre croissant de leur angle polaire (a1, a2, ... , ak, ... , aN) ,
    puis déterminer la moyenne correspondante M0 = (a1 + a2 + ... + aN)/N .

    2°) Déterminer les (N - 1) écarts successifs (b1 = a2 - a1 , ... , bN - 1 = aN - aN - 1) ;
    à chaque fois que l'on trouve un écart (bk = ak + 1 - ak) inférieur au seuil convenu (bmin = 5° , par exemple), augmenter toutes les positions ultérieures (ak + 1 , ak + 2 , ... , aN) de la quantité Da = bmin - bk ;
    une fois l'opération terminée (k = 1, 2, ..., N - 1), toutes les positions successives présenteront un décalage mutuel satisfaisant.

    3°) Afin d'éviter toute dérive de l'ensemble, calculer la nouvelle moyenne M1 = (a1 + a'2 + ... + a'N)/N ;
    diminuer tous les angles de la même quantité (M1 - M0): a"k = a'k - (M1 - M0) ;
    l'ensemble des points retrouvera ainsi son centrage initial sur le cercle.

    Pour un point supplémentaire s'intercalant entre deux des précédents, il faut reprendre tous les calculs puisque leur point de départ est la liste des valeurs classées selon l'ordre croissant.

    Il y aura saturation si de nombreux points se concentrent sur un secteur étroit (90/5 = 18 sur un angle droit); tu pourrais dans ce cas prévoir un second cercle, concentrique au précédent, et de plus grand rayon.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  4. #4
    Candidat au Club
    Homme Profil pro
    Développeur Web
    Inscrit en
    janvier 2018
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 24
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : janvier 2018
    Messages : 4
    Points : 3
    Points
    3

    Par défaut

    Merci beaucoup pour ces réponses, je vais essayer de modéliser tout ça et vous donnerai l'implémentation en code si j'y arrive

  5. #5
    Candidat au Club
    Homme Profil pro
    Développeur Web
    Inscrit en
    janvier 2018
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 24
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : janvier 2018
    Messages : 4
    Points : 3
    Points
    3

    Par défaut

    Merci pour ta solution wiwaxia qui fonctionne à merveille

    J'ai effectivement prévu deux cercles pour mieux répartir les points d'intérêts et mettre aussi en valeur une dimension distance.

    Au niveau du code (JavaScript) ça donne ça :

    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
    40
    41
    42
    /**
     * Private method used to split point angles.
     * @param {array<object>} points
     * @param {number} minSpread
     * @return {array<object>}
     */
    var angleSplitter = function(points, minSpread) {
    
    	// Order points.
    	points.sort(function(pA, pB) {
    		return pA.angle - pB.angle;
    	});
    
    	// Determine average value.
    	var avg0 = getAvgAngle(points);
    
    	// Determine spreads.
    	for (var i = 0; i<points.length-1; i++) {
    		var currentP = points[i];
    		var nextP = points[i+1];
    		var spread = nextP.angle - currentP.angle;
    
    		// Spread too small?
    		if (spread < minSpread) {
    
    			// Adjust next points angles.
    			for (var j = i+1; j<points.length; j++) {
    				points[j].angle += minSpread - spread;
    			}
    		}
    	}
    
    	// Determine new average value.
    	var avg1 = getAvgAngle(points);
    
    	// Readjust angles.
    	points.forEach(function(p) {
    		p.angle -= avg1 - avg0; 
    	});
    
    	return points;
    };
    Et visuellement,

    Sans correction :

    Nom : sans-correction.png
Affichages : 53
Taille : 29,5 Ko

    Avec correction :

    Nom : avec-correction.png
Affichages : 52
Taille : 30,3 Ko

    Merci à vous et bonne continuation !

  6. #6
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 035
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 035
    Points : 4 267
    Points
    4 267

    Par défaut

    J'ai quand même un doute sur cet algorithme.
    Partons avec 6 points, comme dans ton exemple, et Ecart-Mini = 30° ce qui semble en gros le paramètre pris dans ton exemple.

    Au départ, supposons que les 6 points sont en position 5°, 100°, 115°, 260°, 270° et 330°.

    Sauf erreur, tu vas faire : écart 100 --> 115 trop petit, donc on décale les 4 derniers points de 15° , ce qui donne : 5°, 100°, 130°, 275°, 285°, et 345°
    Ecart 275 --> 285 trop petit,donc on décale les 2 derniers points de 20°, ce qui donne : 5°, 100°, 130°, 275°, 305°, et 365°

    Et là pas de chance, comme 365° et 5°, c'est pareil, le 6ème point se retrouve exactement superposé avec le 1er, mais l'algorithme a fini de tourner, et il renvoie ces 6 valeurs.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  7. #7
    Invité
    Invité(e)

    Par défaut

    bj,

    je crois bien que l'algo ne marche pas pour le cas suivant:

    ne marche pas pr certains cas:

    soit le cercle trigo
    soit P_i le point i, et p_i l'angle associé à P_i.

    cas particulier:
    mettons
    p_0 = 0
    p_n = 2pi -delta
    delta ts petit...
    P_0 et P_n vont être accolés...

    cas particulier 2:
    on considère P_(n-1), P_n, avec P_(n-1) = 2pi-minspred
    P_n va être décalé carrément sur P_0 ...

    generalisation: si les points sont bcp concentrés vers la fin du cercle trigo, ben ils vont chevaucher P_0

    solution:
    on peut vouloir faire deux tours de cercle (ca fait très embouteillage de voiture comme solution...)

    edit: tbc m'a doublé: je propose qd même une solution (mais elle me plait pas du tout c'est juste pour le workaround)

  8. #8
    Membre expérimenté

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    724
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 72
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 724
    Points : 1 426
    Points
    1 426
    Billets dans le blog
    5

    Par défaut

    Les objections sont fondées, mais il ne faut pas pousser le bouchon trop loin !
    cas particulier: mettons
    p_0 = 0
    p_n = 2pi -delta
    delta ts petit... P_0 et P_n vont être accolés...

    cas particulier 2:
    on considère P_(n-1), P_n, avec P_(n-1) = 2pi-minspred
    P_n va être décalé carrément sur P_0 ...
    Je m'en suis tenu aux données implicites du problème, à savoir un petit nombre de points (moins de 10) dont les directions s'écartent mutuellement d'un petit angle (au moins égal à 5°), et qui forment un ensemble relativement regroupé.

    La question de la "saturation" du cercle découlant d'un trop grand nombre de points, ou d'un seuil angulaire trop important a été simplement évoquée: il est évident que l'écart angulaire (bmin) ne peut dépasser 360°/N.

    Le classement de la liste suppose l'angle croissant du premier au dernier point, donc que l'arc de cercle (P1P2 ... PN) ne contient pas la discontinuité de la fonction angle polaire.
    Le dessin donné en exemple représente deux groupes de 3 points traités indépendamment l'un de l'autre, et occupant chacun un secteur raisonnablement étendu, de 60 à 120° environ.

    La difficulté est réelle, et l'on ne peut en rester à la définition intuitive et visuelle d'un groupe de points.
    Je reconnais que la méthode proposée, qui augmente les petits écarts sans compensation sur les grands, risque de conduire à des impasses quand les points sont plus nombreux.

    Prenons donc le taureau par les cornes:

    1°) Les angles polaires, situés dans le semi-ouvert [0 ; 2*Pi[, sont définis à partir de l'origine (A) arbitrairement fixée sur le cercle; la liste des (N) points présents est ordonnée selon les valeurs croissantes de l'angle correspondant, de sorte que (A) est encadrée par les points extrêmes P1 et PN d'angles respectifs (a1 , minimal) et (aN , maximal).
    Déterminer la valeur moyenne M0 = (a1 + a2 + ... + aN)/N ... à des fins plus lointaines.

    2°) Déterminer les (N) écarts angulaires séparant les points consécutifs disposés sur le cercle, en calculant:
    # pour (0 < i < N): bi = ai + 1 - ai ;
    # pour (i = N): bN = a1 - aN + 2*Pi .
    Étant donné un seuil minimal (bmin) inférieur à la limite (bmax = 2*Pi/N), ranger les valeurs obtenues dans deux listes séparées, selon que le résultat vérifie:
    a) bi < bmin _ _ _ _ _ _ _ _ _ _ (liste L1 , effectif = N1);
    b) bmin <= bi _ _ _ _ _ _ _ _ _ (liste L2 , effectif = N2 = N - N1);
    et calculer les sommes correspondantes (S1, S2), qui doivent vérifier: S1 + S2 = 2*Pi = 360° .

    3°) Attribuer la valeur (bmin) aux (N1) termes de la première liste, dont la somme passe à (S'1 = N1*bmin > S1). La compensation s'effectue nécessairement sur ceux de la deuxième liste.
    On a en effet: 2*Pi = S1 + S2 = S'1 + S'2 , d'où: S'2 = S2 + S1 - N1*bmin < S2 .

    4°) Chacun des termes de cette dernière liste peut s'écrire sous la forme:
    bk = bmin + bk - bmin = bmin + tk ;
    soit (T) la somme des (N2) termes complémentaires: T = (t1 + t2 + ... + tN) ;
    Il vient: S2 = N2*bmin + T .

    5°) On peut désormais envisager d'attribuer aux termes de la seconde liste les nouvelles valeurs:
    b'k = bmin + t'k qui ne passent jamais en-dessous du seuil souhaité (bmin) ; en notant pareillement (T') la somme des termes complémentaires:
    T' = (t'1 + t'2 + ... + t'N) ,
    et l'on obtient: S'2 = N2*bmin + T' .

    La conservation de la somme totale: S1 + S2 = S'1 + S'2 devient, compte tenu des conventions précédentes:
    S1 +N2*bmin + T = N1*bmin + N2*bmin + T' , ce qui entraîne:
    T' = T + S1 - N1*bmin = T - (N1*bmin - S1) < T .

    Il suffit donc à ce stade d'introduire le rapport inférieur à l'unité:
    R = T'/T = 1 - (N1*bmin - S1)/T
    pour accéder aux valeurs corrigées de la seconde liste:
    b'k = bmin + R*tk , qui restent supérieures à la limite (bmin) .

    6°) Le premier point restant fixe (a1 inchangé), les valeurs nouvelles des autres angles (a'i) s'obtiennent par la somme cumulée des écarts:
    a2 = a1 + b1 , ... , ak + 1 = ak + bk , ... etc.
    Pour les quelques points qui auraient la malice de franchir la frontière (A), il suffirait de retrancher (2*Pi).

    Cerise bien méritée sur le gâteau: en recalculant la valeur de l'angle moyen
    (M2 = (a1 + a'2 + ... + a'N)/N ... ), on peut procéder à un réajustement de l'ensemble par une diminution de tous les angles de (M2 - M1).

    # Il est probable qu'à la suite de ces deux opérations, (P1) ne représente plus le premier terme de la liste, défini par un angle (ai) minimal; il faudra donc procéder à une permutation appropriée.

    Il reste sans doute quelques détails, mais je dois m'arrêter.

    Pas d'ironie facile sur d'éventuelles fautes de frappes, svp. Merci.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  9. #9
    Candidat au Club
    Homme Profil pro
    Développeur Web
    Inscrit en
    janvier 2018
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 24
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : janvier 2018
    Messages : 4
    Points : 3
    Points
    3

    Par défaut

    Merci wiwaxia, je vais regarder ça plus attentivement.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Répartition de points sur une ligne
    Par travonz dans le forum Mathématiques
    Réponses: 3
    Dernier message: 29/01/2013, 23h09
  2. [Google Maps] Point sur un cercle autour d'un point
    Par maitrebn dans le forum APIs Google
    Réponses: 3
    Dernier message: 27/02/2012, 20h11
  3. [Débutant] Répartition de points sur une droite
    Par elirgume dans le forum MATLAB
    Réponses: 1
    Dernier message: 29/04/2011, 17h10
  4. Un point sur un cercle
    Par Speed41 dans le forum Langage
    Réponses: 8
    Dernier message: 10/09/2007, 19h56
  5. Calcul rayon d'une ellipse (distance centre-point sur cercle)
    Par aristeas dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 19/01/2007, 11h37

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo