Servus,
ich habe da nun was rekursiv geloest - klappt auch gut, wenn man 'normale' Mengen an Eingabepunkten in die Methode jagt - ab rund 300 gehts dann aber los - Stack Overflow.
Ich habe etwas nachgelesen und die Lösungsidee die ich hatte, ist dass ich das Konstrukt in eine while-Schleife packe, dann sollte das Problem mit dem Stack gelöst sein.
Bevor ich mir nun da den Kopf zerbreche, kann mir ja einer kurz Rueckmeldung geben, ob er das ähnlich sieht oder ob er eine andere Lösung kennt und nutzen würde.
Hier mal die Methode (meiste sind Kommentare, keine Scheu mal runter zu scrollen):
ich habe da nun was rekursiv geloest - klappt auch gut, wenn man 'normale' Mengen an Eingabepunkten in die Methode jagt - ab rund 300 gehts dann aber los - Stack Overflow.
Ich habe etwas nachgelesen und die Lösungsidee die ich hatte, ist dass ich das Konstrukt in eine while-Schleife packe, dann sollte das Problem mit dem Stack gelöst sein.
Bevor ich mir nun da den Kopf zerbreche, kann mir ja einer kurz Rueckmeldung geben, ob er das ähnlich sieht oder ob er eine andere Lösung kennt und nutzen würde.
Hier mal die Methode (meiste sind Kommentare, keine Scheu mal runter zu scrollen):
Java:
/**
* Methode nimmt den groessten Umkreis aus dem TreeSet und vergleicht dann
* die Umkreise nach Skyum. Am Ende steht der kleinste Kreis fest.
*
* @return
*/
private int findeUmkreis()
{
//System.out.println("KleinsterKreis - findeUmkreis() - Start eines Laufs ...");
// Debugging des TreeSets
int i = 0;
for ( Umkreis u : umkreisBaum)
{
System.out.println("Umkreis Nummer " + i + " mit a: " + u.a.toString() + " | b: " + u.b.toString() + " | c: " + u.c.toString() +" | wvw: " + u.winkelVergleichsWert + " ; mp: " + u.berechneUndGibUmkreisMittelpunkt().toString() + "; radius: " + u.berechneUndGibRadius());
i++;
}
// greift das groesste Element und vergleicht dass es auch ein potentieller Kandidat ist
Umkreis uTop = nimmGroesstenKreis(); // also groesster Kreis aus drei Punkten und somit ein Kandidat ob er alle fasst
System.out.println();
System.out.println("... uTop genommen, hier bei " +
"a: " + uTop.a.xWert + "; " + uTop.a.yWert + " | " +
"b: " + uTop.b.xWert + "; " + uTop.b.yWert + " | " +
"c: " + uTop.c.xWert + "; " + uTop.c.yWert + " | " +
"uTop-winkelVergleichsWert: " + uTop.winkelVergleichsWert );
System.out.println();
// Winkel von U anschauen
// wenn Winkel kleiner 90 Grad ist - da ist der Umkreis
// TODO getter schreiben
if ( uTop.winkelVergleichsWert > 0 ) // gleichbedeutend mit 'tatsaechlicher Winkel kleiner 90 Grad
{
// KUK gefunden
// berechne notwendige Kennzahlen und lass zu Ende laufen
radius = uTop.radius;
mittelpunkt = uTop.berechneUndGibUmkreisMittelpunkt();
//System.out.println();
//System.out.println("KleinsterKreis - findeUmkreis() - KUK gefunden, winkelVergleichsWert uTop (a: " + uTop.a.xWert + "; " + uTop.a.yWert + "| b: " + uTop.b.xWert + "; " + uTop.b.yWert + "| c: " + uTop.c.xWert + "; " + uTop.c.yWert + ") ist " + uTop.winkelVergleichsWert + "; r: " + radius + "; mp: " + mittelpunkt.xWert + "; " + mittelpunkt.yWert );
}
else
{
// Debugging
//System.out.println();
//System.out.println("KleinsterKreis - findeUmkreis() - noch kein KUK, finde neuen Kreiskandidaten ...");
// Stelle Eckdaten des Punktearrays fest
int n = punkteBehaelter.size();
int posB = punkteBehaelter.indexOf(uTop.b);
// Debugging
//System.out.println("--> Eckdaten Punktebehaelter hat die Groesse " + n);
//System.out.println("--> Stellplatz von Referenzpunkt (" + uTop.b.toString() + ") ist " + posB );
// nimm zwei neue Kreise in das Set auf
// TODO Eigenheiten Modulo-Operator siehe JavaInsel8 S. 119
// Modulo gibt den Rest an, also bei n = 4 und posB = 8 ist posB % n = 0, da 8 / 4 = 2 Rest 0;
// Modulo bei n = 4 und posB bei 3 gibt 3/4 = 0 R 3, also 3;
// Modulo bei n = 4 und posB bei -3 gibt;
// Modulo bei n = 4 und posB bei 1 gibt 1/4 = 0 R 1, also 1;
// Modulo ist immer negativ, wenn der Dividend (also der Wert vor dem Operator das Vorzeichens des Restes festlegt)
// Modulo bei n = 4 und posB bei -1, das kommt wenn posB an Stelle 1 steht, aber ich zwei zurueck soll:
// -1 / 4 = 0 R -1 ( jetzt sucht Java die Stelle -1 im Behaelter und wird beim alten Punkt fuendig, das ist falsch)
// Zugriffsindex standardmaessig bestuecken
int pMinusZweiStellplatz = ( posB - 2 ) % n;
int pMinusEinsStellplatz = ( posB - 1 ) % n;
int pPlusEinsStellplatz = ( posB + 1 ) % n;
int pPlusZweiStellplatz = ( posB + 2 ) % n;
// Ausnahmen abgreifen
// Fall (test4.test) [geloest]:
// ArrayOutOfBounds, wenn posB kleiner als 2 ist bzw. wird, was soll also passieren,
// wenn ich bei Index -1 auf das vorletzte zugreifen soll
// n = 4, p ist auf 1, p-2 ist also -1, ist also ArrayOutOfBounds
// Loesung waere Stelle 3, also n - Rest
if (pMinusZweiStellplatz < 0 )
{
int pMinusZweiStellplatzAlt = pMinusZweiStellplatz; // Stellplatz ist etwa -1
pMinusZweiStellplatz = n + pMinusZweiStellplatzAlt; // Stellplatz wird dann 4 + (-1), also 3
}
// Fall (random10.points), siehe Fall (test4.test)
if (pMinusEinsStellplatz < 0 )
{
int pMinusEinsStellplatzAlt = pMinusEinsStellplatz; // Stellplatz ist etwa -1
pMinusEinsStellplatz = n + pMinusEinsStellplatzAlt; // Stellplatz wird dann 4 + (-1), also 3
}
// Fall ( random5.test):
// gibt nur noch 3 Kreise im Set
if ( umkreisBaum.size() < 4 )
{
//System.out.println("KleinsterKreis - findeUmkreis() - nur noch 3 Kreise im Set im Behaelter ...");
// nimm uTop und schau dir den Winkel an
if ( uTop.winkelVergleichsWert > 0)
{
// Umkreis ist uTop im Dreierpaket
radius = uTop.radius;
mittelpunkt = uTop.berechneUndGibUmkreisMittelpunkt();
//System.out.println();
//System.out.println("KleinsterKreis - findeUmkreis() - KUK gefunden (Spezialfall 'nur noch drei Kreise im Set - Dreierpack'; winkelVergleichsWert uTop (a: " + uTop.a.xWert + "; " + uTop.a.yWert + "| b: " + uTop.b.xWert + "; " + uTop.b.yWert + "| c: " + uTop.c.xWert + "; " + uTop.c.yWert + ") ist " + uTop.winkelVergleichsWert + "; r: " + radius + "; mp: " + mittelpunkt.xWert + "; " + mittelpunkt.yWert );
return 2;
}
else
{
// Umkreis ist uTop ohne Referenzpunkt
// Mittelpunkt der Strecke berechnen das ist der Umkreismittelpunkt
mittelpunkt = uTop.berechneUndGibUmkreisMittelpunktEinerStrecke();
// Radius einer Strecke
radius = uTop.berechneUndGibRadiusEinerStrecke();
//System.out.println("KleinsterKreis - findeUmkreis() - KUK gefunden (Spezialfall 'nur noch drei Kreise im Set - Zweierpack'; winkelVergleichsWert uTop (a: " + uTop.a.xWert + "; " + uTop.a.yWert + "| b: -entfernt- | c: " + uTop.c.xWert + "; " + uTop.c.yWert + ") ist " + uTop.winkelVergleichsWert + "; r: " + radius + "; mp: " + mittelpunkt.xWert + "; " + mittelpunkt.yWert );
return 2;
}
}
// Standardfall mehr als 3 Kreise im Set
// Es sind mehr als 3 Kreise im TreeSet, dann kann man da auch immer drei loeschen und zwei reinlegen
if ( umkreisBaum.size() > 3 )
{
// Packe Kreis rein ( P-2, P-1, P+1);
Umkreis neuEins = new Umkreis( punkteBehaelter.get( pMinusZweiStellplatz ), punkteBehaelter.get( pMinusEinsStellplatz ), punkteBehaelter.get( pPlusEinsStellplatz ) );
umkreisBaum.add( neuEins );
//System.out.println("----> Vorhaben: baue Kreis aus ( ( posB - 2 ) % n )[" + (pMinusZweiStellplatz) + "], ( ( posB - 1 ) % n )[" + (pMinusEinsStellplatz) + "] und ( ( posB + 1 ) % n )[" + (pPlusEinsStellplatz) + "]; neuer Kreis gebaut mit " + neuEins.toString() );
// Packe Kreis rein( P-1, P+1, P+2);
Umkreis neuZwei = new Umkreis( punkteBehaelter.get( pMinusEinsStellplatz), punkteBehaelter.get( pPlusEinsStellplatz ), punkteBehaelter.get( pPlusZweiStellplatz ) );
umkreisBaum.add( neuZwei );
//System.out.println("----> Vorhaben: baue Kreis aus ( ( posB - 1 ) % n )[" + ( pMinusEinsStellplatz ) + "], ( ( posB + 1 ) % n )[" + ( pPlusEinsStellplatz ) + "] und ( ( posB + 2 ) % n )[" + (pPlusZweiStellplatz) + "]; neuer Kreis gebaut mit " + neuZwei.toString() );
//System.out.println("--> Packe die beiden Umkreise ins Set: U1 ( " + neuEins.toString() + ") und U2 ( " + neuZwei.toString() + ");");
// loeschen von 3 Punktkreisen macht auch nur Sinn wenn man mehr als zwei Punkte im Behaelter hat
// Debugging des TreeSets
//int i2 = 0;
//for ( Umkreis u : umkreisBaum)
//{
// System.out.println("Umkreis Nummer " + i2 + " mit a: " + u.a.toString() + " | b: " + u.b.toString() + " | c: " + u.c.toString() +" | wvw: " + u.winkelVergleichsWert + " ; mp: " + u.berechneUndGibUmkreisMittelpunkt().toString() + "; radius: " + u.berechneUndGibRadius());
// i2++;
//}
// Debugging des Punktebehaelters
//System.out.println("Punktebehaelter vor Loeschaktion ...");
//int i4 = 0;
//for ( Punkt p : punkteBehaelter)
//{
// System.out.println("Punkt auf Stellplatz " + i4 + ": " + p.toString());
// i4++;
//}
//System.out.println();
// Schwierigkeit
// + beim Loeschen muss man die Kreise erwischen, diese liegen im Set aber nicht in einer bestimmten Reihenfolge
// + der Punktebehaelter ist noch aktuell daher kann man ueber diesen gehen und mittels Index arbeiten
// + Sets koennen die gleichen Kreise nur einmal anlegen, daher muesste ein remove auf den gleich angelegten Kreis klappen
// Loesche die drei beteiligten Kreise aus dem Set
// Kreis P-1, P, P+1
Umkreis loeschKreisEins = new Umkreis(punkteBehaelter.get( pMinusEinsStellplatz ), punkteBehaelter.get( (posB ) % n ), punkteBehaelter.get( pPlusEinsStellplatz ) );
umkreisBaum.remove(loeschKreisEins);
// Kreis P-2, P-1, P
Umkreis loeschKreisZwei = new Umkreis(punkteBehaelter.get( pMinusZweiStellplatz ), punkteBehaelter.get( pMinusEinsStellplatz ), punkteBehaelter.get( ( posB ) % n));
umkreisBaum.remove(loeschKreisZwei);
// Kreis P, P+1, P+2
Umkreis loeschKreisDrei = new Umkreis(punkteBehaelter.get( Math.abs( (posB) % n ) ), punkteBehaelter.get( pPlusEinsStellplatz ), punkteBehaelter.get( pPlusZweiStellplatz ) );
umkreisBaum.remove(loeschKreisDrei);
//System.out.println("--> Loesche Kreis Eins, Zwei, Drei und Referenzpunkt: RefPunkt ( " + (punkteBehaelter.get( (posB ) % n).toString() ) + " ), U1 ( " + loeschKreisEins.toString() + "), U2 ( " + loeschKreisZwei.toString() + ") und U3 ( " + loeschKreisDrei.toString() + " );");
// Debugging des TreeSets
//int i3 = 0;
//for ( Umkreis u : umkreisBaum)
//{
// System.out.println("Umkreis Nummer " + i3 + " mit a: " + u.a.toString() + " | b: " + u.b.toString() + " | c: " + u.c.toString() +" | wvw: " + u.winkelVergleichsWert + " ; mp: " + u.berechneUndGibUmkreisMittelpunkt().toString() + "; radius: " + u.berechneUndGibRadius());
// i3++;
//}
// Loesche den Punkt P aus dem Behaelter
punkteBehaelter.remove(posB);
// Debugging Punktebehaelter
//System.out.println("Punktebehaelter nach Loeschung ...");
//int i5 = 0;
//for ( Punkt p : punkteBehaelter )
//{
// System.out.println("Punkt Stellplatz " + i5 + ": " + p.toString());
// i5++;
//}
//System.out.println();
}
// versuche naechsten Kandidaten durch Selbstaufruf
findeUmkreis();
}
// Verlauf-Meldung
//System.out.println("ACHTUNG: KleinsterKreis - findeUmkreis() - Verlaufen!");
return 1;
}