Quadtree of 2D array

45 views Asked by At

so we have this project where we have to build a quadtree from a 2D array in parameters, the thing is my inital code doesn't manage well rectangle arrays when i want to expand the length of the width and the height it gives me a out of range or place the childs not in the good coordinate.

I tried to expand the length when the width is not dividable by 2 or another if that checks if the height is dividable by 2 , or another that takes the length and width and check if it dividable by two if it doesn't we increment here's the code

// Quadtree est la structure de données pour les arbres
// quaternaires. Les champs non exportés sont :
//   - width, height : la taille en cases de la zone représentée
//     par l'arbre.
//   - root : le nœud qui est la racine de l'arbre.
type Quadtree struct {
    width, height int
    root          *node
}

// node représente un nœud d'arbre quaternaire. Les champs sont :
//   - topLeftX, topLeftY : les coordonnées (en cases) de la case
//     située en haut à gauche de la zone du terrain représentée
//     par ce nœud.
//   - width, height :  la taille en cases de la zone représentée
//     par ce nœud.
//   - content : le type de terrain de la zone représentée par ce
//     nœud (seulement s'il s'agit d'une feuille).
//   - xxxNode : Une représentation de la partie xxx de la zone
//     représentée par ce nœud, différent de nil si et seulement
//     si le nœud actuel n'est pas une feuille.
type node struct {
    topLeftX, topLeftY int
    width, height      int
    content            int
    topLeftNode        *node
    topRightNode       *node
    bottomLeftNode     *node
    bottomRightNode    *node
}

func MakeFromArray(floorContent [][]int) (q Quadtree) {
    // if q.root != nil {
    //  return q
    // }
    q.height = len(floorContent)
    q.width = len(floorContent[0])
    fmt.Println(q.height, q.width)
    q.root = q.creerLesEnfants(q.width, q.height, 0, 0, floorContent)
    return q
}
func (q *Quadtree) creerLesEnfants(largeur, longueur, topleftx, toplefty int, floorContent [][]int) *node {
    nodeActuel := &node{
        topLeftX: topleftx,
        topLeftY: toplefty,
        width:    largeur,
        height:   longueur,
        // content:  1,
    }
    //si elle n'a plu d'enfants donc elle est homogene on lui donne le content actuelle
    if memeContentOuPas(topleftx, toplefty, largeur, longueur, floorContent) {
        nodeActuel.content = floorContent[toplefty][topleftx]
    }
    if !memeContentOuPas(topleftx, toplefty, largeur, longueur, floorContent) && largeur > 1 && longueur > 1 && largeur%2 == 0 && longueur%2 == 0 {

        midX := largeur / 2
        midL := longueur / 2
        nodeActuel.topLeftNode = q.creerLesEnfants(midX, midL, topleftx, toplefty, floorContent)
        nodeActuel.topRightNode = q.creerLesEnfants(midX, midL, topleftx+midX, toplefty, floorContent)
        nodeActuel.bottomLeftNode = q.creerLesEnfants(midX, midL, topleftx, toplefty+midL, floorContent)
        nodeActuel.bottomRightNode = q.creerLesEnfants(midX, midL, topleftx+midX, toplefty+midL, floorContent)
    }
    return nodeActuel
}
func memeContentOuPas(topLeftX, topLeftY, largeur, longueur int, floorContent [][]int) bool {
    //on prend la premiere valeur de floorContent en haut a gauche pour pouvoir la comparer aux autre coordonnées
    premierevaleur := floorContent[topLeftY][topLeftX]
    fmt.Printf("topLeftX: %d, topLeftY: %d, Largeur: %d, Longueur: %d, Première Valeur: %d\n", topLeftX, topLeftY, largeur, longueur, premierevaleur)
    //on parcourt que la zone spécifié de la coordonne en haut a gauche x et y  jusqu'à celle-ci + la coordonnne
    //donc pour parcourir que les valeurs de la zone rectangulaire/carré et pas tout le tableau content
    for y := topLeftY; y < longueur+topLeftY; y++ {
        for x := topLeftX; x < largeur+topLeftX; x++ {
            // fmt.Println(floorContent[y])
            //si renvoie false alors la zone est pas homogene
            if floorContent[y][x] != premierevaleur {
                return false
            }
        }
    }
    return true
}
0

There are 0 answers