Mathématiques - 2 segments se croisent-ils ?

2 segments se croisent-ils ?
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: rodymary

bonjour à tous,

soit 2 segments A et B dont on connait les coordonnées x,y de chacun des points des segments.

j'aimerai savoir s'il existe une méthode simple pour savoir si ces 2 segments se croisent, autrement qu'en calculant leur equation respective, le déterminant, ...

je ne cherche pas à connaitre les coordonnées du point d'intersection, juste savoir s'il existe une intersection.

c'est pour une application informatique
merci d'avance

Posted by: Dominique Lefebvre

Bonsoir,

La méthode la plus simple est sans doute de résoudre l'égalité entre les équations des droites qui portent les segments. Point besoin de déterminant...

Maintenant, dans un programme, tu peux aussi chercher les pixels communs aux deux segments, mais ce n'est pas forcément plus simple!

Posted by: Flodelarab

Citation:

Posté par rodymary

bonjour à tous,

soit 2 segments A et B dont on connait les coordonnées x,y de chacun des points des segments.

j'aimerai savoir s'il existe une méthode simple pour savoir si ces 2 segments se croisent, autrement qu'en calculant leur equation respective, le déterminant, ...

je ne cherche pas à connaitre les coordonnées du point d'intersection, juste savoir s'il existe une intersection.

c'est pour une application informatique
merci d'avance

oui.

Les intervalles des x et des y doivent avoir une partie commune.
Ensuite, prend le rectangle le plus ressérré possible sur ton point concours supposé.... tu trouveras la condition d'intersection

@Dominique: Merci de respecter l'énoncé ... pas d'equation !

Posted by: Dominique Lefebvre

Citation:

Posté par Flodelarab

Oui, sans doute! Mais il faut savoir dégager des solutions rapides et simples. En termes d'efficacité de calcul, connaissant les coordonnées des extrémités des segments, le calcul des deux équations et leur résolution est sans doute le plus rapide.

Ta solution suppose qu'on ait une idée du point d'intersection. Comment un programme pourrait en avoir une? A moins de commencer par un rectangle couvrant tout le domaine! Alors bof, au niveau algo, c'est pas le plus efficace...

Posted by: Dominique Lefebvre

J'y pense, il existe une solution assez simple.

Tu traces le premier segment en mémorisant les pixels activés.
En traçant le second segment, tu vérifie si le pixel que tu veux écrire est déjà activé. Si oui, il s'agit du point d'intersection.

Posted by: Flodelarab

Citation:

Posté par Dominique Lefebvre

J'y pense, il existe une solution assez simple.

Tu traces le premier segment en mémorisant les pixels activés.
En traçant le second segment, tu vérifie si le pixel que tu veux écrire est déjà activé. Si oui, il s'agit du point d'intersection.

pffff

je reve

Posted by: Dominique Lefebvre

Citation:

Posté par Flodelarab

pffff

je reve

Pourquoi, ça marche parfaitement! et en plus tu peux tester si les deux segments sont superposés!

PS: sais-tu que c'est comme ça que fonctionnent les algo d'effacement des arêtes cachées...

Posted by: Flodelarab

Citation:

Posté par Dominique Lefebvre

Pourquoi, ça marche parfaitement! et en plus tu peux tester si les deux segments sont superposés!

PS: sais-tu que c'est comme ça que fonctionnent les algo d'effacement des arêtes cachées...

Tu ne respectes aucune des données de l'énoncé.

