Discussion :

[Sve@r]

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

[dourouc05]

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

[Flodelarab]

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.

[wiwaxia]

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 = s^1/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/a²) = (N*k²*d²)/(La*Ha) = k² , 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.

[Sve@r]

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

Je n'ai pas la réponse.

Pas grave - Merci d'être venu m'apporter ton soutien moral

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

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 n^1/2 cela veut bien dire "n exposant 1/2" donc "racine carrée de n" n'est-ce pas ?

Merci de ta participation

[wiwaxia]

... Mais quand tu écris une formule style n^1/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 (51² - 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:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

 ... Inc(v, 15)

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.

[Sve@r]

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

[wiwaxia]

Bonsoir,

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

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

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

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

[Nebulix]

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

[wiwaxia]

... 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 c_m = 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 = (N_i/S_i) sur un "petit" domaine centré en (x, y), de dimension nettement supérieure à la distance moyenne entre les points
d_m = (La*Ha/N)^1/2 = c_m^-1/2 ,
mais cependant très inférieure à la dimension minimale caractérisant l'image D_im = Min(La, Ha) .
D'où la nécessité du meilleur compromis vérifiant d_m << D_dom << D_im , 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 (N_c) 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: L_g = La/a , H_g = Ha/a .
Le procédé requiert en principe le calcul d'une concentration pour chaque case (c_ij = N_ij/a²),
soit au total: N_c = L_g*H_g = La*Ha/a² .
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 (D_c = 2*r_c) 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.

[Nebulix]

@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,

[wiwaxia]

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

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

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.

[Sve@r]

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.

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.