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.