Umwandeln Vektor-konturierten Zonen (Grenze) auf eine Rasterkarte (Pixelraster)

Question

Ich habe eine Karte, die durch Grenzen (Konturen) wie Länder auf einer Weltkarte in eine Reihe von Regionen zerschneiden wird. Jede Region hat eine bestimmte Oberflächenabdeckung Klasse S (zum Beispiel 0 für Wasser, 0,03 für Gras ...). Die Grenzen sind definiert durch:

• , was einem Wert von S ist auf beiden Seiten davon (0,03 auf einer Seite, 0.0 auf der anderen Seite, im Beispiel unten)
• , wie viele Punkte die Grenze ist aus ( n = 7 in Beispiel unten), und
• n Koordinatenpaar ( x , y ).

Dies ist ein Beispiel dafür.

0.0300      0.0000           7
2660607.5   6332685.5   2660565.0   6332690.5   2660541.5   6332794.5 
2660621.7   6332860.5   2660673.8   6332770.5   2660669.0   6332709.5 
2660607.5   6332685.5

Ich möchte eine Rasterkarte machen, in dem jedes Pixel den Wert von hat S in der Region entspricht, in dem das Zentrum des Pixels fällt.

Beachten Sie, dass die Grenzen darstellen Schritt Änderungen in S . Die verschiedenen Werte von S repräsentiert diskrete Klassen (zum Beispiel Gras oder Wasser) und sind keine Werte, die gemittelt werden können (das heißt kein nasses Gras!).

Beachten Sie auch, dass nicht alle Grenzen geschlossene Schleifen wie in dem Beispiel sind oben. Das ist ein bisschen wie die Landesgrenzen: z.B. die US-kanadische Grenze ist nicht eine geschlossene Schleife, sondern eine Linie an jedem Ende mit zwei anderen Grenzen Beitritt: in dem Kanada-Meer und dem US-Ozean „Grenzen“. (Closed-Loop-Grenzen existieren doch!)

Kann mir jemand zeigen auf einem Algorithmus, der dies tun kann? Ich will nicht das Rad neu erfinden!

Answer 1

So wie ich das gelöst habe, ist wie folgt:

1. März entlang jedem Segment; Stopp in regelmäßigen Abständen L .
2. An jeder Haltestelle, legt einen Tracer Punkt unmittelbar links und rechts von dem Segment (in einem bestimmten kleinen Abstand d aus dem Segment). Die Tracer-Punkte sind die linken und rechten S-Wert zugeordnet sind.
3. Führen Sie eine Nächster-Nachbar-Interpolation. Jeder Punkt auf dem Rastergitter ist die S des nächsten Tracer Punkt zurückgeführt.

Dies funktioniert auch, wenn es nicht geschlossene Linien, z.B. am Rand der Karte.

Dies ist kein „perfekter“ analytischer Algorithmus. Es gibt zwei Parameter: L und d . Der Algorithmus funktioniert wunderbar, solange d << L . Ansonsten können Sie Ungenauigkeiten erhalten (in der Regel Einzelpixel) in der Nähe von Segmentübergängen, insbesondere solche mit spitzen Winkeln.

Answer 2

Der allgemeine Fall für die Verarbeitung diese Art von Geometrie in Vektorform kann ziemlich schwierig sein, vor allem, da nichts über die Struktur, die Sie beschreiben, erfordert die Geometrie konsistent zu sein. Da jedoch Sie nur wollen, es rastern, dann das Problem zu behandeln, als ein Voronoidiagramm Segmente Linie robuster sein kann.

die Voronoidiagramm Annähern durch Ziehen jedes Liniensegment als ein Paar von Quads machen ein Zelt Form grafisch in OpenGL erfolgen. Der Z-Puffer wird verwendet, um die nächste Quad hat Vorrang zu machen, und die Farbe so die Pixel basierend auf welcher Linie am nächsten ist. Der Unterschied besteht darin, dass Sie die Polygone basierend auf welcher Seite der Linie sind sie auf, statt dessen Leitung sie darstellen färben wollen. Ein gutes Papier einen ähnlichen Algorithmus diskutiert, ist Hoff et al schnelle Berechnung rel="nofollow von Generalized Voronoi-Diagramme Mit Graphics Hardware

