Autor Beitrag
icho2099
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 101
Erhaltene Danke: 12

WIN XP, WIN 7, WIN 10
Delphi 6 Prof, Delphi 2005, FPC
BeitragVerfasst: Do 13.10.11 21:57 
Hallo ,

ich habe Punktlisten, aus denen ich Polygone erzeuge (Postleitzahlbereiche in diesem Fall). Das funktioniert soweit einwandfrei.

Nun möchte ich aber eine Gruppe von Polygonen, z.B. alle Postleitzahlbereiche die mit 282xx beginnen, zu einem neuen Polygon, das nur aus dem aüßeren Umriß aller Polygone besteht, umwandeln bzw. neu erstellen.

Letztendlich möchte ich beliebige, zusammenhängende Polygone zu neuen Polygonen "verschmelzen".

Hat jemand eine Idee wie man da rangehen könnte ?

Moderiert von user profile iconNarses: Überflüssige Zeilenumbrüche/Leerzeilen entfernt.
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1600
Erhaltene Danke: 232


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Do 13.10.11 23:37 
Riecht nach anspruchsvoller Graphentheorie, bin mir da aber nicht sicher.

Wenn Du Punkte erfolgreich zu Polygonen verbinden kannst, wie wäre es denn, diese Polygone selbst als Punkte aufzufassen (bzw. zu solchen zu reduzieren, z.B. zu den jeweiligen Schwerpunkten), um diese dann wiederum von einem Polygon einhüllen zu lassen? Danach werden die ursprünglichen Polygone, danach zu Punkten reduziert, dann wieder zu ihren alten Polgonen entfaltet/expandiert.

Visuell habe ich das vor meinem mentalen Auge, wie das aussehen/ablaufen/funktionieren könnte.

Natürlich dürfte das eine höllische Programmierarbeit verursachen, aber das ist ja letztlich auch das, was den Reiz ausmacht und im Erfolgsfalle ein(en) Genuß(gefühl).
F34r0fTh3D4rk
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 5284
Erhaltene Danke: 27

Win Vista (32), Win 7 (64)
Eclipse, SciTE, Lazarus
BeitragVerfasst: Fr 14.10.11 00:19 
Ich glaube was du möchtest, ist die Suche in Wikipedia KONVEXE HÜLLE einer Punktmenge berechnen. Das geht beispielsweise relativ einfach mit Suche in Wikipedia QUICKHULL.

Ansonsten wäre ein Bild zur Anschauung vielleicht gar nicht so verkehrt.
jaenicke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19312
Erhaltene Danke: 1747

W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: Fr 14.10.11 07:07 
Wenn dir das ausreicht, kannst du diese Berechnungen auch einfach dem Betriebssystem überlassen:
CreatePolygonRgn
CombineRgn
und so weiter...
Diese Regionen kannst du dann zeichnen lassen, dabei auch skalieren, rotieren, ...
Ein Vorteil ist auch, dass du so stets ein Regionsobjekt hast, egal ob es zusammenhängend ist oder nicht und du kannst auch automatisch prüfen, ob ein Punkt in dieser Region liegt (z.B. wenn jemand mit der Maus auf eine Karte klickt, ...).

Selbst berechnen könnte in deinem Fall schneller sein, aber dafür ist es auch mehr Arbeit.
Lemmy
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 792
Erhaltene Danke: 49

Windows 7 / 10; CentOS 7; LinuxMint
Delphi 7-XE10.1, VS 2015
BeitragVerfasst: Fr 14.10.11 09:14 
user profile iconF34r0fTh3D4rk hat folgendes geschrieben Zum zitierten Posting springen:
Ich glaube was du möchtest, ist die Suche in Wikipedia KONVEXE HÜLLE einer Punktmenge berechnen. Das geht beispielsweise relativ einfach mit Suche in Wikipedia QUICKHULL.


cool was es alles so gibt... ich hätte das per Brute-Force gelöst :-)

Aber der QuickHull muss nicht zwangsläufig funktionieren, da die PLZ-Bezirke sich ja nicht zwingend wie eine Hülle verhalten, da kann es ja schon mal eine Enklave geben, oder Zacken die in ein anderes PLZ-Gebiet eindringen:

ausblenden Quelltext
1:
2:
3:
             *
            / \
 *---------*   *-----------

einen solchen Fall könnte QuickHull nicht korrekt darstellen.