Personne t'as dit qu'on allait la tracer. (Puis merci l'efficacité)
On te dit de pas calculer les équations.
On te dit que tu as les coordonnées des points des segments.

si, pour le max des xmin, on pas les y dans l'ordre inverse des y pour le min des x max, alors les segments se croisent pas ... ma solution est tellement simple qu'il y a pas d'algo...

Posted by: Dominique Lefebvre

Ouai, moi j'ai lu que c'était pour une appli informatique! Alors, si on écoutait plutôt l'utilisateur! C'est pas un énoncé de pb de cours, c'est un cahier des charges....
Et puis, je suis curieux de connaître ta manière de développer ta solution sans algo, même simple....

Posted by: rodymary

bonjour à vous 2
effectivement je ne compte pas dessiner ou tester point par point, mon language de programmation fait ça bien plus rapidement que je ne saurais le faire.
Flodelarab, ta solution m'intéresse tout particulièrement mais je ne la comprends cependant pas bien ? peux-tu la préciser s'il te plait (ou simplifier, même si pour toi celà parait simple, je ne suis pas matheux...)
merci d'avance

Posted by: rodymary

de manière illustrée, voici mes 2 segments :
http://rodymary45.free.fr/photos/graph1.bmp
Flodelarab, lorsque tu dis "Les intervalles des x et des y doivent avoir une partie commune." => là c'est bon, je pige, c'est après...

Posted by: Flodelarab

Citation:

Posté par rodymary

de manière illustrée, voici mes 2 segments :
Flodelarab, lorsque tu dis "Les intervalles des x et des y doivent avoir une partie commune." => là c'est bon, je pige, c'est après...

http://img244.imageshack.us/img244/6016/graph2qg7.jpg

Voila le rectangle dont je parlais (celui auquel il faut se restreindre)

La droite verticale bleue est le maximum des x minimums.
La droite verticale jaune est le minimum des x maximums.
Cela permet de cerner la zone ou un chevauchement est possible.
J'appelle $x_m$ l'abscisse bleue et $x_M$ l'abscisse jaune.

Si les ordonnées des segments sont dans le meme ordre pour $x_m$ et $x_M$ alors les segments ne se croisent pas. Sinon, il se croisent.

J'ajoute, que l'on peut faire la meme chose en partant des y. Voila pkoi j'ai tracer une droite verte et un droite viollette.

ok?

Posted by: rodymary

euh, non c'est pas beaucoup plus clair
ok pour la "plus petite boite"
quand on parle d'abscisse, c'est bien l'horizontale ?
si je comprends ton explication, ça ne marche pas, car regardes ci-dessous, j'ai inversé le sens du segment (cd)
http://rodymary45.free.fr/photos/graph2qg7.bmp
désolé de paraître boulet mais ce n'était pas un euphémisme de dire que je n'étais pas matheux !
merci pour ta patience !

Posted by: Flodelarab

Citation:

Posté par rodymary

euh, non c'est pas beaucoup plus clair
ok pour la "plus petite boite"
quand on parle d'abscisse, c'est bien l'horizontale ?
si je comprends ton explication, ça ne marche pas, car regardes ci-dessous, j'ai inversé le sens du segment (cd)
désolé de paraître boulet mais ce n'était pas un euphémisme de dire que je n'étais pas matheux !
merci pour ta patience !

Aucun probleme.
ça marche toujours.

Si je prends l'ordre des ordonnées pour xm, j'ai [ab] au dessus de [cd] et si je prends l'ordre des ordonnées pour xM, j'ai [ab] au dessus de [cd].

Donc [ab] et [cd] ne se croisent pas ...

Posted by: rodymary

Citation:

Posté par Flodelarab

Bonjour et pardon pour la réponse tardive, j'étais en déplacement à l'étranger.
Tout d'abord merci pour ta patience, car je ne comprends toujours pas ton raisonnement, je ne vois pas de différence de résultat entre les 2 shémas ci-dessous ?
http://rodymary45.free.fr/photos/G1.bmp http://rodymary45.free.fr/photos/G2.bmp
Shéma 1 : il n'y a pas croisement, shéma 2 : il y a croisement.
Je raisonne bien "segment" et pas "droite", on est d'accord ?
Encore merci !

Posted by: Flodelarab

pour le dessin de gauche, (je fais l'hypothèse que tu ne retrournes pas ton écran, ni que tu marches au plafond), on observe en Xm que [AB] est en dessus de [CD]. On observe également qu'en XM, [AB] est ENCORE en dessus de [CD]

pour le dessin de droite, (je fais l'hypothèse que tu n'as pas bougé depuis la première phrase

), on observe en Xm que [AB] est en dessus de [CD]. On observe également qu'en XM, [AB] est en dessous de [CD]

On a changé l'ordre des segments dans celui de droite.
Donc il y a croisement dans le dessin de droite.

Posted by: rodymary

ce que j'arrive pas à interpreter de façon mathématique (afin de le retranscrire informatiquement), c'est la notion de "en dessous" ou "au dessus" ?

Posted by: Quidam

Plus compliqué tu meurs !

Moi, je pense que la solution proposée par Dominique est bien plus efficace...

Plus précisément. Pour clarifier l'exposé, j'appelle P et Q les extrémités du segment A, R et S les extrémités du segment B.

1 - Tu détermines l'équation de la droite contenant P et Q : soit ax+by+c=0 cette équation.

2 - Tu choisis au contraire pour la droite RS des équations paramétriques :

$\Large x = x_P + \lambda(x_Q-x_P)$
$\Large y = y_P + \lambda(y_Q-y_P)$

3 - Pour déterminer l'intersection des droites, tu remplaces x et y dans l'équation ax+by+c=0 par leur expression donnée par les équations paramétriques :
$\Large ax+by+c=0$ devient
$\Large a(x_P + \lambda(x_Q-x_P))+b(y_P + \lambda(y_Q-y_P))+c=0$

Ceci donne immédiatement :

$\Large \lambda = - \frac{ax_P+by_P+c}{a(x_Q-x_P)+b(y_Q-y_P)}$

Dans les équations paramétriques, $\Large \lambda = 0$ correspond au point P, et $\Large \lambda = 1$ correspond au point Q.

Si donc le $\Large \lambda$ trouvé est compris entre 0 et 1, alors les deux segments se coupent. Sinon, ils ne se coupent pas !
Bien sûr, il faut vérifier que le dénominateur de l'expression ci-dessus n'est pas nul ! S'il était nul cela signifierait que les droites portant PQ et RS sont parallèles (donc éventuellement confondues, là ça devient plus compliqué). Si elles sont parallèles et distinctes, elles ne se coupent pas, a fortiori les segments portés non plus. Il reste à traiter le cas gênant où ces deux droites sont confondues...

Posted by: Quidam

Citation:

Posté par Flodelarab

On te dit de pas calculer les équations.

Personne n'a dit ça !

Posted by: Flodelarab

Citation:

Posté par rodymary

ce que j'arrive pas à interpreter de façon mathématique (afin de le retranscrire informatiquement), c'est la notion de "en dessous" ou "au dessus" ?

dans le premier cas
$4$ Y(X_m_{[AB]})\ > \ Y(X_m_{[CD]})$
et
$4$ Y(X_M_{[AB]})\ > \ Y(X_M_{[CD]})$

Dans le second cas:

$4$ Y(X_m_{[AB]})\ > \ Y(X_m_{[CD]})$
et
$4$ Y(X_M_{[AB]})\ < \ Y(X_M_{[CD]})$

Maintenant, si la relation d'ordre des réels est trop compliqué pour toi Quidam, je pense que tu es handicapé dans la vie pour choisir les prix les plus bas

Posted by: Flodelarab

Citation:

Posté par Quidam

Personne n'a dit ça !

rappel de l'énoncé quelque cm plus haut ....

Citation:

Posté par rodymary

j'aimerai savoir s'il existe une méthode simple pour savoir si ces 2 segments se croisent, autrement qu'en calculant leur equation respective

Posted by: rodymary

Oh là, restons bons enfants.
J'aurais peut-être dû expliquer d'avantage pourquoi je souhaiterai ne pas utiliser d'équations.
Ma priorité absolue étant d'optimiser les calculs et donc de réduire au maximum les diverses manipulations de variables, je dois éviter tant que possible :
- l'utilisation de fonctions complexes genre trigo, exposants, ... même si les ordinateurs possèdent à présent tous un co-processeur arithmétique
- les divisions afin de na pas avoir à tester et gérer les éventuelles divisions par zéro
Il vaut mieux faire quelques conditions imbriquées (SI...ALORS...) que de lancer brutalement des calculs mathématiques et en exploiter les résultats.
C'est pourquoi la solution de Flodelarab m'intéresse tout particulièrement, encore faudrait-il que je la comprenne.
A ce titre, je ne comprends toujours pas une formule du genre $4$ Y(X_m_{[AB]})\$
Ok pour $Y$ , mais que veut dire $X_m_{[AB]}$ ?

Posted by: Flodelarab

Citation:

Posté par rodymary

Oh là, restons bons enfants.
J'aurais peut-être dû expliquer d'avantage pourquoi je souhaiterai ne pas utiliser d'équations.
Ma priorité absolue étant d'optimiser les calculs et donc de réduire au maximum les diverses manipulations de variables, je dois éviter tant que possible :
- l'utilisation de fonctions complexes genre trigo, exposants, ... même si les ordinateurs possèdent à présent tous un co-processeur arithmétique
- les divisions afin de na pas avoir à tester et gérer les éventuelles divisions par zéro
Il vaut mieux faire quelques conditions imbriquées (SI...ALORS...) que de lancer brutalement des calculs mathématiques et en exploiter les résultats.
C'est pourquoi la solution de Flodelarab m'intéresse tout particulièrement, encore faudrait-il que je la comprenne.
A ce titre, je ne comprends toujours pas une formule du genre $4$ Y(X_m_{[AB]})\$
Ok pour $Y$ , mais que veut dire $X_m_{[AB]}$ ?

Y: l'ordonnée pour le segment [AB] a l'abscisse xm prédéfini (droite bleue me semble t il)

Ce ne sont que des indice pour savoir de quoi on parle

Posted by: rodymary

Citation:

Posté par Flodelarab

Y: l'ordonnée pour le segment [AB] a l'abscisse xm prédéfini (droite bleue me semble t il)

ah, c'est bien ce qui m'inquiétait... c'est qu'il me faut trouver cette ordonnée, et pour ce faire, c'est calcul de l'équation de [AB] pour trouver l'intersection entre xm et [AB]... ça n'est du coup plus si "rapide" que je ne le pensais.
Tu vois ce que je veux dire, il aurait suffi de faire quelques SI...ALORS... c'était nickel, mais dès lors qu'il faut passer par une équation (même 2 pour xm et xM), test de division pour le coef de pente a de y=ax+b, ...
A moins que je n'aie mal compris, je te remercie tout de même pour ta patience !!!

Posted by: Flodelarab

Citation:

Posté par rodymary

Je reviens donc a ton énoncé:
Q'entends tu par:

Citation:

soit 2 segments A et B dont on connait les coordonnées x,y de chacun des points des segments.

???

Posted by: rodymary

Je précise mon énoncé.
Soient A et B 2 segments dont on connait les coordonnées de leurs extrémités réspectives :
segment A : (x1A,y1A)-----------(x2A,y2A)
segment B : (x1B,y1B)-----------(x2B,y2B)
Ces 2 segments peuvent être perpendiculaires, parrallèles, séquants ou non, bref toutes les configurations possibles et inimaginables.
Admettons que nous ayons en notre possession 2 fonctions permettant de renvoyer la valeur minimum ou maximum de 2 variables : Notons les Min(variable1,variable2) et Max(variable1,variable2).
Est-ce possible de savoir si oui ou non ces 2 segments possèdent une intersection, uniquement en utilisant ces 2 fonctions, des tests de supériorité/infériorité/égalité/inégalité que nous noterons respectivement > < = ou <>, un algorithme simple du genre Si toto<titi ALORS...
Interdiction d'utiliser la division, et possibilité d'utiliser des variables de travail.
Le tout avec le moins de lignes possibles. Quel challenge me direz-vous !

Posted by: Flodelarab

Citation:

Posté par rodymary

Je précise mon énoncé.
Soient A et B 2 segments dont on connait les coordonnées de leurs extrémités réspectives :
segment A : (x1A,y1A)-----------(x2A,y2A)
segment B : (x1B,y1B)-----------(x2B,y2B)
Ces 2 segments peuvent être perpendiculaires, parrallèles, séquants ou non, bref toutes les configurations possibles et inimaginables.
Admettons que nous ayons en notre possession 2 fonctions permettant de renvoyer la valeur minimum ou maximum de 2 variables : Notons les Min(variable1,variable2) et Max(variable1,variable2).
Est-ce possible de savoir si oui ou non ces 2 segments possèdent une intersection, uniquement en utilisant ces 2 fonctions, des tests de supériorité/infériorité/égalité/inégalité que nous noterons respectivement > < = ou <>, un algorithme simple du genre Si toto<titi ALORS...
Interdiction d'utiliser la division, et possibilité d'utiliser des variables de travail.
Le tout avec le moins de lignes possibles. Quel challenge me direz-vous !

ouai ouai ouai....
c t trop beau.
En fait tu connais rien du segment proprement dit :-)

Seconde méthode: déterminer si le chemin reliant trois points tourne dans le sens des aiguilles d'une montre ou en sens inverse

int ccw(struct point p0, struct point p1, struct point p2) {
int dx1, dx2, dy1, dy2;
dx1 = p1.x - p0.x; dy1 = p1.y - p0.y;
dx2 = p2.x - p0.x; dy2 = p2.y - p0.y;
if (dx1*dy2 > dy1*dx2) return +1;
if (dx1*dy2 < dy1*dx2) return -1;
if ((dx1*dx2 < 0) || (dy1*dy2 < 0)) return -1;
if ((dx1*dx1 + dy1*dy1) < (dx2*dx2 + dy2*dy2)) return +1;
return 0;
}

Par convention, lorsque les points p0, p1, p2 sont colinéaires,
si p0 est entre p1 et p2, ccw retourne -1
si p1 est entre p0 et p2, ccw retourne +1
si p2 est entre p0 et p1, ccw retourne 0

int intersect(struct line l1, struct line l2) {
return ((ccw(l1.p1, l1.p2, l2.p1) *
ccw(l1.p1, l1.p2, l2.p2)) <= 0) &&
((ccw(l2.p1, l2.p2, l1.p1) *
ccw(l2.p1, l2.p2, l1.p2)) <= 0);
}

Cet algorithme semble nécessiter beaucoup de calculs
Cependant, la recherche d'une solution plus courte, mais néanmoins
complète est loin d'être triviale

satisfait ?

Posted by: rodymary

Citation:

Posté par Flodelarab

En fait tu connais rien du segment proprement dit

Ah ok, en fait tu partais du postulat que je connaissais déjà les coef directeur des 2 segments, c'est ça ?
En fait non, j'indiquais bien que je ne connaissais que les coordonnées de leurs extrémités, rien de plus.
Effectivement, ça risque d'être lourd dans ce cas.
Merci pour tout, et chapeau pour votre "dextérité" dans ce domaine un peu flou que sont pour moi les maths !

Posted by: Flodelarab

Citation:

Posté par rodymary

Effectivement, ça risque d'être lourd dans ce cas.

LOURD ?????

Posted by: rodymary

Citation:

Posté par Flodelarab

LOURD ?????

Oui, lourd, car quand l'objectif est de savoir si 2 segments se croisent, ça va, mais dans mon cas, j'ai environ 10000 segments dans tous les sens, et je dois calculer tous les points d'intersections de ces segments entre eux, dans ce cas la moindre économie de calcul se traduit immédiatement par des centièmes de gagné !

Posted by: Flodelarab

Citation:

Posté par rodymary

...je dois calculer tous les points d'intersections de ces segments entre eux....

heureusement que tu nous as dit le contraire ....

Posted by: Dominique Lefebvre

Citation:

Posté par rodymary

Pour y voir plus clair, tes 10 000 segments sont stockés où et comment? S'agit-il de pur calcul ou bien dois-tu les afficher?
Dans quel type d'application gères-tu 10 000 segments. Je ne vois que des applis. graphiques pour ça (ou de CAO/DAO)...

Posted by: rodymary

Citation:

Posté par Flodelarab

heureusement que tu nous as dit le contraire ....

Je ne souhaite calculer les coordonnées du point d'intersection que si c'est nécessaire, car seuls quelques uns de ces milliers de segments vont se croiser.

Posted by: rodymary

Citation:

Posté par Dominique Lefebvre

C'est effectivement une application de type DAO, écrite en Visual Basic. Ce n'est certes pas le langage le plus approprié mais il correspond à mon besoin et à mes connaissances. La partie affichage de ces segments n'est pas un problème, alors que la partie calcul et stockage des données nécessite quant à elle un soin attentif et une optimisation en conséquence.
Le choix du type de variable utilisée dans ce langage est primordial et je travaille à ce titre sur des entiers (c'est le plus gros poste d'optimisation). Revers de la médaille, ce type de variable possède des limites car stocké sur 4 octets, et un "overflow" arrive vite.

Posted by: Flodelarab

Citation:

Posté par rodymary

en Visual Basic

Citation:

Posté par rodymary

optimisation

http://s148670911.onlinehome.fr/for.../smiles/mdr.gif

Posted by: Dominique Lefebvre

Citation:

Posté par rodymary

Bon, je ne vais pas me moquer de ton usage de VB, moi... On fait avec ce qu'on a!

Par contre, je ne suis pas certain que ton seul (et même principal) poste d'optimisation soit l'usage d'entiers! Pourquoi d'ailleurs utilises-tu des long (4 octets) plutôt que des integer (2 octets). As-tu besoin de 4 octets pour stocker les coordonnées d'un point?

A mon sens, ton gros problème d'optimisation va tenir dans le choix de la structure de données que tu vas utiliser pour stocker tes données. En DAO, l'accès doit être très rapide.... Et tu dois gérer 10 000 segments... Comment procèdes-tu?

Posted by: rodymary

Citation:

Posté par Dominique Lefebvre

Je ne relèverai pas plus que ça la moquerie de notre ami...
J'utilise du Long par nécessité, la plus petite unité de mesure recherchée étant le millimètre et je dois pouvoir gérer plusieurs centaines de mètres (les +/-32767 de l'Integer ne suffisent donc pas).
Mon application étant basée sur des segments, je les stocke dans un tableau Segt() défini comme suit :
Type infoSegt
x1 as Long
y1 as Long
x2 as Long
y2 as Long
Group as Long
autres caractéristiques (gras, pointillés, ...)
End Type
L'application est un "AutoCAD Like" très simplifié et sur mesure en terme d'ergonomie/manipulation, pour un apprenti infographiste de 60 ans que le mulot rebute.

