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

[(gile)]

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.

[Goldorak44]

Salut Gile,

 

Beau boulot. Merci pour le partage.

 

;)

[lecrabe]

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

[(gile)]

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

[lecrabe]

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

[(gile)]

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.

[lecrabe]

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

[(gile)]

C'est le lien dans la réponse #4 qui ne fonctionne pas.

 

Je le redonne ici : TestPoint3dTree.zip

[lecrabe]

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

[(gile)]

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

[lecrabe]

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

[(gile)]

Voilà.

 

Télécharger SelectNeighbors.zip.

Débloquer le ZIP.

Extraire les DLLs dans un même répertoire.

Netloader SelectNeighbors.dll.

Lancer les commandes SEL_NN_2D ou SEL_NN_3D.

[lecrabe]

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