Kommen wir wieder zum BruteForce. Wie sind denn die Daten vorhanden? Steht da zu einer PLZ einfach ne Menge n an Koordinaten? Sind die Schnittpunkte der PLZ-Bezirke irgendwie gekennzeichnet?

Vielleicht könnte das funktionieren:

Nimm die Punktmenge der PLZ-Bezirke die zusammengefasst werden sollen
Such in der Punktmenge die Punkte raus, die in GENAU 2 PLZ-Bezirken vorkommen. Damit hast Du schon mal die ersten Stüztpunkte deiner Hülle. Und es müssen genau 2 PLZ-Bezirke sein, denn wenn der Punkt in 3 oder mehr Bezirken vorkommt, dann liegt der in der Mitte der Punktwolke. Wenn Du dich dann so von einem der PLZ-Bezirke zum anderen vorarbeitest, dann bekommst Du auch gleich ne Sortierung zusammen:

SP 1 PLZ1; PLZ2
SP 2 PLZ2; PLZ3
SP 3 PLZ3; PLZ4
...
SPn PLZm; PLZ1

Dann beginnst Du bei SP1 und nimmst alle Punkte die zwischen SP1 und SP2 liegen mit in den Polygon auf. So machst Du weiter bis Du wieder am SP1 angekommen bist...

Jetzt bleibt nur noch die Frage: Wie kommst Du zum ersten Stützpunkt: Dazu einfach in der Punktwolke den Punkt mit dem kleinsten/größten x oder y suchen und von dem aus die folgenden Punkte untersuchen bis Du deinen ersten Stützpunkt der in 2 PLZ-Bezirken vorhanden ist vorkommt..


Grüße

[Nachtrag]

kann so wie oben steht nicht funktionieren, weil im Grunde alle innerhalb der Punktwolke liegenden Punkte zu 2 Bezirken dazugehören - die bilden ja die Grenze. d.h. dann müsste man die Verbindungen vergleichen. d.h. man fängt mit dem Punkt links unten an und schaut ob der in einem weiteren Bezirk enthalten ist. Wenn ja, dann muss die Richtung (Tangens) bestimmt werden und miteinander vergleichen und je nachdem ob man im Uhrzeigersinn rumgeht oder dagegen müsste man dann halt die Verbindung mit dem größten/kleinsten Tangens nehmen...

GRüße
icho2099 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 101
Erhaltene Danke: 12

WIN XP, WIN 7, WIN 10
Delphi 6 Prof, Delphi 2005, FPC
BeitragVerfasst: Fr 14.10.11 13:58 
Besten Dank erst einmal,

auch wenn ich so recht noch keine brauchbare Lösung daraus erkennen kann.
Die Punkte der Polygone liegen als Geo-Koordinaten vor, also als Float, nicht als Integer.
Daher scheiden leider die Region-Funktionen aus.

Die konvexe Hülle um die Punkte herum liefert auch nicht das, was ich brauche. Die äußere Form zweier verschmolzener Polygone setzt sich
ja aus jeweils einem Teil der äußeren Form jedes einzelnen Polygons zusammen. Eine konvexe Hülle würde alle konkaven Teile entfernen.
Die äußere Form soll aber beibehalten werden.

Die Daten liegen in dieser Form vor: [Polygon][LNG][LAT]
ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
//Polygon 0
0 1.37190000000000E+0001 5.10760000000000E+0001
0 1.37210000000000E+0001 5.10750000000000E+0001
0 1.37220000000000E+0001 5.10730000000000E+0001
0 1.37240000000000E+0001 5.10710000000000E+0001
.........
//Polygon 1
1 1.37500000000000E+0001 5.10540000000000E+0001
1 1.37510000000000E+0001 5.10550000000000E+0001
1 1.37540000000000E+0001 5.10550000000000E+0001
1 1.37570000000000E+0001 5.10570000000000E+0001
.....

