Polygone mergen

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo zusammen,

ich stehe gerade ziemlich auf dem Schlauch. Vielleicht hat hier jemand eine Idee.

Ich hatte mir Geokoordinaten der PLZ-Gebiete Deutschlands besorgt. Die Koordinaten habe ich jetzt soweit bearbeitet, dass ich die PLZ-Gebiete als Polygone in einer SVG-Datei darstellen kann.

Soweit so gut. Will man ganz Deutschland darstellen, wird die SVG-Datei aber viel zu groß. Da ich 5-stellige PLZ-Gebiete eigentlich gar nicht brauche, würde ich gerne wissen, ob es eine einfache (also umsetzbare) Möglichkeit gibt, diese Gebiete (Polygone) zu mergen?

Was ich gerne hätte:

3-stellige, 2-stellige, 1-stellige PLZ-Gebiete bzw. eine Polygon für ganz Deutschland.

Ich zerbreche mir schon seit einiger Zeit meinen Kopf über einen geeigneten Algorithmus, komme aber nicht wirklich weiter. Aktuell ist mir nur klar, dass ich besser immer nur zwei benachbarte Polygone gleichzeitig merge. Aber allein das ist schon schwierig.
Hat hier jemand einen Ansatz?

Danke.

MfG
Stephan

PS: Hier mal ein Beispiel.

<?xml version="1.0" encoding="utf-8"?>
#2

Hallo Stephan,

Soweit so gut. Will man ganz Deutschland darstellen, wird die
SVG-Datei aber viel zu groß. Da ich 5-stellige PLZ-Gebiete
eigentlich gar nicht brauche, würde ich gerne wissen, ob es
eine einfache (also umsetzbare) Möglichkeit gibt, diese
Gebiete (Polygone) zu mergen?

Ich zerbreche mir schon seit einiger Zeit meinen Kopf über
einen geeigneten Algorithmus, komme aber nicht wirklich
weiter. Aktuell ist mir nur klar, dass ich besser immer nur
zwei benachbarte Polygone gleichzeitig merge. Aber allein das
ist schon schwierig.
Hat hier jemand einen Ansatz?

Mir fällt spontan das folgende Verfahren ein:
Du suchst zwei benachbarte Polygone, indem Du zwei Polygone suchst, die zwei gemeinsame benachbarte Punkte haben. Die musst Du Dir erst einmal suchen. Für das Mergen nimmst Du alle gemeinsamen benachbarten Punkte und fügst den Pfad so zusammen, dass die Punkte nur einmal im Polygon sind.
Bei Deinem Beispiel sind dies bei den ersten beiden Polygonen die Punkte 671x1387 bis 663x1400. Diese laufen einmal aufwärts (671x1398, 671x1399, …, 663x1400 beim zweiten Polygon) und einmal abwärts (beim ersten Polygon, hierbei musst Du aufpassen, da die Punkte das erste und letzte Element enthalten).
Nun nimmst Du von ersten Polygon den letzten gemeinsamen Punkt (671x1398) und fügst alle Punkt bis zum ersten gemeinsamen Punkt hinzu (673x1398, …, 664x1401 663x1400).
Anschließend wechselst Du zum zweiten Polygon und fängst am gemeinsamen Punkt rückwärts an, das Polygon zu zeichnen, bis es vollständig ist (671x1397, 671x1396, …, 661x1401, 662x1401).
Damit sollten die Polygone miteinander verbunden sein. Die Punkte, die nur die beiden ursprünglichen Polygone als Nachbarn hatten sind durch das Verfahren auch eliminiert.

Viele Grüße
Diether

#3

Mir fällt spontan das folgende Verfahren ein:
Du suchst zwei benachbarte Polygone, indem Du zwei Polygone
suchst, die zwei gemeinsame benachbarte Punkte haben. Die
musst Du Dir erst einmal suchen. Für das Mergen nimmst Du alle
gemeinsamen benachbarten Punkte

das einzige problem bei diesem ansatz könnte sein, dass die polygone
nicht immer gemeinsame punkte haben, sondern auch mal nur gemeinsame
kanten, also eine ecke eines polygons trifft irgendwo in der mitte
auf eine kante eines anderen und teilt sich die kante dann für ein
stück mit dem anderen.
in dem fall müsste man dann durch berechnung interpolieren, ob die
polygone direkt benachbart sind.
das kommt aber auf die eingabedaten an.
ein weiterer sonderfall könnte sein, wenn ein postleitzahlgebiet ein
anderes umkreist, das dürfte aber nicht ganz so kompliziert sein.

#4

Hallo zusammen,

ich werde einfach mal etwas rumprobieren. Den Ansatz von Diether hatte ich mir so ähnlich auch schon überlegt. Mal sehen auf welche Probleme ich dabei noch stoße.

MfG
Stephan