Aller au contenu

Point3dTree arbre 2d / 3d pour organiser les collections de points


(gile)

Messages recommandés

Salut,

 

J'avais écrit cette implémentation d'un arbre k-d pour organiser les collections de Point3d AutoCAD il y a quelques temps.

Comme la "communauté AutoCAD .NET francophone" semble s'étoffer j'ai ajouté cette petite bibliothèque de classe sur gileCAD.

 

Le choix de la structure de données pour stocker un collection peut être déterminant en terme de performances suivant le type de données (surtout avec les collections importantes).

La structure de données Point3dTree permet d'optimiser notablement les recherches de points dans la collection (proches voisins ou plage).

La construction de l'arbre à partir d'une collection classique (List, Point3d[], Point3dCollection, etc.) a certes en coût (même avec un traitement parallèle), mais ce coût est vite rentabilisé si, une fois l'arbre construit, on l'utilise pour plusieurs recherches de points.

 

Pour se faire une idée, avec un dessin contenant 500 000 points il faut environ 1.6 secondes pour collecter les points dans un tableau classique et environ 0.5 secondes pour le convertir en arbre.

Ensuite la recherche du point le plus proche d'un point quelconque ne prend qu'une milliseconde (50 fois moins qu'une recherche séquentielle dans le tableau).

La recherche des 100 points les plus proches prend 50 millisecondes, celle des 500 les plus proches environ 500 millisecondes.

Mais le plus impressionnant est la recherche dans un rayon donné, d'après mes test il faut un rayon susceptible de capturer 15 000 points pour arriver à 1 milliseconde. Idem pour la recherche dans une plage.

 

De plus, les méthodes de la classe Point3dTree supportent les traitements parallèles, autrement dit, autant de recherches simultanées que de cœurs disponibles. Eh oui, si le traitement des objets de la base de données d'AutoCAD ne supporte pas les exécutions parallèles, ce n'est pas le cas pour les objets géométriques comme les Point3d qui sont des structures immuables indépendantes de la base de donnée.

 

L'aide de cette petite bibliothèque générée avec SandCastle d'après les commentaires XML dans le code.

 

 

PS : J'ai aussi rafraichi une autre bibliothèque (plus volumineuse) : GeometryExtension (sur la même page) et j'en ai profité pour refaire l'aide en français.

Gilles Chanteau - gileCAD -
Développements sur mesure pour AutoCAD
ADSK_Expert_Elite_Icon_S_Color_Blk_125.png

Lien vers le commentaire
Partager sur d’autres sites

Hello Gilles

 

Je suis impressionne par tes chiffres relatifs a la Performance !

 

SVP serait il eventuellement possible d'avoir un programme en VLisp + Dotnet ou en "pur" Dotnet pour AutoCAD 2014-2017 (32 ou 64 bits) pour tester :

 

- Selection AutoCAD classique et ne retenir que les Points et les Blocs

 

- Questions:

Recherche dans un Rayon ou N objets Proches (R/P) (Defaut = R)

 

Si Rayon, poser la question du Rayon (Defaut = 10) puis Traitement ...

En sortie N objets selectionnes

 

Sinon Proche - Question: Combien de Points/Blocs proches (1-N) (Defaut = 1)

En sortie N objets selectionnes

 

Merci, Bye, lecrabe

Autodesk Expert Elite Team

Lien vers le commentaire
Partager sur d’autres sites

Salut,

 

Voilà,

 

  1. Télécharger TestPoint3dTree.zip.
  2. Débloquer le zip.
  3. Extraire les deux DLLs dans un même répertoire.
  4. Depuis AutoCAD, charger uniquement TestPoint3dTree.dll.
  5. Utiliser les commandes suivantes pour tester :
    • GENPTS pour générer le nombre spécifié de points dans le rectangle (2d) ou la boite (3d) délimitée par deux points
    • TEST2D pour tester la recherche de points dans un arbre 2d (avec des points en 3d, les distances sont projetées sur le plan XY).
    • TEST3D pour tester la recherche de points dans un arbre 2d.

 

Il me reste à optimiser la recherche du (ou des) voisin(s) le(s) plus proche(s).

 

Actuellement cette recherche est plus rapide dans le coin inférieur gauche que dans le coin supérieur droit...

Gilles Chanteau - gileCAD -
Développements sur mesure pour AutoCAD
ADSK_Expert_Elite_Icon_S_Color_Blk_125.png

Lien vers le commentaire
Partager sur d’autres sites

Hello Grand Maitre Gilles (Le Docteur Strange d'AutoCAD)

 

1) MERCI et donc je vais telecharger et tester des que possible ...

http://gilecad.azurewebsites.net/dotNet.html

 

2) Au fait est ce "exactement" ce que j'avais demande ?

Car en fait ces recherches sont de l'analyse spatiale pour le monde du SIG ...

 

3) Ta derniere phrase ("Actuellement cette recherche ...") me laisse PERPLEXE !

 

Bye, lecrabe

Autodesk Expert Elite Team

Lien vers le commentaire
Partager sur d’autres sites