Posted by: Dominique Lefebvre

Citation:

Posté par rodymary

Bonsoir,

1/ si je comprends bien, tu gères une précision du millimètre sur plusieurs centaines de mètres.... Curieux!

2/Tu stockes tes segments dans un tableau... Je m'en doutais un peu remarque! Et comment accèdes-tu aux données: en séquentiel? Dois-tu rechercher un segment (ou plusieurs) en particulier?

Bon, cela ne nous dit pas comment chercher l'intersection de deux ou plusieurs segments le plus rapidement possible... Je vais chercher dans ma doc, il doit bien y avoir un algo d'intersection bien pensé dans la littérature!

Posted by: rodymary

Citation:

Posté par Dominique Lefebvre

1/ si je comprends bien, tu gères une précision du millimètre sur plusieurs centaines de mètres.... Curieux!

Salut Dominique.
Oui, c'est dans le domaine du batiment et le millimètre suffit dans mon cas.

Citation:

Posté par Dominique Lefebvre

2/Tu stockes tes segments dans un tableau... Je m'en doutais un peu remarque! Et comment accèdes-tu aux données: en séquentiel? Dois-tu rechercher un segment (ou plusieurs) en particulier?

J'ai laissé de côté la gestion de classes et de collections qui ne ferait qu'allourdir les traitements de masse, d'ou l'utilisation d'un tableau simple.
L'accès aux données se fait effectivement en séquentiel, mais est quasi-instantanné car je maintiens en parallèle d'autres tableaux de points dits d'accroche qui changent de couleur au passage du mulot (milieu de segment, points d'intersection, ...).

