Trouver efficacement à quel intervalle appartient un élément

Version imprimable

15/01/2019, 17h20
AbsoluteLogic

Trouver efficacement à quel intervalle appartient un élément

Bonjour,

Pour un segment [a,b], j'ai une subdivision donnée de taille N: le segment est divisé en N sous-segments disjoints dont la réunion fait [a,b].
Etant donnée une valeur x, je souhaiterais savoir à quel intervalle de la subdivision il appartient, si possible en temps constant.
J'ai fait quelques recherches, et j'ai trouvé ce sujet. Mais la meilleure solution reste en O(log(N)) au pire. :(

Cependant, je suis intrigué sur le fait que ce ne soit pas possible de le faire en temps constant pour deux raisons :?:
- on peut imaginer une discrétisation du segment, qui transforme alors ce dernier en tableau dans lequel chaque élément correspond à l'indice du sous intervalle correspondant. On a alors une complexité constante: il faut juste lire la valeur dans le tableau. Evidemment, on ne peut pas se permettre de discrétiser le segment, mais je me dit (sûrement à tort) que ce qui est faisable en discret peut être faisable en continu...
- le problème me fait penser aux tables de hachage (que je ne connais pas très bien), qui à une valeur en associe une autre en temps constant. N'y aurait-il pas moyen de ramener nos sous-intervalles à ces valeurs?

De plus, je peux me permettre de faire un travail préliminaire (connaissant la subdivision mais pas la valeur x) qui n'a pas besoin d'être en temps constant.

Voilà, si vous connaissez des méthodes dans ce domaine, ou que vous avez des idées sur le sujet, je suis preneur.
Merci d'avance

PS: mon problème est en fait en deux dimensions: un rectangle divisé en sous-rectangles, mais je pose d'abord le problème en une dimension, en espérant ensuite pouvoir le ramener en 2D (voire n dimensions :P)
15/01/2019, 18h58
anapurna

salut

en prenant la valeur median de ton segment et faire une recherche dichotomique cela ne le ferais pas ?
il Faut chercher la valeur la plus proche et normalement tu trouve le bon segment
pour la 2d il faudra prendre le point median en x et en y et appliquer la meme regle sur les rectangle cela devrais te limiter ta recherche
ce qui te donne une complexité de ... O(logn) je ne pense pas que tu pourra pas faire mieux
15/01/2019, 19h17
AbsoluteLogic

Citation:

Envoyé par anapurna

en prenant la valeur median de ton segment et faire une recherche dichotomique cela ne le ferais pas ?
[...]
une complexité de ... O(logn) je ne pense pas que tu pourra pas faire mieux

Salut. Merci d'avoir porté ton intérêt au problème.
Oui, la dichotomie est une solution pour obtenir du log(N), comme il l'a été évoqué dans le sujet que j'ai indiqué.
Mais j'ai toujours espoir qu'il y ait une solution en temps constante (éventuellement avec un travail préliminaire non constant) dans la mesure où j'ai évoqué deux problèmes proches résolubles en temps constant...
15/01/2019, 20h01
pseudocode

Citation:

Envoyé par AbsoluteLogic

le problème me fait penser aux tables de hachage (que je ne connais pas très bien), qui à une valeur en associe une autre en temps constant.

C'est en temps constant seulement si on fixe un certains nombres de paramètres, en particulier le nombre de bits et d'opérations par bit.

De même, ta recherche dichotomique en o(log(n)) sera "en temps constant" si tu fixes le nombre de subdivisions N. :P
15/01/2019, 21h32
Flodelarab

1 pièce(s) jointe(s)

Bonjour :coucou:

L'équivalent continu d'un tableau (associatif ou non) s'appelle une fonction.
En l'occurrence, ici, c'est une fonction en escalier.

Charge pour toi de trouver la meilleure façon de définir.

Je pense en particulier à la fonction sigmoïde utilisée dans les réseau de neurones, que tu peux utiliser comme une fonction de heaviside que tu empilerais.

$Formule mathématique$

Code:

gnuplot> plot [0:10][0:10] 0, 2/(1+exp(100*(-x)))+ 5/(1+exp(100*(5-x))) - 3/(1+exp(100*(8-x)))

Pièce jointe 441748
16/01/2019, 16h42
disedorgue

Déjà, comment représentes-tu ton rectangle initial par rapport aux sous rectangles ?
Ont-ils une largeur et longueur différente ou seulement soit la longueur soit la largeur ?

Comment représentes-tu X dans le plan ?
16/01/2019, 19h54
AbsoluteLogic

3 pièce(s) jointe(s)

Merci à tous pour avoir pris le temps de me répondre

Citation:

Envoyé par pseudocode

C'est en temps constant seulement si on fixe un certains nombres de paramètres, en particulier le nombre de bits et d'opérations par bit.

De même, ta recherche dichotomique en o(log(n)) sera "en temps constant" si tu fixes le nombre de subdivisions N. :P

Certes, j'imagine que tu veux mettre en avant qu'il y a une infinité d'intervalle possibles, alors qu'un dictionnaire prend un nombre fini d'entiers possibles en entrée.
Mouais, je ne suis pas convaincu, en allant par là, même le nombre d'intervalle possibles est fini puisque leurs extrémités sont codées sur un certain nombre de bit...

Citation:

Envoyé par Flodelarab

Bonjour :coucou:

L'équivalent continu d'un tableau (associatif ou non) s'appelle une fonction.
En l'occurrence, ici, c'est une fonction en escalier.

Charge pour toi de trouver la meilleure façon de définir.

Je pense en particulier à la fonction sigmoïde utilisée dans les réseau de neurones, que tu peux utiliser comme une fonction de heaviside que tu empilerais.

Houlà, ça fait drôle d'entendre parler des réseaux de neurones et des fonctions sigmoïde, alors que c'est justement ce que je suis en train d'étudier à mon école! Mais en aucun j'en aurai parlé sur ce sujet ^^
C'est vrai, l'idée serait tout simplement d'évaluer une certaine fonction en escalier. Mais je ne pense pas qu'une fonction de Heaviside soit une solution, puisque si l'on considère la complexité par rapport à l'opération la plus longue - ici l'exp -, on reste en temps linéaire par rapport au nombre d'intervalle.
Je fais alors le raisonnement suivant:
Pour évaluer la fonction en escalier en temps constant, il faudrait le représenter par son graphe. Mais cela implique de le discrétiser puisqu'on est en informatique :P. On pourrait donc se dire que ça ne sert à rien: on a justement pris une fonction pour rendre le problème continu, qu'est-ce qu'il raconte là? :roll:
En fait, ça me donne une idée: si on prend comme pas de discrétisation la longueur du plus petit intervalle de notre liste, on peut représenter la subdivision par un tableau dont chaque élément correspond à un pas, et contient le triplet (intervalle de gauche, abscisse de changement, intervalle de droite) si il y a un changement d'ordonnée sur ce pas. Et puisque le pas correspond à la longueur du plus petit intervalle, alors il ne pourra pas y avoir deux changements d'intervalle sur le même pas.
Pièce jointe 442092
Du coup, cela répond à mon problème: on pourra, avec x donné, récupérer l'intervalle correspondant en allant chercher dans le tableau l'élément correspondant et en faisant une comparaison de x avec "l'abscisse de changement". Cela se fait en temps constant, avec une préparation d'un coût non constant. Mais le problème, c'est que l'on est même pas en mesure de connaître ce coût de préparation (et la mémoire occupée) en fonction du nombre d'intervalle, puisque ce sera en O((b-a)/(longueur minimale)).
Mais bon, si la complexité de la préparation n'a pas besoin d'être majorée, ça va. Et libre à nous de trouver un compromis en permettant par exemple de pouvoir encoder 2 (ou plus) changements de valeur sur un pas au lieu d'un seul.
Voilà, je marque le sujet en résolu. Mais il n'est pas interdit de proposer des solutions encore plus performantes, à la fois en terme de mémoire consommée ou de complexité de préparation.

Citation:

Envoyé par disedorgue

Déjà, comment représentes-tu ton rectangle initial par rapport aux sous rectangles ?
Ont-ils une largeur et longueur différente ou seulement soit la longueur soit la largeur ?

Comment représentes-tu X dans le plan ?

C'est juste un ensemble de rectangles qui en "pave" un plus gros comme sur la figure suivante:
Pièce jointe 442096
Et je peux facilement me ramener à un problème en une dimension, en me ramenant à un quadrillage séparant tous ces rectangles, en en étudiant séparément les abscisses et les ordonnées:
Pièce jointe 442097
16/01/2019, 21h22
disedorgue

Et si j'ai bien compris, X est un point et le but est de savoir dans quel rectangle il se trouve ?

Et dans un espace à 3 dimensions, l'algo doit aussi fonctionner ?

Je pose cette question, car pour le cas du plan rectangulaire, intuitivement, je pense que c'est possible de passer par des vecteurs, mais comme je dis, pour l'instant c'est juste intuitif, donc pas encore sur de moi...
17/01/2019, 10h21
wiwaxia

3 pièce(s) jointe(s)

Trouver efficacement à quel intervalle appartient un élément

Bonjour, :D

Je crois que toute la difficulté de ton projet vient de ce qu'il n'est pas réductible à deux problèmes plus simples, à une dimension:

Citation:

Envoyé par AbsoluteLogic

... Pour un segment [a,b], j'ai une subdivision donnée de taille N: le segment est divisé en N sous-segments disjoints dont la réunion fait [a,b].
Etant donnée une valeur x, je souhaiterais savoir à quel intervalle de la subdivision il appartient, si possible en temps constant.
...
PS: mon problème est en fait en deux dimensions: un rectangle divisé en sous-rectangles, mais je pose d'abord le problème en une dimension, en espérant ensuite pouvoir le ramener en 2D (voire n dimensions :P)

En effet, le découpage en intervalles sur chacun des axes que tu espères

Pièce jointe 442209
fait intervenir des limites interdépendantes

Pièce jointe 442212

Il te faut donc définir un ensemble fini de sous-domaines caractérisés par quatre bornes (x_i, x_j, y_k, y_l) et associés au booléen

(((x_i < x) AND (x < x_j)) AND ((y_k < y) AND (y < y_l)))

Pièce jointe 442216

pour obtenir une partition du domaine initial, c'est à dire un partage sans recouvrement mutuel, ni espace vide résiduel.
17/01/2019, 11h45
anapurna

salut

si je comprend bien
tu découpe ton récipient en N intervalle de h tels que N*h =LargeurMax
avec h = Min(Segments)
et donc quand on nous donne X
l'indice dans le tableau de la valeur X sera X div h = Ix
mais cela implique une grosse préparation en amont et pour des segments plus petit un recalcule complet des éléments

sinon le principe est plutôt sympa
pour l'appliquer a la 2D il faudras que l'indice du tableau
soit de l'ordre de x+y*NbCol
17/01/2019, 13h22
wiwaxia

1 pièce(s) jointe(s)

Trouver efficacement à quel intervalle appartient un élément
On pourrait envisager la constitution de deux listes constituées des seuils successifs délimitant les sous-domaines, sur chacun des axes (x'x) et (y'y):
Code:

1 2 3 4 CONST Nx = 5; Ny = 4; VAR LstX: ARRAY[1..Nx] OF Reel; // LstX = (X1, X2, X3, X4, 1) VAR LstY: ARRAY[1..Ny] OF Reel; // LstY = (Y1, Y2, Y3, 1)
puis ensuite une matrice rectangulaire (Nx*Ny) qui caractériserait la partition en livrant la correspondance entre frontières horizontales et verticales.

Dans le cas illustré ci-dessous:

Pièce jointe 442323
la matrice présenterait l'allure suivante:
Code:

1 2 3 4 5 6 7 8 9 10 i\j 1 2 3 4 5 1 1 4 4 7 7 2 2 4 4 7 7 3 3 3 5 7 7 4 3 3 6 6 8
en convenant de caractériser par leur rang les 8 sous-domaines rencontrés successivement au cours d'un balayage de haut en bas et de gauche à droite - donc dans le sens croissant des indices (i, j).
17/01/2019, 14h53
AbsoluteLogic

Citation:

Envoyé par disedorgue

Et si j'ai bien compris, X est un point et le but est de savoir dans quel rectangle il se trouve ?

Et dans un espace à 3 dimensions, l'algo doit aussi fonctionner ?

[EDIT: Wiwaxia a répondu en même temps que moi et je n'avais pas vu son post, donc je répète un peu ce qu'il a dit ^^]
Pour le problème en 2D, X=(x,y) et on doit bien trouver dans quel rectangle il se trouve.
On commence par un travail préliminaire (une seul fois avant de connaitre X): on crée un tableau (de taille 4x5 pour l'exemple qu'on a pris) dans lequel on note les couleurs (ou plutôt les références) des rectangles correspondants.
Ensuite, chaque fois que l'on a un X=(x,y) pour lequel on doit déterminer le rectangle dans lequel il est, on fait le raisonnement suivant. En reprenant les notations de wiwaxia (#9), on cherche pour quel i x est dans [x_i,x_i+1], et pour quel j y est dans [y_j,y_j+1]. On peut alors chercher le rectangle dans le tableau aux indices i,j.

Et en trois dimensions, avec X=(x,y,z), on fait exactement le même raisonnement.

Citation:

Envoyé par anapurna

si je comprend bien
tu découpe ton récipient en N intervalle de h tels que N*h =LargeurMax
avec h = Min(Segments)
et donc quand on nous donne X
l'indice dans le tableau de la valeur X sera X div h = Ix
mais cela implique une grosse préparation en amont et pour des segments plus petit un recalcule complet des éléments

Tu as bien compris ;).
Mais justement, cette préparation est effectivement très peu efficace, mais cette solution est satisfaisante pour moi dans la mesure où elle ne sera faite qu'une seule fois, pour ensuite l'appliquer à des milliers voire des millions de tests pour différents X.
Malgré ça, je me répète: je ne refuse pas d'autres solutions pour lesquelles le calcul pour un X donné se fait en temps constant, et avec un travail préliminaire plus efficace (et moins gourmand en mémoire).

