Zwei Polygone verbinden die sich überlappen ist einfach (union).
Aber was, wenn sich die Polygone nur berühren oder einen sehr kleinen Abstand von einander haben?
Im Internet findet man kaum etwas. Hier findet man einen Ansatz über die Konvexe Hülle. Ich hab ihn mir noch nicht genauer angesehen.
Mein Ansatz basiert darauf, die Polygone so zu verbinden, wie man das als Mensch auch machen würde. Also an den Stellen, wo sie sich zu nahe kommen, werden sie verbunden. Und die restlichen, dann überflüssigen, Teile vom Polygon gelöscht.
Um zu verdeutlichen was genau gemeint ist und wie die Ergebnisse aussehen, hier ein kleines Video.
Die jetzige Version funktioniert recht stabil. Es gibt noch zwei Sonderfälle die zu behandeln sind. Von der Komplexität her hat der Algorithmus eine quadratische Laufzeit und kann Theoretisch auf linear-logarithmisch gesenkt werden.
Aber erstmal werde ich überprüfen, ob der Algorithmus auch auf realen Daten zufriedenstellende Ergebnisse liefert.