Programmations

INSA de LYON

Premier Cycle Deuxième Année

DS MODULE “ PROGRAMMATIONS ” 8 Juin 1998

Durée: 3 heures - Tous les documents sont autorisés

PARTIE  BASE DE DONNEES (10 points)
Après avoir étudié les schémas ci-joints (voir la page 6 du sujet), répondre aux questions suivantes. Pour les expressions de l’algèbre relationnelle, on pourra utiliser indifféremment les noms des attributs ou les numéros des colonnes dans les tables lorsque les noms n'introduisent pas d'ambiguïté dans la requête. Pour l'écriture des requêtes SQL, le respect de la syntaxe SQL d’Access n’est pas exigé.
A) Ecrire en algèbre relationnelle les requêtes suivantes : (3,5 points)

1) Quels sont les chauffeurs qui ont déjà livré des colis à "Toulouse" ? La requête doit fournir les couples (numéro du chauffeur, nom du chauffeur).

2) Quels sont les chauffeurs qui n’ont jamais livré de colis à "Toulouse" ? La requête doit fournir les couples (numéro du chauffeur, nom du chauffeur).

3) Quelles sont les noms des villes où aucun colis n'a été livré ?

4) Quels sont les numéros des chauffeurs qui connaissent tous les clients contenus dans la base ? On considère qu’un chauffeur connaît un client s'il a déjà pris ou déposé au moins un colis chez ce client.
B) Ecrire en langage SQL les requêtes suivantes : (3,5 points)

1) Quel est pour chaque livraison le poids total transporté ? La requête doit fournir les couples (numéro de livraison, poids total).

2) Quel est pour chaque ville le nombre total de livraisons déchargées dans cette ville ? La requête doit fournir les couples (nom de ville, nombre total de livraisons).

3) Quels sont les numéros des clients ayant expédié au moins une livraison de plus de 1000 Kg ? On considère que les données de la base sont en kilogrammes.

4) Quel est pour chaque chauffeur le nombre total de kilomètres qu’il a parcourus pour réaliser ses livraisons ? La requête doit fournir les couples (numéro de chauffeur, nombre total de kilomètres). On considère que pour tout couple de villes, la distance correspondante en kilomètres existe dans la table ReliéeA.

3. 
   Modification du schéma entité-association et du schéma relationnel (3 points)
   

Un ou plusieurs équipiers participent à la manutention lors des livraisons. Ces équipiers peuvent changer suivant les livraisons et travaillent donc avec différents chauffeurs.

Compléter le schéma entité-association et donner les modifications correspondantes au niveau du schéma relationnel afin de prendre en compte les équipiers. Le schéma proposé doit comporter le moins d’entités et d’associations possibles et doit permettre de faire les requêtes suivantes (l’écriture des requêtes n’est pas demandée) :

- Quels sont les chauffeurs et les équipiers qui habitent dans la même ville ?

- Quels sont les équipiers qui ont travaillé avec un chauffeur de "Lyon" ?

- Quels sont les équipiers qui ont déjà livré le client "Plondave" ?

- Quels sont les équipiers qui ont déjà livré le "31/12/1996" ?
PARTIE PASCAL : SEGMENTATION SUPERVISEE D'IMAGES 3D (10 points)

Barème approximatif : A) 3,5 points, B) 4 points et C) 2,5 points
Introduction

La segmentation consiste à partitionner un ensemble de points composant une image 3D en sous ensembles correspondant aux mêmes surfaces. Dans notre cas nous considérons que l'image 3D est celle d'un objet et pour réaliser la segmentation nous utilisons des informations complémentaires contenues dans un fichier CAO qui décrit les surfaces de l'objet. Ce type de segmentation a de nombreuses applications, telles que le guidage d'un bras robot lors de la saisie d'un objet ou encore la détection de défauts sur des pièces usinées.

A) Image 3D

Nous appelons image 3D un ensemble de points représentant les surfaces externes d'un objet, obtenu par un capteur télémétrique laser à balayage. Ce type de capteur permet d'obtenir des images composées de plusieurs milliers de points en quelques secondes ( environ 10 000 points / seconde). Un point de l'image est composé de deux informations : sa position dans l'espace ( composante X, composante Y, composante Z) et sa luminance codée en entier de 0 (noir) à 255 (blanc). Le calculateur associé au pilotage du capteur stocke ces informations dans un fichier typé (appelé fichier image) dont la structure est la suivante :

X

Y

Z

Luminance

Nous obtenons des images telles que celle donnée figure 1.

Figure 1 - Image 3D d'un objet

1) Le type Pascal d'un fichier image est défini par :

type

fichierImage = file of tPoint;

Proposer une définition pour le type tPoint.

2) La taille des fichiers étant importante, nous utilisons la mémoire du calculateur afin d’améliorer la rapidité des traitements (les accès mémoires étant beaucoup plus rapides que les accès fichiers) ; pour cela nous stockons ces informations, pour la durée du traitement, dans une liste chaînée.

Donner la déclaration du type listePoints permettant de décrire la liste chaînée contenant les points d'une image.

3) Donner une procédure qui initialise une liste de type listePoints.

4) Proposer une réalisation de la procédure suivante :

