Da du ja maximal 5 verschiedene Ausgangspunkte hast, ist die Zahl der Flächen begrenzt, die sich erzeugen lassen. Es lassen sich maximal 3 Flächen konstruieren. Es gibt maximal 2 Schnittpunkte - daher muss jedes Dreieck mindestens eine Ecke haben, die ein Ausgangspunkt ist. Das ist ein Vorteil: Wenn du für jeden Ausgangspunkt die angrenzende Fläche gefunden hast, dann hast du zwingend alle Teilflächen gefunden. Außerdem kann jeder Ausgangspunkt nur eine einzige angrenzende Fläche haben.
Dein Algorithmus sieht dann folgendermaßen aus:
- Zu jedem Ausgangspunkt die 2 direkt mit ihm verbundenen Ausgangspunkte herausfinden und so abspeichern, dass der Algorithmus schnell diese 2 Punkte/Strecken zu jedem Punkt herausfinden kann.
- Berechnung aller Schnittpunkte durch simples Durchiterieren aller Möglichkeiten. Diese Punkte werden dann so abgespeichert, dass der Algorithmus schnell zu jeder Strecke die Anzahl und die auf ihr befindlichen Schnittpunkte herausbekommen kann.
- Zu jedem Ausgangspunkt die beiden nächsten mit ihm verbundenen Punkte herausfinden:
- Eine Strecke hat keinen Schnittpunkt - der Endpunkt ist der gesuchte Punkt.
- Eine Strecke hat 1 Schnittpunkt - der Schnittpunkt ist der gesuchte Punkt.
- Eine Strecke hat 2 Schnittpunkte - der am nächsten liegende Punkt ist der gesuchte Punkt - mit Pythagoras oder beim Schneiden gespeicherten Werten Werten herausfinden.
- Die beiden nächsten Punkte zu einem Ausgangspunkt spannen das Dreieck auf.
Ich hoffe, ich hab keinen Fehler gemacht und das funktioniert so wie ich es mir denke.
Optimierungen sind natürlich möglich, aber ich hab sie erstmal der Verständlichkeit wegen weggelassen.
Was passiert, wenn zwei Punkte aufeinander liegen oder ein Punkt direkt auf einer Strecke, weiß ich nicht - können sich die anderen ja gerne überlegen.
Vielleicht ist dem Algorithmus ja sowas auch egal...