OVH Cloud OVH Cloud

Dll ou non

16 réponses
Avatar
Patrice Henrio
J'ai besoin d'une fonction déterminant l'intersection de deux segments
(attention pas deux droites).
J'ai réalisé celle-ci dans mon programme.
Je voulais savoir si il y avait un avantage particulier (autre que le
partage du code) à créer une dll contenant cette fonction ou non : rapidité
d'exécution par exemple.
Si je réalise cette fonction en C++, vais-je réellement gagner du temps ?
Cette fonction est utilisée à peu près trente mille fois à chaque cycle du
programme principal.

6 réponses

1 2
Avatar
Jean-Marc
Je vois bien le probleme. Pour ce qui concerne la question initiale
(VB/C) pour les calculs: avec l'algo que tu donnes, c'est sur et
certain que tu gagneras du temps si la fonction est en C: j'ai eu à
faire ce genre de choses pour un cas assez proche (quelques calculs
arithmetiques + quelques tests), et le résultat était sans appel: Gain
de l'ordre de 10 à 20 avec le C.

- Avant de faire le calcul d'intersection, éliminer avec une méthode
rapide les segments qui ne peuvent pas intersecter: il existe des
méthodes très très rapides pour ça, basées sur les projections
orthogonales; en gros, tu projettes tes coordonnées sur les axes des X
et des Y. Si les projetés n'intersectent pas, alors les segments
n'intersectent pas non plus. Si les projetés en X n'intersectent pas,
tu sors. Sinon, tu projettes en Y; Si ça n'intersecte pas, tu sors. Si
Les 2 intersectent, alors tu calcules; tu élimines donc déja très
rapidement tous les cas pour lesquels tout calcul est inutile. Ces
fonctions pourront aussi être codées en C.

Le petit dessin illustre ceci:
B
+
| C
A | +
+ | |
^ | | | D
| | | | +
| | | | |
-+-------------------------------->
| a b c d

On voit bien qu'on peut très rapidement et sans calcul conclure que
[AB] et [CD] n'intersectent PAS, simplement en regardant les abscisses
des projetés orthogonaux sur l'axe des X; la même chose s'applique en
Y. Si les projetés intersectent en X ET en Y, alors il y a intersection
et on doit calculer.

- Penser à implémenter un mécanisme de cache: je suppose que tous les
segments ne bougent pas tous sans arrêt: on ne recalcule pas ce qui a
déjà été calculé. Ceci a un coût: qui dit cache dit mémoire pour le
cache. Cependant, si le temps de recherche dans le cache est inférieur
au temps de re calcul, ça peut valoir le coup (mais ça demande toujours
une étude au cas par cas).

--
Jean-marc
"There are only 10 kind of people
those who understand binary and those who don't."



"Patrice Henrio" a écrit dans le message de
news:%
En fait je recherche l'intersection d'un polygone avec un cadre
rectangulaire.
Je ne peux pas utiliser les API rgn car il s'agit de trouver cette
interscetion en ignorant ce qui se passe en dehors du rectangle. On


connait
seulemnt les points du polygone qui sont à l'intérieur du rectangle et


ceux
d'entrée et de sortie du rectangle.
D'après mes recherches, j'ai vu qu'il me fallait connaitre l'intersection
d'un côté du polygone avec le rectangle ce qui peut donner 0, 1 ou deux
points. De plus, imposer le sens de parcours du polygone, semble


simplifier
les calculs, le côté est donc un segment orienté. Dans le cas des deux
points il me faut récupérer le plus près de l'origine du segment.
Je suis loin d'avoir résolu tous les problèmes, en particulier pour un
polygone dont le pourtour est entièrement en dehors du rectangle, comment
différencier les cas ou le rectangle est à l'intérieur du polygone
(grosso-modo un rectangle dans un cercle) de celui où il est à l'extérieur
du polygone (cas limite, un rectangle dans une couronne).
Merci de vous intéresser à mon problème.

Pour ce qui concerne "le cycle du programme", en fait pour la majorité des
évènements concernant ma forme ou l'un de ses composants (clic,


déplacement
...) un calcul utilisant la fonction précitée se lance pour chaque point
d'un tableau de 30000 points.


