Nombre maximal possible de rectangles pouvant être traversés par une seule ligne droite

Question

J'ai trouvé ce problème de défi qui stipule ce qui suit :

Supposons qu'il existe n rectangles dans le plan XY. Écrivez un programme pour calculer le nombre maximum possible de rectangles qui peuvent être traversés par une seule ligne droite tracée sur ce plan.

J'ai réfléchi pendant un certain temps mais je n'ai pas trouvé de solution. Peut-être qu'à un moment donné, nous utiliserons des étapes de programmation dynamique, mais je n'ai pas réussi à trouver comment commencer.

Answer 1

Voici une esquisse d'une solution O(n^2 log n).

D'abord, les préliminaires partagés avec d'autres réponses. Lorsque nous avons une ligne passant par certains rectangles, nous pouvons la translater vers l'un des deux côtés jusqu'à ce qu'elle passe par un coin d'un certain rectangle. Après cela, nous fixons ce coin comme centre de rotation et faisons tourner la ligne vers l'un des deux côtés jusqu'à ce qu'elle passe par un autre coin. Pendant tout le processus, tous les points d'intersection entre notre ligne et les côtés du rectangle restent sur ces côtés, de sorte que le nombre d'intersections reste le même, tout comme le nombre de rectangles traversés par la ligne. En conséquence, nous ne pouvons considérer que les lignes qui passent par deux coins de rectangle, ce qui est plafonné par O(n^2), et constitue une amélioration bienvenue par rapport à l'espace infini des lignes arbitraires.

Alors, comment vérifier efficacement toutes ces lignes ? Tout d'abord, ayons une boucle externe qui fixe un point A et considère ensuite toutes les lignes passant par A. Il y a O(n) choix de A.

Maintenant, nous avons un point A fixe, et nous voulons considérer toutes les lignes AB passant par tous les autres coins B. Pour ce faire, il faut d'abord trier tous les autres coins B en fonction de l'angle polaire de AB, ou, en d'autres termes, de l'angle entre l'axe Ox et le vecteur AB. Les angles sont mesurés de -PI à +PI ou de 0 à 2 PI ou autrement, le point dans lequel on coupe le cercle pour trier les angles peut être arbitraire. Le tri se fait en O(n log n).

Maintenant, nous avons des points B ₁ , B ₂ , ..., B _k triés par l'angle polaire autour du point A (leur nombre k est quelque chose comme 4n-4, tous les coins de tous les rectangles sauf celui où le point A est un coin). Tout d'abord, regardez la ligne AB ₁ et compter le nombre de rectangles traversés par cette ligne en O(n). Après cela, envisagez de faire tourner AB ₁ à AB ₂ alors AB ₂ à AB ₃ jusqu'à AB _k . Les événements qui se produisent au cours de la rotation sont les suivants :

• Quand nous tournons vers AB _i et B _i est le premier coin d'un rectangle dans notre ordre, le nombre de rectangles traversés augmente de 1 dès que la ligne rotative atteint B _i .

• Quand nous tournons vers AB _j et B _j est le dernier coin d'un certain rectangle dans notre ordre, le nombre de rectangles traversés diminue de 1 dès que la ligne tourne au-delà de B _j .

Les coins qui sont les premiers et les derniers peuvent être établis avec un prétraitement O(n), après le tri, mais avant de considérer les événements ordonnés.

En bref, nous pouvons passer au prochain événement de ce type et mettre à jour le nombre de rectangles traversés en O(1). Et il y a k = O(n) événements au total. Ce qu'il reste à faire est de suivre le maximum global de cette quantité tout au long de l'algorithme. La réponse est justement ce maximum.

L'algorithme complet s'exécute en O(n * (n log n + n + n)), soit O(n^2 log n), comme annoncé.

Answer 2

