algorithm - Número máximo de rectángulos que se pueden cruzar con una sola línea recta

geometry dynamic-programming

Question

Encontré este problema de desafío que dice lo siguiente:

Supongamos que hay n rectángulos en el plano XY. Escribe un programa para calcular la cantidad máxima posible de rectángulos que se pueden cruzar con una sola línea recta dibujada en este plano.

He estado intercambiando ideas durante bastante tiempo, pero no he podido encontrar ninguna solución. Tal vez en algún momento, usemos pasos de programación dinámica pero no pudimos descubrir cómo comenzar.

Answer 1

Solución

En el espacio de todas las líneas del gráfico, las líneas que pasan por una esquina son exactamente las que están a punto de disminuir el número o las intersecciones. En otras palabras, cada uno forma un máximo local.

Y para cada línea que pasa por al menos una esquina, existe una línea asociada que pasa por dos esquinas que tiene el mismo número de intersecciones.

La conclusión es que solo necesitamos verificar las líneas formadas por dos esquinas rectangulares, ya que forman un conjunto que representa completamente los máximos locales de nuestro problema. De aquellos elegimos el que tiene la mayor cantidad de intersecciones.

Complejidad del tiempo

Esta solución primero necesita recuperar todas las líneas que pasan por dos esquinas. El número de dicha línea es O (n ^ 2) .

Entonces necesitamos contar el número de intersecciones entre una línea determinada y un rectángulo. Obviamente, esto se puede hacer en O (n) comparando con cada rectángulo.

Puede haber una forma más eficiente de proceder, pero sabemos que este algoritmo es como máximo O (n ^ 3) .

Implementación de Python3

Aquí hay una implementación de Python de este algoritmo. Lo orienté más hacia la legibilidad que hacia la eficiencia, pero hace exactamente lo que se define arriba.

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])

Esta implementación usa los siguientes ayudantes.

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

Y aquí está la definición de clase que sirve como estructura de datos para rectángulos y líneas.

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)

Ejemplo

Aquí hay un ejemplo de trabajo del código anterior.

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)
#
# *
# *
#
# ** **
# ** **
#
# **
# **

Podemos ver claramente que una solución óptima debería encontrar una línea que pase por tres rectángulos y de hecho es lo que produce.

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

Answer 2

¿Qué tal el siguiente algoritmo:

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 otras palabras, comience dibujando líneas desde cada esquina de rectángulo a cada esquina de rectángulo y encuentre la cantidad máxima de intersecciones. Como lo sugirió @weston, podemos evitar calcular la misma línea dos veces comenzando el ciclo interno desde la esquina al lado de A

Answer 3

(Edición de mi respuesta anterior que consideraba girar el avión).

Aquí está el boceto del algoritmo O(n^2) , que combina la idea de Gassa con la referencia de Evgeny Kluev a arreglos de dos líneas como secuencias angulares ordenadas.

Comenzamos con una lista de bordes doblemente conectados o una estructura similar, lo que nos permite dividir un borde en O(1) tiempo, y un método para atravesar las caras que creamos a medida que llenamos un plano bidimensional. Para simplificar, usemos solo tres de las doce esquinas en los rectángulos a continuación:

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

Insertamos los tres puntos (esquinas) en el plano dual de acuerdo con la siguiente transformación:

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

Ingresemos los puntos en orden A, B, C Primero ingresamos A => y = x - 1 . Como solo hay un borde hasta ahora, insertamos B => y = 5x - 3 , que crea el vértice, (1/2, -1/2) y divide nuestro borde. (Un aspecto elegante de esta solución es que cada vértice (punto) en el plano dual es en realidad el punto dual de la línea que pasa por las esquinas de los rectángulos. Observe 1 = 1/2*1 + 1/2 y 3 = 1/2*5 + 1/2 , puntos (1,1) y (5,3) .)

Ingresando el último punto, C => y = 4x - 6 , ahora buscamos la cara más a la izquierda (podría ser una cara incompleta) donde se intersecará. Esta búsqueda es O(n) tiempo ya que tenemos que probar cada cara. Encontramos y creamos el vértice (-3, -18) , dividimos el borde inferior de 5x - 3 y atravesamos los bordes para dividir la mitad derecha de x - 1 en el vértice (5/3, 2/3) . Cada inserción tiene un tiempo O(n) ya que primero debemos encontrar la cara más a la izquierda, luego atravesar cada cara para dividir los bordes y marcar los vértices (puntos de intersección para la línea).

