Discussion :

[kaaon]

Bonjour,

je cherche un moyen efficace pour faire des calculs dans des espaces à plusieurs dimensions.
En fait, mes structures sont décrites par des inéquations:

Une "boule" définie sur 4 dimensions sera de la forme
r² >= (x-x0)²+(y-y0)²+(z-z0)²+(t-t0)²
avec (x0,y0,z0,t0) le centre de ma boule.

Un "paraléllépipède" en 4 dimension :
1 < x < 4, 2 < y < 5, 3 < z < 4, 0.3 < t < 0.9

Ce qui me pose un problème c'est pour la collision entre entre les objets.
Un exemple de problème c'est de savoir si mon "paraléllépipède" intersecte ma "boule".
Pour un exemple donnée c'est simple. Mais la difficulté vient du fait que je peux avoir n'importe quelle structure (dans un espace à n dimension) du moment qu'elle est définie par des inéquations.

J'ai d'abord pensé à regarder au niveau des algorithmes de collisions en 3D, mais ça serait un boulot énorme de tout repasser en n dimension.
Du coup j'ai pensé à un solveur de contraintes, mais je n'en connais pas qui travaille sur des réels à dimension bornée et qui accepte les inégalités.

Si vous avez des idées, des algos ou des librairies, vous êtes le bienvenu.

[FrancisSourd]

La programmation mathématique consiste à minimiser (ou maximiser) une fonction objectif f(x) de R^n dans R sous les contraintes que g_i(x)>=0 et h_i(x)=0.

Tu es donc dans le cas particulier où il n'y a pas de fonction objectif: il suffit de trouver une solution faisable. Si tes fonctions g_i et h_i sont linéaires, le problème est bien résolu, tu peux utiliser lp_solve ou glpk.

Dans le cas général, le problème est très difficile. Même si tu considères que les contraintes sont des fonctions polynomiales.
Il y a un guide des codes pour l'optimisation
http://www-fp.mcs.anl.gov/otc/GUIDE/OptWeb/
qui pourra peut-être t'aider (regarde du côté de l'optimisation contrainte).

[Nemerle]

Une "boule" définie sur 4 dimensions sera de la forme
r² >= (x-x0)²+(y-y0)²+(z-z0)²+(t-t0)²
avec (x0,y0,z0,t0) le centre de ma boule.

euh... c'est r2<=, et pas r2>= (petite erreur de frappe )

Dans ton problème, le "pavé" est fixe, donc la collision peut s'expliciter complêtement: il te suffit de calculer la distance du pavé au centre de ta boule (cf google). Comme ton pavé est constant, ta formule de calcul est une fonction ne dépendant que de (x0,y0,z0).

[kaaon]

Merci pour ton lien FrancisSourd, je vais chercher de ce coté car mon problème peut effectivement être vu comme un problème de faisabilité.

Une solution pourrait aussi être de linéariser les équation en faisant des approximations puis d'utiliser les polytopes avec un algorithme de simplexe.

Mais alors, c'est la complexité qui va sûrement me poser un problème.

[Nemerle]

je réitere: la solution est explicite avec quelques calculs...

C'est un exo classique en Deug 2nde année

[FrancisSourd]

je réitere: la solution est explicite avec quelques calculs...

C'est effectivement le cas pour l'exemple donné mais kaaon parle de "n'importe quelle structure (dans un espace à n dimension) du moment qu'elle est définie par des inéquations."

Une solution pourrait aussi être de linéariser les équation en faisant des approximations puis d'utiliser les polytopes avec un algorithme de simplexe.

La programmation linéaire peut être intéressante si tu travailles avec des volumes convexes. En générant successivement des plans tangents tu peux avoir un représentation de plus en plus fine de ton volume par un polyèdre englobant.

Si le volume n'est pas convexe, cette piste conduit à des représentations linéaires par morceaux qui impliquent de la programmation linéaire en nombre entiers: cela a peu de chance d'être efficace.

Comme tu le verras en regardant ces méthodes de programmation mathématique, on fait souvent des relaxations lagrangiennes des contraintes, ce qui peut être interprété comme une autre manière d'approximer les frontières des volumes.