Citation:

Envoyé par anapurna

sinon le principe est plutôt sympa
pour l'appliquer a la 2D il faudras que l'indice du tableau
soit de l'ordre de x+y*NbCol

Je ne vois pas vraiment ce que tu veux dire, mais je ne pense pas avoir besoin de ça, ça ne résoudra pas le problème du passage aux rectangles.
Mais avec la nouvelle explication, tu vois sûrement ce que je veux dire.
17/01/2019, 17h29
anapurna

salut

dans ton exemple ton découpage n'est pas uniforme ce qui me trouble .
utilise tu un fonction logarithmique ou autre pour ton découpage ?
le X fournit est bien un position ?

tu ou l'un des autres intervenant dis

Citation:

on cherche pour quel i x est dans [xi,xi+1], et pour quel j y est dans [yj,yj+1]. On peut alors chercher le rectangle dans le tableau aux indices i,j.

ce qui revient a faire une recherche de X ... quel type de recherche tu déplace le problème a mon avis

je comprend bien le but d’accès direct à l'indice mais si tu n'as pas moyen de retrouver cette indice rapidement
toutes ta jolie mécanique ne sert a rien

en réfléchissant un peu je m’aperçois qu'il y a effectivement un loups dans mon descriptifs ... que fait t'on lorsque
l'intervalle tombe en plein milieu d'un changement de zone
pour pallier a ceci il faut que l'on puisse trouver un diviseur commun à tout les segments