En el plano dual ahora tenemos:

Después de construir la disposición de la línea, comenzamos nuestra iteración en nuestros tres puntos de ejemplo (esquinas rectangulares). Parte de la magia en reconstruir una secuencia angular ordenada en relación con un punto es dividir los ángulos (cada uno correspondiente con una intersección de línea ordenada en el plano dual) en los que corresponden con un punto a la derecha (con una mayor coordenada x) y los de la izquierda y la concatenación de las dos secuencias para obtener una secuencia ordenada de -90 grados a -270 grados. (Los puntos de la derecha se transforman en líneas con pendientes positivas en relación con el punto fijo, las de la izquierda, con pendientes negativas. Gire su sevicio / pantalla en el sentido de las agujas del reloj hasta que la línea para (C*) 4x - 6 vuelva horizontal y usted Veo que B* ahora tiene una pendiente positiva y A* negativa.

¿Por qué funciona? Si un punto p en el plano original se transforma en una línea p* en el plano dual, atravesar esa línea dual de izquierda a derecha corresponde con rotar una línea alrededor de p en el plano original que también pasa por p . La línea doble marca todas las pendientes de esta línea giratoria por la coordenada x desde infinito negativo (vertical) a cero (horizontal) hasta infinito (vertical de nuevo).

(Resumiremos la lógica de recuento de rectángulo, actualizando count_array para el rectángulo actual mientras iteramos a través de la secuencia angular: si es 1, incremente el recuento de intersección actual; si es 4 y la línea no está directamente en una esquina, ajústelo en 0 y decrementa el recuento de intersección actual).

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)

Podemos ver que (5,9) está por encima de la línea a través de AC (y = 5/3x - 2/3) , lo que significa que en este punto habríamos contado la intersección con el rectángulo de la derecha y aún no hemos reiniciado el recuento , totalizando 3 rectángulos para esta línea.

También podemos ver en el gráfico del plano dual, las otras secuencias angulares:

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 4

Aquí hay un boceto de una solución O (n ^ 2 log n).

Primero, los preliminares compartidos con otras respuestas. Cuando tenemos una línea que pasa por algunos rectángulos, podemos traducirla a cualquiera de los dos lados hasta que pase por una esquina de algún rectángulo. Después de eso, reparamos esa esquina como el centro de rotación y rotamos la línea a cualquiera de los dos lados hasta que pasa a través de otra esquina. Durante todo el proceso, todos los puntos de intersección entre nuestra línea y los lados del rectángulo permanecieron en estos lados, por lo que el número de intersecciones permaneció igual, al igual que el número de rectángulos cruzados por la línea. Como resultado, podemos considerar solo las líneas que pasan por dos esquinas rectangulares, que está limitado por O (n ^ 2), y es una mejora bienvenida en comparación con el espacio infinito de líneas arbitrarias.

Entonces, ¿cómo revisamos eficientemente todas estas líneas? Primero, tengamos un bucle externo que corrige un punto A y luego considera todas las líneas que pasan por A. Hay O (n) elecciones de A.

Ahora, tenemos un punto A fijo, y queremos considerar todas las líneas AB pasando por todas las demás esquinas B. Para hacer eso, primero clasifique todas las demás esquinas B según el ángulo polar de AB, o, en otras palabras, ángulo entre el eje Ox y el vector AB. Los ángulos se miden de -PI a + PI o de 0 a 2 PI o de lo contrario, el punto en el que cortamos el círculo para ordenar los ángulos puede ser arbitrario. La clasificación se realiza en O (n log n).

Ahora, tenemos los puntos B ₁ , B ₂ , ..., B _k ordenados por el ángulo polar alrededor del punto A (su número k es algo así como 4n-4, todas las esquinas de todos los rectángulos, excepto aquella en la que el punto A es una esquina ) Primero, mira la línea AB ₁ y cuenta el número de rectángulos cruzados por esa línea en O (n). Después de eso, considere rotar AB ₁ a AB ₂ , luego AB ₂ a AB ₃ , todo el camino hasta AB _k . Los eventos que ocurren durante la rotación son los siguientes:

• Cuando rotamos a AB _i , y B _i es la primera esquina de un rectángulo en nuestro orden, la cantidad de rectángulos cruzados aumenta en 1 tan pronto como la línea giratoria golpea B _i .