Ich zeige nur einen Ausschnitt, es sind insgesamt 1.086.233 Punkte, die 8.270 Polygone bilden.
Alle Punkte mit gleicher Polygon-Nummer (der erste Wert) bilden ein Polygon. Die Postleitzahlen
werden aus einer separaten Tabelle zugeordnet, spielen aber für die Aufgabe selber auch keine
Rolle.
Ich erstelle Objekte für jedes Polygon mit jeweils einem offenen Array für die Punkte.

ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
Type
  //GeoPoint speichert Länge/Breite eines Einzelpunktes
  tGeoPoint       = Record
                      LNG       : Double;
                      LAT       : Double;
                    end;

  //GeoPoints ist ein offenes Array von GeoPoints
  tGeoPoints      = Array of tGeoPoint;

  //tIntPoints ist das selbe aber als Array of tPoint
  tIntPoints      = Array of tPoint;

  //===========================================================================
  //PLZShape ist ein Objekt für genau einen Postleitzahlbereich
  //Es enthält die Shapenummer ShapeNo und ein offenes Array aller
  //GeoPoints, die den Umriss des Bereiches bilden.
  //PLZ sind als String und als Integer verfügbar
  //===========================================================================
  tPLZShape       = Class(tObject)
                    Private
                      FShapeNo    : Integer;
                      FPLZ        : String;
                      FPLZi       : Integer;
                      FPoints     : tGeoPoints;
                      FintPoints  : tIntPoints;
                      FLineColor  : tColor;
                      FLineWidth  : Integer;
                      FFillColor  : tColor;

                      FGMMx       : tGMMx;

                      FFilled     : Boolean;
                      FFrameRect  : TRect;
                      FSelected   : Boolean;

                      Function    rdCount:Integer;

                    Public
                      Property    ShapeNo:Integer read FShapeNo write FShapeNo;         //die Shapenummer
                      Property    Points:tGeoPoints read FPoints;                       //die Punkte
                      Property    Count:Integer read rdCount;                           //Anzahl Punkte
                      Property    PLZ:String read FPLZ write FPLZ;                      //PLZ als String
                      Property    PLZi:Integer read FPLZi write FPLZi;                  //PLZ als Integer
                      Property    LineColor:tColor read FLineColor write FLineColor;
                      Property    LineWidth:Integer read FLineWidth write FLineWidth;
                      Property    FillColor:tColor read FFillColor write FFillColor;
                      Property    GMMx:tGMMx read FGMMx write FGMMx;                    //GMMx bildet die Karte ab
                      Property    Filled:Boolean read FFilled write FFilled;
                      Property    FrameRect:TRect read FFrameRect write FFrameRect;
                      Property    Selected:Boolean read FSelected write FSelected;

                      Constructor Create(aShapeNo : Integer; aGMMx : tGMMx);
                      Destructor  Destroy; Override;

                      Procedure   AddGeoPoint(aLNG,aLAT : Double);                      //Punkt hinzufügen

                      Procedure   MakeIntPoints;                                        //Integerpunktwerte
                      Procedure   DrawShape(Canvas : tCanvas);                          //auf Camvas abbilden
                      Procedure   DrawFrameRect(Canvas : tCanvas);                      //Rahmenrechteck zeichnen

                      Function    MouseInRect(x,y : Integer):Boolean;
                    end;

Ich kann die Polygone anzeigen, mit der Maus auswählen etc. Ich hab einen Ausschnitt als Screenshot beigelegt, der zeigt
mehrere markierte Polygone (PLZBereiche), die verschmolzen werden sollen. Vielleicht erleichtert das das Verständnis für
die Aufgabe.
Bin natürlich weiterhin für jede Hilfe dankbar.
Einloggen, um Attachments anzusehen!
Oliver Marx
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 80
Erhaltene Danke: 18

Win 7 Prof.
Delphi XE Prof.
BeitragVerfasst: Fr 14.10.11 14:38 
Hi,

sind denn die Punkte auf einer Grenze zwischen zwei angrenzenden Regionen immer identisch?
Dann könntest du die Punkte ermitteln, an denen sich die Grenzen berühren und die Punkte entfernen. Für die restlichen Punkte musst du dann nur noch die Umlaufrichtung ermitteln und kannst dann die restlichen Punkte zusammenführen.

Viele Grüße

Oliver
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: Sa 15.10.11 10:28 
Hallo,

Zitat:
Die Punkte der Polygone liegen als Geo-Koordinaten vor, also als Float, nicht als Integer.
Daher scheiden leider die Region-Funktionen aus

Du kannst deine GeoKoordinaten ja einfach auf longint skalieren.
Der Bereich wäre ja von 0 .. 360 Grad Länge und +- 90 Grad Breite.
Zitat:
1.37190000000000E+0001 5.10760000000000E+0001

Mit 6 Nachkommastellen Genauigkeit ( mehr als float bei 51,00 hat ) wäre es ein Leichtes die Zahlen mit 1e6 zu multiplizieren und auch so zu speichern.
51,0760° Breite wäre dann 51.076.000 (*1e-6 )
Damit wäre Combinergn etc anwendbar.

