Discussion :

[guitz]

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

[joel.drigo]

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.

[guitz]

Ok merci, lequels des 2 algo est le plus optimisé stp ? En entrée je n'aurai jamais plus de 16 * 4 = 64 points

[joel.drigo]

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(n²), 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).

[guitz]

C'est parfait , merci encore

[guitz]

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.

[Nebulix]

//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
}

Ne suffit-il pas de trouver le premier ? (qui serait le prochain point à inclure)

[guitz]

Je cherche un algo optimal de tri, que me conseillez vous svp ?

[wiwaxia]

Bonjour,

J'ai peut-être mal compris la demande, parce que les deux conditions requises (1 et 2) me paraissent inconciliables:

... Du coup quel algo de tri (de sorte que tous les points autres que l_Points[0] soit distribués de façon ordonnée du plus loin au plus rapproché en coordonnées polaires 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.

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.

[guitz]

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

[tbc92]

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.

[guitz]

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