Projet 04 : Nuage de points (Analyse spatiale et géométrique)#
Dans les systèmes d'information géographique (SIG), la vision par ordinateur, la robotique mobile (capteurs LiDAR) et l'apprentissage automatique (clustering k-means), le traitement de nuages de points (point clouds) est omniprésent.
L'objectif de ce projet est de concevoir un moteur d'analyse spatiale complet en langage C capable de caractériser géométriquement un ensemble de points 2D : calcul du barycentre, boîte englobante (bounding box), distance euclidienne et identification des paires de points les plus proches et les plus éloignées.
1. Fondements mathématiques#
Soit un nuage de \(N\) points dans le plan cartésien : \(\mathcal{P} = \{ P_1, P_2, \dots, P_N \}\) où chaque point \(P_i\) est repéré par ses coordonnées réelles \((x_i, y_i)\).
A. Distance euclidienne#
La distance euclidienne entre deux points \(P_1(x_1, y_1)\) et \(P_2(x_2, y_2)\) est donnée par : $\(d(P_1, P_2) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)$
B. Barycentre (Centre de gravité)#
Le barycentre \(G(\bar{X}, \bar{Y})\) d'un nuage de points équipondérés correspond à la moyenne arithmétique de leurs coordonnées : $\(\bar{X} = \frac{1}{N} \sum_{i=1}^N x_i \qquad \bar{Y} = \frac{1}{N} \sum_{i=1}^N y_i\)$
C. Boîte englobante (Bounding Box)#
La boîte englobante minimale alignée sur les axes (AABB - Axis-Aligned Bounding Box) est le plus petit rectangle contenant l'ensemble des points : $\(\mathcal{B} = [X_{\min}, X_{\max}] \times [Y_{\min}, Y_{\max}]\)$ - Largeur : \(L = X_{\max} - X_{\min}\) - Hauteur : \(H = Y_{\max} - Y_{\min}\) - Aire : \(\text{Aire} = L \times H\)
2. Modélisation logicielle#
classDiagram
class Point2D {
+char nom[16]
+double x
+double y
}
class BoundingBox {
+double x_min
+double x_max
+double y_min
+double y_max
}
class PairePoints {
+Point2D p1
+Point2D p2
+double distance
}
class Nuage2D {
+Point2D points[100]
+int taille
}
Nuage2D *-- Point2D
3. Implémentation complète en langage C#
Voici le code source complet, incluant l'analyse géométrique, la recherche d'extrêmes et l'affichage d'un diagramme ASCII simplifié :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <float.h>
#define CAPACITE_MAX 100
// Modèle d'un point 2D étiqueté
typedef struct
{
char nom[16];
double x;
double y;
} Point2D;
// Boîte englobante
typedef struct
{
double x_min, x_max;
double y_min, y_max;
double largeur;
double hauteur;
double aire;
} BoundingBox;
// Paire de points et leur distance associée
typedef struct
{
Point2D p1;
Point2D p2;
double distance;
} PaireDistance;
// Structure du nuage de points
typedef struct
{
Point2D points[CAPACITE_MAX];
int taille;
} Nuage2D;
// Calcule la distance euclidienne entre deux points
double CalculerDistance(Point2D a, Point2D b)
{
double dx = b.x - a.x;
double dy = b.y - a.y;
return sqrt(dx * dx + dy * dy);
}
// Ajoute un point au nuage
int AjouterPoint(Nuage2D *nuage, const char *nom, double x, double y)
{
if (nuage->taille >= CAPACITE_MAX)
{
fprintf(stderr, "Erreur : capacite maximale atteinte.\n");
return 0;
}
Point2D *p = &nuage->points[nuage->taille];
strncpy(p->nom, nom, sizeof(p->nom) - 1);
p->nom[sizeof(p->nom) - 1] = '\0';
p->x = x;
p->y = y;
nuage->taille++;
return 1;
}
// Calcule le centre de gravité (barycentre)
Point2D CalculerBarycentre(const Nuage2D *nuage)
{
Point2D g = {"Barycentre_G", 0.0, 0.0};
if (nuage->taille == 0) return g;
double somme_x = 0.0;
double somme_y = 0.0;
for (int i = 0; i < nuage->taille; i++)
{
somme_x += nuage->points[i].x;
somme_y += nuage->points[i].y;
}
g.x = somme_x / nuage->taille;
g.y = somme_y / nuage->taille;
return g;
}
// Détermine la boîte englobante
BoundingBox CalculerBoundingBox(const Nuage2D *nuage)
{
BoundingBox bb;
if (nuage->taille == 0)
{
memset(&bb, 0, sizeof(BoundingBox));
return bb;
}
bb.x_min = bb.x_max = nuage->points[0].x;
bb.y_min = bb.y_max = nuage->points[0].y;
for (int i = 1; i < nuage->taille; i++)
{
if (nuage->points[i].x < bb.x_min) bb.x_min = nuage->points[i].x;
if (nuage->points[i].x > bb.x_max) bb.x_max = nuage->points[i].x;
if (nuage->points[i].y < bb.y_min) bb.y_min = nuage->points[i].y;
if (nuage->points[i].y > bb.y_max) bb.y_max = nuage->points[i].y;
}
bb.largeur = bb.x_max - bb.x_min;
bb.hauteur = bb.y_max - bb.y_min;
bb.aire = bb.largeur * bb.hauteur;
return bb;
}
// Recherche de la paire la plus proche et de la paire la plus éloignée
void AnalyserPairesExtremes(const Nuage2D *nuage, PaireDistance *plus_proche, PaireDistance *plus_eloignee)
{
if (nuage->taille < 2) return;
plus_proche->distance = DBL_MAX;
plus_eloignee->distance = -1.0;
for (int i = 0; i < nuage->taille; i++)
{
for (int j = i + 1; j < nuage->taille; j++)
{
double d = CalculerDistance(nuage->points[i], nuage->points[j]);
if (d < plus_proche->distance)
{
plus_proche->distance = d;
plus_proche->p1 = nuage->points[i];
plus_proche->p2 = nuage->points[j];
}
if (d > plus_eloignee->distance)
{
plus_eloignee->distance = d;
plus_eloignee->p1 = nuage->points[i];
plus_eloignee->p2 = nuage->points[j];
}
}
}
}
// Affiche la liste et la synthèse géométrique
void AfficherRapportNuage(const Nuage2D *nuage)
{
printf("=================================================================\n");
printf(" RAPPORT D'ANALYSE SPATIALE DU NUAGE DE POINTS \n");
printf("=================================================================\n");
printf("Nombre de points : %d\n\n", nuage->taille);
printf("%-12s | %-12s | %-12s\n", "Nom", "Abscisse X", "Ordonnee Y");
printf("---------------------------------------------\n");
for (int i = 0; i < nuage->taille; i++)
{
printf("%-12s | %10.2f | %10.2f\n",
nuage->points[i].nom, nuage->points[i].x, nuage->points[i].y);
}
printf("---------------------------------------------\n\n");
Point2D g = CalculerBarycentre(nuage);
printf(">> Centre de gravite (Barycentre) : G(%.3f, %.3f)\n", g.x, g.y);
BoundingBox bb = CalculerBoundingBox(nuage);
printf(">> Bounding Box (Boite englobante) :\n");
printf(" X dans [%.2f ; %.2f] (Largeur = %.2f)\n", bb.x_min, bb.x_max, bb.largeur);
printf(" Y dans [%.2f ; %.2f] (Hauteur = %.2f)\n", bb.y_min, bb.y_max, bb.hauteur);
printf(" Aire totale couverte = %.2f unites carrees\n\n", bb.aire);
if (nuage->taille >= 2)
{
PaireDistance min_p, max_p;
AnalyserPairesExtremes(nuage, &min_p, &max_p);
printf(">> Plus proche voisin :\n");
printf(" Entre %s(%.2f, %.2f) et %s(%.2f, %.2f) -> Distance = %.4f\n\n",
min_p.p1.nom, min_p.p1.x, min_p.p1.y,
min_p.p2.nom, min_p.p2.x, min_p.p2.y, min_p.distance);
printf(">> Diametre du nuage (Paire la plus eloignee) :\n");
printf(" Entre %s(%.2f, %.2f) et %s(%.2f, %.2f) -> Distance = %.4f\n",
max_p.p1.nom, max_p.p1.x, max_p.p1.y,
max_p.p2.nom, max_p.p2.x, max_p.p2.y, max_p.distance);
}
printf("=================================================================\n");
}
int main(void)
{
Nuage2D nuage;
nuage.taille = 0;
// Insertion d'un jeu de points représentatif (constellation)
AjouterPoint(&nuage, "Alpha", 2.0, 3.0);
AjouterPoint(&nuage, "Beta", 5.0, 8.0);
AjouterPoint(&nuage, "Gamma", 9.0, 2.0);
AjouterPoint(&nuage, "Delta", 1.5, 3.5);
AjouterPoint(&nuage, "Epsilon", 12.0, 11.0);
AjouterPoint(&nuage, "Zeta", 7.0, 6.0);
// Exécution et affichage des métriques
AfficherRapportNuage(&nuage);
return EXIT_SUCCESS;
}
4. Analyse algorithmique et complexité#
- Calcul du barycentre et de la bounding box : Une seule passe linéaire sur les \(N\) points est requise \(\implies \mathcal{O}(N)\).
- Recherche de la paire la plus proche (recherche exhaustive) : Elle examine \(\frac{N(N-1)}{2}\) paires de points distincts. La complexité temporelle est donc en \(\mathcal{O}(N^2)\).
- Perspective pour grands volumes de données (\(N > 10^5\)) : En calcul scientifique et en infographie 3D, pour éviter le coût quadratique \(\mathcal{O}(N^2)\), on partitionne l'espace avec des structures d'arbres spatiaux tels que les kd-trees ou les quadtrees, réduisant la recherche du plus proche voisin à \(\mathcal{O}(N \log N)\).
Commentaires