TODO
- initialisation hypercube
- nouvelle stratégie de selection des points pour l'init de pavage
- constructeur par transfert
Le projet
L'archive du projet contient un fichier projet Code::Blocks permettant de visualiser facilement les fichiers du projet.
Sous Linux, il est possible d'exécuter le programme directement via Code::Blocks, cependant il est vivement recommandé de compiler le projet en ligne de commande avec make.
Le projet est divisé en deux programmes:
- Un programme principal utilisateur
- Un programme de test des fonctionnalités
et quatre fichiers:
- Paving.hpp regroupe les classes templatées et leur définitions
- Paving_config.hpp propose des paramètres modifiables par l'utilisateur
- main.cpp offre une fonction main utilisateur
- test.cpp effectue une batterie de tests
Le fichier Paving_config.hpp propose 6 variables modifiables par l'utilisateur selon ses besoins:
- DIMENSION: la dimension courante du programme (peut être modifiée avec une option du programme, Cf ci-dessous)
- DIMTEST: la dimension de la matrice paramétrable pour les tests de calcul de déterminant
- TYPECOORD: le type des coordonnées des échantillons
- TYPEVAL: le type des valeurs des échantillons
- WINDIM_X: la longueur des fenêtres d'affichage
- WINDIM_Y: la hauteur des fenêtres d'affichage
Compilation
$ make
$ make bin/PavIn
$ make bin/testPavIn
$ make doc
Haut de page
Programme principal utilisateur
En dimension 2, et uniquement, la librairie
Grapic développée par Alexandre Meyer permet de visualiser l'évolution du pavage dans une fenêtre graphique.
Exemple d'exécution du programme en dimension 2 (avec affichage graphique)
Exécution du programme en ligne de commande:
$ bin/PavIn -g 8 -10 50
Etape 0: Création des points
Le programme:
- lis les points du fichier donné ou génère des points aléatoirement
- retient les deux points extremaux (sud-ouest et nord-est) pour un affichage adapté
- crée un pavage et affiche les points
|
Nuage de points
|
Etape 1: Création du simplexe englobant
Pour créer un N-Simplexe englobant, la fonction d'initialisation crée un (N+1)-Simplexe avec les N points:
- (T, 0, 0, ...)
- (0, T, 0, ...)
- (0, 0, T, ...)
- ...
et complété avec le point
- (-T, -T, -T, ...)
Le paramètre T est initialisé au maximum des valeurs absolues des coordonnées des points. Il est incrémenté par un coefficient proportionnel à cette valeur.
Ce (N+1)-Simplexe est ensuite projeté une dimension en dessous pour obtenir un N-Simplexe englobant tous les points.
Ensuite, une étape d'affinage de ce N-Simplexe est effectuée:
- chacun des points (T, 0, ...), (0, T, ...) ... du simplexe est diminué tant que tous les points lui appartiennent toujours,
- puis, sur le même modèle, le point (-T, -T, ...) est augmenté.
Ainsi, un N-Simplexe englobant tous les points donnés est obtenu. Les points de ce simplexe sont ajoutés au pavage, on leur donne la valeur du point qui leur est le plus proche.
|
Simplexe englobant
|
Etape 2: Ajout d'un premier point
Le plus le plus proche du point extrême p_min (sud-ouest) est choisi. Il est utilisé pour découper le simplexe englobant en N+1 simplexes.
|
Ajout d'un premier point
|
Etape 3: Ajout de tous les points
Sur le même modèle que précédemment, le programme ajoute tous les points restants en choisissant le point le plus proche du dernier ajouté.
|
Ajout de tous les points
|
Etape 4: Point utilisateur
Enfin le programme propose à l'utilisateur de rentrer les N coordonnées d'un point du pavage. Il recherche le simplexe contenant ce point dans le pavage et calcule la valeur du point en interpolant avec tous les points du simplexe.
Si le point n'appartient à aucun simplexe du pavage, le programme affichera un tel message d'erreur et donnera la valeur 0 au point utilisateur.
A l'affichage dans la fenêtre graphique, le dernier point entré par l'utilisateur est relié par des arêtes oranges à tous les points du simplexe qui servent à interpoler sa valeur.
|
Point utilisateur
|
Et la sortie standard correspondant à l'exécution de ce programme:
babs@jara:~/Master/proggen/PavIn$ bin/PavIn -g 8 -10 50
----------------—
## PavIn ##
----------------—
Generating 8 random points of dimension 2
Paving initialisation
Creating englobing simplex...
Refining englobing simplex...
Englobing simplex :
-1 {
(75, 0)
(0, 75)
(-12, -12)
}
Adding point (0, -6) [7]:
added
Adding point (23, 8) [46]:
added
Adding point (27, 4) [37]:
added
Adding point (43, 16) [30]:
added
Adding point (46, -4) [11]:
added
Adding point (35, 40) [42]:
added
Adding point (24, 40) [41]:
added
Adding point (8, 45) [35]:
added
INITIALISATION SUCCESS
Insert the 2 coordonates of the point you want the value :
1: 10
2: 15
Getting (10, 15)
Containing simplex: 16 {
(8, 45) [35]
(23, 8) [46]
(0, -6) [7]
}
At point
(10, 15), calculated value is
28.623
Continue ? [y/n] n
----------------—
## PavIn ##
----------------—
Haut de page
Programme de tests
$ make bin/testPavIn
$ bin/testPavIn
- Dimension 2
En dimension 2, le programme utilise les données issues de la figure ci-contre.
Il calcule:
-
La somme A+B = (7, 2)
-
La différence A-B = (-3, -5)
-
les déterminants suivants:
-
les volumes des simplexes suivants:
Il teste si chacun des points A, B, C, P, Q et R appartient au simplexe {A, B, C}.
Il calcule la valeur des points A, B, C, P, R, S, T et U.
Résultats:
-
a : 2
-
b : 14
-
c : -8
-
p : 2.32
-
r : 11.6
-
s : 3.36
-
t : -4.56
-
u : -3
|
Test dimension 2
|
- Dimension 3
En dimension 3, le programme utilise les données issues de la figure ci-contre.
Il calcule:
-
Les déterminants suivants:
-
les volumes des simplexes suivants:
-
{S, T, U, V} = [(6 x 5 / 2) x 7] / 3 = 35
-
{S, T, U, X} = [(6 x 5 / 2) x 2] / 3 = 10
puis teste si chacun de ces 8 points se trouve dans le simplexe {S, T, U, V}
et calcule la valeur au point X : 2.28571 |
Test dimension 3
|
- Dimension 4
Le programme calcule les deux déterminants suivants:
- Dimension paramétrable
Dans le fichier Paving_config.hpp se trouve une variable constante DIMTEST qui permet de paramétrer la dimension pour le test de calcul de determinant.
Par défaut à 10, le test crée une matrice 10x10 et la remplie de manière aléatoire de telle sorte qu'une ligne de la matrice soit égale à la première, ainsi le déterminant vaudra forcément 0.
- Test de pavages
Enfin, un pavage de dimension 2 et un de dimension 3 sont crées et initialisés grâce au constructeur avec bornes de la classe Paving. Ainsi l'utilisateur peut suivre l'évolution du pavage en dimension 2 grâce à la fenêtre graphique.
D'autre pavages jusqu'en dimension 10 sont en commentaires et prêts à l'emploi à la fin du fichier, mais leur exécution peut vite prendre du temps.
Haut de page
Références
