Comment vérifier si les coordonnées cartésiennes constituent efficacement un rectangle?

Question

La situation est la suivante:

• Il existe N réseaux.
• Dans chaque tableau (0..N-1) il y a (x, y) tuples (coordonnées cartésiennes) stockée
• La longueur de chaque rangée peut être différent

Je veux extraire le sous-ensemble des combinaisons de coordonnées qui constituent un retangle complet de en d'autres termes; toutes les coordonnées cartésiennes sont adjacentes les unes aux autres.

Exemple:

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

donne le résultat suivant:

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

Pas deux points peuvent provenir de la même série. Je viens d'abord de calculer le produit cartésien, mais cela devient rapidement infaisable (mon cas d'utilisation à l'heure actuelle comporte 18 tableaux de points, chaque tableau contenant environ 10 coordonnées différentes).

Answer 1

Laissez XY être votre ensemble de tableaux. Construire deux nouveaux ensembles X et Y, où X est égal à XY avec tous les tableaux triés en coordonnées x et Y est égal à XY avec tous les tableaux triés en ordonnée.

• Pour chaque point (x0, y0) dans l'un des tableaux en X: trouver chaque point (x0, y1) avec la même coordonnée x et une autre coordonnée y dans les réseaux restants de X
• pour chaque paire de points (si elle existe): recherche Y pour les points (x1, y0) et (x1, y1)

Soit C la taille du plus grand tableau. Ensuite, le tri de tous les ensembles prend du temps O (N * C * log (C)). À l'étape 1, trouver un seul point correspondant prend du temps O (N * log (C)) puisque tous les tableaux de X sont triés. Trouver tous ces points est en O (C * N), car il y a au plus C * N points globalement. L'étape 2 prend le temps O (N * log (C)) puisque Y est trié. Par conséquent, l'exécution globale asymptotique est dans O (C * N^2 * log (C)^2).

Pour C == 10 et N == 18, vous obtiendrez environ 10 000 opérations. Multipliez cela par 2, puisque j'ai laissé tomber ce facteur en raison de Big-O-notation.

La solution a l'avantage supplémentaire d'être extrêmement simple à mettre en œuvre. Tout ce dont vous avez besoin est de tableaux, de tri et de recherche binaire, les deux premiers étant très probablement intégrés dans la langue, et la recherche binaire étant extrêmement simple.

Notez également qu'il s'agit de l'exécution dans le cas pire où tous les rectangles commencent à la même coordonnée x. Dans le cas moyen, vous ferez probablement beaucoup mieux que cela.

Answer 2

Vous pouvez utiliser hachant à grand effet:

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(...) 

Quand je dis exists, je veux dire faire quelque chose comme:

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) 

Ceci est O(#bins^2 * items_per_bin^2) ~ 30000, ce qui est carrément rapide dans votre cas de 18 tableaux et 10 items_per_bin - beaucoup mieux que l'approche du produit externe qui est ... bien pire avec O(items_per_bin^#bins) ~ 3trillion. =)

---

sidenote mineur:

Vous pouvez réduire à la fois la base et l'exposant dans votre calcul en faisant plusieurs passages de « taille ». par exemple.

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 

Vous pouvez le faire en tri selon la coordonnée X, répétez l'opération pour la coordonnée Y, en O(P log(P)) temps en termes de nombre de points. Vous pouvez peut-être faire cela en même temps que le hachage. Si un méchant organise votre entrée, il peut faire en sorte que cette optimisation ne fonctionne pas du tout. Mais en fonction de votre distribution, vous pouvez voir une accélération significative.