2 segments se croisent-ils ?

[Flodelarab]

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" ?

:ptdr:

dans le premier cas

et


Dans le second cas:


et



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 :ptdr:

[Flodelarab]

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

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

[Flodelarab]

Personne n'a dit ça !

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

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

[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
Ok pour , mais que veut dire ?

[Flodelarab]

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
Ok pour , mais que veut dire ?

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

[rodymary]

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 !!!

[Flodelarab]

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 !!!

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

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

???

[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 totoInterdiction 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 !

[Flodelarab]

[quote="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 > , un algorithme simple du genre Si toto 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 ?

[rodymary]

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 !

[Flodelarab]

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

:doh: :doh: :doh:
LOURD ?????

[rodymary]

:doh: :doh: :doh:
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é !

[Flodelarab]

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

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

[Dominique Lefebvre]

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é !

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)...

[rodymary]

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.

[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)...

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.

[Flodelarab]

en Visual Basic

optimisation

[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.

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?

[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?

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.

[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.

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!