Oliver Marx seine Vermutung ist natürlich einleuchtend.
Vielleicht wäre es dabei hilfreich zu wissen bzw. festzuhalten, welche Nachbarpolygone ein Polygon hat.

Gruß Horst
jaenicke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 19312
Erhaltene Danke: 1747

W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
BeitragVerfasst: Sa 15.10.11 11:07 
Die Regionsfunktionen sind vor allem aus anderen Gründen nicht ohne weiteres anwendbar:
Es sind schlicht zu viele Polygone, da gehen die Systemressourcen zur Neige. Mehr als 10000 GDI Handles sind keine gute Idee und die Grenze kommt ja schon recht nahe.

Deshalb bliebe dann nur ein Ansatz, den ich selbst auch schon einmal gewählt habe:
Ich speichere die Regionen als Rechtecke für Hittests und prüfe erst genauer, wenn der Klick überhaupt ungefähr auf der Region liegt. Dadurch kann ich die Region (gekapselt durch entsprechende Objekte) erzeugen, wenn ich sie brauche.
Wenn mehrere kombiniert werden, ist es ja nur noch ein Handle, das ich mir merken kann.

Die wichtigste Frage ist erst einmal:
Was soll denn danach mit den kombinierten Polygonen passieren? In welcher Form werden daher die resultierenden Polygondaten benötigt?
icho2099 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 101
Erhaltene Danke: 12

WIN XP, WIN 7, WIN 10
Delphi 6 Prof, Delphi 2005, FPC
BeitragVerfasst: Sa 15.10.11 19:18 
Ich benötige die neuen Polygone (Regionen) hauptsächlich zur Darstellung auf der Karte.

Es ist kein Problem die ~8.000 Regionen als Polygone abzubilden. Ich erstelle ja keine
sichtbaren Objekte, verbrauche also auch keine Ressourcen für die Darstellung.
Hittest mache ich ähnlich wie Jaenicke beschreibt. Ich berechne zu jedem Polygon das
umschließende Rechteck (FFrameRect). Bei Mausbewegung z.B. bestimme ich alle Rechtecke, in denen
der Mauszeiger liegt. Dann berechne ich von diesen Rechtecken den euklidischen Abstand zwischen deren
Mittelpunkt und dem Mauszeiger und nehme dann dasjenige mit dem kleinsten Abstand.
Das funzt relativ gut und ich erspare mir die "Punkt in Polygone" Berechnungen, die erheblich aufwändiger sind.
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
//Liefert das Shape zurück, dessen FrameRect-Mittelpunkt der
//Position x/y am nähesten ist.
//dient zur Selektierung der Shapes
Function tPLZShapes.NearestShape(x,y:Integer):tPLZShape;
Var i       : Integer;
    CP      : tPoint;
    Distn   : Double;
    minDist : Double;
begin
  Result  := NIL;
  minDist := MaxInt;
  For i := 0 to High(FPLZShapes) do begin
    If FPLZShapes[i].MouseInRect(x,y) then begin
      //Mittelpunkt des FrameRects
      CP   := CenterPoint(FPLZShapes[i].FrameRect);
      //Abstand zum Mauspunkt
      Distn := Sqrt(Sqr(CP.X-x)+Sqr(CP.Y-y));
      //Shape mit kleinstem Abstand als Ergebnis
      If Distn < minDist then begin
        minDist := Distn;
        Result := FPLZShapes[i];
      end;
    end;
  end;
end;

Zum Verschmelzen markierte Polygone sollen neue Bereiche bilden (z.B. Vertriebsbereiche, Zuständigkeitsgebiete, etc. )
Diese neuen Bereiche sollen dann nur durch ihren Umriß in der Karte abgebildet werden.
Die neuen Bereiche müssen aber variabel bleiben. Es muss also möglich sein, dass zukünftig Polygone hinzugefügt oder
auch entfernt werden. (Löcher und Inseln sind ausgeschlossen, wenngleich die Prüfung auf Löcher und Inseln auch noch ein
Problem werden könnte...)
Die resultierenden Polygone werden ebenso wie die bereits existierenden als Liste von Geo-Koordinaten benötigt.

Ich verfolge den Vorschlag von Oliver Marx. Mal sehen, ob ich das zur Laufzeit immer wieder neu bestimmen kann, oder ob ich
die neuen Polygone speichern muß. Ich werde berichten.