Volume d'une intersection cube - sphère

Stephi
Stephi
dans Géométrie
Bonjour à tous,

J'ai des difficultés sur le calcul du volume de l'intersection d'un cube et d'une sphère:

La sphère de rayon r coupe une partie d'un cube de côté a. La sphère se trouve à l'origine du repère et les coordonnées des sommets du cube sont connus.

Je cherche comment résoudre ce problème indépendamment de comment est-ce que la sphère coupe le cube.
J'ai pensé passer par les intégrales, mais je suis bloqué.

Merci d'avance pour votre aide,
Stephi

Réponses

  • Bu
    Bu
    "Je cherche comment résoudre ce problème indépendamment de comment est-ce que la sphère coupe le cube. "

    Ça en dépend forcément, bien sûr ! Tu n'auras pas une seule formule, mais tout un tas suivant les cas.
  • Stephi
    Stephi
    Salut Bu,
    peux tu m ´ aider ?
    merci d´avance
  • GregorySAir
    GregorySAir
    Bonjour,

    Je suis aussi a la recherche de cette reponse.
    Malheureusement je pense que le probleme est tres complique et qu'il n'y a pas de solution analytique.

    Gregory
  • Stephi
    Stephi
    salut Gregory,

    j ai abondonner la possibilité de trouver une solution analytique, et je développe actuellement une solution nummérique.
    Où en es tu?

    Merci d avance pour ta reponse.

    Stephi
  • Rescassol
    Rescassol
    Bonjour,

    Ce n'est pas terrible, surtout peu précis à moins d'être patient, mais un simple Monte-Carlo sur la boîte englobante de la réunion des deux solides pourrait faire l'affaire.

    Tu programmes en quel langage ?

    Cordialement,

    Rescassol
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Bonjour Rescassol,
    Je suis étonné de cette idée qui semble assez répandue que la méthode de Monté-Carlo est "peu précise, à moins d'être patient".
  • Rescassol
    Rescassol
    Bonjour,

    Tout simplement parce qu'elle converge très lentement.
    Par exemple, si on tire $n$ couples $(x;y)$ de flottants dans $[0;1]$, et qu'on teste combien vérifient $x^2+y^2\leq1$ pour avoir une approximation de $\dfrac{\pi}{4}$, il faut une très grande valeur de $n$ pour avoir ne serait-ce que $4$ ou $5$ decimales de $\pi$.
    Par contre, je ne connais pas la complexité théorique, j'ai seulement expérimenté.
    En Python (Pyzo), par exemple, $2$ décimales en $1.2$ secondes et $n=10^6$.
    Bien sûr, c'est interprété, mais ça ne change rien au nombre de décimales.

    Cordialement,

    Rescassol
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Je n'ai pas compris ton raisonnement pour l'évaluation de pi/4.
    Peux-tu m'expliquer ?
  • Rescassol
    Rescassol
    Bonjour,

    Désolé, Dlzlogic, je croyais que tu connaissais Monte-Carlo.

    Sur la figure suivante, si $M(x;y)$ est un point aléatoire du carré $ABCD$ (loi uniforme sur $[0;1]$ pour $x$ et $y$), la probabilité que $M$ soit à l'intérieur du quart de disque de centre $A$ et de rayon $1$ est égale au quotient de l'aire du quart de disque et de l'aire du carré, c'est à dire $\dfrac{\pi}{4}$.
    On fait donc des statistiques en prenant un grand nombre $n$ de points $M$, et comme tu le sais, la fréquence tend vers la probabilité quand $n$ tend vers l'infini.

    2hrcyex.jpg

    Cordialement,

    Rescassol
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Oui, merci, entre-temps j'avais compris.
    Naturellement, en faisant 1000 simulations, on aura environ 785 cas favorables, soit au mieux 3 chiffres significatifs.
    Avec quel outil tu calcules cela ? Peux-tu montrer le code ?
    C'est un peu le même principe que le problème de l'aiguille (de Buffon). Wolf, avec 5000 expériences, a obtenu une valeur avec 2 chiffres significatifs exactes.
  • Rescassol
    Rescassol
    Bonjour,

    Voilà le code en Python, traduisible facilement en n'importe quoi: 
    ###################################################################
# Importations
###################################################################

from math import *
import random
import time

###################################################################
# Fonctions
###################################################################

def Monte_Carlo(n):
    k = 0
    for i in range(n):
        x=random.random()
        y=random.random()
        if x ** 2 + y ** 2 < 1:
            k += 1
    p = 4 * k / n
    return p
  
###################################################################
# Script principal de test
###################################################################
  
n = 1000000

t1=time.clock()
Approx = Monte_Carlo(n)
t2=time.clock()
print('Approximation =', Approx)
print('Temps = ' + str(t2 - t1))
print('Erreur = ' + str(abs(pi - Approx)))

