package test003;
import java.awt.Point;
import java.util.ArrayList;
import java.util.ListIterator;
import javax.swing.JOptionPane;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;
public class JobaQuarterConvexHull
{
Point startPoint;
Point endPoint;
Point currentPoint;
Point currentConvexPoint;
ArrayList<Point> outlinePoints;
ArrayList<Point> convexPoints;
ListIterator<Point> litout;
ListIterator<Point> litcon;
JobaQuarterConvexHull( ArrayList<Point> outlineP, Point start, Point end )
{
outlinePoints = new ArrayList<Point>();
outlinePoints.add( new Point(start) );
outlinePoints.addAll( outlineP );
outlinePoints.add( end );
litout = outlinePoints.listIterator();
convexPoints = new ArrayList<Point>();
startPoint = new Point( (int)start.getX(), (int)start.getY() );
endPoint = new Point( (int)end.getX(), (int)end.getY() );
litcon = convexPoints.listIterator();
computeConvexPoints();
}
private void computeConvexPoints()
{
String dbg = new String();
dbg += "Bin in der Methode computeConvexPoints()....\n";
// ++++ Start Stegreifberechnungen für convexPoints, die zum Ausbruch aus der Methode führen
if ( outlinePoints.size() == 0 )
{
dbg += " Bin im Stegreifzweig für outlinePoints, hier outlinePoints.size() == 0 \n";
litcon.add(startPoint);
litcon.add(endPoint);
return;
}
if ( outlinePoints.size() == 1 )
{
dbg += " Bin im Stegreifzweig für outlinePoints, hier outlinePoints.size() == 1 \n";
litcon.add(startPoint);
currentPoint = litout.next();
boolean erg = isLeftToLine(startPoint, endPoint, currentPoint);
if ( erg == true )
{
litcon.add(currentPoint);
}
litcon.add(endPoint);
return;
}
// ---- Ende Stegreifberechnungen
// ++++ Start Gehe-Vorwärts-Algorithmus
int loopCounter = 0;
while ( litout.hasNext() == true && loopCounter < 100 )
{
loopCounter++;
dbg += "Trete in die Schleife ein, litout hasNext(), loopCounter bei " + loopCounter + " ...\n";
dbg += " +-----------------------------------------+\n";
dbg += " | Collection: outlinePoints .... \n";
dbg += " +-----------------------------------------+\n";
for (Point p : outlinePoints )
{
dbg += " | P ( " + p + ");\n";
}
dbg += " +-----------------------------------------+\n";
dbg += " +-----------------------------------------+\n";
dbg += " | Collection: convexPoints .... \n";
dbg += " +-----------------------------------------+\n";
for (Point p : convexPoints )
{
dbg += " | P ( " + p + ");\n";
}
dbg += " +-----------------------------------------+\n";
// nimm den nächsten Punkt der outlinePoints als aktuellen Punkt
currentPoint = new Point(litout.next()); // Punkt als Kopie damit er Teil der Outline bleibt
dbg += "Nehme als currentPoint litout.next(), hier P ( " + currentPoint + " ); \n";
// erstmal aufnehmen und currentConvexPoint setzen mit einer Kopie
currentConvexPoint = new Point(currentPoint);
litcon.add(currentConvexPoint);
dbg += "Bilde currentConvexPoint als Kopie von currentPoint, hier " + currentPoint + ".\n";
dbg += "Nehme currentConvexPoint mit litcon.add in die convexPoints-Collection auf, hier " + currentConvexPoint + ".\n";
dbg += "( +++ Check aktuelle convexPoints-Liste: ";
for (Point p : convexPoints )
{
dbg += "| P ( " + p + "); ";
}
dbg += " +++)\n";
// +++++++ Start Walk-Back-Mechanismus
// +++++++ Stegreifberechnungen für convexPoints, die zum Abbruch der Aussen-Schleife und damit der Berechnung aller Punkte führen, sollte sich identisch mit return-Aufruf verhalten
// +++++++ Stegreifberechnungen für convexPoints, die zum Abbruch der Aussen-Schleifen-Iteration führen und damit der Berechnung für den currentPoint aus outlinePoints
if ( convexPoints.size() == 0 )
{
dbg += " Bin im Stegreifzweig für convexPoints, convexPoints.size() == 0 \n";
// nimm erstmal den Extrempunkt rein
litcon.add(startPoint);
dbg += " --> litcon.add(startPoint), hier " + startPoint + " und nextRun\n";
continue; // nimm nächsten Punkt
}
if ( convexPoints.size() == 1 )
{
dbg += " Bin im Stegreifzweig für convexPoints, convexPoints.size() == 1 \n";
// da liegt dann nur der Startpunkt drin, da hole mal den nächsten Punkt, bei 2 greift dann ein
// anderer Zweig
dbg += " --> keine Aktion nur nextRun\n";
continue;
}
if ( convexPoints.size() == 2 )
{
dbg += " Bin im Stegreifzweig für convexPoints, convexPoints.size() == 2 \n";
dbg += " --> RLT auf currentConvexPoint zu startPoint-endPoint ...\n";
// prüfe den currentConvexPoint gegen Start und Ende und entscheide ob er drin bleiben darf
// es müssen noch weitere Punkte kommen, da sonst bereits der Stegreifzweig outlinePoints == 1 griefe :-)
Point a = startPoint; // ist auch schon drin
Point b = endPoint;
Point c = currentConvexPoint;
boolean erg = isLeftToLine(a, b, c);
if ( erg == true )
{
dbg += " ----> erg, c liegt links, litcon.add() auf currentConvexPoint, hier " + currentConvexPoint + " und nextRun.\n";
litcon.add(currentConvexPoint);
continue; // nächsten Punkt holen der dann ja gleich ein neuer currentConvexPoint wird
}
else
{
dbg += " ----> erg false, c liegt rechts, keine Aktion nur nextRun.\n";
// Punkt nicht aufnehmen und neuen holen
continue;
}
}
// +++++++ Walkback-Algorithmus, nur wenn Stegreifberchnungen nicht greifen
// Neuaufnahme fordert Walkback, convexPoints.size() ist mindestens 3,
int loopTwoCounter = 0;
while ( litcon.hasPrevious() == true )
{
loopTwoCounter++;
dbg += "\n*** Eintritt in die while-innen-Schleife zum Walkback, loopTwoCounter bei " + loopTwoCounter + " ...\n";
// Stegreifberechnungen um die Aussage für den currentConvexPoint zu treffen
if ( convexPoints.size() == 2 )
{
// hier liegen der Startpunkt und der erste Punkt drin, da kann man dann aus dieser
// Schleife ausbrechen, dann wird diese Sache vom Stegreifzweig der eine Hierachie
// weiter oben liegenden Schleife behandelt
break;
}
// Standardalgorithmus Walkback
// nimm den letzten und vorletzten Punkt von litcon als Kind und Enkel
dbg += "Check currentConvexPoint ist bei " + currentConvexPoint + "\n";
Point currentConvexPointChild;
Point currentConvexPointGrandChild;
currentConvexPointChild = litcon.previous();
dbg += "Nimm litcon.previous() hier " + currentConvexPointChild + " als currentConvexPointChild.\n";
// TODO hier hagelt es einen NullPointer
if ( litcon.hasPrevious() == true )
{
currentConvexPointGrandChild = litcon.previous();
dbg += "Nimm litcon.previous() hier " + currentConvexPointGrandChild + " als currentConvexPointGrandChild.\n";
}
else
{
currentConvexPointGrandChild = new Point(startPoint);
dbg += "Nimm startPoint-Kopie als litcon.previous() hier " + currentConvexPointGrandChild + " als currentConvexPointGrandChild.\n";
}
// Pruefe
Point a = currentConvexPoint;
Point b = currentConvexPointChild;
Point c = currentConvexPointGrandChild;
dbg += " Gehe in den RLT fürs Walkback hier mit c (Grandchild) " + c + "; a (currentConvexPoint) " + a + "; b (Child) " + b + ";\n";
boolean erg = isRightToLine(a, b, c);
if ( erg == true )
{
// das letzte gelieferte des litcon ist das GrandChild, also vorher noch einmal nach vorne um bei previous zu landen
Point pointToDelete = litcon.next();
litcon.remove();
dbg += "--> erg WalkbackRLT c ist rechts von ab, litcon.remove auf pointToDelete hier" + pointToDelete + " und nextRun.\n";
dbg += "(+++ Check convexPoints-Col: ";
for ( Point p : convexPoints)
{
dbg += "| " + p + "; ";
}
dbg += "\n";
continue;
}
else
{
// Punkt liegt innerhalb, dann muss nichts gelöscht werden
// aus dem Walkback kann man weg, man kann sogar aus
dbg += "--> erg WalkbackRLT c ist links von ab, keine Aktion, Schleifenabbruch mit break.\n";
break;
}
} // Ende while innen
dbg += "while-Innen-Schleife ist komplett durch.\n";
}
// while aussen durch
// adde letzten Punkt zu den convexPoints
dbg += "while-Schleifen sind komplett durch.\n";
litcon.add(endPoint);
dbg += "litcon.add() auf den endPoint anwenden, hier " + endPoint + "\n";
dbg += "......... gesamte Methode ist durchgelaufen .... \n";
JTextArea jta = new JTextArea(dbg, 30, 80);
JScrollPane jsp = new JScrollPane(jta);
JOptionPane.showMessageDialog(null, jsp);
}
public ArrayList<Point> getConvexPoints()
{
return convexPoints;
}
private boolean isRightToLine(Point a, Point b, Point c )
{
// Strecke a nach b, Punkt c ist der zu testende Punkt
double d = ( ( c.getX() - a.getX() ) * ( c.getY() + a.getY() ) + ( b.getX() - c.getX() ) * ( b.getY() + c.getY() ) + ( a.getX() - b.getX() ) * ( a.getY() + b.getY() ) );
// Testfall a = 200,200; b = 200, 100; c = 400, 200; also Marschrichtung wie im Quadrant 1, passt
if ( d > 0 )
{
//JOptionPane.showMessageDialog(null, "d ist groesser 0, Punkt liegt rechts der Geraden.");
return true;
}
else if ( d < 0 )
{
//JOptionPane.showMessageDialog(null, "d ist kleiner 0, Punkt liegt links der Geraden.");
return false;
}
else if ( d == 0 )
{
//JOptionPane.showMessageDialog(null, "d ist 0, Punkt liegt auf der Geraden.");
return false;
}
else {}
return false;
}
private boolean isLeftToLine( Point a, Point b, Point c )
{
// Strecke a nach b, Punkt c ist der zu testende Punkt
double d = ( ( c.getX() - a.getX() ) * ( c.getY() + a.getY() ) + ( b.getX() - c.getX() ) * ( b.getY() + c.getY() ) + ( a.getX() - b.getX() ) * ( a.getY() + b.getY() ) );
// Testfall a = 200,200; b = 200, 100; c = 400, 200; also Marschrichtung wie im Quadrant 1, passt
if ( d < 0 )
{
//JOptionPane.showMessageDialog(null, "d ist kleiner 0, Punkt liegt links der Geraden.");
return true;
}
else if ( d > 0 )
{
//JOptionPane.showMessageDialog(null, "d ist groesser 0, Punkt liegt rechts der Geraden.");
return false;
}
else if ( d == 0 )
{
//JOptionPane.showMessageDialog(null, "d ist 0, Punkt liegt auf der Geraden.");
return false;
}
else {}
return false;
}
}