PS : Je viens de comprendre ce que vous voulez faire ... des fois il faut prendre un peu de recule pour mieux voir ;)
c'est quand même pas si simple a trouver la fonction en escalier qui détermine les différents element
ne serait t'il pas plus simple de subdiviser ton écran par des pas constant
et ensuite au sein de ces subdivision rechercher l’élément correspondant en accès direct dans un tableaux

imagine que tu est une image de 1024 pixel
tu la subdivise par 16 ce qui te donne 16 element de 64 pixel

ton X par exemple est de 82

donc IDCASE = (X Div 64) +1 = 2 donc ton element se trouve dans la deuxième subdivision
ensuite de la subdivision tu cherche X -(64 * IDCASE - 1) = 18
maintenant as tu la possibilités de créer de subdivisions en mémoire c'est une autre histoire
tu auras un temps constant 2 accès
le premier pour réduire le choix des éléments et le second pour définir précisément ou tu te trouve dans un tableau indiquant bien évidement sur lequel des rectangle il pointes
c'est une sorte de ZOOM la première opération tu ne vois rien de précis (global) a la seconde tu as la précision afin de déterminer avec exactitude ce que tu cherche (detail)

Citation:

Envoyé par anapurna

c'est quand même pas si simple a trouver la fonction en escalier qui détermine les différents element
ne serait t'il pas plus simple de subdiviser ton écran par des pas constant
et ensuite au sein de ces subdivision rechercher l’élément correspondant en accès direct dans un tableaux

imagine que tu est une image de 1024 pixel
tu la subdivise par 16 ce qui te donne 16 element de 64 pixel

ton X par exemple est de 82

donc IDCASE = (X Div 64) +1 = 2 donc ton element se trouve dans la deuxième subdivision
ensuite de la subdivision tu cherche X -(64 * IDCASE - 1) = 18
maintenant as tu la possibilités de créer de subdivisions en mémoire c'est une autre histoire
tu auras un temps constant 2 accès
le premier pour réduire le choix des éléments et le second pour définir précisément ou tu te trouve dans un tableau indiquant bien évidement sur lequel des rectangle il pointes
c'est une sorte de ZOOM la première opération tu ne vois rien de précis (global) a la seconde tu as la précision afin de déterminer avec exactitude ce que tu cherche (detail)

C'est ce que je fais au début, mais je prends le pas égal à la longueur minimale des sous-intervalles. De cette manière, une fois que j'ai fait le travail "global" en ayant IDCASE, je suis sûr que le travail "détail" se fera en temps constant dans la mesure où l'élément du tableau ne pourra contenir au plus qu'un changement d'intervalle.
Je ne comprend donc pas comment tu imagines un temps constant pour le "détail" si tu prends un pas ne dépendant pas des intervalles: une fois que tu sauras quel élément du tableau regarder, tu ne pourras pas majorer le nombre d'intervalles à prendre en compte pour le détail. Je vois dans ton exemple que tu imagines des pixels, donc des entiers, mais il faut considérer des flottants. Donc la taille des sous-intervalles peut être aussi petit que possible...

