Wie wird eine Polylinie oder ein Polygon in einen Kettencode umgewandelt?

Question

Ich habe eine offene oder geschlossene Polylinie (Polygon) aus der Menge der 2D-Punkte.

Ich muss diese Polylinie als Kettencode darstellen. Wenn ich richtig verstanden habe, muss ich Polyliniensegmente mit dem Bresenham-Algorithmus rastern und die Kettencodeform dieses Rasters konstruieren. Aber gibt es einen besseren Algorithmus?

Was sind die optimalen Algorithmen zum Konvertieren von Polyline (Polygon) in Chain-Code?

Answer 1

Ja, es wird wesentlich schneller sein, die Punkte direkt in die Fourier-Transformation zu zeichnen. Überspringe das Raster und mache daraus einen Chaincode, schließlich brauchst du die Punkte richtig, um in die Richtung zu kommen, in die die Polylinie für den algorithmischen Gebrauch von Kuhl-Giardiana 1982 geht. Wenn Sie alle Pixel in der richtigen Reihenfolge haben möchten, können Sie dies direkt erreichen, indem Sie die Pixel in den Algorithmus selbst zeichnen, anstatt alles zu rastern. In der Tat würde dies im Grunde den Chain-Code und das Raster überspringen.

---

Alle Linien werden von der Form y sein = mx + b und der schnellste Weg, dies zu tun sein wird, Bresenhamschen. Abhängig von der eventuellen Verwendung können Sie sich jedoch für den Algorithmus von Wu entscheiden, so dass Sie sicher sein können, Anti-Aliasing zu verwenden, was dazu führt, dass die Linien schärfer aussehen (und Sie müssen das Alpha speichern). Angenommen, Sie benötigen den Kettencode für etwas Bestimmtes, ja, Sie benötigen die tatsächlichen Pixel, die diese Linie erzeugt, was bedeutet, dass Sie einen Linienzeichnungsalgorithmus verwenden.

Die meisten Ihrer Zeichen-Apis geben Ihnen das gerasterte Bild und nicht den Kettencode. Es besteht die Möglichkeit, die Polylinie in ein schwarzes Bild von passender Größe zu zeichnen und durch das gesamte Bild zu gehen und jedes schwarze Pixel aufzulisten. Es wäre einfach zu programmieren, wenn auch langsam und unnötig und in unternehmenskritischen Operationen wäre es kein Starthilfe.

Der Code wird ziemlich einfach sein, machen Sie einfach Bresenham und dann werfen Sie die Punkte, wo es einen Punkt in den Chaincode hinzufügen würde.

public void plotLines(int[] twodshape, Chaincode chain) { 
    for (int i = 0, s = twodshape.length-4; i < s; i+=2) { 
     plotLine(twodshape[i],twodshape[i+1],twodshape[i+2],twodshape[i+3],chain); 
    } 
} 
public void plotLine(int x0, int y0, int x1, int y1, Chaincode chain) { 

    int dy = y1 - y0; //BRESENHAM LINE DRAW ALGORITHM 
    int dx = x1 - x0; 

    int stepx, stepy; 

    if (dy < 0) { 
     dy = -dy; 
     stepy = -1; 
    } else { 
     stepy = 1; 
    } 

    if (dx < 0) { 
     dx = -dx; 
     stepx = -1; 
    } else { 
     stepx = 1; 
    } 
    if (dx > dy) { 
     dy <<= 1;             // dy is now 2*dy 
     dx <<= 1; 
     int fraction = dy - (dx >> 1);       // same as 2*dy - dx 
     chain.add(x0,y0); 

     while (x0 != x1) { 
      if (fraction >= 0) { 
       y0 += stepy; 
       fraction -= dx;        // same as fraction -= 2*dx 
      } 
      x0 += stepx; 
      fraction += dy;         // same as fraction += 2*dy 
      chain.add(x0,y0); 
     } 
     chain.add(x0,y0); 
    } else { 
     dy <<= 1;             // dy is now 2*dy 
     dx <<= 1;             // dx is now 2*dx 
     int fraction = dx - (dy >> 1); 
     chain.add(x0,y0); 
     while (y0 != y1) { 
      if (fraction >= 0) { 
       x0 += stepx; 
       fraction -= dy; 
      } 
      y0 += stepy; 
      fraction += dx; 
      chain.add(x0,y0); 
     } 
     chain.add(x0,y0); 
    } 
} 

Update: entfernte ich die rekursive Bit, die ich brauchte, dass für ein bestimmtes Problem mit Linien von Punkt A gezogen wird zu Punkt B nicht gleich sein von B nach A. garantiert werden Durch die Rundung die Piste. Zum Beispiel, wenn Sie 1 Pixel und rechts 5 hochgehen. Es gibt zwei gleichwertige Möglichkeiten, dies zu tun, und es gab mir keine einheitliche Antwort.

---

Wenn Sie es tief in chaincode:

public int convertToChaincode(int cx, int cy) { 
    if ((cx == 1) && (cy == 0)) return 0; 
    if ((cx == 1) && (cy == 1)) return 1; 
    if ((cx == 0) && (cy == 1)) return 2; 
    if ((cx == -1) && (cy == 1)) return 3; 
    if ((cx == -1) && (cy == 0)) return 4; 
    if ((cx == -1) && (cy == -1)) return 5; 
    if ((cx == 0) && (cy == -1)) return 6; 
    if ((cx == 1) && (cy == -1)) return 7; 
    return -1; //error. 
} 

public void plotLine(int x0, int y0, int x1, int y1, ChainCode chain) { 

    int dy = y1 - y0; //BRESENHAM LINE DRAW ALGORITHM 
    int dx = x1 - x0; 

    int stepx, stepy; 
    int cx = 0; 
    int cy = 0; 

    if (dy < 0) { 
     dy = -dy; 
     stepy = -1; 
    } else { 
     stepy = 1; 
    } 

    if (dx < 0) { 
     dx = -dx; 
     stepx = -1; 
    } else { 
     stepx = 1; 
    } 
    if (dx > dy) { 
     dy <<= 1;             // dy is now 2*dy 
     dx <<= 1; 
     int fraction = dy - (dx >> 1);       // same as 2*dy - dx 
     //typically set start point. 

     while (x0 != x1) { 
      if (fraction >= 0) { 
       y0 += stepy; 
       cy = stepy; 
       fraction -= dx;        // same as fraction -= 2*dx 
      } 
      x0 += stepx; 
      cx = stepx; 
      fraction += dy;         // same as fraction += 2*dy 
      chain.add(convertToChaincode(cx,cy)); 
     } 
    } else { 
     dy <<= 1;             // dy is now 2*dy 
     dx <<= 1;             // dx is now 2*dx 
     int fraction = dx - (dy >> 1); 
     //typically set start point 
     while (y0 != y1) { 
      if (fraction >= 0) { 
       x0 += stepx; 
       cx = stepx; 
       fraction -= dy; 
      } 
      y0 += stepy; 
      cy = stepy; 
      fraction += dx; 
      chain.add(convertToChaincode(cx,cy)); 
     } 
    } 
}