Discussion :

[Drimeker]

Bonjour,

j'aurais voulu savoir s'il existait une commande prédéfinie dans Matlab permettant de trouver s'il existe une intersection entre deux segments donnés ?
(avec comme données à ma disposition : les coordonnées(x,y) des 4 points et bien entendu les deux segments existants)

Si une telle fonction n'existe pas, pourriez-vous m'aider si vous avez déjà eu ce problème et connaîtriez donc un algorithme pour calculer si oui ou non il y a intersection (le point d'intersection ne m'intéresse en rien, je souhaiterai juste une réponse booléenne).

Merci d'avance


Drim

[mihaispr]

Salut!

Ici une source sur FEX pour t'inspirer beaucoup:

http://www.mathworks.com/matlabcentr...exchange/17751



Ici des liens utiles pour toi (comme documentation):

http://www.mathleague.com/help/geometry/basicterms.htm

http://mathworld.wolfram.com/Line.html

Oui, il existe une fonction dedie en matlab pour l'intersection. Elle s'appelle intersect.

Par example pour 2 vecteurs:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
>> A = [1 2 3 6]; B = [1 2 3 4 6 10 20];
>> C=intersect(A,B) %en vecteur C on fait l'intersection
 
C =
 
     1     2     3     6
 
>>

Bonjour,

j'aurais voulu savoir s'il existait une commande prédéfinie dans Matlab permettant de trouver s'il existe une intersection entre deux segments donnés ?
(avec comme données à ma disposition : les coordonnées(x,y) des 4 points et bien entendu les deux segments existants)

Et maintenant repondre a ta question.

Pour tes coordonnes tu as comme ca:

Le premier point P1(x1,y1) est donne de l'array nomme array1 par example:

array1= [2 3 1 5;2 4 4 4] -l'array1 est vu comme point P1

ou x1 represent la premiere ligne et y1 represent la deuxieme ligne

Le deuxieme point P2(x2,y2) est donne de l'array nomme array2 par example:

array2=[1 1 1 1 ;2 2 2 2] -l'array2 est vu comme point P2

ou x2 represent la premiere ligne et y2 represent la deuxieme ligne


Et ainsi du suite....

Tu as 4 arrays qui representent tes points.

Et comme tu sais en mathematique un segment est donne par 2 points.

Donc tes 4 points sont representes par 4 arrays et tu as 2 segments.

Tu peux choisir comme tu veux les points pour definir un segment(par example P1 avec P2, P1 avec P3 ,P1 avec P4 comme tu veux mais seulement 2 points pour chaque segment).


J'espere que ca t'aides!

Bonne chance,

Michel

[paradize3]

La fonction 'intersect' de matlab sert a obtenir l'intersection de deux ensembles! Elle n'a donc rien a voir avec l'intersection geometrique de deux segements.

Les algorithmes de references pour l'intersection de deux segements sont decris dans le livre "Computational Geometry in C" par Joseph O'Rouke. Tu peux trouver l'implementation de l'auteur en C et en Java sur: http://maven.smith.edu/~orourke/books/ftp.html (la fonction s'appelle SegSegInt et est contenue dans segseg.c. Attention l'auteur assume des points en coordonnees entieres. Si tu as absoluement besoin de coordonnes reelles il y faut prendre en compte les problemes de robustesse, etc.
Un MEX-wrapper pour cette fonction devrait etre tres facile a ecrire.

Salutations,

Greg

EDIT:
j'ai attache le fichier segsegint.c avec un wrapper mex ecrit en vitesse...

syntaxe d'appel de la fonction:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
Calling Syntax: [p, code] = segsegint(a,b,c,d);
  performs the intersection of two 2D closed segments ab and cd
  Returns p and a char with the following meaning:
  'e': The segments collinearly overlap, sharing a point.
  'v': An endpoint (vertex) of one segment is on the other segment,
       but 'e' doesn't hold.
  '1': The segments intersect properly (i.e., they share a point and
       neither 'v' nor 'e' holds).
  '0': The segments do not intersect (i.e., they share no points).
  Note that two collinear segments that share just one point, an endpoint
  of each, returns 'e' rather than 'v' as one might expect.

Example:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
[p, code] = segsegint(int32([0 0]),int32([1 1]),int32([0 1]),int32([1 0]))
p =
    0.5000
    0.5000
code = 1
 
