¿Cómo puedo verificar si las coordenadas cartesianas forman un rectángulo de manera eficiente?

Question

La situación es la siguiente:

• Hay N matrices.
• En cada array (0..N-1) hay (x, y) tuplas (coordenadas cartesianas) almacenados
• La longitud de cada matriz puede ser diferente

I quieren extraer el subconjunto de combinaciones de coordenadas que componen un total de de tamaño N. En otras palabras; todas las coordenadas cartesianas son adyacentes entre sí.

Ejemplo:

findRectangles({ 
    {*(1,1), (3,5), (6,9)}, 
    {(9,4), *(2,2), (5,5)}, 
    {(5,1)}, 
    {*(1,2), (3,6)}, 
    {*(2,1), (3,3)} 
}) 

produce el siguiente:

[(1,1),(1,2),(2,1),(2,2)], 
..., 
...(other solutions)... 

No hay dos puntos pueden provenir de un mismo conjunto.

Primero calculé el producto cartesiano, pero esto rápidamente se vuelve inviable (mi caso de uso en este momento tiene 18 conjuntos de puntos con cada arreglo conteniendo aproximadamente 10 coordenadas diferentes).

Answer 1

Deje que XY sea su conjunto de matrices. Construya dos conjuntos nuevos X e Y, donde X es igual a XY con todas las matrices ordenadas en coordenada x e Y es igual a XY con todas las matrices ordenadas en coordenada y.

• Para cada punto (x0, y0) en cualquiera de las matrices en X: encontrar cada punto (x0, y1) con la misma coordenada x y una diferente coordenada y en las matrices restantes de X
• para cada par de puntos (si existe): buscar y para los puntos (x1, y0) y (x1, y1)

sea C el tamaño de la matriz más grande. Luego, ordenar todos los conjuntos toma tiempo O (N * C * log (C)). En el paso 1, encontrar un único punto de coincidencia toma tiempo O (N * log (C)) ya que todas las matrices en X están ordenadas. Encontrar todos esos puntos está en O (C * N), ya que hay como máximo C * N puntos en general. El paso 2 lleva tiempo O (N * log (C)) ya que Y está ordenado.

Por lo tanto, el tiempo de ejecución total asintótico está en O (C * N^2 * log (C)^2).

Para C == 10 y N == 18, obtendrá aproximadamente 10.000 operaciones. Multiplica eso por 2, ya que disminuí ese factor debido a la notación Big-O.

La solución tiene el beneficio adicional de ser extremadamente simple de implementar. Todo lo que necesita es arreglos, ordenamiento y búsqueda binaria, los primeros dos de los cuales muy probablemente estén incorporados en el lenguaje, y la búsqueda binaria es extremadamente simple.

También tenga en cuenta que este es el tiempo de ejecución en el peor caso donde todos los rectángulos comienzan en la misma coordenada x. En el caso promedio, probablemente lo harás mucho mejor que esto.

Answer 2

Puede utilizar hash con gran efecto:

hash each point (keeping track of which list it is in) 
for each pair of points (a,b) and (c,d): 
    if (a,d) exists in another list, and (c,b) exists in yet another list: 
     yield rectangle(...) 

Cuando digo exists, me refiero a hacer algo como:

hashesToPoints = {} 
for p in points: 
    hashesToPoints.setdefault(hash(p),set()).add(p) 
for p1 in points: 
    for p2 in points: 
     p3,p4 = mixCoordinates(p1,p2) 
     if p3 in hashesToPoints[hash(p3)] and {{p3 doesn't share a bin with p1,p2}}: 
      if p4 in hashesToPoints[hash(p4)] and {{p4 doesn't share a bin with p1,p2,p3}}: 
       yield Rectangle(p1,p2) 

Esta es O(#bins^2 * items_per_bin^2) ~ 30000, que es francamente rápida en su caso de 18 matrices y 10 items_per_bin - mucho mejor que el enfoque de producto externo que es ... mucho peor con O(items_per_bin^#bins) ~ 3trillion. =)

---

sidenote menor:

Usted puede reducir tanto la base como exponente en el cálculo al hacer múltiples pasadas de "poda". p.ej.

remove each point that is not corectilinear with another point in the X or Y direction 
then maybe remove each point that is not corectilinear with 2 other points, in both X and Y direction 

Usted puede hacer esto mediante la clasificación de acuerdo con la coordenada X, repita el procedimiento para la coordenada Y, en O(P log(P)) tiempo en términos de número de puntos. Es posible que puedas hacer esto al mismo tiempo que hashing también. Si un mal tipo está organizando su entrada, puede hacer que esta optimización no funcione en absoluto. Pero dependiendo de su distribución, puede ver una aceleración significativa.