# On obtient une approximation, pas très précise, de pi

    Cordialement,

    Rescassol
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Ok, merci.
    Cependant, je me demande si c'est un exemple de convergence, bonne ou mauvaise, de la méthode.
    En gros avec 10000 mesures, on ne peut pas espérer plus de 3 chiffres significatifs pour un calcul d'aire.
    Par ailleurs, on estime qu'un calcul d'aire, fait avec des moyens visuels, a une précision d'environ 1/500.
    Mais, là, on est en plein [HS] :-o
  • leon1789
    leon1789
    A priori, le rayon de l'intervalle de confiance à 95% est grosso-modo en 1/ n^0.5 , donc pour n= 10 000, c'est une précision de 1/100, donc on a à peine 2 chiffres significatifs. Pour en avoir assurément 3 (ie une précision de 0.0005) , il faut prendre n = 1 / 0.0005^2 = 4 000 000
    Et à chaque fois que l'on voudra une décimale supplémentaire, il faudra multiplier n par 100 !

    Une convergence en 1/ n^0.5 est très lente, il n'y a aucune surprise.
  • Stephi
    Stephi
    Bonjour,

    Je programme avec OpenFoam, une boite à outils de simulation qui utilisant c++.
    Voici ce que j´essaie de programmer:

    ----Générer des points dans le cube et/ ou aussi sur la surface du cube ou bien seulement sur la surface du cube (même distance entre tous les points par exemple)
    ----et après calculer les distances (PO) de chaque point par rapport au centre de la sphère.
    ----Puis comparer cette distance au rayon de la sphère.
    ----Et enfin formuler le volume de l’intersection comme étant:
    V = volume du cube multiplier par le nombre de points dont la distance(PO) est inférieur au rayon de la sphère puis diviser par le nombre de points total générer.

    C´est fou mais la méthode donne un très bon résultat quand nombre de points générer est grand.

    Cordialement
    Stephi
  • GaBuZoMeu
    GaBuZoMeu
    L'obtention de formules exactes avec disjonction de cas ne doit pas être si impossible que ça. Juste une affaire de soin et de patience.
  • Sylviel
    Sylviel
    En complément sur monte-carlo : la méthode n'est pas efficace en dimension 1, 2 ou 3 où les méthodes déterministe type éléments fini sont bien plus rapide. Du pseudo Monte Carlo sera plus efficace de la dimension 5 à 15 en gros, et après c'est Monte-Carlo qui l'emporte (sauf cas particulier).

    edit : le terme usuel est plutôt quasi-Monte Carlo.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Bonjour Sylviel,
    A mon avis, cette affirmation devrait être justifiée et au moins expliquée.
    Qu'appelles-tu "pseudo" Monte-Carlo ?
    Il faudrait aussi préciser ce que tu entends par "efficace" dans ce contexte.
    Quelques exemples dans différentes dimensions seraient utiles pour la compréhension.
  • [Utilisateur supprimé]
    [Utilisateur supprimé]
    Toujours à propos de la méthode de Monte-Carlo
    Ci dessous une simulation du calcul de pi/4.
    La valeur affichée est le comptage. Il correspond donc à pi/4 * 10000 théorique.
    Evaluation de pi = 7893 ( pour 7854 théorique - Monte-Carlo)
    Evaluation de pi = 7783 ( pour 7854 théorique - Monte-Carlo)
    Evaluation de pi = 7838 ( pour 7854 théorique - Monte-Carlo)
    Evaluation de pi = 7842 ( pour 7854 théorique - Monte-Carlo)
    Evaluation de pi = 7851 ( pour 7854 théorique - Monte-Carlo)
    Evaluation de pi = 7876 ( pour 7854 théorique - Monte-Carlo)
    Evaluation de pi = 7900 ( pour 7854 théorique - Monte-Carlo)
    Evaluation de pi = 7848 ( pour 7854 théorique - Monte-Carlo)
    Evaluation de pi = 7900 ( pour 7854 théorique - Monte-Carlo)
    Evaluation de pi = 7853 ( pour 7854 théorique - Monte-Carlo)

    La même chose, pas la méthode déterministe, éléments finis 100x100.
    Méthode éléments finis compt= 7951 ( pour 7854 théorique )
  • h
    h
    Commentaire très naïf sur l'estimation du volume d'une boule en fonction de la dimension $d$.

    1) Éléments finis version très naïve : je partitionne $[-1,1]^d$ en $N=n^d$ petits cubes de même dimension, je compte le nombre de cube qui sont inclus (ou qui touchent) la boule unité etc. L'erreur est majoré par un truc de l'ordre de $n^{-d} n^{d-1}$ (le volume d'un petit cube multiplié par le nombre de cubes qui touchent la sphère unité) soit en $n^{-1} = N^{-1/d}$. Bon mais la majoration est sans doute très grossière, par le jeu des compensations ça ne me paraîtrait pas insensé qu'on gagne significativement.

    2) Monte-Carlo : en $N^{-1/2}$ par le TCL.

    Mais tout cela est très naïf ! Qui en sait plus pour le 1) même en se contentant de découper en cubes de mêmes dimensions ?
  • Sylviel
    Sylviel
    @Dlzlogic.
    Réponse rapide : les méthodes de quasi-Monte Carlo consiste à utiliser une suite déterminisite "remplissant bien l'espace" plutôt qu'une suite aléatoire uniforme pour les simulations. Par efficace j'entends le rapport précision obtenue / temps de calcul. Tu trouveras ce genre de résultats dans les cours qui traite des méthodes numériques probabiliste.
  • Rescassol
    Rescassol
    Bonjour,

    Stephi, Ta sphère est centrée à l'origine du repère et a pour rayon $r$.
    Comment est donné ton cube ? si tu connais son côté $a$ et les coordonnées des sommets, il y a des données en trop, tu les supposes cohérentes ou il faut faire des vérifications ?
    Le cube est il quelconque ou a-t-il des faces parallèles aux plans de coordonnées ?
    Peux tu nous donner un exemple de sphère et de cube particuliers pour qu'on puisse tester ?

    Cordialement,

    Rescassol
  • Maeglin
    Maeglin
    Stephi a écrit:
    J'ai des difficultés sur le calcul du volume de l'intersection d'un cube et d'une sphère:


    [size=large]Hello à tou(te)s ![/size]

    [size=x-large]Eurêkha, alors... :)o[/size]

    le problème a déjà été visité et traité en entier par la simulation animée puis en programmation Python avec ces magnifiques [size=medium]Crows and cats[/size].:-D

    Quand on vous dit et répète que la recherche par indexation sur mots-clés depuis un moteur Google doit être le B-A-BA de l'élève ! Ah,ces jeunes.(:D
  • leon1789
    leon1789
    dlzlogic écrivait :
    La même chose, pas la méthode déterministe, éléments finis 100x100. Méthode éléments finis compt= 7951 ( pour 7854 théorique )

    Je sais bien que Dizlogic pense qu'il n'y a pas mieux que Monté Carlo, mais je ne sais pas comment il programme la méthode des éléments finis (pourtant pas compliquée !) : pour un maillage 100x100 de [0,1]x[0,1], elle donne 7857 (et non 7951), ce qui est assez proche de 7854.
  • h
    h
    À l'arrache chez-moi ça donne ça (minoration et majoration) :

    --> n=100;x=ones(n,1)*[1/n:1/n:1];y=x';sum(x.^2+y.^2<=1)
    ans =

    7752.

    -->n=100;x=ones(n,1)*[0:1/n:1-1/n];y=x';sum(x.^2+y.^2<=1)
    ans =

    7953.

    On peut affiner. Qu'as-tu fait exactement leon1789 ?
  • leon1789
    leon1789
    Comme tu le montres avec tes deux calculs, il y a un choix à faire pour les carrés touchant le cercle : on les compte ou pas ? Ce choix arbitraire n'est pas anodin. Sans parler aussi du choix <= 1 ou < 1 qui a aussi une influence sur les résultats (7750 et 7949).

    Bref, j'ai considéré le centre des carrés comme point de repère, lieu plus "équilibré". Dans ce cas, par chance, prendre <1 ou <=1 donne le même résultat : 7857

    Je ne connais pas ton langage, mais cela ressemblerait à n=100;x=ones(n,1)*[0.5/n: 1/n: 1 - 0.5/n];y=x';sum(x.^2+y.^2<=1)
    Confirmes-tu ?
  • h
    h
    Je confirme, merci. Par contre avec cette méthode il reste à contrôler l'erreur. La moyenne de ma borne inférieure et de ma borne supérieure est 7852.5. Pas mal non plus, sauf qu'il reste là aussi à contrôler l'erreur. Cela dit ce n'est pas bien palpitant.

    Note : le langage ésotérique que j'utilise est scilab.
  • nitpicker
    nitpicker
    Une petite correction de vocabulaire : ce que vous écrivez, ce ne sont pas des éléments finis, lesquels servent à approcher la solution d'un problème variationnel, ce sont juste des sommes de Riemann pour l'intégrale de la fonction caractéristique du disque. Il ne faut pas espérer une trop bonne précision avec des sommes de Riemann... La fonction caractéristique d'un disque n'étant de toutes façons pas vraiment régulière, il ne faut pas attendre une grande précision de n'importe quelle méthode numérique déterministe non plus, d'ailleurs.
  • Maeglin
    Maeglin
    Hi.
    On a évoqué les éléments finis ou Monte-Carlo dans une équation d'un volume d'intersection en 3D ! Encore un coucou qui s'égare, ravi. Ah Chouette.
    L'auteur définit plusieurs régimes distincts reliés au ratio de rho et d, où le premier est le rayon de la sphère et le second est 1/2x la largeur du cube.
    Le premier régime est celui sphérique, où rho / d < 1. Il ressemble à une sphère : le dernier régime est juste un CUBE. Il se produit à rho / d > sqrt(3):
  • GaBuZoMeu
    GaBuZoMeu
    Il ne sert à rien de chercher sur internet la réponse à un problème quand on n'a pas compris l'énoncé : la sphère et le cube n'ont pas même centre.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 3

topopot +2 Invités