Dénombrement du nombre de rectangles — Les-mathematiques.net The most powerful custom community solution in the world

Dénombrement du nombre de rectangles

Modifié (7 May) dans Géométrie
Bonjour,
Je cherche une méthode rigoureuse et générale pour dénombrer le nombre de rectangles formés par des rectangles qui se chevauchent.
J'ai trouvé 21.

 .  
Pour les nœuds d'un quadrillage  régulier, il y a une formule générale à partir du nombre de lignes L et du nombre de colonnes C : 
L (L + 1 ) ×  C (C+ 1 ) / 4.



Mais comment faire dans le cas de la figure avec les rectangles  qui se chevauchent ?
Si je cherche à former un quadrillage avec les points d'intersections et/ou les sommets des rectangles, il ne se sera pas régulier et je ne pourrai pas appliquer la formule précédente. 
Merci pour votre aide.

Réponses

  • Modifié (8 May)
    Je n'ai pas de méthode générale, et je doute qu'il en existe de meilleure que de passer en revue chaque quadruplet de points et de vérifier s'il forme un rectangle. Par ailleurs, tu ne dis pas s'il faut ne considérer que les lignes déjà tracées ou si l'on peut en imaginer d'autres.
    Pour cet exemple, je vais considérer que tu voulais n'utiliser que les segments déjà tracés.
    Et bien, je ne trouve pas le même nombre de rectangles que toi.
    Dans un premier temps, omettons le rectangle bleu.
    Dans le rouge, il y a 3 verticales qui traversent entièrement le rectangle. Nommons les 10 points sur les segments haut et base de ce rectangle de gauche à droite et de haut en bas, A,B,C,D,E,F,G,H,I,J
    - si on considère les sous-rectangles qui ne sont pas traversés par une telle verticale, il y en a 4 : ABGF, BCHG, CDIH, DEJI
    - si on considère les sous-rectangles qui sont traversés par une verticale, il y en a 3 : ACHF, BDIG, CEJH
    - si on considère les sous-rectangles qui sont traversés par deux verticales, il y en a 2 : ADIF, BEJG
    - enfin, il y a le rectangle rouge entier AEJF
    En tout, cela fait déjà 10 rectangles.
    De même, dans le vert, on en compte 6 de cette sorte (toujours sans prendre en compte pour l'instant l'intersection avec le rectangle bleu) dont BCHG que l'on a déjà compté dans le rouge. Cela en donne donc 5 de plus.
    Dans le rectangle bleu, je nomme K,L,M,N les 4 points du segment du haut O et P les intersections avec le rectangle rouge et Q,R,S les 3 points du segment du bas, et enfin T et U les extrémités du segment jaune à l'intérieur du rectangle bleu.
    Je dénombre les rectangles suivants.
    - au-dessus du segment rouge : KLHO, LMIH, MNPI, puis KMIO, LNPH et KNPO
    - en dessous de ce segment rouge : OHRQ, HPSR et OPSQ, ainsi que IPUT
    - de part et d'autre de ce segment : KLRQ, LNSR et MNUT- enfin, le rectangle entier KNSQ
    Il ne reste alors que le jaune dont les sous-rectangles ont déjà tous été comptés et le rectangle quadricolore CDML.
    Au total, j'arrive donc à 29 30 31 rectangles.

    [Edit] J'ai rajouté le LNSR suggéré par Paul, ainsi que le CDML trouvé plus tard.
  • Modifié (8 May)
    Bonjour
    La description mathématique de ta figure est en fait très complexe et il n'y a aucune raison pour qu'il existe une formule simple aboutissant au dénombrement demandé. Je ne vois pas mieux que l'énumération exhaustive des rectangles présents, obtenue de la façon suivante:
    Soit $A$ (resp. $B$) l'ensemble des abscisses (resp. des ordonnées) des segments de droite verticaux (resp. horizontaux) en présence.
    Soit $T:= \left\{(a,b,c,d) \in A^2\times B^2 \mid a<b, \: c<d \right\}. \qquad\forall (a,b,c,d) \in T,$
    $R(a,b,c,d) $ désigne le rectangle de sommets $(a,c) ,(a,d) ,(b,c), (b,d)\:$ et  $\:\:f(a,b,c,d) := \left\{\begin{array}{cl}1&\text {si } R(a,b,c,d) \text { est tracé}\\ 0& \text{sinon}. \end{array}\right.$
    Le nombre des rectangles tracés sur la figure est alors: $$\boxed{\mathcal N = \displaystyle \sum _{t\in T} f(t) =\sum_{\substack {(a,b) \in A\\a<b}} \sum_{\substack {(c,d) \in B\\c<d}} f(a,b,c,d).}$$
    C'est sur ce principe banal que se fonde le décompte des rectangles lorsque l'on a affaire à une grille $L \times C$, et c'est une situation où les choses sont très simples: $\quad\text{Card} T =\binom {L +1}2 \times \binom {C+1} 2 , \quad \forall t \in T, \:\: f(t) =1, \quad \mathcal N = \dfrac {LC(L+1)(C+1)}4.$
    Dans le cas de ta figure, en notant $A =\{a,b,c,d,e,f,g,h \} $ et pour $\:x \in A, \:\: N(x):=\displaystyle \sum _{\substack{ y\in A\\y>x}}\sum_{\substack {(z,u) \in B\\z<u}} f(x,y,z,u),$ on obtient:
    $N(a) =4, \:\: N(b) =8, \:N(c)=7, \: N(d) =7, \: N(e)=5 ,\:N(f)=N(g)= N(h) =0 \:\:$ de sorte que $\boxed{\mathcal N = \displaystyle \sum_{x\in A} N(x)=31.}$

    Les seuls points susceptibles d'être des sommets des rectangles cherchés sont les $28$ points d'intersection apparaissant sur la figure ,que je nomme $A,B,\dots Z,\omega, \infty$ en les énumérant par abscisses croissantes, et pour les points de mêmes abscisses, par ordonnées décroissantes. Ainsi, les sommets du rectangle rouge seront $ABZY$, ceux du rectangle orangé $PT\infty\:\omega .$
    $\bullet \quad N(a) =4: \quad ABED,\:ABMK,\:ABSQ,\:ABZY.$
    $\bullet\quad  N(b) =8:\quad CDKJ,\:DEMK,\:EFOM,\:CEMJ,\:DFOK,\:CFOJ,\:DESQ,\:DEZY.$
    $\bullet \quad N(c) =7: \quad GHML,\:HINM,\:GINL,\:GHSR,\:GHVU,\:HIXV,\:GIXU.$
    $\bullet \quad N(d)=7 :\quad KLRQ,\: LMSR, \: KMSQ,\:LMVU,\:MNXV,\:LNXU,\:KMZY.$
    $\bullet \quad N(e)=5 :\quad  RSVU,\:STWV,\:RTWU,\:QSZY, \:PT\infty\:\omega .$
  • Modifié (8 May)
    Bonjour à tous
    En classant les rectangles selon le nombre de couleurs que possède leur périmètre, j'arrive à $30$ rectangles!
    Il me semble que bisam a oublié son LNSR (pour moi un "bleu, bleu, bleu, vert") mais je n'arrive pas au $31$ de Lou!
    Mélenchons nos proches sentiments.
    Cordialement
    Paul.
  • Modifié (8 May)
    Bon, j'ai fait un programme Python, pour être exhaustif... et comme d'habitude @Lou16 a raison.
    J'avais aussi oublié le rectangle CDML (rouge, jaune, bleu, vert, pour Paul) dans mon compte .
    class Point:
        """Représente un point géométrique du plan"""
    
        def __init__(self, x: int, y: int, name: str):
            self.x = x
            self.y = y
            self.name = name
    
        def __eq__(self, other):
            return self.x == other.x and self.y == other.y
    
        def __hash__(self):
            return hash((self.x, self.y))
    
        def __repr__(self):
            return self.name
    
    ## Définition des points et de leurs voisins
    
    A = Point(0, 5, "A")
    B = Point(1, 5, "B")
    C = Point(3, 5, "C")
    D = Point(4, 5, "D")
    E = Point(6, 5, "E")
    
    F = Point(0, 3, "F")
    G = Point(1, 3, "G")
    H = Point(3, 3, "H")
    I = Point(4, 3, "I")
    J = Point(6, 3, "J")
    
    K = Point(2, 4, "K")
    L = Point(3, 4, "L")
    M = Point(4, 4, "M")
    N = Point(5, 4, "N")
    
    O = Point(2, 3, "O")
    P = Point(5, 3, "P")
    
    Q = Point(2, 1, "Q")
    R = Point(3, 1, "R")
    S = Point(5, 1, "S")
    
    T = Point(4, 2, "T")
    U = Point(5, 2, "U")
    
    V = Point(1, 6, "V")
    W = Point(3, 6, "W")
    
    X = Point(4, 7, "X")
    Y = Point(7, 7, "Y")
    
    Z = Point(7, 2, "Z")
    
    AA = Point(1, 0, "AA")
    AB = Point(3, 0, "AB")
    
    POINTS = (A, B, C, D, E, F, G, H, I, J, K, L, M, N,
              O, P, Q, R, S, T, U, V, W, X, Y, Z, AA, AB)
    
    VOISINS = {A : (B, C, D, E, F),
               B : (V, C, D, E, G, AA, A),
               C : (W, D, E, L, H, R, AB, B, A),
               D : (X, E, M, I, T, C, B, A),
               E : (J, D, C, B, A),
               F : (A, G, O, H, I, P, J),
               G : (B, V, O, H, I, P, J, AA, F),
               H : (L, C, W, I, P, J, R, AB, O, G, F),
               I : (M, D, X, P, J, T, H, O, G, F),
               J : (E, P, I, H, O, G, F),
               K : (L, M, N, O, Q),
               L : (C, W, M, N, H, R, AB, K),
               M : (D, X, N, I, T, L, K),
               N : (P, U, S, M, L, K),
               O : (K, H, I, P, J, Q, G, F),
               P : (N, J, U, S, I, H, O, G, F),
               Q : (O, K, R, S),
               R : (H, L, C, W, S, AB, Q),
               S : (U, P, N, R, Q),
               T : (I, M, D, X, U, Z),
               U : (P, N, Z, S, T),
               V : (W, B, G, AA),
               W : (C, L, H, R, AB, V),
               X : (Y, D, M, I, T),
               Y : (Z, X),
               Z : (Y, U, T),
               AA : (G, B, V, AB),
               AB : (R, H, L, C, W, AA)}
    
    ## Fonctions
    
    def vers_droite(A: Point, B: Point) -> bool:
        return A.y == B.y and A.x < B.x
    
    def vers_gauche(A: Point, B: Point) -> bool:
        return A.y == B.y and A.x > B.x
    
    def vers_haut(A: Point, B: Point) -> bool:
        return A.x == B.x and A.y < B.y
    
    def vers_bas(A: Point, B: Point) -> bool:
        return A.x == B.x and A.y > B.y
    
    def est_rectangle(A: Point, B: Point, C: Point, D: Point) -> bool:
        return (vers_droite(A, B)
            and vers_bas(B, C)
            and vers_gauche(C, D)
            and vers_haut(D, A))
    
    def compte_rectangles():
        l = []
        for A1 in POINTS:
            for A2 in VOISINS[A1]:
                for A3 in VOISINS[A2]:
                    for A4 in VOISINS[A3]:
                        if est_rectangle(A1, A2, A3, A4):
                            l.append((A1, A2, A3, A4))
        print(len(l))
        return l

  • Merci Lou!
    Une petite coquille: tu notes deux points "N" et tu n'as pas de "W".

    Je reste un peu sur ma faim:
    La figure proposée peut se coder $12324314, 42131432$ (:= abscisses croissantes, ordonnées décroissantes) où rouge, vert, bleu, orangé =1,2,3,4. C'est de ce seul codage que j'aurais aimé déduire le nombre total de rectangles.

    Bien à vous
    Paul
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!