IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Trouver des bulles de densité dans un nuage de points


Sujet :

Algorithmes et structures de données

  1. #1
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut Trouver des bulles de densité dans un nuage de points
    Bonjour

    Ma question est toute simple: j'ai un nuage de points en 2D (de l'ordre de 100000 points) et il faut que j'arrive à identifier les zones du plan contenant une concentration plus forte que d'autres zones.

    Et je n'ai absolument aucune idée de la façon de procéder.

    Désolé d'être aussi flou, je le suis tout autant pour ce sujet...

    Bien Cordialement
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    Août 2008
    Messages
    26 609
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2008
    Messages : 26 609
    Points : 188 580
    Points
    188 580
    Par défaut


    Une solution bourrine : tu découpes ton espace en blocs 3D (à la manière d'un octree), tu vois dans lesquels tu as le plus de points (peut-être afficher sur une courbe les nombres de points par bloc, triés par ordre croissant ? tu devrais y avoir un coude à un moment, donc un seuil pour déterminer à partir de quand un bloc comporte "beaucoup" de points).
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    Par défaut
    Bonjour

    Je n'ai pas la réponse.

    Ne peux-tu pas faire une dichotomie ?
    Chaque fois que tu partages ton espace en deux, les 2 morceaux sont de tailles égales.
    Tu peux savoir quelle zone est la plus dense.
    Et tu recommences.

    Tu dois pouvoir trouver des centres de concentration.

    Après, il faudrait savoir si tu as besoin de l'enveloppe de cette zone.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  4. #4
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Trouver des bulles de densité dans un nuage de points
    Bonjour,

    Il faut cerner la limite du découpage de la zone contenant le nuage de points, limite qui correspondra aux plus fins détails observables sur une carte densimétrique.
    Sur une image de dimensions (La, Ha) on peut attribuer à chacun des (N) points présents une aire élémentaire s = (La*Ha/N), d'où l'ordre de grandeur de la distance le séparant de ses plus proches voisins:
    d = s1/2 = (La*Ha/N)1/2 .

    Envisager à ce stade un découpage de l'image en (Nc) cases carrées d'arête a ~ k*d (avec k ~ 5 à 10), de sorte que l'on trouvera en moyenne dans chacune d'entre elles un nombre de points égal à
    N/Nc = N/(La*Ha/a2) = (N*k2*d2)/(La*Ha) = k2 , soit en moyenne 25 à 100 points.
    Il faut s'attendre à des concentrations locales plus élevées, culminant à 300 voire 500 points, mais cela reste représentable sur une échelle de couleur.

    Il faudra compter les points présents dans chaque case, et mémoriser les résultats dans une matrice d'entiers pour des calculs annexes (recherche du maximum, choix d'un facteur de conversion en couleurs) - la mémorisation peut éventuellement se faire sur une image bitmap, au niveau de la couleur locale, par un dénombrement dans une base appropriée.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  5. #5
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par dourouc05 Voir le message
    Une solution bourrine
    J'adore
    Surtout que j'ai envisagée mon propre bourrinage: itérer sur chacun des points, lui attribuer un cercle de rayon "r" ("r" à combien j'en sais encore trop rien) et compter combien d'autres points j'y trouve et trier ensuite l'ensemble des résultats...

    Citation Envoyé par Flodelarab Voir le message
    Je n'ai pas la réponse.
    Pas grave - Merci d'être venu m'apporter ton soutien moral

    Citation Envoyé par Flodelarab Voir le message
    Ne peux-tu pas faire une dichotomie ?
    Oui, pourquoi pas. Pour l'instant étant au plus bas niveau du bouzin je peux envisager ce que je veux

    Citation Envoyé par wiwaxia Voir le message
    Il faut......par un dénombrement dans une base appropriée.
    Là bravo. Ca a l'air très poussé. Je vais prendre le temps de tout bien relire au calme. Mais quand tu écris une formule style n1/2 cela veut bien dire "n exposant 1/2" donc "racine carrée de n" n'est-ce pas ?

    Merci de ta participation
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  6. #6
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Trouver des bulles de densité dans un nuage de points
    Citation Envoyé par Sve@r Voir le message
    ... Mais quand tu écris une formule style n1/2 cela veut bien dire "n exposant 1/2" donc "racine carrée de n" n'est-ce pas ? ...
    Oui, tout à fait.

    la mémorisation peut éventuellement se faire sur une image bitmap, au niveau de la couleur locale, par un dénombrement dans une base appropriée.
    Effectivement, en voulant être bref, je n'ai pas été clair du tout .
    Je voulais dire par là: mémoriser tout résultat provisoire du comptage à l'aide des composantes de la couleur locale, au niveau de la case concernée, par exemple en codant pour tout nouveau point détecté:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    IF (r<251) THEN Inc(r, 5)
               ELSE BEGIN
                          r:= 0; Inc(v, 5)
                   END;
    ce qui revient à compter en base 51 et permet de dénombrer jusqu'à 2600 points (512 - 1).
    Le nombre correspondant s'obtient par les instructions:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    Npoint:= 5 * v; Inc(Npoint, 5 * r);
    L'ennui est que faute de connaître au préalable la plus grande valeur, on n'utilise qu'une petite partie de l'échelle et n'obtient que des couleurs sombres, peu contrastées.
    On peut y remédier par une petite modification:
    qui conduira à la valeur maximale: Npmax = (255/15)*51 + 50 = 917 .

    Un autre procédé permet de s'affranchir du quadrillage de la grille précédemment constituée des (Nc) cases. Sa mise en oeuvre est nettement plus lourde, bien qu'elle s'apparente à ce qui précède, et il vaut sans doute mieux que tu maîtrise ce qui a été donné avant de l'aborder.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  7. #7
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par wiwaxia Voir le message
    Bonjour,
    Salut

    J'ai bien relu, tout réécrit et j'ai enfin tout compris.

    On part de l'hypothèse que les points sont uniformément répartis. Donc effectivement, chaque point aura une surface propre de l'ordre de s = (La*Ha/N). Si on dit que cette surface est un carré, alors son côté "c" sera (La*Ha/N)1/2. Donc effectivement, deux points seront espacés d'un côté donc d (distance moyenne) = c = (La*Ha/N)1/2. Et d²=La*Ha/N=s

    En découpant le plan en Nc cases, alors chaque case aura une surface égale à LaHa/Nc. Et si on dit que chaque case a un côté "a", alors chaque case a une surface égale à a². D'où a²=La*Ha/Nc

    Ensuite on prend la distance moyenne "d" comme unité. Et on dit que chaque Nc case aura une taille de "k" unités. Donc chaque case aura un côté égal à "kd" et une surface égale à k²d² = k²*La*Ha/N.
    Mais comme a²=k²d² alors La*Ha/Nc=k²*La*HA/N. On simplifie par La*Ha ce qui donne 1/Nc=k²/N ou (en multipliant par N) N/Nc=k². Et comme N est le nombre de points, alors k²=N/Nc est le nombre de points moyen par case. Et comme c'est moi qui choisit "k" alors c'est moi qui décide combien de points moyen je veux avoir. Joli
    Je vais partir sur cet algorithme.

    En revanche je n'ai rien pigé sur la base 51. Mais je ne travaille pas sur une image bitmap
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  8. #8
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Trouver des bulles de densité dans un nuage de points
    Bonsoir,

    Citation Envoyé par Sve@r Voir le message
    ... J'ai bien relu, tout réécrit et j'ai enfin tout compris ...
    Ravi de vois un lecteur refaire les calculs, stylo en main, pour les comprendre.

    Citation Envoyé par Sve@r Voir le message
    ... On part de l'hypothèse que les points sont uniformément répartis. Donc effectivement, chaque point aura une surface propre de l'ordre de s = (La*Ha/N). Si on dit que cette surface est un carré, alors son côté "c" sera (La*Ha/N)1/2 ...
    Ce modèle simpliste est très éloigné de la réalité, mais a le mérite de conduire à une ordre de grandeur pour la distance (d).

    Citation Envoyé par Sve@r Voir le message
    ... Mais comme a²=k²d² alors La*Ha/Nc=k²*La*HA/N. On simplifie par La*Ha ce qui donne 1/Nc=k²/N ou (en multipliant par N) N/Nc=k². Et comme N est le nombre de points, alors k²=N/Nc est le nombre de points moyen par case. Et comme c'est moi qui choisit "k" alors c'est moi qui décide combien de points moyen je veux avoir ...
    L'arête (a) des cases doit être un diviseur commun aux dimensions (La, Ha) de l'image.

    Citation Envoyé par Sve@r Voir le message
    ... En revanche je n'ai rien pigé sur la base 51 ...
    Pas grave, c'est un détail secondaire.
    Tu comprendras si tu reviens plus tard sur ce sujet (255 = 5*51, entre autres).


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  9. #9
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par wiwaxia Voir le message
    Ravi de vois un lecteur refaire les calculs, stylo en main, pour les comprendre.
    C'est un peu la base quand on pose une question que de lire une réponse, surtout quand elle semble (après une première lecture superficielle) avoir du sens
    J'ai trop répondu, et surtout trop eu de PO qui ne lisent pas les réponses (dernier exemple ici) pour ne pas savoir ce qu'on ressent quand on se casse le fion à répondre (et une réponse travaillée avec des formules écrites avec soin ) et qu'on voit l'abruti d'en face ne faire aucun effort de son côté
    Ceci dit, j'ai aussi appris à écrire des formules

    Citation Envoyé par wiwaxia Voir le message
    L'arête (a) des cases doit être un diviseur commun aux dimensions (La, Ha) de l'image.
    Là ce n'est pas possible car ça signifie que La*Ha/a est un entier. Or a=kd et d=(La*Ha/N)1/2. Ca veut dire que La*Ha/(k*(La*Ha/N)1/2) qui se réduit en (La*Ha/N)1/2/k est un entier. Or je ne maitrise ni les dimensions, ni N (et j'avais fait l'hypothèse que k était entier).


    Citation Envoyé par wiwaxia Voir le message
    Tu comprendras si tu reviens plus tard sur ce sujet (255 = 5*51, entre autres).
    Moui. C'est égal à 3*5*17. On peut donc utiliser aussi la base 15 ou 17 ou 85 ? Base 15 ou 17 je peux appréhender. Mais bosser en base 51 ou 85
    Toutefois je te le redis je ne bosse pas sur une bitmap. En fait je bosse sur un shape géographique et mes points sont des coordonnées. Sauf que je dois afficher des bulles de densité de points et non les points eux-mêmes...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  10. #10
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Trouver des bulles de densité dans un nuage de points
    Citation Envoyé par Sve@r Voir le message
    C'est un peu la base ... que de lire une réponse, surtout quand elle semble (après une première lecture superficielle) avoir du sens ...
    Très flatté

    Citation Envoyé par Sve@r Voir le message
    ... Ceci dit, j'ai aussi appris à écrire des formules ...
    Alors tant mieux, c'est encourageant.
    La typographie me donnait aussi beaucoup de mal, au début; je peux maintenant mener de front le calcul mental et la frappe du texte - ce qui n'élimine pas les coquilles dues aux verres progressifs .
    Le peu d'expérience que j'ai d'autres sites apparentés m'a montré qu'on dispose ici de moyens de très bonne qualité.

    Citation Envoyé par Sve@r Voir le message
    ... Toutefois je te le redis je ne bosse pas sur une bitmap. En fait je bosse sur un shape géographique et mes points sont des coordonnées. Sauf que je dois afficher des bulles de densité de points et non les points eux-mêmes ...
    Laisse tomber le bricolage des couleurs, ce sont de faux problèmes.
    Je vois mieux ce que tu cherches, on peut reprendre le sujet plus tard.
    Des précisions simplement: qu'est-ce que c'est qu'un shape géographique ? Mon ignorance est totale sur ce sujet.
    Disposes-tu de la liste séparée des positions des points (en longitude/latitude) ? Les plus grandes distances restent-elles raisonnablement limités (< 5000 km) ?


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  11. #11
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    J'ai fait quelques tests, et voici ce que ça donne.
    J'ai 55000 points dans mon cas répartis grosso-modo dans des bulles... Mes points Blancs ont des coordonnées entières, mais peu importe. Ce qui compte, ce que mes points ont des coordonnées entre 0 et 1000.
    Je crée un tableau de 1000*1000, et pour chaque élément de ce tableau, j'attribue une note (un niveau)
    - Option 1 : en comptant les points blancs à une distance inférieure à 10
    - Option 2 : en comptant les points blancs à une distance inférieure à 10, mais en faisant un dégradé : un point blanc tout proche rapporte plus qu'un point blanc un peu plus éloigné.
    C'est cette option 2 que j'ai retenue.

    J'obtiens ainsi pour les 1000*1000 éléments de mon tableau un certain niveau (une altitude). Et je vais tracé des courbes de niveau. Mon niveau est une variable 'continue', puisque je n'ai pas simplement compté les points (option 1), mais j'ai appliqué un dégradé (option2).
    Pour tracer une courbe de niveau, niveau=4.5 par exemple, Je prend chaque point qui a un niveau supérieur ou égal à 4.5, et je regarde parmi ses 4 voisins directs s'il a un voisin avec un niveau strictement inférieur à 4.5. Si oui, ce point est sur ma bordure, et si non, ce point n'est pas sur la bordure. (il est donc à l'intérieur de la bulle, puisque son niveau est supérieur au seuil).

    Le dessin ci-dessous est obtenue en prenant 2 courbes de niveau (niveau 3.9 et 4.9 dans mon cas...)
    Nom : image_contours_rayon11.jpg
Affichages : 1366
Taille : 347,9 Ko


    En modifiant un peu ma fonction 'dégradé' , et en prenant des cercles de rayon 13 au lieu de 10, j'obtiens des contours plus lisses. Ici, chaque point blanc est remplacé par un cône de base circulaire, de rayon 13 et de hauteur 13. Quand 2 cônes se chevauchent, les hauteurs se cumulent. Et le tracé rouge correspond à la courbe de niveau 55. Nom : image_contours_rayon13.jpg
Affichages : 1355
Taille : 352,3 Ko
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  12. #12
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par wiwaxia Voir le message
    Des précisions simplement: qu'est-ce que c'est qu'un shape géographique ? Mon ignorance est totale sur ce sujet.
    Disposes-tu de la liste séparée des positions des points (en longitude/latitude) ? Les plus grandes distances restent-elles raisonnablement limités (< 5000 km) ?
    Un shape c'est un fichier vecteur d'extension "shp" contenant toute un série d'informations géométriques telles que le point, la ligne et es polygones. Il permet ainsi de représenter une carte géographique.

    Mes points sont stockés de façon indépendante dans une bdd et sont tous très rapprochés les uns des autres (distance moyenne de l'odre de 30km).

    Citation Envoyé par tbc92 Voir le message
    J'ai 55000 points dans mon cas... Je crée un tableau de 1000*1000, et pour chaque élément de ce tableau, j'attribue une note (un niveau) en comptant les points blancs à une distance inférieure à 10.
    Donc pour chacun des 1000*1000 pixels de ton tableau, tu as regardé combien il y avait, parmis les 55000 points, de points situés à une distance inférieure à 10. Ce qui fait 1000*1000*55000 calculs soit 55 milliards de calculs. Je me trompe ???

    Citation Envoyé par tbc92 Voir le message
    Pour tracer une courbe de niveau, niveau=4.5 par exemple, Je prend chaque point qui a un niveau supérieur ou égal à 4.5, et je regarde parmi ses 4 voisins directs s'il a un voisin avec un niveau strictement inférieur à 4.5.
    Pourquoi "4" voisins ? Les voisins Nord, Sud, Est, Ouest ? Donc ça signifie que chaque point connait chacun de ses 4 voisins ???

    J'ai oublié de dire qu'il fallait que ça soit (assez) rapide. Style j'affiche une carte et j'ai les bulles qui apparaissent dans la seconde (ou les deux secondes).

    En tout cas ton dessin est magnifique. J'aimerais savoir quel outil tu utilises pour le générer.
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  13. #13
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    Décembre 2013
    Messages
    4 038
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : Décembre 2013
    Messages : 4 038
    Points : 9 347
    Points
    9 347
    Par défaut
    Les 4 voisins.... Je ne parle pas ici des 55000 pts 'aléatoires' du début, je parle du tableau de 1024x1024 pixels que je génère. Les 4 voisins sont donc triviaux.
    En temps de traitement, on n'est pas en secondes, mais 3 ou 4 minutes avec SQLServer (je découvre, et j'ai utilisé ce sujet pour me 'former'). Je détermine tous les pixels qui sont sur la bordure par 2 requêtes:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    insert into niveau (x,y,niv)
    	select x.n, y.n , sum (13.0 - sqrt ( (x.n-p.x)*(x.n-p.x)+(y.n-p.y)*(y.n-p.y)    ) ) 
    	from nnn as x, nnn as y , points as p 
    	where (x.n-p.x)*(x.n-p.x)+(y.n-p.y)*(y.n-p.y) < 169
    	  and p.x between x.n-13 and x.n+13
    	  and p.y between y.n-13 and y.n+13
    	group by x.n,y.n
    nnn est une table qui contient 1024 lignes (les nombres de 0 à 1023) ; Points est une table qui contient les 55000 points initiaux. Cette requête donne une certaine altitude pour chacun des 1024*1024 pixels.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    insert into bordure ( x, y  )
    	select a.x, a.y 
    	from niveau a with ( index ( pk2_niveau)) 
    	cross apply ( select    top 1 b.x, b.y from niveau b with ( index ( pk_niveau)) 
    	where b.niv < 55  
    	and b.x between a.x-1 and a.x+1  
    	and b.y between a.y-1 and a.y+1   
    	and abs(b.x-a.x) + abs(b.y-a.y) = 1  ) bb
    where a.niv >= 55
    Et cette 2ème requête détermine les pixels qui sont à la frontière.
    Reste plus qu'à mettre tout dans une image... et je fais ça avec le seul outil que je maîtrise vraiment, Windev.

    Si les 55000 points sont fixes, il y a un traitement préliminaire à faire pour déterminer la bordure correspondante. Et on n'a plus qu'à afficher la portion de bordure qui nous intéresse, selon la partie de carte affichée.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  14. #14
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Bonjour,

    Le problème décrit ressemble vraiment beaucoup à du Multivariate kernel density estimation (M-KDE, en abrégé).

    La page wikipedia explique très bien le problème et les solutions (telle que le découpage en grille et les limitations qui vont avec).
    En pas de la page, dans les références, il y a des liens vers des bibliothèques/outils qui permettre de résoudre le problème sans trop d'effort.

    Cordialement,
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  15. #15
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Trouver des bulles de densité dans un nuage de points
    En partant de l'image d'un nuage de points, de dimensions 540x540, j'ai regardé ce que donnait l'association d'une grille comportant des cases de taille (a) croissante, supérieure à (dmoy) et divisant les dimensions (La, Ha) de l'image.

    Le nuage hâtivement improvisé (et peut-être pas de la meilleure façon ...) résulte de la superposition de deux ensemencements, l'un uniforme sur tout le domaine de l'image, l'autre confiné plus ou moins étroitement au voisinage d'une portion de courbe et dont l'effectif représente 30% du nombre total de points (ici égal à 50000).

    Nom : P=50000_540x540_0.300.png
Affichages : 706
Taille : 44,1 Ko

    La distance moyenne vaut 2.415 ; voici les quadrillages obtenus et les valeurs correspondantes des dimensions de la grille (Dg = Dim/a = 540/a) et de l'effectif maximal de points présents (EmaxC) - donnée indispensable à la définition de l'échelle de couleurs.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
       a       Dg    Emax    k = a/D<sub>m</sub>      k<sup>2</sup>
     
       3      180      17      1.242      1.543
       4      135      19      1.656      2.743
       5      108      29      2.070      4.287
       6       90      35      2.484      6.173
       9       60      63      3.727     13.888
      10       54      79      4.141     17.146
      12       45      96      4.969     24.690
      15       36     142      6.211     38.579
      18       30     194      7.453     55.553
    Nom : P=50000_A=3M=17.png
Affichages : 711
Taille : 54,2 Ko_Nom : P=50000_A=4M=19.png
Affichages : 738
Taille : 17,6 Ko_Nom : P=50000_A=5M=29.png
Affichages : 703
Taille : 29,6 Ko

    Nom : P=50000_A=6M=35.png
Affichages : 696
Taille : 11,1 Ko_Nom : P=50000_A=9M=63.png
Affichages : 709
Taille : 13,7 Ko_Nom : P=50000_A=10M=79.png
Affichages : 704
Taille : 6,5 Ko

    Nom : P=50000_A=12M=96.png
Affichages : 663
Taille : 5,2 Ko_Nom : P=50000_A=15M=142.png
Affichages : 722
Taille : 7,2 Ko_Nom : P=50000_A=18M=194.png
Affichages : 690
Taille : 3,4 Ko

    Le format a été réduit de moitié pour économie de place.

    Le point de départ de toutes les images est la liste des coordonnées des points; la grille est un tableau d'entiers au format Word:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     TYPE Ve2D    = RECORD  x, y: Z_32  END;
          LstVe2D = ARRAY[1..NmaxP] OF Ve2D;
          TabW    = ARRAY[0..NmaxC, 0..NmaxC] OF Word;
     
     VAR Nuage: LstVe2D;
         Grille: TabW;
    Les pixels de la nouvelle image se calculent rapidement, dans la mesure où l'échelle des couleurs a été préalablement effectuée sur liste séparée, pour tous les nombres de points du domaine [0 ; EmaxC].
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
          LstPix  = ARRAY[0..NmaxC] OF Pixel;
     
     VAR ... / ...
         ListeC: LstPix;
    À remarquer que, quelle que soit l'échelle, il n'apparaît aucune structure au niveau du bruit de fond.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  16. #16
    Membre expérimenté
    Profil pro
    chercheur
    Inscrit en
    Avril 2004
    Messages
    830
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Avril 2004
    Messages : 830
    Points : 1 453
    Points
    1 453
    Par défaut
    Citation Envoyé par Sve@r Voir le message
    ... les zones du plan ... une concentration plus forte
    Les premières questions à résoudre sont :
    Qu'est-ce qu'une "zone" ?
    Comment est définie la "concentration" dans une zone N ?
    Désolé de paraitre pisse-froid mais dans beaucoup de cas, une question mal formulée entraine une réponse tout à fait à côté de la plaque.
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  17. #17
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut Trouver des bulles de densité dans un nuage de points
    Citation Envoyé par Sve@r Voir le message
    ... Ma question est toute simple: j'ai un nuage de points en 2D (de l'ordre de 100000 points) et il faut que j'arrive à identifier les zones du plan contenant une concentration plus forte que d'autres zones ...
    La demande ne présente aucune ambiguïté: il s'agit ici de concentration surfacique, c'est-à-dire d'un nombre de points rapporté à l'unité de surface, ici le pixel en l'absence de toute référence physique (une distance géographique, par exemple).
    On observe ainsi sur l'image de dimensions (La*Ha) représentant un nuage de (N) points une concentration moyenne cm = N/(La*Ha) .

    En raison de la structure discontinue de l'objet décrit (le nuage), il n'est pas possible de définir la concentration locale au voisinage d'un point donné (x, y) comme en Physique c = (dN/dS), en recourant à des infiniment petits;
    on doit encore se limiter au calcul d'une concentration moyenne c = (Ni/Si) sur un "petit" domaine centré en (x, y), de dimension nettement supérieure à la distance moyenne entre les points
    dm = (La*Ha/N)1/2 = cm-1/2 ,
    mais cependant très inférieure à la dimension minimale caractérisant l'image Dim = Min(La, Ha) .
    D'où la nécessité du meilleur compromis vérifiant dm << Ddom << Dim , et se traduisant par un choix empirique.

    Deux solutions, entre autres, se présentent:

    1°) Le quadrillage à l'aide d'une grille constituée de (Nc) cases carrées, dont l'arête (a) divise (si possible) entièrement les dimensions (La, Ha) de l'image analysée,
    et présente pour dimensions propres: Lg = La/a , Hg = Ha/a .
    Le procédé requiert en principe le calcul d'une concentration pour chaque case (cij = Nij/a2),
    soit au total: Nc = Lg*Hg = La*Ha/a2 .
    C'est ce qui a été mis en oeuvre et longuement testé au message #15.

    2°) Le dénombrement (éventuellement pondéré) des points du nuage situés à l'intérieur d'un cercle centré en (x, y),
    et dont le diamètre (Dc = 2*rc) doit vérifier - comme (a) - les conditions évoquées plus haut.
    Le procédé, qui exige le calcul de la concentration locale en chacun des points de l'image, apparaît nettement plus lourd que le précédent, mais livre une bien meilleure représentation du nuage, continue et affranchie de tout quadrillage.

    Dans un cas comme dans l'autre, une fonction couleur appropriée (r, v, b) = F(c) permet de visualiser le comportement d'une fonction de deux variables (x, y), et de localiser sur le domaine de l'image les régions de forte densité.

    Là encore, la demande de recherche des "zones de plus forte concentration" exprimée par Sve@r est très claire, et les messages (#11, #14, #15) y répondent directement, chacun à leur manière.

    Une lecture attentive des échanges eût évité une remarque tout à fait à côté de la plaque .
    Intervention utile cependant, qui a suscité une mise au point peut-être utile à quelques uns (et en tous cas à moi-même), et me permettra de coder plus rapidement le second procédé si j'en ai le temps.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  18. #18
    Membre expérimenté
    Profil pro
    chercheur
    Inscrit en
    Avril 2004
    Messages
    830
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : Avril 2004
    Messages : 830
    Points : 1 453
    Points
    1 453
    Par défaut
    @wiwaxia (en toute camaraderie)
    La demande ne présente aucune ambiguïté...Deux solutions, entre autres, se présentent

    D'où la nécessité du meilleur compromis vérifiant dm << Ddom << Dim , et se traduisant par un choix empirique.
    Certaines ambiguïtés te paraissaient "évidentes", tu les a remplacées par l'objet que tu avais compris, presque sans t'en rendre compte. Dans beaucoup de cas çà peut marcher, mais en cas d'erreur çà peut mener à des catastrophes.
    Intervention utile cependant,
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  19. #19
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 333
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 333
    Points : 2 570
    Points
    2 570
    Billets dans le blog
    9
    Par défaut
    Citation Envoyé par Nebulix Voir le message
    @wiwaxia ... Certaines ambiguïtés te paraissaient "évidentes", tu les a remplacées par l'objet que tu avais compris, presque sans t'en rendre compte ...
    Tout le monde peut se tromper par défaut d'attention ou sous l'effet d'un à-priori, et je ne suis pas au-dessus de la condition commune.
    Mais puisque j'ai longuement répondu sur la question posée (sans prétendre en avoir fait le tour), quelles interprétations donnes-tu de ton côté de la demande initiale de Sve@r et quelles réponses pourrais-tu proposer ?
    C'est cela qui est intéressant.

    Citation Envoyé par Nebulix Voir le message
    ... Dans beaucoup de cas çà peut marcher, mais en cas d'erreur çà peut mener à des catastrophes ...
    En cas de réponse erronée ou inappropriée, les autres intervenants sont suffisamment nombreux, et ont toutes qualifications pour apporter les rectifications nécessaires. C'est la raison d'être et tout l'intérêt des échanges sur forum.
    Et puis n'exagérons rien: on ne gère pas une centrale nucléaire , et en cas d'erreur patente, je me consolerai aisément d'un froissement d'amour-propre. L'important n'est pas d'avoir raison, mais d'apporter quelque chose - l'expérience montrant qu'on y apprend simultanément beaucoup.

    Citation Envoyé par Nebulix Voir le message
    Les premières questions à résoudre sont :
    Qu'est-ce qu'une "zone" ?
    Comment est définie la "concentration" dans une zone N ? ...
    Pour parler vrai, j'ai trouvé ces questions choquantes, à la limite de la mauvaise foi.
    Rien de tel qu'une séries d'interrogations premières (qu'est-ce qu'un plan ? un point ? un nuage ?) pour désarçonner les interlocuteurs, et torpiller un débat à peu de frais.
    Lorsque l'on dit que la Voie Lactée est la région de ciel présentant une forte densité d'étoiles, cela est parfaitement compréhensible pour quiconque ayant observé le ciel nocturne.
    Les développements mathématiques à donner ensuite dépendront de la question posée, et des connaissances de la personne qui écoute.
    Sous ce rapport, toute réponse est un pari sur la compréhension et la curiosité du demandeur, puisqu'il faut passer du langage ordinaire (où les mots ont un sens souvent vague ou multiple) à celui des mathématiques et de la programmation.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  20. #20
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Nebulix Voir le message
    Les premières questions à résoudre sont :
    Qu'est-ce qu'une "zone" ?
    Comment est définie la "concentration" dans une zone N ?
    Citation Envoyé par wiwaxia Voir le message
    Pour parler vrai, j'ai trouvé ces questions choquantes, à la limite de la mauvaise foi.
    Rien de tel qu'une séries d'interrogations premières (qu'est-ce qu'un plan ? un point ? un nuage ?) pour désarçonner les interlocuteurs, et torpiller un débat à peu de frais.
    Lorsque l'on dit que la Voie Lactée est la région de ciel présentant une forte densité d'étoiles, cela est parfaitement compréhensible pour quiconque ayant observé le ciel nocturne.
    Les développements mathématiques à donner ensuite dépendront de la question posée, et des connaissances de la personne qui écoute.
    Sous ce rapport, toute réponse est un pari sur la compréhension et la curiosité du demandeur, puisqu'il faut passer du langage ordinaire (où les mots ont un sens souvent vague ou multiple) à celui des mathématiques et de la programmation.
    Je suis assez d'accord. J'ai trouvé que tes questions étaient du pinaillage et je suis content de ne pas être le seul. Mais bon, toute question (même de cette nature) mérite réponse donc si on imagine un cadran de montre (montre à aiguilles) avec 150 points situés dans le triangle formé par le centre, le chiffre 1 et le chiffre 2 ; et 10 points situés dans le reste du cadran, ma question était "comment détecter cette concentration de 150 points" (attention, il s'agit ici d'une illustration de la question et non de conditions réelles car je ne travaille pas sur un plan en forme de montre mais bon, si on arrive à trouver cette concentration sur une surface en forme de disque, je présume qu'on arrivera à trouver cette concentration sur n'importe quelle surface plane). Et j'ai eu dans l'ensemble des réponses de grande qualité. Et j'ai vu avec surprise que ce topic, que je pensais inintéressant pour une grande majorité, attirait au contraire beaucoup de gens motivés qui se sont donnés la peine de carrément programmer des jeux d'essais pour montrer des résultats assez artistiques.
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

Discussions similaires

  1. Trouver des valeurs non uniques dans une table
    Par morbli dans le forum Langage SQL
    Réponses: 11
    Dernier message: 29/09/2011, 12h56
  2. [Débutant] Trouver des suites de nombres dans un vecteur
    Par Drastalouf dans le forum MATLAB
    Réponses: 1
    Dernier message: 01/06/2010, 23h34
  3. [Débutant] Insérer des noms dans un nuage de points.
    Par darkalex54 dans le forum MATLAB
    Réponses: 4
    Dernier message: 21/04/2010, 11h07
  4. Réponses: 10
    Dernier message: 05/03/2010, 15h37
  5. Détection des phases dans un nuage de point
    Par Victhestatic dans le forum Signal
    Réponses: 2
    Dernier message: 19/01/2010, 12h33

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo