Une idée comme ça: on va imaginer les régions stockées sous la forme (x_min, x_max, y_min, y_max). Alors si on les range par ordre x_min croissant, on peut traverser la liste pour chercher celles qui contiennent un point (x, y) de la façon suivante:
* tant que x_max < x, on peut continuer, aucune chance que le point soit dedans (un seul test par zone, donc);
* dès que x_max >= x, on regarde la condition x_min <= x ; tant qu'elle est vraie, on fait la vérification y >= y_min et y <= y_max (ie: on regarde complètement ces zones: quatre tests par zone);
* dès que x_min > x, on s'arrête de parcourir la liste, il n'est plus possible que le point soit dans les zones (zéro test par zone).
Ca doit accélérer un peu les choses ; sachant qu'on peut encore améliorer les points suivants:
1) s'assurer que le compilo fait une évaluation paresseuse des conditions sur y (ie: pas de test de la seconde si la première est déjà fausse);
2) pour les zones qui ont le même x_min, les ranger par x_max croissant;
3) et pour les zones qui ont les mêmes x_min et x_max, les ranger par y_min croissant;
4) et pour les zones qui ont les mêmes x_min, x_max et y_min, les ranger par y_max croissant.
Le 1) coûte pas cher. Par contre 2), 3) et 4), suivant les configurations qui apparaissent dans le problème, on n'a rien à gagner. En fait, elles ne coûtent pas si cher à l'insertion, mais l'algo de parcours devient un peu lourd à écrire.
Et naturellement, si le problème fait qu'il vaut mieux ranger par y_min que par x_min, il ne faut pas se gêner!
# Re: Algorithme
Posté par Snark_Boojum . En réponse au journal Algorithme. Évalué à 1.
* tant que x_max < x, on peut continuer, aucune chance que le point soit dedans (un seul test par zone, donc);
* dès que x_max >= x, on regarde la condition x_min <= x ; tant qu'elle est vraie, on fait la vérification y >= y_min et y <= y_max (ie: on regarde complètement ces zones: quatre tests par zone);
* dès que x_min > x, on s'arrête de parcourir la liste, il n'est plus possible que le point soit dans les zones (zéro test par zone).
Ca doit accélérer un peu les choses ; sachant qu'on peut encore améliorer les points suivants:
1) s'assurer que le compilo fait une évaluation paresseuse des conditions sur y (ie: pas de test de la seconde si la première est déjà fausse);
2) pour les zones qui ont le même x_min, les ranger par x_max croissant;
3) et pour les zones qui ont les mêmes x_min et x_max, les ranger par y_min croissant;
4) et pour les zones qui ont les mêmes x_min, x_max et y_min, les ranger par y_max croissant.
Le 1) coûte pas cher. Par contre 2), 3) et 4), suivant les configurations qui apparaissent dans le problème, on n'a rien à gagner. En fait, elles ne coûtent pas si cher à l'insertion, mais l'algo de parcours devient un peu lourd à écrire.
Et naturellement, si le problème fait qu'il vaut mieux ranger par y_min que par x_min, il ne faut pas se gêner!
Bon courage