Algorithme pour fusionner les rectangles adjacents en polygones

j'ai dû écrire un algorithme pour fusionner les polygones adjacents dans le cadre d'un projet expérimental avec la toile HTML5 (nothing glorious, un puzzle :-) les trous dans le polygone résultant sont naturellement supportés. La routine Javascript se trouve dans la fonction appelée Polygon.prototype.merge() in www dot raymondhill dot net / puzzle-rhill / jigsawpuzzle-rhill-3 dot js

la clé est de supprimer les segments qui sont dupliqués, mais de direction opposée. Explication approximative: un Point est {x:?,y:?}, un Segment est {ptA:?, ptB:?}, un Contour est {pts: []} (une collection d'objets Point connectés), un polygone est {contours: []} (une collection d'objets Contour.)

L'algorithme de fusion collecter segments dans un grand pool de gros objets de Segment, où les doublons sont éliminés. Tout d'abord, tous les segments de tous les contours définissant le polygone A sont ajoutés au pool. Ensuite, tous les segments de tous les contours définissant le polygone B sont ajoutés au pool, mais nous testons et Supprimer pour dupliquer (facilement fait en utilisant un objet Point comme hashkey).

puis nous prenons un segment de la piscine (au hasard c'est bien), et nous le "marchons" jusqu'à ce que nous atteignions une "impasse", c'est-à-dire qu'aucun autre segment ne peut être connecté. Cela forme un objet Contour. Nous répétons jusqu'à ce que toute la collection de segments ait été utilisée. À mesure que les segments sont utilisés, ils sont retirés du bassin. "Marcher" un segment signifie que nous prenons son point final, et nous cherchons un segment qui correspond au point de départ. il.

comme dit, en conséquence nous avons une collection D'objets Contour qui définissent le polygone. Certains contours seront remplis, d'autres seront creux. Pour déterminer si un Contour est rempli ou creux, il suffit de vérifier si le Contour est dans le sens des aiguilles d'une montre ou dans le sens contraire des aiguilles d'une montre, ou si sa surface est positive ou négative. C'est une convention, dans mon cas, dans le sens des aiguilles contours sont remplis, dans le sens antihoraire sont creux.

Voici mon implémentation, moins les détails et moins la gestion des erreurs. J'espère que j'ai copié/collé assez pour que vous le fassiez fonctionner tout de suite, sinon référez-vous à mon fichier JS ci-dessus pour le contexte:

// Point object
function Point(a,b) {
    // a=x,b=y
    if (b) {
        this.x=a;
        this.y=b;
        }
    // a=Point or {x:?,y:?}
    else if (a) {
        this.x=a.x;
        this.y=a.y;
        }
    // empty
    else {
        this.x=this.y=0;
        }
    }
Point.prototype.toHashkey = function() {
    return this.x+"_"+this.y;
    };
Point.prototype.clone = function() {
    return new Point(this);
    };
// Segment object
function Segment(a,b) {
    this.ptA = new Point(a);
    this.ptB = new Point(b);
    }
// Contour object
function Contour(a) {
    this.pts = []; // no points
    if (a) {
        if (a instanceof Array) { // assume array of Point objects
            var nPts = a.length;
            for (var iPt=0; iPt<nPts; iPt++) {
                this.pts.push(a[iPt].clone());
                }
            }
        }
    }
Contour.prototype.clone = function() {
    return new Contour(this);
    };
Contour.prototype.addPoint = function(p) {
    this.pts.push(p);
    };
// Polygon object
function Polygon(a) {
    this.contours = []; // no contour
    if (a) {
        if (a instanceof Polygon) {
            var contours = a.contours;
            var nContours = contours.length;
            for ( var iContour=0; iContour<nContours; iContour++ ) {
                this.contours.push(new Contour(contours[iContour]));
                }
             }
        else if ( a instanceof Array ) {
            this.contours.push(new Contour(a));
            }
        }
    }
Polygon.prototype.merge = function(other) {
    // A Javascript object can be used as an associative array, but
    // they are not real associative array, as there is no way
    // to query the number of entries in the object. For this
    // reason, we maintain an element counter ourself.
    var segments={};
    var contours=this.contours;
    var nContours=contours.length;
    var pts; var nPts;
    var iPtA; var iPtB;
    var idA; var idB;
    for (var iContour=0; iContour<nContours; iContour++) {
        pts = contours[iContour].pts;
        nPts = pts.length;
        iPtA = nPts-1;
        for ( iPtB=0; iPtB<nPts; iPtA=iPtB++ ) {
            idA = pts[iPtA].toHashkey();
            idB = pts[iPtB].toHashkey();
            if (!segments[idA]) {
                segments[idA]={n:0,pts:{}};
                }
            segments[idA].pts[idB] = new Segment(pts[iPtA],pts[iPtB]);
            segments[idA].n++;
            }
        }
    // enumerate segments in other's contours, eliminate duplicate
    contours = other.contours;
    nContours = contours.length;
    for ( iContour=0; iContour<nContours; iContour++ ) {
        pts = contours[iContour].pts;
        nPts = pts.length;
        iPtA=nPts-1;
        for (iPtB=0; iPtB<nPts; iPtA=iPtB++) {
            idA = pts[iPtA].toHashkey();
            idB = pts[iPtB].toHashkey();
            // duplicate (we eliminate same segment in reverse direction)
            if (segments[idB] && segments[idB].pts[idA]) {
                delete segments[idB].pts[idA];
                if (!--segments[idB].n) {
                    delete segments[idB];
                    }
                }
            // not a duplicate
            else {
                if (!segments[idA]) {
                    segments[idA]={n:0,pts:{}};
                    }
                segments[idA].pts[idB] = new Segment(pts[iPtA],pts[iPtB]);
                segments[idA].n++;
                }
            }
        }
    // recreate and store new contours by jumping from one point to the next,
    // using the second point of the segment as hash key for next segment
    this.contours=[]; // regenerate new contours
    var contour;
    for (idA in segments) { // we need this to get a starting point for a new contour
        contour = new Contour();
        this.contours.push(contour);
        for (idB in segments[idA].pts) {break;}
        segment = segments[idA].pts[idB];
        while (segment) {
            contour.addPoint(new Point(segment.ptA));
            // remove from collection since it has now been used
            delete segments[idA].pts[idB];
            if (!--segments[idA].n) {
                delete segments[idA];
                }
            idA = segment.ptB.toHashkey();
            if (segments[idA]) {
                for (idB in segments[idA].pts) {break;} // any end point will do
                segment = segments[idA].pts[idB];
                }
            else {
                segment = null;
                }
            }
        }
    };

quand nous "marchons" le segment pour créer un contour, il y a un cas où un segment peut se connecter à plus d'un segment:

+------+-------+
|   Poly A     | two segments sharing same start point Z
|              | 
+      +---<---Z---->---+
|      |       | Poly B |
|      |       |        |
+      +-------+--------+
|                       |
|                       |
+------+-------+--------+

qui peut conduire à deux résultats valides (l'algorithme ci-dessus conduira au hasard à l'un ou l'autre):

résultat 1, un contour rempli:

+------+--->---+
|   Poly A     |
|              | 
+      +---<---+---->---+
|      |       |        |
|      |       |        |
+      +--->---+        +
|                       |
|                       |
+------+---<---+--------+

résultat 2, un contour rempli, un contour creux:

+------+--->---+
|   Poly A     |
|              | 
+      +---<---+---->---+
|      | Hole A|        |
|      |       |        |
+      +--->---+        +
|                       |
|                       |
+------+---<---+--------+

cela ne devrait pas être un problème cependant, car votre code devrait déjà être prêt à gérer les trous.

autre détail important: l'algorithme ci-dessus ne se débarrasse pas des points intermédiaires ('+'), en fait ils sont attendus ou bien l'algorithme ne fonctionnera pas, comme dans le cas suivant:

+------>-------+
|   Poly A     |
|              | 
|              | +---->---+
|              | | Poly B |
|              | |        |
|              | +----<---+
|              |
|              |
+------<-------+

Ma compréhension est que c'est ce que vous avez. J'imagine que l'algorithme pourrait être étendu pour soutenir un tel cas en trouvant et ajouter les points d'intersection à l'avance (ce n'était pas nécessaire dans mon cas):

+------>-------+
|   Poly A     |
|              | 
|              + +---->---+
|              | | Poly B |
|              | |        |
|              + +----<---+
|              |
|              |
+------<-------+

Espérons que cette aide.

P.S.: vous pouvez "tester" l'algorithme avec le puzzle, en cassant des morceaux ensemble pour générer des trous, etc.: http://www.raymondhill.net/puzzle-rhill/puzzle-rhill.php?puzzlePieces=16&puzzleComplexity=1&puzzleURL=http://www.public-domain-photos.com/free-stock-photos-4/travel/los-angeles/los-angeles-skyline.jpg&puzzleRotate=0&puzzleVersion=3

je veux le regarder dans quelque chose comme Général Polygon Clipper. Vous faites essentiellement des opérations de polygones (ou) syndicaux. Le fait qu'ils soient tous rectangles rend juste le calcul un peu plus facile, mais il pourrait facilement être fait avec quelque chose comme GPC.

il y a aussi des emballages de langues pour beaucoup de langues.

si vous utilisez une bibliothèque de traitement spatial (comme JTS [java], NTS [.net] ou GEOS [c++], qui sont toutes open source et utilisables pour des applications commerciales, contrairement à GPC), vous pouvez simplement fusionner les rectangles.

la façon générale de faire ceci est de construire un graphique des bords des entrées (rectangles), effectuer des intersections, étiqueter les bords comme à l'intérieur ou à l'extérieur du résultat, et juste garder les bords extérieurs. Je ne connais pas d'algorithme spécifique pour traiter les rectangles, mais il serait probablement simiar, sauf, comme indiqué, le calcul serait plus simple.

si vos limites sont raisonnables utilisez un tableau 2D de bord counts, sinon vous devrez utiliser des dictionnaires imbriqués.

parce que toutes les largeurs et les hauteurs sont les mêmes, vous pouvez identifier un bord uniquement par une combinaison de x, y, et l'orientation (verticale ou horizontale)

exemple de pseudo-code: list_of_edges = nouvelle liste arr_count = new int [] [] []

fill_with_zeroes(arr_count )

foreach rect
   foreach edge
      arr_count [edge.x][edge.y][edge.orientation] += 1

foreach edge in arr_count
   if count[edge] = 1
      list_of_edges.add(edge]

bien sûr, si vous voulez ordonner les bords, alors vous devez passer à travers le tableau un autre temps

foreach edge in arr_count
    if count[edge] = 1
        add_recursive(edge)

add_recursive(x,y):
    for both horizontal and vertical orientations of edge starting at x, y:
    count[edge] = 0
    if (edge.orientation is horizontal)
        return add_recursive( x+1, y)
    else 
        return add_recursive( x, y+1 )

désolé, ce pseudo-code est assez bâclée, mais vous devriez obtenir l'idée générale

pourquoi ne pas essayer ce qui suit. Je pense que cela fonctionnera si conçu correctement.

1. trouver le plus petit rectangle emclosant, essentiellement max-x, min-x et max-y et min-Y. Ce sera notre toile pour le dessin. Initialise un tableau 2D de bits dx X dy où dx, dy sont la largeur de ce rectangle externe, à tous les 0s.

2. notre objectif est de trouver le contour, essentiellement des coins des rectangles afin que nous puissions réduire ce problème à un niveau où nous nous en chargeons de calcul, une fois que nous avons des points que nous pouvons pour obtenir les coordonnées.

3. numérisez le tableau 2D ci-dessus et marquez un point 1 s'il est contenu dans l'un des rectangles donnés.

4. maintenant, scannez le tableau 2D et cherchez les points dont le voisinage a une Division 3:1, c'est-à-dire sur 3 côtés il a 1s et sur un côté 0s ou vice versa. Ces points sont ceux qui définiront contour.

je pense que la complexité sera managiable si nous pouvons réduire l'ampleur du problème à bon escient.

j'ai trouvé un moyen beaucoup plus simple:

1. Créer une image noire.
2. dessinez des rectangles remplis sur l'image en couleur blanche. Avec cela tous les rectangles superposés seront connectés.
3. trouver les contours de la tache.

C'est elle!

j'ai eu un problème similaire plus tôt. Je ne sais pas exactement comment vos points sont alignés, mais le mien était toujours espacé à 5 mètres l'un de l'autre.

ma solution était d'obtenir le point ordonné par la coordonnée X.

avait deux listes, une appelée précédente et une appelée courante.

si current était vide, ajoutez le point à current. Si le courant n'est pas vide, puis vérifiez si le point est adjacent à l'un des points actuel (exécuter la liste par en arrière comme il y a une plus grande chance un point récent est adjacent)

Si le point n'est pas adjacent à un point quelconque de l'actuel, puis vérifier si l'un des points actuel est adjacent à un point quelconque dans la liste précédente. Si oui, alors fusionnez-les (concat), sinon déplacez les points de la liste précédente vers une autre liste contenant les polygones complets, puis définissez previous = current, empty current et ajoutez le point en cours de traitement à current.

selon la façon dont vos points sont traités(le commande), vous pourriez avoir besoin pour exécuter toutes les polygones à nouveau pour vérifier si elles sont adjacentes à l'un des autres polygones.

désolé pour le long mur de texte, faites-moi savoir si vous voulez coder, il est en c# et pas très propre.

il suffit de tester si les rectangles se touchent et ensuite exécuter coque convexe sur l'union de leurs points.

ou vous pouvez également tester manuellement pour voir quel côté des rectangles se touchent et ajouter le point dans le bon ordre à un objet Polygone.

Ces assumer polygones fermés suffit (pas de trous).