Die 3D-Geometrie wird so etwas wie diese Skizze aussieht mit 3 rot / gelb Segmenten und 1 blau / grün Segment:

Dieses Verfahren erfordert Sie nicht alles in eine geschlossene Schleife zu konvertieren, und erfordert keine Phantasie Geometrie Bibliotheken. Alles wird durch den z-Puffer behandelt und sollte schnell genug sein, in Echtzeit auf jede moderne Grafikkarte laufen. Eine Verfeinerung wäre homogene Koordinaten zu verwenden, um die Basen Projekt bis ins Unendliche zu machen.

I implementiert diesen Algorithmus in einem Python-Skript unter http://www.pasteall.org/9062/ python . Eine interessante Einschränkung ist, dass Konen mit den Enden der Linien Kappe nicht ohne funktionierten die Form des Kegels zu verzerren, da die Konen die Endpunkte der Segmente waren z Bekämpfung darstellt. Für die Probengeometrie Sie zur Verfügung gestellt, sieht die Ausgabe wie folgt aus:

Answer 3

Ich würde Ihnen empfehlen, eine Geometrie-Algorithmus-Bibliothek zu verwenden, wie CGAL . Besonders das zweite Beispiel in dem "2D-Polygons" Seite des Referenzhandbuchs sollten Sie, was Sie brauchen. Sie können jede „Grenze“ als Polygon definieren und überprüfen, ob bestimmte Punkte innerhalb der Polygone sind. Also im Grunde wäre es so etwas wie

sein

for every y in raster grid
  for every x in raster grid
    for each defined polygon p
      if point(x,y) is inside polygon p
        pixel[X][Y] = inside_color[p]

Ich bin mir nicht so sicher, was mit dem outside_color zu tun, weil die äußeren Regionen überlappen, werden sie nicht? Wie auch immer, bei Ihrem Beispiel sucht, könnte jeder Außenbereich Wasser, so dass Sie nur einen endgültigen tun könnten

    if pixel[X][Y] still undefined then pixel[X][Y] = water_value

(oder als Alternative, stellen Pixel [X] [Y] vor Iterieren durch die Polygonliste water_value)

Answer 4

• zuerst, konvertieren alle Ihre Grenzen in geschlossenen Schleifen (möglicherweise die Ränder Ihrer Karte einschließlich) und indentify die Innenfarbe. dies muss möglich sein, sonst hat man eine Inkonsistenz in Ihren Daten
• Verwendung Bresenham-Algorithmus all Grenzlinien auf der Karte, in einer einzigen nicht verwendeten Farbe zu zeichnen
  • speichern Sie eine Liste aller „Randpixel“, wie Sie tun, um diese
• dann für jede Grenze
  • triangulate es (Delaunay)
  • die Dreiecke durchlaufen, bis Sie ein, dessen Zentrum zu finden, ist in Ihrem Rand (Point-in-Polygon-Test)
  • FloodFill Ihre Karte an diesem Punkt in der Innenfarbe Grenze
• , wenn Sie in allen Innenbereichen ausgefüllt haben, durch die Liste der Randpixel iterieren, sehen, welche Farbe jeder sollte
sein

Answer 5

• Wählen Sie zwei nicht benötigten Farben als Marker „leer“ und „Grenze“
• füllen Sie alle Bereich mit "leeren" Farbe
• ziehen alle Region grenzt von "Grenze" Farbe
• durchlaufen Punkte auf erste mit „leeren“ Farbe
finden
• bestimmen, welche Region sie gehört ( „Punkt innerhalb Polygon“ google, wahrscheinlich müssen Sie Ihre Grenzen machen geschlossen wie Martin DeMello vorgeschlagen)
• durchführen Flut-fill-Algorithmus von diesem Punkt mit Farbe der Region
gehen
• zum nächsten „leer“ Punkt (keine Notwendigkeit, die Suche starten - einfach weiter)
• und so weiter, bis keine „leeren“ Punkte bleiben