Nahmd,
Nein. Wenn der Algorithmus korrekt ist, wird die Implementierung alle Aufgaben lösen. Da gibt es keine “Schwierigkeit” mehr, sondern nur die Frage nach Rechenzeit und Speicherplatz.
Eine kurze Überlegung zeigt, dass man sich auf die “Anschlusspunkte”, an denen weitere Wege ansetzen, und die konkaven Eckpunkte des Polygons beschränken kann, und nur Kanten zwischen diesen Punkten betrachten muss. Erster Entwurf eines Algorithmus: 1. die konkaven Ecken des Polygons finden (trivial) und zu den Anschlusspunkten werfen. 2. Von jedem Punkt der enthaltenen Menge eine Kante zu allen gradlinig erreichbaren (“sichtbaren”) Punkten erzeugen. 3. Auf diesem Graph von jedem der Anschlusspunkte zu jedem anderen Anschlusspunkt die kürzeste Verbindung suchen (Implementierung per Mini-Router). 4. Aus dem Graph alle Kanten streichen, die von keiner der optimalen Verbindungen benutzt werden. 5. Heuraka.
Das ist auch nicht Aufgabe einer Applikation, sondern wird bei der Vorverarbeitung der Daten erledigt. Als Ergebnis fliegt die Fläche raus und wird durch die erzeugten Kanten ersetzt. Nur für das Routing natürlich und nicht für die Anzeige, bei letzterer bleibt die Fläche. Die Applikation weiß nichts von dieser Konversion.
Zu den weglosen Wegen…
Ich möchte den Auswertern nichts vorschreiben, sondern ihnen so viele Informationen geben, dass sie vernünftige Entscheidungen treffen können. In meinem Fall mit den gangbaren, aber weglosen Flächen kann ich mir durchaus vorstellen, dass sie in einer Spezialkarte, z.B. der Topo von maxbe oder der Garmin-Alpenkarte von unixasket dezent dargestellt werden.
Gruß Wolf