Bonjour,
Connaissez vous svp un bon algo pour créer un polygone convexe qui englobe un tableau 2D quelconque de carrés (proprité IsVisible vaut aléatoirement false ou true) ?
Bonjour,
Connaissez vous svp un bon algo pour créer un polygone convexe qui englobe un tableau 2D quelconque de carrés (proprité IsVisible vaut aléatoirement false ou true) ?
Salut,
D'abord considérer les sommets des carrés qui sont sur la bordure extérieure (donc les sommets des carrés qui ne sont pas entourés de 8 carrés. Ensuite, par exemple, utiliser un parcours de Graham, ou une marche de Jarvis, pour la détermination de l'enveloppe convexe de ces sommets.
Ok merci, lequels des 2 algo est le plus optimisé stp ? En entrée je n'aurai jamais plus de 16 * 4 = 64 points
Avec n le nombre de points, et h le nombre de points dans l'enveloppe, Jarvis est en 0(nh), donc au pire en O(n2), alors que Graham est en O(n log n), pouvant descendre à O(n) si les points sont pré triés suivant une coordonnée (ou un angle).
Bonjour,
J'ai commencé à implémenter cet algo à la sauce Unreal Engine 4.
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are colinear // 1 --> Clockwise // 2 --> Counterclockwise int32 AInfrastructureGraphManager::GetOrientation(FVector p, FVector q, FVector r) { int32 val = (q.Y - p.Y) * (r.X - q.X) - (q.X - p.X) * (r.Y - q.Y); if (val == 0) return 0; // colinear return (val > 0) ? 1 : 2; // clock or counterclock wise } // A function used by library function qsort() to sort an array of // points with respect to the first point int32 AInfrastructureGraphManager::Compare(FVector p0, FVector p1, FVector p2) { // Find orientation int32 o = GetOrientation(p0, p1, p2); float a = (p2 - p0).Size(); float b = (p1 - p0).Size(); if (o == 0) return (a*a >= b*b) ? -1 : 1; return (o == 2) ? -1 : 1; } TArray<FVector> AInfrastructureGraphManager::GetConvexHull(TArray<FVector> Points) { TArray<FVector> l_Points; TArray<FVector> l_ConvexHull; int32 l_minYIndex = 0; l_Points.Append(Points); for (int32 i = 1; i < l_Points.Num(); i++) { if ((l_Points[i].Y < l_Points[l_minYIndex].Y) || (l_Points[i].Y == l_Points[l_minYIndex].Y && l_Points[i].X < l_Points[l_minYIndex].X)){ l_minYIndex = i; } } l_Points.Swap(0, l_minYIndex); l_ConvexHull.Add(l_Points[0]); for (int32 i = 1; i < l_Points.Num() - 1; i++) { //J'aimerais trier l_Points de sorte que Compare(l_Points[0], l_Points[i], l_Points[i+1])) vale 1, de sorte que tous les points autres que l_Points[0] soient distribués de façon ordonnées du plus loin au plus rapproché en coordonnées polaire dans le sens inverse des aiguilles d'une montre } return l_ConvexHull; }
C'est galère dans UE4 d'utiliser une librairie externe c++, donc je ne peux utiliser qsort(). Du coup quel algo de tri (de sorte que tous les points autres que l_Points[0] soit distribués de façon ordonnées du plus loin au plus rapproché en coordonnées polaire dans le sens inverse des aiguilles d'une montre) me conseillez vous svp ? Je souhaite qu'au final, en parcourant le tableau, Compare(l_Points[0], l_Points[i], l_Points[i+1])) renvoie toujours 1.
Ne suffit-il pas de trouver le premier ? (qui serait le prochain point à inclure)//J'aimerais trier l_Points de sorte que Compare(l_Points[0], l_Points[i], l_Points[i+1])) vale 1, de sorte que tous les points autres que l_Points[0] soient distribués de façon ordonnées du plus loin au plus rapproché en coordonnées polaire dans le sens inverse des aiguilles d'une montre
}
Je cherche un algo optimal de tri, que me conseillez vous svp ?
Bonjour,
J'ai peut-être mal compris la demande, parce que les deux conditions requises (1 et 2) me paraissent inconciliables:
Les points successifs définiraient une spirale s'enroulant autour de son centre sans le sens trigonométrique (Rho diminuant lorsque l'angle polaire augmente) - ce qui ne peut être le cas d'un ensemble quelconque de points.
Il faut choisir l'un ou l'autre: ordre décroissant des distances, ou disposition dans le sens trigonométrique.
Exemple (en se rapportant à vue d'oeuil au centre (P0): (3 4 5 1 2) ou (5 2 4 3 1).
L'ordre le plus "naturel" est celui des angles polaires, directement reliés au parcours de l'enveloppe dans le sens trigonométrique.
Salut wiwaxia,
En fait tu vas mieux comprendre ce que je veux obtenir si tu fais les Swap() suivants sur mon croquis bleu (ordre souhaité des P1, ... , Pn) :
Swap (P1,P5);
Swap (P3,P4);
La convexité est obtenue après ..
Sur le croquis bleu, les points PO à P5 sont déjà triés selon l'angle, en ordre trigonométrique inverse, si on considère que le centre est un point un peu en dessous à droite de P2.
Bonjour,
Les points sont aléatoires, le croquis est juste un exemple.
Je sais quel algo de tri utiliser pour par exemple une distance de la plus grande à la plus petite avec P0, mais quel algo utiliser de façon à ce que Compare(l_Points[0], l_Points[i], l_Points[i+1])) renvoie toujours 1 (voir croquis bleu) ?
Merci
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager