Répartition lissée de points sur un cercle

Version imprimable

30/09/2018, 16h24
giorgioarmanix

3 pièce(s) jointe(s)

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 :

Pièce jointe 416143

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 :

Pièce jointe 416147

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°).

Pièce jointe 416149

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.
30/09/2018, 17h11
Flodelarab
Bonjour :coucou:

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.
30/09/2018, 17h17
wiwaxia

Répartition lissée de points sur un cercle

Bonjour, :D

Une solution consisterait à

1°) Lister les (N) points selon l'ordre croissant de leur angle polaire (a₁, a₂, ... , a_k, ... , a_N) ,
puis déterminer la moyenne correspondante M₀ = (a₁ + a₂ + ... + a_N)/N .

2°) Déterminer les (N - 1) écarts successifs (b₁ = a₂ - a₁ , ... , b_{N - 1} = a_N - a_{N - 1}) ;
à chaque fois que l'on trouve un écart (b_k = a_{k + 1} - a_k) inférieur au seuil convenu (b_min = 5° , par exemple), augmenter toutes les positions ultérieures (a_{k + 1} , a_{k + 2} , ... , a_N) de la quantité Da = b_min - b_k ;
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 M₁ = (a₁ + a'₂ + ... + a'_N)/N ;
diminuer tous les angles de la même quantité (M₁ - M₀): a"_k = a'_k - (M₁ - M₀) ;
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.
30/09/2018, 17h25
giorgioarmanix

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 :)

2 pièce(s) jointe(s)

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:

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 :

Pièce jointe 416171

Avec correction :

Pièce jointe 416174

Merci à vous et bonne continuation !

30/09/2018, 19h27
tbc92

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.
30/09/2018, 19h37
Invité

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)
01/10/2018, 11h44
wiwaxia

Les objections sont fondées, mais il ne faut pas pousser le bouchon trop loin ! :D

Citation:

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 (b_min) 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 (P₁P₂ ... P_N) 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 P₁ et P_N d'angles respectifs (a₁ , minimal) et (a_N , maximal).
Déterminer la valeur moyenne M₀ = (a₁ + a₂ + ... + a_N)/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): b_i = a_{i + 1} - a_i ;
# pour (i = N): b_N = a₁ - a_N + 2*Pi .
Étant donné un seuil minimal (b_min) inférieur à la limite (b_max = 2*Pi/N), ranger les valeurs obtenues dans deux listes séparées, selon que le résultat vérifie:
a) b_i < b_min _ _ _ _ _ _ _ _ _ _ (liste L1 , effectif = N1);
b) b_min <= b_i _ _ _ _ _ _ _ _ _ (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 (b_min) aux (N1) termes de la première liste, dont la somme passe à (S'1 = N1*b_min > 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*b_min < S2 .

4°) Chacun des termes de cette dernière liste peut s'écrire sous la forme:
b_k = b_min + b_k - b_min = b_min + t_k ;
soit (T) la somme des (N2) termes complémentaires: T = (t₁ + t₂ + ... + t_N) ;
Il vient: S2 = N2*b_min + T .

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

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

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

6°) Le premier point restant fixe (a₁ inchangé), les valeurs nouvelles des autres angles (a'_i) s'obtiennent par la somme cumulée des écarts:
a₂ = a₁ + b₁ , ... , a_{k + 1} = a_k + b_k , ... 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 = (a₁ + a'₂ + ... + 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, (P₁) ne représente plus le premier terme de la liste, défini par un angle (a_i) 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. :aie: Merci.
03/10/2018, 13h44
giorgioarmanix

Merci wiwaxia, je vais regarder ça plus attentivement.