Rectangles de couverture

Question

J'ai N rectangles dont les côtés sont parallèles aux axes x et y. Il existe un autre rectangle, modèle . J'ai besoin de créer un algorithme qui peut dire si les modèle est entièrement couverte par le N rectangles.

J'ai quelques idées. Je pense que tout d'abord, je dois trier les rectangles par leur côté gauche (cela peut être fait en O(n log n) temps), puis utilisez une ligne de balayage verticale.

+------------------------------------------------------------> x
|O
|                  +----+
|   +---------+    |    |
|   |        ++----+--+ |
|   |      +-++----+-+| |
|   |      | |     +-++-+
|   +------+ +-------++
|          +---------+
|
|
|
|y

Le rectangle bleu est le modèle .

Tout d'abord, j'ai besoin de l'algorithme abstrait. Il n'y a pas d'exigences particulières en ce qui concerne la réalisation. Un rectangle peut être représenté par une paire de points (gauche-haut et bas-droit).

C'est l'une des tâches de préparation d'un examen. Je sais que le meilleur algorithme peut faire cela en O(n log n) temps.

Answer 1

Voici un algorithme pour diviser et conquérir. La complexité moyenne du cas est très bonne et je dirais que c'est quelque chose comme O(n log MaxCoords) . Dans le pire des cas, il pourrait être quadratique, mais je pense qu'un tel test serait assez difficile à créer. Pour le rendre encore plus difficile, rendez l'ordre des appels de fonctions récursives aléatoire. Peut-être que ce que @Larry a suggéré peut permettre d'arriver à O(n log n) en moyenne.

Je n'arrive pas à trouver une solution en ligne de balayage, mais pour les tests que j'ai effectués, c'est très rapide.

En gros, il faut utiliser une fonction récursive qui fonctionne sur le rectangle bleu. On vérifie d'abord si le rectangle bleu est complètement couvert par l'un des autres rectangles. Si oui, on a fini. Si non, on le divise en 4 quadrants, et on appelle récursivement la fonction sur ces quadrants. Les 4 appels récursifs doivent retourner vrai. J'ai inclus du code C# qui dessine les rectangles. Vous pouvez le modifier pour qu'il fonctionne également avec des valeurs plus grandes, mais supprimez les procédures de dessin dans ce cas, car elles prendront une éternité. Je l'ai testé avec un million de rectangles et un carré d'un milliard de côté généré de telle sorte qu'il ne soit pas couvert, et la réponse fournie ( false ) a pris environ une seconde sur un quadcore.

J'ai testé cela sur des données aléatoires principalement, mais cela semble correct. S'il s'avère que ce n'est pas le cas, je supprimerai ce message, mais peut-être que cela vous mettra sur la bonne voie.

public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    List<Rectangle> Rects = new List<Rectangle>();

    private const int maxRects = 20;

    private void InitRects()
    {
        Random rand = new Random();

        for (int i = 0; i < maxRects; ++i) // Rects[0] is the model
        {
            int x = rand.Next(panel1.Width);
            int y = rand.Next(panel1.Height);

            Rects.Add(new Rectangle(new Point(x, y), new Size(rand.Next(panel1.Width - x), rand.Next(panel1.Height - y))));
        }
    }

    private void DrawRects(Graphics g)
    {
        g.DrawRectangle(Pens.Blue, Rects[0]);
        for (int i = 1; i < Rects.Count; ++i)
        {
            g.DrawRectangle(Pens.Red, Rects[i]);
        }
    }

    private bool Solve(Rectangle R)
    {
        // if there is a rectangle containing R
        for (int i = 1; i < Rects.Count; ++i)
        {
            if (Rects[i].Contains(R))
            {
                return true;
            }
        }

        if (R.Width <= 3 && R.Height <= 3)
        {
            return false;
        }

        Rectangle UpperLeft = new Rectangle(new Point(R.X, R.Y), new Size(R.Width / 2, R.Height / 2));
        Rectangle UpperRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y), new Size(R.Width / 2, R.Height / 2));
        Rectangle LowerLeft = new Rectangle(new Point(R.X, R.Y + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2));
        Rectangle LowerRight = new Rectangle(new Point(R.X + R.Width / 2 + 1, R.Y + + R.Height / 2 + 1), new Size(R.Width / 2, R.Height / 2));

        return Solve(UpperLeft) && Solve(UpperRight) && Solve(LowerLeft) && Solve(LowerRight);
    }

    private void Go_Click(object sender, EventArgs e)
    {
        Graphics g = panel1.CreateGraphics();
        panel1.Hide();
        panel1.Show();
        Rects.Clear();

        InitRects();
        DrawRects(g);

        textBox1.Text = Solve(Rects[0]).ToString(); 
    }