Procedure lireImage(nomfic : string; var lp : listePoints);

qui renvoie dans lp les points contenus dans le fichier image dont le chemin d'accès est donné par nomfic. On considère que la lecture du fichier se déroule toujours correctement.

B) Modèle CAO

Pour superviser la segmentation nous utilisons un fichier, appelé fichier CAO, qui a servi à concevoir l'objet. Ce fichier décrit les surfaces délimitant l'objet, chacune d'elle étant approximée par un ensemble de triangles. Un tel exemple d'approximation est donné figure 2. Généralement, les surfaces simples (rectangles) sont approximées par deux triangles de même taille, et les surfaces à géométrie plus complexe sont approximées par plus de triangles, dont le nombre et les dimensions dépendent de la courbure de la surface.

Figure 2 - Surface quelconque triangulée	3 surfaces simples, chacune approximée par 2 triangles

Chaque triangle est représenté par les coordonnées (X, Y, Z) de chacun de ses sommets. Le fichier CAO décrivant ces informations est un fichier typé qui a la structure suivante :

N° de surface

X1

Y1

Z1

X2

Y2

Z2

X3

Y3

Z3

Le premier champ contient le numéro de la surface (codé en entier) à laquelle appartient le triangle ; les 9 autres champs contiennent les coordonnées des sommets du triangle (codées en réels).

Voici un extrait possible d'un tel fichier CAO :
...

2	10.0	10.0	0.0	15.0	10.0	0.0	15.0	15.0	0.0
1	7.3	3.2	10.0	7.3	4.0	10.0	10.0	3.2	12.0
3	5.2	3.2	15.0	8.1	4.0	15.0	10.0	3.2	14.0

...
On notera que les triangles associés à une même surface ne se suivent pas forcément dans le fichier.

1) Le type Pascal d'un fichier CAO est défini par :

type

fichierCAO = file of tTriangle;

Proposer une définition pour le type tTriangle.
2) Pour la même raison que précédemment, nous chargeons ce fichier en mémoire dans une structure du type suivant :

Cette structure est composée d'une liste de type listeSurfaces contenant les numéros des surfaces. Chaque élément de cette liste contient aussi un pointeur vers une autre liste de type listeTriangles décrivant les triangles associés. Ainsi, dans notre exemple, l'élément correspondant à la surface numéro 2 contient un pointeur vers une liste de 3 éléments décrivant les 3 triangles associés à cette surface dans l'extrait du fichier CAO.

Donner les déclarations des types listeSurfaces et listeTriangles.

3) Donner une procédure qui initialise une liste de type listeSurfaces.

4) Proposer une réalisation de la procédure suivante :

Procedure lireSurfaces(nomfic : string; var ls : listeSurfaces);

qui renvoie dans ls la structure présentée en B-2) remplie avec les surfaces et les triangles décrits dans le fichier CAO dont le chemin d'accès est donné par nomfic. On considère que la lecture du fichier se déroule toujours correctement.
C) Segmentation

Segmenter une image consiste dans notre cas à associer à chaque point de l'image 3D une surface du modèle CAO. Pour cela, nous calculons pour chaque point P de l'image 3D la distance le séparant de chaque triangle du modèle CAO (voir remarque ci-dessous) et nous associons à ce point P la surface contenant le triangle le plus proche (de P !!!). Une segmentation réelle devrait aussi éliminer les points parasites de l'image (tels que les points blancs), mais ces aspects ne seront pas traités dans ce sujet.

Proposer une réalisation de la procédure suivante :

Procedure ecrireSegmentation(nomfic : string; lp : listePoints;

ls : listeSurfaces);

qui effectue la segmentation des points de lp selon les surfaces de ls et sauvegarde cette segmentation dans le fichier dont le chemin d'accès est donné par nomfic.

Le fichier utilisé doit être un fichier typé contenant pour chaque point ses coordonnées ainsi que le numéro de la surface qui lui a été associée par la segmentation. On considère que l'écriture du fichier se déroule toujours correctement.

Remarque :

On suppose déjà écrite la fonction suivante :

Function distance(X,Y,Z,Ax,Ay,Az,Bx,By,Bz,Cx,Cy,Cz : real) : real

qui renvoie la distance du point de coordonnées (X,Y,Z) au triangle de sommets (A,B,C) ayant pour coordonnées respectives (Ax,Ay,Az), (Bx,By,Bz) et (Cx,Cy,Cz).

Schémas utilisés dans la partie base de données

Le schéma décrit une base de données dans laquelle sont enregistrées des livraisons.

On notera les points suivants :

- une ville est identifiée simplement par son nom.

- tous les colis d'une livraison donnée ont le même expéditeur et le même destinataire.

Colis : (Numéro, Poids, NoLivraison)

Livraison : (Numéro, Date, NoChauffeur, NoDestinataire, NoExpéditeur)

Client : (Numéro, NomSociété, NomVille)

Chauffeur : (Numéro, Nom, NomVille)

Ville : (Nom, NbHabitants)

ReliéeA : (NomVilleDépart, NomVilleArrivée, Distance)

Les clés primaires sont soulignées,

Les clés étrangères apparaissent en italique.