"Jean-Marc" a écrit dans le message de


news:
41e11f4c$0$14670$
> "Patrice Henrio" a écrit dans le message de
> news:%
>> Je n'en suis pas sûr, je vous joins le code
>
> // le code
>
> Hello,
>
> je ne suis pas un expert en mathématique, mais je sais qu'il y a plus
> efficace (moins d'operations arithmetiques) pour retrouver les
> coordonnées du point d'intersection de 2 segments. Cependant, les
> fonctions usuelles retournent les coordonnées cartésiennes du point
> d'intersection des 2 segments, et non pas comme dans cette fonction
> l'abscisse barycentrique. Je ne sais pas si le fait de connaitre cette
> abscisse barycentrique est une contrainte liée à la suite des calculs.
> Je ne peux donc pas juger de l'efficacité ni de l'utilité de cet algo.
>
> 2 choses:
>
> - il existe sur le Net des centaines de pages traitant de
> l'intersection de segments. Une recherche avec:
> 'better algorithm segment intersection' dans Google donne
> tout un tas de résultats intéressants. Voir aussi Knuth et les autres.
>
> - le groupe de mathematiques (fr.sci.maths) est plein d'experts!
>
> - tel qu'il est, cet algo me semble tout à fait adapté à un portage en
> C (il n'utilise pas de fonctions trigonométriques, etc).
>
> Si les performances n'étaient pas suffisantes, alors il faudrait
> envisager d'autres solutions.
>
> --
> Jean-marc
> "There are only 10 kind of people
> those who understand binary and those who don't."
>
>




Avatar
Patrice Henrio
Si en fait mes segments bougent souvent.
En effet, comme je l'ai déjà expliqué dans des discussions précédentes, je
cherche à dessiner une partie de la sphère terrestre sur un rectangle, mais
je veux pouvoir faire tourner la terre, et pas seulement autour de son axe.
Je suis parti du fait que je n'ai besoin que d'une "petite fenêtre" de la
terre, donc je projette à partir du centre sur un plan tangent à la terre.
Les déformations liées à cette représentation sont négligeables sur cette
fenêtre. Le contour des pays est défini par une liste de points en
longitude-latitude. Je calcule alors les coordonnées dans mon écran de ces
points et j'utilise l'API polygone pour dessiner.
Tout cela marchait merveilleusement tant que l'Amérique était ignorée. En
effet pour les points hors écran, la topologie des formes était sensiblement
conservée car je bloquais à un cadre égal à neuf fois l'écran, largement
suffisant.
Mais avec le dessin de l'Amérique, je me suis aperçu que certaines fois, les
terres et les océans étaient inversées. Cela est lié, à mon avis, à la
définition de l'intérieur d'un polygone.
Il faut donc que je gère autrement mes contours.
Donc pour répondre au problème du cache : dés que je change de latitude ou
de longitude du point cenral, mes segments sont modifiés, et cela arrive dés
que l'utilisateur voyage sur le globe, à peu près 9 évènements sur 10.
Par contre je suis allé sur les sites que tu indiquais et j'y ai puisé des
infos pertinentes pour mon problème. Cela m'a permis d'améliorer
sensiblement l'algorithme principal.

Pour ma fonction d'intersection, je vais utiliser ta remarque sur les
projections. je la connaissais mais je ne pensais pas qu'elle pouvait être
utile ici. En fait elle est doublement utile puisque mon rectangle à ses
côtés parallèles aux axes, donc en deux tests je sais s'il y a 0 point
solution.

Encore merci.



"Jean-Marc" a écrit dans le message de news:
41e14d3b$0$310$
Je vois bien le probleme. Pour ce qui concerne la question initiale
(VB/C) pour les calculs: avec l'algo que tu donnes, c'est sur et
certain que tu gagneras du temps si la fonction est en C: j'ai eu à
faire ce genre de choses pour un cas assez proche (quelques calculs
arithmetiques + quelques tests), et le résultat était sans appel: Gain
de l'ordre de 10 à 20 avec le C.

- Avant de faire le calcul d'intersection, éliminer avec une méthode
rapide les segments qui ne peuvent pas intersecter: il existe des
méthodes très très rapides pour ça, basées sur les projections
orthogonales; en gros, tu projettes tes coordonnées sur les axes des X
et des Y. Si les projetés n'intersectent pas, alors les segments
n'intersectent pas non plus. Si les projetés en X n'intersectent pas,
tu sors. Sinon, tu projettes en Y; Si ça n'intersecte pas, tu sors. Si
Les 2 intersectent, alors tu calcules; tu élimines donc déja très
rapidement tous les cas pour lesquels tout calcul est inutile. Ces
fonctions pourront aussi être codées en C.

Le petit dessin illustre ceci:
B
+
| C
A | +
+ | |
^ | | | D
| | | | +
| | | | |
-+-------------------------------->
| a b c d

On voit bien qu'on peut très rapidement et sans calcul conclure que
[AB] et [CD] n'intersectent PAS, simplement en regardant les abscisses
des projetés orthogonaux sur l'axe des X; la même chose s'applique en
Y. Si les projetés intersectent en X ET en Y, alors il y a intersection
et on doit calculer.

- Penser à implémenter un mécanisme de cache: je suppose que tous les
segments ne bougent pas tous sans arrêt: on ne recalcule pas ce qui a
déjà été calculé. Ceci a un coût: qui dit cache dit mémoire pour le
cache. Cependant, si le temps de recherche dans le cache est inférieur
au temps de re calcul, ça peut valoir le coup (mais ça demande toujours
une étude au cas par cas).

--
Jean-marc
"There are only 10 kind of people
those who understand binary and those who don't."



"Patrice Henrio" a écrit dans le message de
news:%
En fait je recherche l'intersection d'un polygone avec un cadre
rectangulaire.
Je ne peux pas utiliser les API rgn car il s'agit de trouver cette
interscetion en ignorant ce qui se passe en dehors du rectangle. On


connait
seulemnt les points du polygone qui sont à l'intérieur du rectangle et


ceux
d'entrée et de sortie du rectangle.
D'après mes recherches, j'ai vu qu'il me fallait connaitre l'intersection
d'un côté du polygone avec le rectangle ce qui peut donner 0, 1 ou deux
points. De plus, imposer le sens de parcours du polygone, semble


simplifier
les calculs, le côté est donc un segment orienté. Dans le cas des deux
points il me faut récupérer le plus près de l'origine du segment.
Je suis loin d'avoir résolu tous les problèmes, en particulier pour un
polygone dont le pourtour est entièrement en dehors du rectangle, comment
différencier les cas ou le rectangle est à l'intérieur du polygone
(grosso-modo un rectangle dans un cercle) de celui où il est à
l'extérieur
du polygone (cas limite, un rectangle dans une couronne).
Merci de vous intéresser à mon problème.

Pour ce qui concerne "le cycle du programme", en fait pour la majorité
des
évènements concernant ma forme ou l'un de ses composants (clic,


déplacement
...) un calcul utilisant la fonction précitée se lance pour chaque point
d'un tableau de 30000 points.


"Jean-Marc" a écrit dans le message de


news:
41e11f4c$0$14670$
> "Patrice Henrio" a écrit dans le message
> de
> news:%
>> Je n'en suis pas sûr, je vous joins le code
>
> // le code
>
> Hello,
>
> je ne suis pas un expert en mathématique, mais je sais qu'il y a
> plus
> efficace (moins d'operations arithmetiques) pour retrouver
> les
> coordonnées du point d'intersection de 2 segments. Cependant,
> les
> fonctions usuelles retournent les coordonnées cartésiennes du
> point
> d'intersection des 2 segments, et non pas comme dans cette
> fonction
> l'abscisse barycentrique. Je ne sais pas si le fait de connaitre
> cette
> abscisse barycentrique est une contrainte liée à la suite des
> calculs.
> Je ne peux donc pas juger de l'efficacité ni de l'utilité de cet algo.
>
> 2 choses:
>
> - il existe sur le Net des centaines de pages traitant de
> l'intersection de segments. Une recherche avec:
> 'better algorithm segment intersection' dans Google donne
> tout un tas de résultats intéressants. Voir aussi Knuth et les autres.
>
> - le groupe de mathematiques (fr.sci.maths) est plein d'experts!
>
> - tel qu'il est, cet algo me semble tout à fait adapté à un portage
> en
> C (il n'utilise pas de fonctions trigonométriques, etc).
>
> Si les performances n'étaient pas suffisantes, alors il
> faudrait
> envisager d'autres solutions.
>
> --
> Jean-marc
> "There are only 10 kind of people
> those who understand binary and those who don't."
>
>








Avatar
Jean-Marc
"Patrice Henrio" a écrit dans le message de
news:%
Pour ma fonction d'intersection, je vais utiliser ta remarque sur les
projections. je la connaissais mais je ne pensais pas qu'elle pouvait être
utile ici. En fait elle est doublement utile puisque mon rectangle à ses
côtés parallèles aux axes, donc en deux tests je sais s'il y a 0 point
solution.

Encore merci.



Content d'avoir pu être utile. Si tu implémentes tout de même ta
fonction d'intersection en C, je serais intéressé par curiosité
intellectuelle de connaitre le gain obtenu dans ce cas précis.


Bonne journée.

--
Jean-marc
"There are only 10 kind of people
those who understand binary and those who don't."
Avatar
ng
Salut,

Peut-on voir ton code ?

--
Nicolas G.
FAQ VB : http://faq.vb.free.fr
API Guide : http://www.allapi.net
Google Groups : http://groups.google.fr/
MZ-Tools : http://www.mztools.com/

Patrice Henrio wrote:
J'ai besoin d'une fonction déterminant l'intersection de deux segments
(attention pas deux droites).
J'ai réalisé celle-ci dans mon programme.
Je voulais savoir si il y avait un avantage particulier (autre que le
partage du code) à créer une dll contenant cette fonction ou non :
rapidité d'exécution par exemple.
Si je réalise cette fonction en C++, vais-je réellement gagner du
temps ? Cette fonction est utilisée à peu près trente mille fois à
chaque cycle du programme principal.


Avatar
ng
Oups mauvais thread :/

--
Nicolas G.
FAQ VB : http://faq.vb.free.fr
API Guide : http://www.allapi.net
Google Groups : http://groups.google.fr/
MZ-Tools : http://www.mztools.com/

ng wrote:
Salut,

Peut-on voir ton code ?


Patrice Henrio wrote:
J'ai besoin d'une fonction déterminant l'intersection de deux
segments (attention pas deux droites).
J'ai réalisé celle-ci dans mon programme.
Je voulais savoir si il y avait un avantage particulier (autre que le
partage du code) à créer une dll contenant cette fonction ou non :
rapidité d'exécution par exemple.
Si je réalise cette fonction en C++, vais-je réellement gagner du
temps ? Cette fonction est utilisée à peu près trente mille fois à
chaque cycle du programme principal.




Avatar
Jean-Marc
J'ai fait vite fait un petit test, en codant uniquement la fonction qui
détermine si il y a ou non intersection. J'ai codé la même fonction (ça
revient à faire: If (c > a And c < b) Or (d > a And d < b) Then ) et je
l'ai fait en VB en en C, en utilisant les meilleures options de compil
pour les 2 langages. Le programme VB (lancé hors IDE, bien sur) me
donne les résultats suivants: Le code qui appelle la fonction C
s'exécute environ 3,3 fois plus vite, calcul fait sur une moyenne de
100 exécutions d'une boucle d'1 millions d'appels). Pour la petite
histoire, sur une machine moyenne (AMD XP2000+ 900 Mhz / 756Mo RAM) 1
million de tests d'intersections se font en 0.039 secondes, ce qui
n'est pas si mal! Hors, le code de la fonction est minuscule et on paye
ici l'overhead d'appel de la dll. Il est évident qu'avec plus de code,
le gain sera encore plus sensible. Je suis sur que sur une fonction
complète (le vrai calcul de l'intersection) on devrait gagner un
facteur 6 ou 7. Ceci pour dire que dans ce cas, le portage en C des
fonctions critiques vaut clairement le coup.

--
Jean-marc
"There are only 10 kind of people
those who understand binary and those who don't."
1 2