@nox:
Ja, diese Überlegung hab ich auch gemacht, dazu kommt noch, dass ich nicht mit Sicherheit garantieren kann, dass alle Polygone konvex sind, was die Berechnung eines Schwerpunkts meinen Recherchen nach ziemlich verkompliziert.
@Black-Panther: Ich weiß jetzt nicht so genau, auf was Du hinaus willst, Hill-Climbing Algorithmus ist m.W. doch eine Methode, um Optimierungsprobleme zu lösen, oder ? Hab da bis jetzt noch nicht soviel Ahnung von, inwiefern das auf geometrische Probleme angwendet werden kann.
Mir ist gestern noch eine Idee gekommen, wie das Problem evt. lösbar ist: Ich baue einen BSP- bzw. KD-Tree auf, indem ich solange den 2D-Raum aufteile (x-, y-, x-, y-Richtungen...), bis in einem Knoten (Quadranten) <= 2 Polygone drin sind - dann weiß ich doch, dass diese beiden Polygone eine gemeinsame Kante haben. Das wäre auch einfach zu implementieren, da ich schonmal einen Quadtree eingebaut hatte...
Bin für alle Kommentare zu o.g. Idee dankbar... (hab jetzt noch nicht angefangen, das zu implementieren/testen)