• Cuando rotamos a AB _j , y B _j es la última esquina de un rectángulo en nuestro orden, el número de rectángulos cruzados disminuye en 1 tan pronto como la línea gira más allá de B _j .

Qué esquinas son las primeras y las últimas se pueden establecer con algún preprocesamiento de O (n), después del ordenamiento, pero antes de considerar los eventos ordenados.

En resumen, podemos rotar al siguiente evento y actualizar el número de rectángulos cruzados en O (1). Y hay k = O (n) eventos en total. Lo que queda por hacer es rastrear el máximo global de esta cantidad a lo largo de todo el algoritmo. La respuesta es solo este máximo.

El algoritmo completo se ejecuta en O (n * (n log n + n + n)), que es O (n ^ 2 log n), tal como se anuncia.

Answer 5

Podemos tener un método de programación dinámica O(n^2 (log n + m)) adaptando la idea de Andriy Berestovskyy de iterar ligeramente sobre las esquinas para insertar la relación de la esquina actual con respecto a todos los otros rectángulos en un árbol de intervalos para cada uno de nuestros 4n ciclos de iteración.

Se creará un nuevo árbol para la esquina que estamos intentando. Para las cuatro esquinas de cada rectángulo, repetiremos sobre cada uno de los otros rectángulos. Lo que vamos a insertar serán los ángulos que marcan el arco que crean las esquinas más alejadas del rectángulo emparejado en relación con la esquina fija actual.

En el ejemplo directamente debajo, para la esquina R del rectángulo inferior fijo al insertar el registro para el rectángulo medio, insertaríamos los ángulos que marcan el arco de p2 a p1 en relación con R (aproximadamente (37 deg, 58 deg) ). Luego, cuando verifiquemos el rectángulo alto en relación con R , insertaremos el intervalo de ángulos que marcan el arco de p4 a p3 en relación con R (aproximadamente (50 deg, 62 deg) ).

Cuando insertemos el siguiente registro de arco, lo comprobaremos con todos los intervalos de intersección y mantendremos un registro de la mayoría de las intersecciones.

(Tenga en cuenta que debido a que cualquier arco en un círculo de 360 ​​grados para nuestro propósito tiene una contraparte girada 180 grados, es posible que necesitemos hacer un corte arbitrario (cualquier información alternativa sería bienvenida). Por ejemplo, esto significa que un arco de 45 grados a 315 grados se dividirían en dos: [0, 45] y [135, 180]. Cualquier arco no dividido solo podría cruzarse con uno u otro, pero de cualquier forma, es posible que necesitemos un hash adicional para asegurarnos de que los rectángulos no sean dobles. contado)

Answer 6

Si considera una línea giratoria en ángulo Θ y proyecta todos los rectángulos en esta línea, obtendrá N segmentos de línea. El número máximo de rectángulos cruzados por una perpendicular a esta línea se obtiene fácilmente clasificando los puntos finales aumentando la abscisa y manteniendo un recuento de los intervalos encontrados de izquierda a derecha (mantenga un rastro de si un punto final es un inicio o un final). Esto se muestra en verde.

Ahora dos rectángulos se cruzan por todas las líneas en un ángulo comprendido entre las dos tangentes internas [ejemplo en rojo], de modo que todos los ángulos de "evento" que se deben considerar (es decir, todos los ángulos para los que se puede observar un cambio de conteo) son N (N-1) ángulos.

Entonces el esquema de resolución de la fuerza bruta es

• para todos los ángulos límite (O (N²) de ellos),

  • proyectar los rectángulos en la línea giratoria (operaciones O (N)),

  • contar las superposiciones y mantener el más grande (O (N Log N) para ordenar, luego O (N) para contar).

Esto toma en total O (N³Log N) operaciones.

Asumiendo que los géneros no necesitan volver a realizarse en su totalidad para cada ángulo si podemos hacerlos incrementalmente, podemos esperar una complejidad reducida a O (N³). Esto necesita ser verificado.

Nota:

Las soluciones que restringen que las líneas pasen por la esquina de un rectángulo son incorrectas. Si dibujas cuñas desde las cuatro esquinas de un rectángulo hasta la extensión completa de otra, quedará un espacio vacío en el que puede estar todo un rectángulo que no se tocará, aunque exista una línea a través de las tres.