[Talk-de] Fläche in Polygone aufteilen

[Markus]

Liebe Geometer,

ich suche Stichworte zur Recherche,
sowie Formeln, Konstruktionsregeln, Tools, Datenmodelle
wie man eine Fläche in Polygone aufteilt.

Beispielsweise Land bei einer Erbteilung oder einem Computerspiel.

Gegeben ist eine durch ein Polygon begrenzte Fläche
oder alternativ die Erde als Ellipsoid.

Bedingungen:
- ein Polygon entspricht einem Land
- Knoten werden als WGS-84 Koordinate angegeben
- Kanten teilen zwei Flächen zweier Besitzer
- Kanten dürfen sich nicht kreuzen
- jede Kante gehört zu zwei Polygonen
- jeder Knoten gehört zu zwei oder mehreren Polygonen
- Knoten können ein Dreiländereck
  oder ein Mehrländereck bezeichnen

- Einfügen
-- auf Kanten zwischen zwei Länderecken
   können beliebig viele Knoten eingefügt werden
   dadurch werden Kanten in Teilkanten aufgeteilt
   und können durch Verschieben der neuen Knoten abgewinkelt werden

- Löschen
-- Kanten dürfen gelöscht werden
-- Punkte, die keine Länderecken sind, dürfen gelöscht werden
   die zwei beteiligten Kanten werden zu einer Kante verschmolzen

- Flächen aufteilten:
-- an zwei Knoten, die nicht zur gleichen Kante gehören,
   eine zusätzliche Kante einfügen
-- an zwei Kanten je ein Knoten einfügen
   und die zwei neuen Knoten mit einer Kante verbinden
   (dadurch entstehen zwei neue Dreiländerecken)
-- an einer Kante ein Knoten einfügen
   und dieser zu einem nicht zu dieser Kante gehörenden Knoten
   mit einer zusätzlichen Kante verbinden

- Flächen zusammenfügen:
-- eine gemeinsame Kante zwischen zwei Länderecken löschen

Ergebnis:
Eine Datenbank, in der die Polygone, ihr Besitzer,
und natürlich die Knoten und Kanten aller Polygone,
gegliedert nach Polygon enthalten sind.

Mit herzlichem Gruss
Markus