Answer 2

Voici un algorithme générique

1. Y a-t-il un rectangle couvrant l'ensemble du modèle ?
   si oui, vous avez terminé
2. si non, y a-t-il des rectangles couvrant partiellement le modèle ?
   si oui
3. est l'union de toutes les intersections du rectangle et du modèle égale au modèle
   si 2. ou 3. est non alors la réponse est non, sinon c'est oui

La question est maintenant de savoir comment faire ce qui précède de manière efficace. Ce qui précède peut être fait en une seule boucle sur tous les polygones, donc je pense que vous cherchez un temps O(n).

Si vous devez créer un algorithme efficace qui testera plusieurs modèles, ou si vous devez optimiser la réponse la plus rapide possible (au détriment de la préparation des données), vous recherchez une structure qui permettra de répondre rapidement à la question de savoir si un rectangle intersecte (ou contient) un rectangle.

Si vous utilisez, par exemple kd-trees Je pense qu'il est possible de répondre à cette question en un temps O(log n) - mais la variable importante de cet algorithme est également le nombre de rectangles trouvés k. Vous obtiendrez quelque chose comme O(k + log n) et vous devrez également effectuer la partie union pour tester si le modèle est couvert.

A mon avis, l'union pourrait être calculée en O(k log k), donc si k est petit, on peut s'attendre à O(log n) et si k est comparable à n, cela devrait être O(k log k).

Voir aussi este question.

EDIT : En réponse à la complexité des intersections et des unions.

Plus en détail, nous avons deux scénarios selon que k << n ou k comparable à n

a) dans le cas de k << n et en supposant une complexité polynomiale pour l'intersection/union (donc ici j'abandonne la supposition O(k log k) ) nous avons :

• log n à trouver une gamme dans un arbre indexé kd (de rectangles),
• k étapes pour retrouver tous les rectangles de cette "branche",
• f(k) un certain temps polynomial pour calculer les intersections et les unions

Le total est O(k + log n + f(k)), qui est directement égal à O(log n) puisque le grand O ne dépend que du terme à croissance la plus rapide.

Dans ce cas, la partie la plus importante de l'algorithme est la recherche des polygones.

b) dans le cas où k est comparable à n, nous devons examiner la complexité des algorithmes d'intersection et d'union. (remarquez le parallèle ici sur la façon dont les RDBMs, en fonction de la sélectivité, peuvent utiliser l'index ou faire un balayage de table ; c'est un choix similaire à ce que nous avons ici).
Si k est assez grand, l'algorithme devient moins un algorithme pour trouver les rectangles qui coupent le rectangle et devient plus un algorithme pour calculer l'union des polygones.