(Modification de ma réponse précédente qui envisageait la rotation de l'avion).

Voici un croquis de la O(n^2) qui combine l'idée de Gassa avec la référence d'Evgeny Kluev aux arrangements de lignes doubles comme séquences angulaires triées.

Nous partons d'une liste d'arêtes doublement connectées ou d'une structure similaire, ce qui nous permet de diviser une arête en deux. O(1) et une méthode pour parcourir les faces que nous créons lorsque nous remplissons un plan bidimensionnel. Pour simplifier, n'utilisons que trois des douze coins des rectangles ci-dessous :

9|     (5,9)___(7,9)
8|         |   |
7|    (4,6)|   |
6|    ___C |   |
5|   |   | |   |
4|   |___| |   |
3|  ___    |___|(7,3)
2| |   |  B (5,3)
1|A|___|(1,1)
 |_ _ _ _ _ _ _ _
   1 2 3 4 5 6 7

Nous insérons les trois points (coins) dans le plan dual selon la transformation suivante :

point p => line p* as a*p_x - p_y
line l as ax + b => point l* as (a, -b)

Entrons les points dans l'ordre A, B, C . Nous entrons d'abord A => y = x - 1 . Comme il n'y a qu'un seul bord jusqu'à présent, nous insérons B => y = 5x - 3 qui crée le sommet, (1/2, -1/2) et divise notre bord. (Un aspect élégant de cette solution est que chaque sommet (point) dans le plan dual est en fait le point dual de la ligne passant par les coins des rectangles. Observez 1 = 1/2*1 + 1/2 y 3 = 1/2*5 + 1/2 points (1,1) y (5,3) .)

Entrée du dernier point, C => y = 4x - 6 nous cherchons maintenant la face la plus à gauche (qui pourrait être une face incomplète) où elle se croisera. Cette recherche est O(n) temps puisque nous devons essayer chaque face. Nous trouvons et créons le sommet (-3, -18) qui divise le bord inférieur de 5x - 3 et traverser les bords pour diviser la moitié droite de x - 1 au sommet (5/3, 2/3) . Chaque insertion a O(n) temps puisque nous devons d'abord trouver la face la plus à gauche, puis traverser chaque face pour séparer les bords et marquer les sommets (points d'intersection de la ligne).

Dans le plan double, nous avons maintenant :

Après avoir construit l'arrangement de lignes, nous commençons notre itération sur nos trois points d'exemple (coins du rectangle). Une partie de la magie de la reconstruction d'une séquence angulaire triée par rapport à un point consiste à partitionner les angles (chacun correspondant à une intersection de ligne ordonnée dans le plan double) en ceux correspondant à un point à droite (avec une coordonnée x plus grande) et ceux à gauche et à concaténer les deux séquences pour obtenir une séquence ordonnée de -90 degrés à -270 degrés. (Les points à droite se transforment en lignes avec des pentes positives par rapport au point fixe ; ceux à gauche, avec des pentes négatives. Faites pivoter votre sevice/écran dans le sens des aiguilles d'une montre jusqu'à ce que la ligne de (C*) 4x - 6 devient horizontal et vous verrez que B* a maintenant une pente positive et A* négatif.)

Pourquoi cela fonctionne-t-il ? Si un point p dans le plan d'origine est transformée en une ligne p* dans le plan dual, alors parcourir cette ligne double de gauche à droite correspond à une rotation d'une ligne autour de p dans le plan original qui passe aussi par p . La ligne double marque toutes les pentes de cette ligne de rotation par la coordonnée x de l'infini négatif (vertical) à zéro (horizontal) à l'infini (vertical à nouveau).

