Canvas détecter le croisement de deux droites

Version imprimable

17/05/2019, 16h08
PhilLU

Canvas détecter le croisement de deux droites

Bonjour,
Je dois tracer une route aléatoire entre plusieurs points.
Je cherche à détecter un croisement éventuel pour pouvoir rejeter cette route.
J'utilise Canvas et des coordonnés x,y bien sûr associées à chaque point.
Autre détail, la route revient à son point de départ.
Merci pour vos idées...
;)
PhilLu
17/05/2019, 17h27
BeanzMaster

Bonjour un petit tour vers les maths et la géométrie devrait te permettre de trouver le point d'intersection de deux lignes

https://en.wikipedia.org/wiki/Line–line_intersection
http://mathworld.wolfram.com/Line-LineIntersection.html
https://martin-thoma.com/how-to-chec...nts-intersect/

A+

[EDIT] Je viens de trouver ca en Delphi : http://www.delphipages.com/tip/test_...ion-10800.html et https://stackoverflow.com/questions/...code-in-pascal

Bonjour,

tu veux tester l'intersection de 2 segments ou de 2 droites ? si c'est 2 droites, c'est plus simple (tester la pente des 2 droites)

Sinon ce code tiré de SwissDelphiCenter teste l'intersection de 2 segments :

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
function Intersect(const x1, y1, x2, y2, x3, y3, x4, y4: Double): Boolean;
var
  UpperX: Double;
  UpperY: Double;
  LowerX: Double;
  LowerY: Double;
  Ax: Double;
  Bx: Double;
  Cx: Double;
  Ay: Double;
  By: Double;
  Cy: Double;
  D: Double;
  F: Double;
  E: Double;
begin
  Result := False;
 
  Ax := x2 - x1;
  Bx := x3 - x4;
 
  if Ax < 0.0 then
  begin
    LowerX := x2;
    UpperX := x1;
  end
  else
  begin
    UpperX := x2;
    LowerX := x1;
  end;
 
  if Bx > 0.0 then
  begin
    if (UpperX < x4) or (x3 < LowerX) then
      Exit;
  end
  else if (Upperx < x3) or (x4 < LowerX) then
    Exit;
 
  Ay := y2 - y1;
  By := y3 - y4;
 
  if Ay < 0.0 then
  begin
    LowerY := y2;
    UpperY := y1;
  end
  else
  begin
    UpperY := y2;
    LowerY := y1;
  end;
 
  if By > 0.0 then
  begin
    if (UpperY < y4) or (y3 < LowerY) then
      Exit;
  end
  else if (UpperY < y3) or (y4 < LowerY) then
    Exit;
 
  Cx := x1 - x3;
  Cy := y1 - y3;
  d  := (By * Cx) - (Bx * Cy);
  f  := (Ay * Bx) - (Ax * By);
 
  if f > 0.0 then
  begin
    if (d < 0.0) or (d > f) then
      Exit;
  end
  else if (d > 0.0) or (d < f) then
    Exit;
 
  e := (Ax * Cy) - (Ay * Cx);
 
  if f > 0.0 then
  begin
    if (e < 0.0) or (e > f) then
      Exit;
  end
  else if (e > 0.0) or (e < f) then
    Exit;
 
  Result := True;
 
(*
 
  Simple method, yet not so accurate for certain situations and a little more
  inefficient (roughly 19.5%).
  Result := (
  ((Orientation(x1,y1, x2,y2, x3,y3) * Orientation(x1,y1, x2,y2, x4,y4)) <= 0) and
  ((Orientation(x3,y3, x4,y4, x1,y1) * Orientation(x3,y3, x4,y4, x2,y2)) <= 0)
  );
*)
end;
(* End of SegmentIntersect *)

Lien original

A+
Charly

J'ai retrouvé cela dans mes archives

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
  TDPoint = record
    X,Y : Double ;
  end ;
 
function CalculeIntersec (P1,P2,P3,P4 : TDPoint; var X,Y : Double ) : boolean ;
var
  a1,a2,b1,b2 : Double ;
begin
  Result := false ;
  if ((P1.x-P2.x)=0) or ((P3.x-P4.x)=0) then
    exit ;
  a1 := (P1.y-P2.y)/(P1.x-P2.x) ;
  b1 := P1.y - (P1.x * a1)  ;
  a2 := (P3.y-P4.y)/(P3.x-P4.x) ;
  b2 := P3.y - (P3.x * a2) ;
  if a1=a2 then exit ;
  x := (b2-b1)/(a1-a2) ;
  y := a1*x + b1 ;
  Result := true ;
end ;

18/05/2019, 10h16
Charly910

Bonjour,

@ALWEBER : cela donne l'intersection des droites portant les segments P1P2 et P3P4. Mais cela ne dit pas si l'intersection se fait sur les segments ou en dehors.

A+
Charly
19/05/2019, 14h07
Charly910

1 pièce(s) jointe(s)

Bonjour,

j'ai un peu modifié le code d'ALWEBER, car il ne traitait pas le cas ou l'un des 2 segments était vertical. Le petit logiciel joint donne aussi la position de l'intersection par rapport aux 2 segments.

Pièce jointe 476239

A+
Charly
19/05/2019, 17h07
ALWEBER

Citation:

Envoyé par Charly910

Bonjour,

j'ai un peu modifié le code d'ALWEBER, car il ne traitait pas le cas ou l'un des 2 segments était vertical. Le petit logiciel joint donne aussi la position de l'intersection par rapport aux 2 segments.
...

merci
20/05/2019, 11h49
Charly910

1 pièce(s) jointe(s)

Arghh ! Bug sur la détermination de la position du point d'intersection par rapport à P1P2 ou P3P3 (bug si un des segments est vertical !). Voici une version corrigée avec une autre méthode utilisant les produits scalaires :

Pièce jointe 476466

A+
Charly
26/05/2019, 16h33
BeanzMaster

2 pièce(s) jointe(s)

Salut,

vu que le sujet m'intéresse et que j'ai besoin de ce genre de chose dans un de mes projets.
Avec Lazarus, j'ai réalisé une petite application de test sur la manipulation et l'application des formules mathématiques de lignes 2D dans un repère cartésien.
Cette application n'est qu'une ébauche et c''est encore à peaufiner.

La conversion vers Delphi ne devrait pas poser de problème majeur.

Je mets le code à disposition ici, en attendant d' améliorer encore un peu la classe "TLine2D" et d'uploader cette exemple dans les "Téléchargements" de DVP

L'exécutable en 64bits de l'application pour Windows est également présent afin de pouvoir tester.

Pièce jointe 478136

Si vous avez des suggestions n'hésitez pas ;)

Pièce jointe 478132

Bon dimanche

A+