Intersections de splines

Version imprimable

11/09/2017, 02h04
guitz

Intersections de splines

Bonjour,

Dans le cadre du développement de mon city builder je suis confronté à la problématique de ne pas construire de route au dessus de routes existantes (sans parler d'intersection).

Soient A l'union de splines existantes (les routes qui ont déja été créées) et B la spline en cours de prévisualisation (un premier clic définit le premier point, un second clic le point tangente et des mouvement de souris déplacent le dernier point permettant de visualiser la spline avant validation, cliquer une derniere fois valide le dernier point et donc la spline)

subdiviser chaque spline de A et la spline de B en segments n'étaient pas couteux algorithmiquement grâce à l'algo de de Casteljau (à condition d'avoir un nombre d'itérations raisonnables), mais là où ça devient très couteux cest quand il s'agit de vérifier si B peut être validé, donc si B n'est pas en intersection avec A. Puisque :

40 fois par secondes( B est en prévisualisation, donc chaque mouvement de souris, modifient l'apparence de la spline), il ya 3 boucles emboitées :

Pour tous segments s2 de B -> pour toutes splines de A -> pour tous segments s1 de A (sachant qu'une spline peut contenir une trentaine de segments, donc imaginez si A contient 500 splines...), si s1 est en intersection avec s2 on sort de la fonction en renvoyant false, et B ne peut être validé.

Je me penche alors vers la solution qui consiste à faire une intersection de chaque spline validée avec une grille 2D (par exemple 5000 x 5000).
toutes les splines de A ont été snappée précédemment avec un certain pas, sur la grille. Au moment de prévisualiser B je récupère les indices i et j de chaque points xi ([xi xi+1] mesure un certain pas) de la spline qui correspondent à un snap sur la grille, et si Grid[i][j]->IsOccupied = true, je ne valide pas B.

Cet algo semble bien moins couteux que le précédent, mais y a-t'il mieux svp ?
11/09/2017, 12h05
dourouc05

:salut:

J'aurais en tête une approche plus analytique : déterminer la forme polynomiale de chacune de ces courbes, puis chercher une solution au système d'équations non linéaire (méthode de Newton, par exemple — les calculs de jacobiennes devraient être assez faciles).

Ensuite, tu peux probablement implémenter un filtre sur les segments que tu considères : s'il n'y a aucune chance qu'il y ait une intersection, alors inutile de perdre son temps en des calculs lourds. Par exemple, tu pourrais déterminer un triangle dans lequel ta courbe est contenue (parallèle à la tangente à la courbe au niveau des deux extrémités du segment), pour chaque segment, puis vérifier si les triangles des routes existantes et de la nouvelle route ont une intersection
11/09/2017, 12h32
guitz

Merci Dourouc05.

Bien vu pour les triangles englobants.
Je vais comparer nos 2 méthodes et garder la moins couteuse

Un bon informaticien est un flemmard et un radin
11/09/2017, 15h11
dourouc05

Petite trouvaille : si tu passes à des "combinaisons linéaires de cerces positives à support compact minimal" (B-spline), tu pourrais utiliser http://www.sciencedirect.com/science...783968590024X/ (n'oublie pas SciHub ;)).

http://cagd.cs.byu.edu/~557/text/ch7.pdf pourrait aussi être utile.
11/09/2017, 15h40
guitz

Ton second pdf a l'air très utile :ccool:

Toutefois à vue de nez ça m'a l'air quand même plus couteux que la méthode de la grille, mais peut être que je me trompe. Je vais faire tourner ces 2 algos et les comparer
11/09/2017, 17h43
anapurna

salut

l'utilité de tout recalculer me parait un peu folle
tu ne doit recalculer que la partie modifiée sous le curseur le reste ne bouge pas
11/09/2017, 21h12
guitz

1 pièce(s) jointe(s)

Salut,

Dans mon algo foireux d'intersection de segments de splines, je ne calcule pas en temps réel à chaque fois les segments de A, ils sont calculés en amont à chaque fois qu'une nouvelle spline est validée. Mais même ainsi mon algo rame la mort.

Finalement je vais laisser tomber la grille provisoirement et me pencher sur la solution plus élégante (mais au combien plus compliquée) de dourouc05. Mais j'ai amélioré l'idée en ne calculant le chevauchement avec les splines du plus proche au moins proche de B. Donc à chaque fois que le premier point de B est choisi (avant la prévisualisation puisque la tangente n'est pas encore définie) je fais un tri du tableau qui contient toutes les splines de A de la plus proche à la moins proche. Vu que la proba qu'une spline chevauche une autre spline est plus importante avec une spline voisine, ça évite bien des calculs inutiles.
Si cet algo me pose trop de pbs et/ou est impossible à assez bien optimiser je rebasculerai sur la matrice de booléens.

Edit :

Pièce jointe 310998

Chaque spline de A (routes déja présentes ) stocke son propre baricentre (segment noir vertical). Je vais calculer le chevauchement ou non de B (route en cours de prévisualisation en vert) avec la spline de A dont le baricentre est le plus proche au plus lointain
12/09/2017, 10h45
anapurna

salut

ton problème fait penser furieusement aux théorie de collision dans les jeux video
regarde ce lien il peut t’intéresser
12/09/2017, 11h03
guitz

Merci beaucoup anapurna :ccool:
13/09/2017, 15h38
Nebulix

Pour afficher la nouvelle spline, il faut affecter une couleur à un pixel. Il n'est pas beaucoup plus couteux de lire avant la couleur du pixel pour voir s'il appartient à une route ou au fond.
16/09/2017, 22h12
guitz

1 pièce(s) jointe(s)

Merci pour ton conseil Nebulix, mais jignore si c'est faisable sur Unreal Engine. Si mon algo montre ses limites je me pencherai sur ta solution.

Mais pour le moment avec une seule itération de subdivision de triangles box (algo de Casteljau) c'est parfaitement fluide (le fait de calculer un éventuel chevauchement avec la spline de la plus proche à la plus lointaine aidant puisque ça évite bien souvent des calculs inutiles.

Pièce jointe 312310

Les 2 triangles dans le grands sont une subdivision d'itération i = 1.
L'algo est pas parfait puisque dans la spline de prévisualisation (en vert) le point commun des 2 triangles est décalé de la spline. Mais bon pour le moment j'ai que l'algo de Casteljau à disposition.

Je vais voir ce que ça donne à itérer jusqu'à i = 3
25/09/2017, 00h29
guitz

1 pièce(s) jointe(s)

Bonjour,

l'itération jusqu'à i = 3 se passe bien, cet algo a l'air pas mal optimisé pour le moment je laisse en l'état. Je peux donc détecter si une spline chevauche une autre et interdire ou non la construction d'une route. A présent je dois gérer la possibilité de créer une route qui rejoins une autre pour obtenir un carrefour.

Soient A la route existante et B la route en cours de prévisualisation. A et B sont courbes. Si B chevauche A je suis sensé interdire la validation de B sauf que si la souris est suffisemment proche de de la spline de A alors B est validéé et un carrefour est créé.

Pièce jointe 314077

Que B chevauche A ou non, si la souris est dans le triangle T englobant la totalité de la spline de A ainsi que l'épaisseur de la route ( triangle T en mémoire mais pas sur l'image), alors il peut y avoir carrefour. Etape suivante de l'algo : trouver le point p sur la spline de A le plus proche de la souris et mesurer la distance d entre cette dernière et p. Si d < tolérance, alors on valide le tracé de B et le carrefour.

Quel algo peu couteux (car appelé 40 fois par secondes) svp permet de trouver le point d'une spline à distance minimale d'un point quelconque ?
25/09/2017, 11h04
wiwaxia

Intersections de splines

Bonjour, :)

Citation:

Envoyé par guitz

... Quel algo peu couteux (car appelé 40 fois par secondes) svp permet de trouver le point d'une spline à distance minimale d'un point quelconque ?

La spline (S_A) étant paramétrée par une variable (t) du domaine [0 ; 1], la recherche de son point (A) le plus proche d'un centre (C) relève de la localisation progressive du minimum de la fonction h = AC² = F_(t) = (X_A(t) - X_C)² + (Y_A(t) - Y_C)² .

Partir pour cela de l'intervalle initial I₀ = [t_min ; t_max], que l'on partage en (N = 10) sous-domaines, de largeur Delta₀ = (t_max - t_min) / N = (1 - 0)/10 = 0.1 ;

# calculer la suite des (N + 1) termes h_k = F(k*Delta₀) pour (k) variant de (0) à (N), et repérer la plus faible h_m , ainsi que l'indice (m₀) et l'argument correspondants (t₀ = m₀ * Delta₀ = m₀ / N) ;

# passer à la nouvelle suite de (2*N + 1) termes h_k = F(t₀ + k*Delta₁) pour (k) variant désormais de (-N) à (+N), et une largeur (N) fois plus faible Delta₁ = Delta₀ / N ;
le nouveau domaine exploré est ainsi borné par les valeurs: (t_min = t₀ - N*Delta₁ = t₀ - Delta₀ , t_max = t₀ + N*Delta₁ = t₀ + Delta₀);
repérer le nouveau minimum (h_m), ainsi que son indice (m₁) et son nouvel argument (t₁ = t₀ + m₁ * Delta₁ = t₀ + m₁ / N²) ;

# reprendre le processus précédent, jusqu'à parvenir à la précision nécessaire Delta_j = Delta₀ / N^(j) = 1 / 10^(j+1) .
Six ou huit étapes devraient suffire; cela dépend évidemment de la précision attendue.

On peut aussi, par un procédé analogue, repérer le zéro de l'expression des différences successives:
g_ik = F(t_i-1 + (k+0.5)*Delta_i) - F(t_i-1 + (k-0.5)*Delta_i) .

Je crains cependant que tout cela ne devienne très long, pour de très nombreuses recherches.
S'il faut comparer un grand nombre de splines à une nouvelle pour s'assurer de leur non-superposition, il paraît plus rentable de travailler sur la matrice de pixels correspondant au corps de l'image (la grille 2D ?), comme cela a déjà été dit.
25/09/2017, 11h45
wiwaxia

Intersections de splines

Si ton logiciel te permet de tracer chaque courbe sous la forme d'un ruban de largeur finie, il y a un moyen rapide de tester l'empiètement éventuel des (Ns) splines présentes avec une nouvelle.
# Sur le fond d'image initialement noir (couleur 000), tracer les (Ns) splines connues avec la même couleur (par ex. rouge m00), ce qui revient à imposer à chaque pixel du ruban la valeur (255, 0, 0) indépendamment de sa valeur précédente;
# Tracer la nouvelle spline en attribuant à tout pixel de son ruban une valeur dépendant de sa valeur actuelle:
noir (000) ---> bleu (00m) ou rouge (m00) ---> vert (0m0) .

Ainsi toute zone de chevauchement se signalera par la plus brillante coloration (vert).
Le test visuel est suffisamment sensible pour dispenser de tout algorithme de vérification.

Cela implique un contrôle local de la couleur qui ne va peut-être pas de soi. Peut-on envisager par exemple un tracé en semi-transparence, qui préserverait la mémoire de la couleur antérieure ? Cela permettrait de retrouver les zones de chevauchement dans l'image finale.

PS: Nebulix proposait un moyen apparenté (#10)
25/09/2017, 11h56
guitz

Citation:

Envoyé par wiwaxia

Je crains cependant que tout cela ne devienne très long, pour de très nombreuses recherches.
S'il faut comparer un grand nombre de splines à une nouvelle pour s'assurer de leur non-superposition, il paraît plus rentable de travailler sur la matrice de pixels correspondant au corps de l'image (la grille 2D ?), comme cela a déjà été dit.

Merci wiwaxia pour ta réponse.

Pas de besoin d'effectuer ce calcul pour toutes les splines. En effet toutes les splines déjà validées ont un triangle englobant Ti (en mémoire, pas sur l'image) qui englobe la spline Ai et aussi l'épaisseur de route.

1. Si la souris est dans l'un des Ti ET que un chevauchement de la spline B a été détecté sur Aj (avec j != i) on ne valide pas B
2. Si la la souris est dans l'un des Ti ET (que un chevauchement de la spline B a été détecté sur Ai OU aucun chevauchement n'a été detecté avec tous les Ai (pour 1 allant de 1 à nombre de spline validées)), alors on utilise éventuellement ton algo pour voir si la souris est suffisamment proche de la spline Ai pour valider ou non un carrefour

Donc ton algo serait appliqué que sur une seule spline.

Je vais tester ton algo

Edit : malheureusement ce n'est pas possible ta solution avec la superposition de couleurs de pixels sur UE4
25/09/2017, 14h54
wiwaxia

1 pièce(s) jointe(s)

Intersections de splines
Citation:

Envoyé par guitz

... Pas de besoin d'effectuer ce calcul pour toutes les splines ...
Donc ton algo serait appliqué que sur une seule spline ...

Bonne nouvelle, donc: le procédé est envisageable.

Le nombre d'étapes dépend de la précision du type des flottants en cause.
Comme il s'agit sans doute de splines d'ordre 3 (ou 4, tout au plus), les sinuosités de la courbe sont relativement douces, comme les variations locales des grandeurs qui leur sont attachées (coordonnées, courbures, distances).
On ne trouvera donc pas de fantaisie brutale au mauvais endroit (du genre de celle représentée ci-dessous):

Pièce jointe 314192

En conséquence, il ne sera pas nécessaire de poursuivre au-delà de la seconde étape (j_final = 1) si l'on trouve D²_min >~ 1.5 * L_route .

Les instructions données n'excluent pas une recherche de la racine hors de l'intervalle [0 ; 1]; cela ne présente pas d'inconvénient calculatoire dans la mesure où interviennent des polynômes, donc des fonctions dépourvues de singularité aux frontières du domaine; le débordement est de plus limité: (0.888...) < t < (1.111...) .
On peut insérer des critères d'arrêt du type:
Code:

1 2 3 IF (tmax < 0) THEN tlim:= 0 IF (tmin > 1) THEN tlim:= 1 // instructions à traduire et compléter
déplacer l'une des bornes du nouveau domaine ou terminer le procédé initial par les corrections:
Code:

1 2 3 IF (tlim < 0) THEN tlim:= 0 IF (tlim > 1) THEN tlim:= 1
27/09/2017, 00h18
guitz

1 pièce(s) jointe(s)

wiwaxia, je me suis trompé.

Il se peut que la souris soit dans plusieurs triangles englobant (qui incluent l'épaisseur de route). Donc l'algo de minimisation de distance entre souris et spline va concerner plusieurs spline. Ta technique itérative qui fait une partition de [0, 1] serait alors peut être trop couteuse ( comme tu l'as redouté). Je garde ta technique sous le coude mais je vais tenter d'abord cet essai.

Autre chose, ma spline est quadratique (d'ordre 2), car elle a 3 points de contrôle (les 2 points + la tangente). Je sais pas si ça peut t'aider

Pièce jointe 314739

Soient P le point de la souris, S(tmin) le point sur la spline, tel que S(tmin) = min({ pour tous t appartenant à [0,1], norme(P-S(t)) tq (P - S(t)).T(t) = 0 } . T(t) étant bien entendu la tangente.

J'aimerais trouver l'algo qui va trouver dans un nombre minimale d'itérations, 2 t successifs, où le produit scalaire change de signe, afin de trouver un sous ensemble de [0,1] le plus plus petit possible, qui contient tmin.

Intuitivement j'aurais envie de tester :

t=0
t=0.5
si pas changement de signe alors tmin est dans [0.5, 1]
t=0.75
t=1
si pas changement de signe alors tmin est dans [0.5, 0.75]

etc...

Pensez vous qu'on peut optimiser le balayage ?
27/09/2017, 08h10
wiwaxia

1 pièce(s) jointe(s)

Intersections de splines

J'avais bien songé à la recherche du zéro de la dérivée, mais la lourdeur des calculs (relatifs à des splines supposées d'ordre 3, que suggéraient les dessins) m'en avaient dissuadé.

Tu as trouvé par intuition une solution géométrique, qui correspond effectivement au minimum du carré de la distance; on a en effet:

D² = PS² = PS│PS (produit scalaire du vecteur par lui-même), d'où par dérivation:

(d/dt)D² = (d/dt)(PS│PS) = 2*(PS│(d/dt)PS) = 2*(PS│ST) , en notant (ST) le vecteur tangent en (S) à la spline orientée par le paramètre (t).

Le minimum de la distance est bien caractérisé par l'orthogonalité des deux vecteurs, (d/dt)D² = 0 impliquant PS│ST = 0 .

Pièce jointe 314783

Passons au cas particulier d'une courbe du second ordre: en notant (K₀, K₁, K₂) les points de contrôle, il vient (citation de mémoire, tu corrigeras les éventuelles incorrections):

OS = (1 - t)².0K₀ + 2*t*(1 - t).0K₁ + t².0K₂ , d'où:

(d/dt)OS = -2*(1 - t).0K₀ + 2*(1 - 2*t).0K₁ + 2*t.0K₂ = ST , ainsi que l'expresion du produit scalaire:
F(t) = PS│ST = -2*(1 - t)*(PS│0K₀) + 2*(1 - 2*t)*(PS│0K₁) + 2*t*(PS│0K₂) .

Il suffit donc de repérer le plus petit intervalle aux extrémités duquel la fonction change de signe, et vérifiant par conséquent: F(t_j)*F(t_j+1) < 0 .

Ce que tu as suggéré

Citation:

... Intuitivement j'aurais envie de tester :
t=0
t=0.5
si pas changement de signe alors tmin est dans [0.5, 1]
t=0.75
t=1
si pas changement de signe alors tmin est dans [0.5, 0.75]

etc ...

correspond à la recherche classique d'une racine par dichotomie.

Une division par 10 du domaine initial [0 ; 1], systématiquement reprise pour les nouveaux intervalles jusqu'à la précision attendue (DeltaT = 10^-8 ?) serait peut-être plus rapide.

PS: les signes mentionnés sur la figure sont à inverser à cause du choix de mes vecteurs, mais c'est tout à fait secondaire.
02/10/2017, 12h25
guitz

Merci wiwaxia, et toutes mes escuses car cette fonction est en fait native dans UE4. Je n'ai pas pensé à regarder car je doutais qu'elle y soit.

Mais notre algo servira quand même à d'autres
03/10/2017, 13h56
henderson

Salut !

Mon intervention va paraître de trop ici, mais as-tu pensé à développer une interface pour le design du décor (réseau routier, bâtiments etc...).
Auquel cas, il suffit de travailler en fil de fer, vue de dessus sans jamais être ennuyé par les procédures graphiques qui sont toujours très lourdes.
Cela permet aussi à l'aide de quelques fonctionnalités très simples de repositionner les objets et donc de remodeler à souhait ce qui peut et doit l'être.

La détection des intersections relève plus de l'urbanisation par la machine (au quel cas c'est indispensable) et moins pour un urbaniste humain.

Pour info, j'utilise la fonction sinusoïdale pour tracer mes courbes.
Il suffit pour cela d'associer au segment AB un handle (comme on le ferait pour une courbe de Bezier) pour en fixer l'amplitude, le signe (localement convexe ou concave) et la symétrie (courbe d'apparence exotique)!
Donc tout ça se fait facilement à vue !

On passe toujours du temps à développer mais on peut en passer beaucoup plus à en utiliser le résultat !
Donc autant ajouter quelque chose qui va simplifier l'usage (pour toi comme pour tout autre utilisateur)!

Bonne urbanisation !
07/10/2017, 14h04
guitz

Citation:

Envoyé par henderson

Salut !

Mon intervention va paraître de trop ici, mais as-tu pensé à développer une interface pour le design du décor (réseau routier, bâtiments etc...).
Auquel cas, il suffit de travailler en fil de fer, vue de dessus sans jamais être ennuyé par les procédures graphiques qui sont toujours très lourdes.
Cela permet aussi à l'aide de quelques fonctionnalités très simples de repositionner les objets et donc de remodeler à souhait ce qui peut et doit l'être.

Bonjour,

Jusqu'à présent je n'ai travaillé qu'en "fil de fer", les objets mathématiques de chaque segment du graphe sont des splines. Ensuite l'affichage se fait dans une autre classe.

Citation:

Envoyé par henderson

La détection des intersections relève plus de l'urbanisation par la machine (au quel cas c'est indispensable) et moins pour un urbaniste humain.

Je ne comprends pas.

Citation:

Envoyé par henderson

Pour info, j'utilise la fonction sinusoïdale pour tracer mes courbes.
Il suffit pour cela d'associer au segment AB un handle (comme on le ferait pour une courbe de Bezier) pour en fixer l'amplitude, le signe (localement convexe ou concave) et la symétrie (courbe d'apparence exotique)!
Donc tout ça se fait facilement à vue !

Les splines quadratiques offrent beaucoup plus de possibilités que la fonction sinusoidale

Merci pour ton post henderson
08/10/2017, 12h37
wiwaxia

Intersections de splines

Citation:

Envoyé par guitz

... Les splines quadratiques offrent beaucoup plus de possibilités que la fonction sinusoidale ...

Tout dépend, comme pour les courbes de Bézier, du lot de fonctions que l'on se donne au départ (il en faudra certainement plusieurs !) ... mais c'est sûrement plus compliqué à mettre en oeuvre, et beaucoup plus lourd en calculs.
Le splines présentent effectivement, vis-à-vis des contraintes imposées, une souplesse incomparable en raison de leur simplicité.

Il se pourrait toutefois que le recours aux fonctions sinusoïdales s'avère avantageux dans certains cas particuliers ... Mais là je sors franchement du sujet .
08/10/2017, 15h23
henderson

Salut !

Citation:

Envoyé par wiwaxia

...
Il se pourrait toutefois que le recours aux fonctions sinusoïdales s'avère avantageux dans certains cas particuliers ... Mais là je sors franchement du sujet .

A ce stade, c'est juste pour me simplifier la vie au niveau de la mise en place du réseau routier avec des courbes sinusoïdales sporadiques : amplitude et symétrie modifiable grâce à un point de contrôle qui se dessine toujours sur la courbe elle-même (en pi/2 quelque soit le rapport de symétrie).
En tant qu'urbaniste, je suis à même de voir par moi-même si mon tracé intercepte ou non autre chose !
J'ai donc tendance à modeler visuellement (comme je l'ai toujours fait en imagerie 3D y compris sur SoftImage dès 1990) !
Ici c'est une question de moyen que l'on peut se donner pour attendre l'objectif ... Donc à chacun ses trucs et astuces et surtout sa manière de modéliser (organisation des données et fonctionnalités de l'objet en C++) !

Par contre ma classe jCity ... comme elle génère un objet en expansion ... la machine a besoin d'algorithmie parce qu'elle ... est aveugle !!!
Cette discussion est donc de ce point de vue très intéressante !
Et c'est pour cette raison que je ne vais pas insister d'avantage !

A plus !

Bonjour,

Bon alors j'ai pas réussi à implémenter cette résolution d'un polynôme de degré 4, du coup je me suis rabattu sur la méthode par dichotomie. C'est moins bien optimisé mais dans mon projet ce n'est pas grave car ce code n'est pas appelé x fois par secondes.

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
bool AInfrastructureGraphManager::DichotomyStep(FVector a0, FVector a1, FVector a2, FVector b0, FVector b1, FVector b2) {
 
 
 
	if (CollisionSegSeg(GetLocationAtDistanceAlongSpline(a0, a1, a2, MinS), GetLocationAtDistanceAlongSpline(a0, a1, a2, (MinS + MaxS) / 2), GetLocationAtDistanceAlongSpline(b0, b1, b2, MinT), GetLocationAtDistanceAlongSpline(b0, b1, b2, (MinT + MaxT) / 2)) == true) {
 
		MaxS = (MinS + MaxS) / 2;
		MaxT = (MinT + MaxT) / 2;
 
		return true;
	}
 
	if (CollisionSegSeg(GetLocationAtDistanceAlongSpline(a0, a1, a2, (MinS + MaxS) / 2), GetLocationAtDistanceAlongSpline(a0, a1, a2, MaxS), GetLocationAtDistanceAlongSpline(b0, b1, b2, MinT), GetLocationAtDistanceAlongSpline(b0, b1, b2, (MinT + MaxT) / 2)) == true) {
 
		MinS = (MinS + MaxS) / 2;
		MaxT = (MinT + MaxT) / 2;
 
		return true;
	}
 
 
	if (CollisionSegSeg(GetLocationAtDistanceAlongSpline(a0, a1, a2, MinS), GetLocationAtDistanceAlongSpline(a0, a1, a2, (MinS + MaxS) / 2), GetLocationAtDistanceAlongSpline(b0, b1, b2, (MinT + MaxT) / 2), GetLocationAtDistanceAlongSpline(b0, b1, b2, MaxT)) == true) {
 
		MaxS = (MinS + MaxS) / 2;
		MinT = (MinT + MaxT) / 2;
 
		return true;
	}
 
	if (CollisionSegSeg(GetLocationAtDistanceAlongSpline(a0, a1, a2, (MinS + MaxS) / 2), GetLocationAtDistanceAlongSpline(a0, a1, a2, MaxS), GetLocationAtDistanceAlongSpline(b0, b1, b2, (MinT + MaxT) / 2), GetLocationAtDistanceAlongSpline(b0, b1, b2, MaxT)) == true) {
 
		MinS = (MinS + MaxS) / 2;
		MinT = (MinT + MaxT) / 2;
 
		return true;
	}
 
	return false;
 
}
 
 
FVector AInfrastructureGraphManager::GetLocationAtDistanceAlongSpline(FVector PointA, FVector PointB, FVector PointC, float s) {
 
	float l_X = (1 - s)*(1 - s)*PointA.X + 2 * s*(1 - s)*PointC.X + s*s*PointB.X;
	float l_Y = (1 - s)*(1 - s)*PointA.Y + 2 * s*(1 - s)*PointC.Y + s*s*PointB.Y;
 
	return FVector(l_X, l_Y, 0.f);
 
}
 
 
FVector AInfrastructureGraphManager::GetSplinesIntersection(FVector a0, FVector a1, FVector a2, FVector b0, FVector b1, FVector b2) {
 
	float l_epsilon = 0.01; //plus il est petit plus c'est précis mais couteux et inversement. 
							//TODO à optimiser et rendre proportionnel à la longueur de la spline la plus longue
	bool l_bool = true;
 
	MinS = 0; MaxS = 1; MinT = 0; MaxT = 1;
 
	while (MaxS - MinS > l_epsilon && l_bool == true) {
 
		l_bool = DichotomyStep(a0, a1, a2, b0, b1, b2);
 
	}
 
	return GetLocationAtDistanceAlongSpline(a0, a1, a2, (MinS + MaxS) / 2.0);
 
}