(Résumons la logique de comptage des rectangles, en mettant à jour le count_array pour le rectangle actuel tout en itérant à travers la séquence angulaire : s'il est égal à 1, incrémentez le compte d'intersection actuel ; s'il est égal à 4 et que la ligne n'est pas directement sur un coin, mettez-le à 0 et décrémentez le compte d'intersection actuel).

Pick A, lookup A*
=> x - 1.

Obtain the concatenated sequence by traversing the edges in O(n)
=> [(B*) 5x - 3, (C*) 4x - 6] ++ [No points left of A]

Initialise an empty counter array, count_array of length n-1

Initialise a pointer, ptr, to track rectangle corners passed in
the opposite direction of the current vector.

Iterate:
  vertex (1/2, -1/2)
  => line y = 1/2x + 1/2 (AB)

  perform rectangle-count-logic

  if the slope is positive (1/2 is positive):
    while the point at ptr is higher than the line:
      perform rectangle-count-logic

  else if the slope is negative:
    while the point at ptr is lower than the line:
      perform rectangle-count-logic

  => ptr passes through the rest of the points up to the corner
     across from C, so intersection count is unchanged

  vertex (5/3, 2/3)
  => line y = 5/3x - 2/3 (AC)

On peut voir que (5,9) est au-dessus de la ligne passant par AC (y = 5/3x - 2/3) ce qui signifie qu'à ce stade, nous aurions compté l'intersection avec le rectangle le plus à droite et n'aurions pas encore remis le compte à zéro, ce qui donne un total de 3 rectangles pour cette ligne.

Nous pouvons également voir dans le graphique du plan double, les autres séquences angulaires :

for point B => B* => 5x - 3: [No points right of B] ++ [(C*) 4x - 6, (A*) x - 1]

for point C => C* => 4x - 6: [(B*) 5x - 3] ++ [(A*) x - 1]
(note that we start at -90 deg up to -270 deg)

Answer 3

Solution

Dans l'espace de toutes les lignes du graphique, les lignes qui passent par un coin sont exactement celles où le nombre d'intersections est sur le point de diminuer. En d'autres termes, elles forment chacune un maximum local.

Et pour toute ligne qui passe par au moins un coin, il existe une ligne associée qui passe par deux coins et qui a le même nombre d'intersections.

La conclusion est que nous devons seulement vérifier les lignes formées par deux coins de rectangle car elles forment un ensemble qui représente entièrement les maxima locaux de notre problème. Parmi celles-ci, nous choisissons celle qui a le plus d'intersections.

Complexité du temps

Cette solution doit d'abord récupérer toutes les lignes qui passent par deux coins. Le nombre de ces lignes est O(n^2) .

Nous devons ensuite compter le nombre d'intersections entre une ligne donnée et un rectangle. Cela peut évidemment être fait en O(n) en comparant à chacun des rectangles.

Il pourrait y avoir une manière plus efficace de procéder, mais nous savons que cet algorithme est alors au plus O(n^3) .

Mise en œuvre de Python3

Voici une implémentation Python de cet algorithme. Je l'ai orienté plus vers la lisibilité que l'efficacité, mais il fait exactement ce qui est défini ci-dessus.

def get_best_line(rectangles):
    """
    Given a set of rectangles, return a line which intersects the most rectangles.
    """

    # Recover all corners from all rectangles
    corners = set()
    for rectangle in rectangles:
        corners |= set(rectangle.corners)

    corners = list(corners)

    # Recover all lines passing by two corners
    lines = get_all_lines(corners)

    # Return the one which has the highest number of intersections with rectangles
    return max(
        ((line, count_intersections(rectangles, line)) for line in lines),
        key=lambda x: x[1])

Cette implémentation utilise les aides suivantes.

def get_all_lines(points):
    """
    Return a generator providing all lines generated
    by a combination of two points out of 'points'
    """
    for i in range(len(points)):
        for j in range(i, len(points)):
            yield Line(points[i], points[j])

def count_intersections(rectangles, line):
    """
    Return the number of intersections with rectangles
    """
    count = 0

    for rectangle in rectangles:
        if line in rectangle:
           count += 1

    return count

Et voici la définition des classes qui servent de structure de données pour les rectangles et les lignes.

import itertools
from decimal import Decimal

class Rectangle:
    def __init__(self, x_range, y_range):
        """
        a rectangle is defined as a range in x and a range in y.
        By example, the rectangle (0, 0), (0, 1), (1, 0), (1, 1) is given by
        Rectangle((0, 1), (0, 1))
        """
        self.x_range = sorted(x_range)
        self.y_range = sorted(y_range)

    def __contains__(self, line):
        """
        Return whether 'line' intersects the rectangle.
        To do so we check if the line intersects one of the diagonals of the rectangle
        """
        c1, c2, c3, c4 = self.corners

        x1 = line.intersect(Line(c1, c4))
        x2 = line.intersect(Line(c2, c3))

        if x1 is True or x2 is True \
                or x1 is not None and self.x_range[0] <= x1 <= self.x_range[1] \
                or x2 is not None and self.x_range[0] <= x2 <= self.x_range[1]:

            return True

        else:
            return False

    @property
    def corners(self):
        """Return the corners of the rectangle sorted in dictionary order"""
        return sorted(itertools.product(self.x_range, self.y_range))

class Line:
    def __init__(self, point1, point2):
        """A line is defined by two points in the graph"""
        x1, y1 = Decimal(point1[0]), Decimal(point1[1])
        x2, y2 = Decimal(point2[0]), Decimal(point2[1])
        self.point1 = (x1, y1)
        self.point2 = (x2, y2)

    def __str__(self):
        """Allows to print the equation of the line"""
        if self.slope == float('inf'):
            return "y = {}".format(self.point1[0])

        else:
            return "y = {} * x + {}".format(round(self.slope, 2), round(self.origin, 2))

    @property
    def slope(self):
        """Return the slope of the line, returning inf if it is a vertical line"""
        x1, y1, x2, y2 = *self.point1, *self.point2

        return (y2 - y1) / (x2 - x1) if x1 != x2 else float('inf')

    @property
    def origin(self):
        """Return the origin of the line, returning None if it is a vertical line"""
        x, y = self.point1

        return y - x * self.slope if self.slope != float('inf') else None

    def intersect(self, other):
        """
        Checks if two lines intersect.
        Case where they intersect: return the x coordinate of the intersection
        Case where they do not intersect: return None
        Case where they are superposed: return True
        """

        if self.slope == other.slope:

            if self.origin != other.origin:
                return None

            else:
                return True

        elif self.slope == float('inf'):
            return self.point1[0]

        elif other.slope == float('inf'):
            return other.point1[0]

        elif self.slope == 0:
            return other.slope * self.origin + other.origin

        elif other.slope == 0:
            return self.slope * other.origin + self.origin

        else:
            return (other.origin - self.origin) / (self.slope - other.slope)

Exemple

Voici un exemple fonctionnel du code ci-dessus.

rectangles = [
    Rectangle([0.5, 1], [0, 1]),
    Rectangle([0, 1], [1, 2]),
    Rectangle([0, 1], [2, 3]),
    Rectangle([2, 4], [2, 3]),
]

# Which represents the following rectangles (not quite to scale)
#
#  *
#  *   
#
# **     **
# **     **
#
# **
# **

Nous pouvons clairement voir qu'une solution optimale devrait trouver une ligne qui passe par trois rectangles et c'est effectivement ce qu'elle produit.

print('{} with {} intersections'.format(*get_best_line(rectangles)))
# prints: y = 0.50 * x + -5.00 with 3 intersections

Answer 4

Que pensez-vous de l'algorithme suivant ?

RES = 0 // maximum number of intersections
CORNERS[] // all rectangles corners listed as (x, y) points

for A in CORNERS
    for B in CORNERS // optimization: starting from corner next to A
        RES = max(RES, CountIntersectionsWithLine(A.x, A.y, B.x, B.y))

return RES

En d'autres termes, commencez à tracer des lignes de chaque coin de rectangle à chaque autre coin de rectangle et trouvez le nombre maximum d'intersections. Comme suggéré par @weston, nous pouvons éviter de calculer deux fois la même ligne en commençant la boucle interne à partir du coin à côté de A .

Answer 5

Si l'on considère une ligne tournante à angle et si l'on projette tous les rectangles sur cette ligne, on obtient N segments de ligne. Le nombre maximal de rectangles traversés par une perpendiculaire à cette ligne s'obtient facilement en triant les points d'extrémité par abscisse croissante et en gardant le compte des intervalles rencontrés de gauche à droite (garder la trace du fait qu'un point d'extrémité est un début ou une fin). Cette ligne est représentée en vert.

Maintenant, deux rectangles sont coupés par toutes les lignes à un angle compris entre les deux tangentes internes [exemple en rouge], de sorte que tous les angles "événements" à considérer (c'est-à-dire tous les angles pour lesquels un changement de compte peut être observé) sont ces N(N-1) angles.

Alors le schéma de résolution par force brute est

• pour tous les angles limites (O(N²) d'entre eux),

  • projeter les rectangles sur la ligne de rotation (O(N) opérations),

  • compter les chevauchements et garder les plus grands (O(N Log N) pour trier, puis O(N) pour compter).

Cela prend au total O(N³Log N) opérations.

En supposant que les tris n'ont pas besoin d'être refaits entièrement pour chaque angle si nous pouvons les faire de manière incrémentielle, nous pouvons espérer une complexité abaissée à O(N³). Ceci doit être vérifié.

---

Note :

Les solutions qui limitent les lignes à passer par le coin d'un rectangle sont fausses. Si vous tracez des coins à partir des quatre coins d'un rectangle jusqu'à la totalité d'un autre, il restera un espace vide dans lequel peut se trouver un rectangle entier qui ne sera pas touché, même s'il existe une ligne passant par les trois.