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
}