[p, code] = segsegint(int32([0 0]),int32([1 1]),int32([10 11]),int32([11 10]))
code = 0

Pour recompiler la fonction (teste avec le compilateur de visual c++ 2005) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
mex segsegint.c

[Kangourou]

Salut,

sinon tu as une fonction intersectEdges dans le lien suivant
http://www.mathworks.com/matlabcentr...eexchange/7844

a+

[paradize3]

intersectEdges ne semble pas fonctionner dans certain scenarios - eg: segments //, segments qui ne s'intersectent pas, etc.


Salutations,

Greg

[mihaispr]

La fonction 'intersect' de matlab sert a obtenir l'intersection de deux ensembles! Elle n'a donc rien a voir avec l'intersection geometrique de deux segements.

Je sais ca paradize mais il a demande comment il fait l'intersection des 2 segments et je lui ai donne un example clair comment il peut commencer.

Amicalment,

Michel

[chris05]

sinon essaies cette fonction

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
 
function [boul] = intersections_segment (X1,X2,F1,F2)
 
 
syms x  %définition de la variable x
 
%initialisation
f1b=0;
f2b=0;
boul=0;
n=1;
 
%interpolation polynomiale
f1=polyfit(X1,F1,n);
f2=polyfit(X2,F2,n);
 
 
%ecriture des fonctions d'interpolation
for i=1:n+1
    f1b=f1b+ f1(i)*x^(n-i+1);
    f2b=f2b+ f2(i)*x^(n-i+1);
end
f_inter=f1b-f2b;%calcul de la différences des fonctions d'interpolation
 
 
%application numerique des fonction d'interpolation pour le tracé
xb=min(min(X1),min(X2)):(max(max(X1),max(X2))-min(min(X1),min(X2)))/100:max(max(X1),max(X2));
f1b=subs(f1b,x,xb);
f2b=subs(f2b,x,xb);
 
 
%tracé des fonctions
figure()
hold on
plot(X1,F1,'--r')
plot(X2,F2,'--y')
plot(xb,f1b,'r')
plot(xb,f2b,'y')
 
title('tracé des fonctions et de leurs interpolations')
xlabel('x')
ylabel('f')
legend('F1','F2','interpolation de F1','interpolation de F2')
hold off
 
%calcul des intersections
inter=eval(solve(f_inter,x))
 
%verification intersection segments
x1min=min(X1);
x1max=max(X1);
 
for i=1:length(inter)
    if inter(i) <= x1max && inter(i) >= x1min 
        boul=1;
 
    end
end

c'est en fait une fonction qui interpole avec un polynome deux serie de données pour aboutir à leurs intersections.
Je l'ai un peu remanier pour l'adapter a ton cas (désolé les puristes, c'est encore une fois un travail sale et baclé, mais j'ai pas beaucoup de temps !).

X1 est le vecteur contenant les absisses de ton premier segment.
X2 est le vecteur contenant les absisses de ton 2eme segment.
F1 est le vecteur contenant les ordonnées de ton 1er segment.
F2 est le vecteur contenant les ordonnées de ton 2eme segment.

la fonction renvoie une opération bouléenne (1 si intersection des segments, 0 sinon), te traces les droites correspondant a tes segments et te marques les intersections de ces droites éventuelles (inter). Rassures toi si l'intersection est au dehors du segment, la fonction te retourne quand meme 0.

en esperant que cela t'aidera.

cordialement

[Kangourou]

intersectEdges ne semble pas fonctionner dans certain scenarios - eg: segments //, segments qui ne s'intersectent pas, etc

Greg

En, fait je suis l'auteur du package mentionné plus haut (geom2d). Il peut y avoir des bugs non détectés (et effectivement il semble y en avoir pour intersectEdges), mais je suis preneur de toute remontée de bugs ou d'erreurs. Je corrige intersectEdges, et j'update l'archive.

Sinon pour chris05: passer par l'interpolation polynomiale, c'est quand meme un peu le marton-pilon pour ecraser une mouche, non ?

[chris05]

héhé oui je suis un peu bourrin dans mon genre ^^

Avez vous remaquer que l'auteur de se post n'a répondu à aucun de nos messages ?? Ne se donne-t-on pas du mal pour rien finalement?? J'ai l'impression qu'on parle tous dans le vent depuis un petit moment ....

[al_x67]

Moi ça m'a bien aidé