Mais, je crois que l'arbre kd peut également aider à trouver l'intersection des segments (qui sont nécessaires pour construire l'union), donc même cette partie de l'algorithme pourrait ne pas nécessiter k^2 temps. A ce stade, je rechercherais des algorithmes efficaces pour calculer l'aire des unions.

Answer 3

Vous êtes sur la bonne voie avec la ligne de balayage. Conceptuellement, nous voulons détecter quand l'intersection du modèle avec la ligne de balayage n'est pas couverte par les autres rectangles. Le modèle de haut niveau consiste à décomposer chaque rectangle en un événement "bord gauche" et un événement "bord droit", à trier les événements par coordonnée x (en mettant les gauches avant les droits si les rectangles sont fermés et les droits avant les gauches s'ils sont ouverts), puis à traiter chaque événement en temps O(log n). Il s'agit essentiellement d'un devoir à domicile, je n'en dirai donc pas plus.

Answer 4

Il y a un trivial O(N^2) qui est similaire à l'approche "raster" évoquée. Puisque tous les rectangles sont parallèles à l'axe, il ne peut y avoir qu'au maximum 2N dimension x et y distinctes. Triez tous les x et y et remappez-les : x_i -> i . Donc maintenant vous avez un 2N x 2N où vous pouvez facilement utiliser la matrice naïve O(N^2) algorithme.

Answer 5

J'y ai réfléchi et je crois que j'ai enfin compris ce que @algorithmist signifié par ligne de balayage . Cependant, la présence même de sorting les opérations signif signif signif d que c pour moi :

• O(n log n) en moyennement
• O(n**2) dans le pire cas

Ligne de balayage

Tout d'abord, nous avons besoin d'un certain tri, parce que notre sweep line consistera à parcourir un ensemble ordonné.

Ce jeu ordonné comprendra les top y bottom de chacune des red pour autant qu'ils se situent entre les top y bottom de blue . Cela divise notre espace en (au maximum) n*2 des bandes horizontales.

Maintenant, nous devons nous assurer que dans chaque strip , l'ensemble de blue est couverte, et cette opération ne peut pas avoir plus de O(log n) La complexité, cela pourrait être fait si nous avions (pour chaque bande) une liste des intervalles couverts. Voici l'événement @algorithmist parle de

Pour gérer cet événement, nous utiliserons un arbre binaire décrit ci-dessous qui gère l'ajout ou la suppression d'un rectangle en exactement O(log n) et donne l'intervalle le plus à droite couvert par l'arbre, que nous utilisons pour savoir si la bande de blue est couvert ou non.

Arbre binaire

Tout d'abord, je vais indexer les red rectangles. Nous les trions à l'aide de cette fonction :

def __lt__(lhs, rhs):
  return (lhs.left <  rhs.left)
      or (lhs.left == rhs.left and lhs.right < rhs.right)

Je vais donc créer un arbre binaire dédié.

• Il aura N feuilles, chacune représentant un red rectangle et indiquant sa présence ou son absence. Ils sont classés selon l'indice.
• Chaque nœud intermédiaire aura pour valeur l'intervalle le plus à droite couvert par ses enfants.

Gestion du bug "le bloc de code ne peut pas suivre la liste" :

class Node:
  def __init__(self):
    self.interval = []
    self.left  = None
    self.right = None

Maintenant, nous avons deux possibilités, disons que les enfants couvrent [a,b] y [c,d] :

• si c <= b alors le nœud tient [a,d]
• sinon, il tient [c,d]

Pourquoi cela fonctionne-t-il ? Prenons un exemple avec 4 feuilles :

        _ [1,9] _
       /         \
   [1,7]         [6,9] <-- Special node merge
   /   \         /   \
  /     \       /     \
[1,3] [2,7]   [3,5] [6,9]

Le nœud spécial ignore [3,5] parce que ce n'est pas l'intervalle le plus à droite. Le raisonnement est que les rectangles sont ordonnés :

• Aucun rectangle à droite de [6,9] couvrira le manque [5,6] intervalle puisqu'ils commencent après 6
• Les rectangles à gauche de [3,5] commencer avant 3 donc s'ils couvrent les manquants [5,6] ils couvriront [3,5] de toute façon

La Racine peut ne pas indiquer l'ensemble exact des intervalles couverts : seulement l'intervalle le plus à droite couvert. Cependant, il est parfaitement suffisant pour nous permettre de savoir si blue est complètement couvert ou non !

Il y a 2 opérations disponibles sur cet arbre :

• Marquer un rectangle comme présent
• Marquer un rectangle comme absent

Chacune est similaire :

• si le rectangle était déjà dans cet état, ne rien faire
• sinon, basculer son état, puis mettre à jour son intervalle parent (de manière récursive, jusqu'à la Racine)

La partie récursive prend O(log n) . C'est une propriété classique des arbres binaires équilibrés. Et une fois que c'est fait, nous avons l'intervalle le plus à droite couvert par la Racine, ce qui est suffisant pour dire si oui ou non la blue Le segment est entièrement couvert ou non.

Complexité

La complexité de l'algorithme est simple :

• Nous avons O(n) événements
• Chaque événement est traité dans O(log n)

Ce qui donne O(n log n) pour la partie centrale.

Cependant, nous ne devons pas oublier que nous avons également 2 sort opérations :

• un pour classer les événements (pour la ligne de balayage)
• l'autre pour classer les rectangles (pour l'arbre binaire)

Chacun doit prendre O(n log n) en Moyenne mais peut dégénérer en O(n**2) dans le pire des cas, en fonction de l'algorithme de tri utilisé.