Citation:

Posté par Dominique Lefebvre

Bon, cela ne nous dit pas comment chercher l'intersection de deux ou plusieurs segments le plus rapidement possible... Je vais chercher dans ma doc, il doit bien y avoir un algo d'intersection bien pensé dans la littérature!

Profites-en pour dépoussiérer ta bibliothèque dans ce cas !
Merci

Posted by: Dominique Lefebvre

Bonjour,

Je dépoussière la doc...
J'ai donc fait comme l'ami Flodelarab, j'ai consulté les classiques, par exemple le R.Sedgewick (Algorithmes en langage C chez Dunod). A la page 368, tu trouveras les algos décrits par Flodelarab dans son post 27. Ces algos sont expliqués de manière complète.
Mais comme le souligne R.Sedgewick, les deux codes proposés ne s'appliquent plus vraiment dans le cas où P segments parmi N s'intersectent (comme il dit!). Or il me semble que ce soit ton cas, non?

Il propose au chapitre 27 (page 414) un algo qui traite le pb, basé sur les techniques d'arbre binaire (intesection de 2 segments parmi N, mais on peut généraliser à P parmi N). C'est un peu long à expliquer et pour garantir la clarté je te recommande la lecture du bouquin (qui est une référence dans les écoles d'ingé...).

Une information importante donnée par Robert: la recherche des I intersections parmi N segments est un algo d'ordre minimum (N+I)logN.

Je continue mes recherches...

Posted by: Dominique Lefebvre

Dans mes références, j'ai trouvé ce doc:
http://www.enseignement.polytechniq...y/00/pc5/a5.pdf -
Dans les pages 134 et suivantes, tu trouveras qq algos intéressants sur notre problème.

Posted by: Dominique Lefebvre

Citation:

Posté par rodymary

Salut Dominique.
J'ai laissé de côté la gestion de classes et de collections qui ne ferait qu'allourdir les traitements de masse, d'ou l'utilisation d'un tableau simple.
L'accès aux données se fait effectivement en séquentiel, mais est quasi-instantanné car je maintiens en parallèle d'autres tableaux de points dits d'accroche qui changent de couleur au passage du mulot (milieu de segment, points d'intersection, ...).

Dans ce cas particulier, je ne pensais pas du tout aux classes et autres collections, qui en calcul et amha, relèvent du gadget....
Non, je pensais plutôt à des structures en arbres. La plupart des algos que je connais dans ce domaine travaillent sur des arbres binaires (voir le cours d'algo et le bouquin de Sedgewick que je t'ai mis en référence).
Faire des arbres en VB, c'est possible mais coton... A cause de la manipulation des pointeurs. Mais bon, je ne suis pas spécialiste de VB.

Posted by: rodymary

VB n'est en effet pas champion en manipulation de pointeur, je vais néanmoins jeter un oeil intéressé au bouquin de Robert, ça fait longtemps que je cherche une méthode différente pour gérer ce type de problème.
Merci pour tout en tous cas !