2) Au fait est ce "exactement" ce que j'avais demande ?

Car en fait ces recherches sont de l'analyse spatiale pour le monde du SIG ...

 

Pas exactement, c'est vite adapté de la commande de test dont je me sers.

Les commandes ne fonctionnent, en l'état, qu'avec des points.

L'arbre est construit une seule fois au premier appel de la commande.

Les commandes proposent 3 options : Distance, Nombre, Plage.

Pour chaque point trouvé, une entité point est dessinée sur le calque "POINT_3D_TREE" (rouge).

Les temps et nombre de points sont affichés en ligne de commande.

Gilles Chanteau - gileCAD -
Développements sur mesure pour AutoCAD
ADSK_Expert_Elite_Icon_S_Color_Blk_125.png

Lien vers le commentaire
Partager sur d’autres sites

Hello Gilles

 

Desole mais je n'arrive a RIEN !

 

- ZIP decompresse et obtention d'un fichier DLL "Point3dTree.dll" (et non pas "TestPoint3dTree.dll")

- Chargement avec NETLOAD dans mon MAP 2017 x64 : aucune erreur

- Mais aucune commande: genpts ou test2d ou test3d

 

Mais je suis peut etre "fatigue" cet AM !?

 

Bye, lecrabe

Autodesk Expert Elite Team

Lien vers le commentaire
Partager sur d’autres sites

Hello Gilles

 

En effet avec TON lien, cela fonctionne tout de suite mieux !

 

Sur un fichier d'environ 9200 points 2D et 3D (Leve de Rue en Long),

la commande TEST2D ou TEST3D offre un resultat instantanee !!

 

Ce qui necessite "un peu de temps", en fait c le dessin des N points sur le calque "POINT_3D_TREE"

 

Par exemple sur la commande TEST3D et 5000 points (sur les 9200 de mon dessin de test)

j'ai le resultat et 5000 points dessines en environ 0.5 seconde !!!

 

SVP (dans un moment de folle generosite)

serait il possible d'avoir la petite adaptation que j'ai demandee ??

Pouvoir passer par une selection AutoCAD classique et recuperer le XYZ des POINTs et BLOCs

et Selectionner les POINTs et BLOCs concernes en sortie ...

 

MERCI, Bye, lecrabe

Autodesk Expert Elite Team

Lien vers le commentaire
Partager sur d’autres sites

Salut,

 

J'ai réussi à corriger le déséquilibre dans les recherches de points voisins, les téléchargements sont à jour.

 

@lecrabe,

 

Je vais essayer de te faire ça.

Donc, si j'ai bien compris, on reconstruit l'arbre à chaque sélection de points ou blocs.

Récupérer les coordonnées, certes, mais comment ? dans la fenêtre de texte ? dans un fichier ? avec quelle précision ?

Sélectionner les points ou blocs, là ça va être plus long, l'arbre utilise uniquement les points (coordonnées), pas les entités, il va donc falloir les retrouver...

Gilles Chanteau - gileCAD -
Développements sur mesure pour AutoCAD
ADSK_Expert_Elite_Icon_S_Color_Blk_125.png

Lien vers le commentaire
Partager sur d’autres sites

Hello Gilles

 

>>> Récupérer les coordonnées, certes, mais comment ? dans la fenêtre de texte ? dans un fichier ? avec quelle précision ?

Signifiait pour moi, recuperer les Coords XYZ pour les mettre dans l'arbre ...

( Je n'ai absolument pas besoin de recuperer ces Coords XYZ )

 

Peux tu "peut etre" dans ton arbre ajouter l'ObjectId des entites AutoCAD

ainsi a la sortie, ce sera facile de construire la selection des Points et Blocs concernes !

 

Tu pourrais garder l'arbre et les ObjectId et demander au lancement

si on veut "simplement" re-utiliser l'arbre precedent

et non pas refaire une nouvelle selection et donc reconstruire l'arbre ...

 

Voila mes reflexions ...

 

Bye, lecrabe

Autodesk Expert Elite Team

Lien vers le commentaire
Partager sur d’autres sites

Hello Gilles

 

1) Sur mon fichier de test (46000 points graphiques) ton SELNN semble bien marcher !

 

2) Pas encore teste sur des Blocs ou un melange de Points ET Blocs !?

Mais j'ai confiance en notre "Fabuleux Docteur Strange du Monde AutoCAD" !

 

MERCI, Bye, lecrabe

Autodesk Expert Elite Team

Lien vers le commentaire
Partager sur d’autres sites

Créer un compte ou se connecter pour commenter

Vous devez être membre afin de pouvoir déposer un commentaire

Créer un compte

Créez un compte sur notre communauté. C’est facile !

Créer un nouveau compte

Se connecter

Vous avez déjà un compte ? Connectez-vous ici.

Connectez-vous maintenant
×
×
  • Créer...

Information importante

Nous avons placé des cookies sur votre appareil pour aider à améliorer ce site. Vous pouvez choisir d’ajuster vos paramètres de cookie, sinon nous supposerons que vous êtes d’accord pour continuer. Politique de confidentialité