Aus GPS-Daten die umschließende Fläche ermitteln?

[moenk]

Ich habe auch noch ein Fitzelchen Basic-Source zur Berechnung von Schnittpunkten von Geraden. Das muss man hier vorher machen, Wenn man sich das aufmalt, dann sieht man auch die neuen Punkte die dann erst zur Fläche berechnet werden können. Verschneidung ist eben so ein Thema, aber das wurde hier ja schon erwähnt.

 

[Geofix]

Ich würde folgenden (vieleicht nicht sehr eleganten) Algorithmus vorschlagen:

Der Vorschlag umreißt nur die grobe Idee, nicht die Details wie Schnittpunktberechnung etc.

Du speicherst zu jedem Polygonsegment noch je ein Attribut dafür ob Links und Rechts "innen" oder "außen" liegt. Zunächst beginst Du mit "links = außen und rechts = außen", denn noch ist nicht klar, ob Du jemals eine Fläche umfahren wirst (denn dazu muß sich der Polygonzug mitdestens an einer Stelle schneiden oder berühren). So gehst Du jetzt von Punkt zu Punkt und prüfst jedes mal auf Schnittpunkte mit allen bereits bekannten Linien. Solltest Du einen Schnittpunkt finden, dann würde ich an dieser Stelle einen Hilfspunkt berechnen und einfügen, sowie beide betroffenen Linien an diesem Punkt teilen. In Deinem Beispiel geschieht das beim Step P7 --> P8.

Jetzt kommt das nächste Problem. Du mußt herausfinden ob die Fäche Links- oder Rechtsherum umschlossen wurde. Dann markierst Du alle Linien auf der entsprechenden Seite mit "innen". (Dein Beispiel: Hilfsp.-3-5-6-7-Hilfsp. "rechts = innen". Nun Fläche berechnen und merken (Mit dem Gauss?).

Nun machst Du weiter mit der Linie Hilfspunkt - P8....

Ab jetzt ist es aber interessant ob du die Linie von der Seite mit einer Außen- oder Innenmarkierung triffst. Immer wenn Du "von außen kommst" hast Du neues Gebiet umschlossen. Dann folgt wieder die obige Prozedur und eine Aufsummierung der Fläche.

Programmtechnisch kann man das sicher in Form von Listen speichern.

Wie gesagt, das ist nur eine grobe Idee...

 

[Geofix]

Zwei Verbesserungen sind mir noch eingefallen, nachdem ich gestern den Computer ausgeschaltet hatte:

1. Wenn Du eine Linie von "außen nach innen" überquerst, kannst Du alle folgenden Segmente bis zum nächsten "innen nach außen"-Übergang einfach übergehen.
2. Nach der Berechnung der Teilfläche kannst Du alle Linien die nun "links und rechts = innen" sind aus der Liste löschen.

Begründung: Eine Linie die im bereits "erschlossenen" Gebiet liegt, kann niemals Grenze zu "neu eroberten" Bereichen sein.
Falls Du den Ansatz für praktikabel hältst, können wir uns Gedanken zur Lösung der Teilprobleme machen.