Citation:

Envoyé par anapurna

Je viens de comprendre ce que vous voulez faire ... des fois il faut prendre un peu de recule pour mieux voir ;)

J'ai codé ce que j'imaginais en C# pour le tester. Je le poste pour lever toute ambiguité sur le raisonnement (les langages de programmation sont fait pour ça ;)). J'avoue ne pas avoir le courage de l'écrire en pseudocode, mais je pense que ça reste compréhensible, même sans connaissance en C#.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
    class IntervalPartition
    {
        struct IntervalChange
        {
            public int index;
            public float xChange;
        }
 
        IntervalChange[] intervallesChange;
        float start;
        float end;
        float pas;
 
        public IntervalPartition(float[] partition)
        {
            start = partition[0];
            end = partition[partition.Length - 1];
 
            // On choisit un pas de discrétisation égal au pas le plus petit de la subdivision
            // et on vérifie que la subdivision est triée pour éviter des absurdités
            pas = float.PositiveInfinity;
            for (int i = 1; i < partition.Length; i++)
            {
                if (partition[i] < partition[i - 1])
                    throw new Exception("Subdivision non triée");
                if (partition[i] > partition[i - 1])
                    pas = Math.Min(pas, partition[i] - partition[i - 1]);
            }
 
            // On crée un tableau contenant les informations sur ce qui se passe sur l'intervalle complet
            // chaque élément représente ce qui se passe sur un pas
            int n = (int)Math.Ceiling((end-start) / pas);
            intervallesChange = new IntervalChange[n];
            int partitionIndex = 0;
            for(int i=0; i<n; i++)
            {
                // Sur chaque pas
                intervallesChange[i].index = partitionIndex;
                if (start + (i+1)*pas > partition[partitionIndex+1])
                {
                    // soit on rencontre un changement d'intervalle
                    partitionIndex++;
                    intervallesChange[i].xChange = partition[partitionIndex]; 
                }
                else
                    // soit on continue sans changer
                    intervallesChange[i].xChange = end;     // Valeur par défaut, s'il n'y a aucun changement d'intervalle
            }
        }
 
        public int GetIntervalOf(float x)
        {
            if(x > end || x < start)
                throw new Exception("x est hors des limites");
            // On calcule dans quel pas de discrétisation on se trouve
            IntervalChange intervalChange = intervallesChange[(int)((x - start) / pas)];
            // et on regarde dans notre tableau quel sous-intervalle sur ce pas on prend
            if (x < intervalChange.xChange)
                return intervalChange.index;
            else
                return intervalChange.index + 1;
        }
    }

Et pour ceux qui n'ont toujours pas compris comment je passais d'intervalles 1D à des rectangles 2D, je poste également mon code pour le faire.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
    public class Rectangle
    {
        public float x;
        public float y;
        public float w;
        public float h;
 
        public Rectangle(float X, float Y, float W, float H)
        {
            x = X; y = Y; w = W; h = H;
        }
 
        public override string ToString()
        {
            return "(X:" + x + ", Y:" + y + ", W:" + w + ", H:" + h + ")";
        }
    }
 
    class RectanglePartition
    {
 
        IntervalPartition xPartition;
        IntervalPartition yPartition;
        Rectangle[,] grid;
 
        float epsilon = 1e-6f; // epsilon utilisé à cause des erreurs lors des comparaisons de flottants.
 
        public RectanglePartition(Rectangle[] rectangles)
        {
            // On suppose que les rectangles donnés forment bien une partition d'un plus grand rectangle
 
            List<float> xPartitionList = new List<float>();
            List<float> yPartitionList = new List<float>();
            for (int i=0; i<rectangles.Length; i++)
            {
                // Pour chaque rectangle
                int indexPartition;
                // Ajout du côté gauche
                for (indexPartition = 0; indexPartition < xPartitionList.Count; indexPartition++)
                    if (xPartitionList[indexPartition] >= rectangles[i].x * (1 - epsilon))
                        break;
                if(indexPartition == xPartitionList.Count || Math.Abs(xPartitionList[indexPartition] - rectangles[i].x) > epsilon)
                    xPartitionList.Insert(indexPartition, rectangles[i].x);
                // Ajout du côté haut
                for (indexPartition = 0; indexPartition < yPartitionList.Count; indexPartition++)
                    if (yPartitionList[indexPartition] >= rectangles[i].y * (1-epsilon))
                        break;
                if (indexPartition == yPartitionList.Count || Math.Abs(yPartitionList[indexPartition] - rectangles[i].y) > epsilon)
                    yPartitionList.Insert(indexPartition, rectangles[i].y);
                // Ajout du côté droit
                for (indexPartition = 0; indexPartition < xPartitionList.Count; indexPartition++)
                    if (xPartitionList[indexPartition] >= (rectangles[i].x + rectangles[i].w) * (1 - epsilon))
                        break;
                if (indexPartition == xPartitionList.Count || Math.Abs(xPartitionList[indexPartition] - (rectangles[i].x + rectangles[i].w)) > epsilon)
                    xPartitionList.Insert(indexPartition, rectangles[i].x + rectangles[i].w);
                // Ajout du côté bas
                for (indexPartition = 0; indexPartition < yPartitionList.Count; indexPartition++)
                    if (yPartitionList[indexPartition] >= (rectangles[i].y + rectangles[i].h) * (1 - epsilon))
                        break;
                if (indexPartition == yPartitionList.Count || Math.Abs(yPartitionList[indexPartition] - (rectangles[i].y + rectangles[i].h)) > epsilon)
                    yPartitionList.Insert(indexPartition, rectangles[i].y + rectangles[i].h);
            }
 
            xPartition = new IntervalPartition(xPartitionList.ToArray());
            yPartition = new IntervalPartition(yPartitionList.ToArray());
 
            grid = new Rectangle[xPartitionList.Count-1, yPartitionList.Count-1];
            // On remplit le tableau pour référencer chaque rectangle.
            foreach(Rectangle rectangle in rectangles)
            {
                int xStart = xPartition.GetIntervalOf(rectangle.x);
                int yStart = yPartition.GetIntervalOf(rectangle.y);
                int xEnd = xPartition.GetIntervalOf(rectangle.x + rectangle.w);
                int yEnd = yPartition.GetIntervalOf(rectangle.y + rectangle.h);
                for (int x = xStart; x < xEnd; x++)
                    for (int y = yStart; y < yEnd; y++)
                        grid[x, y] = rectangle;
            }
        }
 
        public Rectangle GetRectangleOf(float x, float y)
        {
            return grid[xPartition.GetIntervalOf(x), xPartition.GetIntervalOf(y)];
        }
    }