Hallo Com. ,
Ich hab ein dringendes Problem. Ich muss eine Laboraufgabe fertigstellen, welche mir den Schnittpunkt von N Kanten über einen Scannlinealgorithmus ermittelt.
Der Scannline ansatz als solches ist kein Problem, allerdings das Testen ob ein Schnittpunkt vorliegt und das berechnen macht mir Sorgen.
Ich finde den Fehler nicht, wenn ihr also mal einen Blick auf meinen Ansatz werfen könntet?
Um das Programm zu verstehen, hier die Datentypen Punkt und Kante, welche die Strecke in der 2D-Ebene Repräsentieren:
Wie sieht ein Punkt aus ?
Wie sieht eine Kante aus ?
Hier der Test ob ein Schnittpunkt vorliegt:
Hier nun der Ansatz zum Berechnen des Schnittpunktes:
Der Scannline Algorithmus, Aufruf wird Durchgereicht:
Ich hab ein dringendes Problem. Ich muss eine Laboraufgabe fertigstellen, welche mir den Schnittpunkt von N Kanten über einen Scannlinealgorithmus ermittelt.
Der Scannline ansatz als solches ist kein Problem, allerdings das Testen ob ein Schnittpunkt vorliegt und das berechnen macht mir Sorgen.
Ich finde den Fehler nicht, wenn ihr also mal einen Blick auf meinen Ansatz werfen könntet?
Um das Programm zu verstehen, hier die Datentypen Punkt und Kante, welche die Strecke in der 2D-Ebene Repräsentieren:
Wie sieht ein Punkt aus ?
Java:
public class Punkt {
//Ein Punkt mit X- und Y-Ordinate
private Kante kante;
private int x;
private int y;
public Punkt(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return this.x;
}
public int getY() {
return this.y;
}
public void setKante(Kante kante) {
this.kante = kante;
}
public Kante getKante() {
return this.kante;
}
}Wie sieht eine Kante aus ?
Java:
//Kante mit sortierten Punkten nach X-Wert
public class Kante {
private Punkt rechterPunkt;
private Punkt linkerPunkt;
private int name;
public Kante(Punkt eins, Punkt zwei, int name) {
this.name = name;
if (eins.getX() < zwei.getX()) {
this.linkerPunkt = eins;
this.rechterPunkt = zwei;
} else {
this.rechterPunkt = eins;
this.linkerPunkt = zwei;
}
}
public Punkt getLinks() {
return this.linkerPunkt;
}
public Punkt getRechts() {
return this.rechterPunkt;
}
public int gename() {
return name;
}
}Hier der Test ob ein Schnittpunkt vorliegt:
Java:
public boolean schnittpunktTest(Kante p, Kante q) {
boolean schnitt = false;
int o1 = ccw(p.getLinks(), p.getRechts(), q.getLinks());
int o2 = ccw(p.getLinks(), p.getRechts(), q.getRechts());
int o3 = ccw(q.getLinks(), q.getRechts(), p.getLinks());
int o4 = ccw(q.getLinks(), q.getRechts(), p.getRechts());
if (((o1 * o2) <= 0) && ((o3 * o4) <= 0)) {
schnitt = true;
}
return schnitt;
}
public int ccw(Punkt a, Punkt b, Punkt c) {
int u1 = b.getX() - a.getX();
int u2 = b.getY() - a.getY();
int v1 = c.getX() - a.getX();
int v2 = c.getY() - a.getY();
int det = (u1 * v2) - (u2 * v1);
if (det > 0) {
return 1;
} else if (det < 0) {
return -1;
} else if ((u1 * v1 < 0) || (u2 * v2 < 0)) {
return -1;
} else if ((u1 * u1 + u2 * u2) >= (v1 * v1 + v2 * v2)) {
return 0;
}
return 1;
}Hier nun der Ansatz zum Berechnen des Schnittpunktes:
Java:
public Punkt schnittpunktTest2(Kante a, Kante b) {
Punkt schnitt = null;
int x1 = a.getLinks().getX();
int x2 = a.getRechts().getX();
int x3 = b.getLinks().getX();
int x4 = b.getRechts().getX();
int y1 = a.getLinks().getY();
int y2 = a.getRechts().getY();
int y3 = b.getLinks().getY();
int y4 = b.getRechts().getY();
//Die Determinante berechnen und schauen ob sie Ungleich 0 ist
// Ist die Determinante der Kanten 0 , so liegt ein Sonderfall vor
double determinante = (((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1)));
if (determinante == 0) {
System.err.println("Determinante = 0 ! Parallelen, Kollinär oder übelappend! ");
return null;
}
//Hier geht es nach folgendem Mathematischen Ansatz weiter:
//Pa = P1 + alpha * ( P2 - P1 )
//Pb = P3 + betah * ( P4 - P3 )
//Ein Schnittpunkt liegt vor, wenn Pa == Pb
// Daraus folgt:
//x1 + alpha (x2 - x1) = x3 + betha (x4 - x3)
//y1 + alpha (y2 - y1) = y3 + betha (y4 - y3)
//wenn wir umstellen erhalten wir :
double alpha = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3))/determinante;
double betah =(((x2 - x1) * (y1 - y3)) - ((y2 - y1) * (x1 - x3)))/determinante;
//damit können wir einsetzen und erhalten die Punkte:
int xa = (int) (x1 + (alpha * (x2 - x1)));
int ya = (int) (y1 + (alpha * (y2 - y1)));
int xb = (int) (x3 + (betah * (x4 - x3)));
int yb = (int) (y3 + (betah * (y4 - y3)));
schnitt = new Punkt(xa, yb);
return schnitt;
}Der Scannline Algorithmus, Aufruf wird Durchgereicht:
Java:
.....
private void scann() {
Iterator<Punkt> it = sortX.iterator();
while (it.hasNext() && kanten.size() > 1) {
Punkt akt = it.next();
if (akt == akt.getKante().getLinks()) {
int index = kanten.indexOf(akt.getKante());
Kante a = kanten.get(index);
Kante b = null;
Kante c = null;
if (index + 1 < kanten.size()) {
b = kanten.get(index + 1);
}
if(index-1>=0){
c=kanten.get(index - 1);
}
if (b != null&&schnitt.schnittpunktTest(a, b) ) {
System.out.println("ich mache was");
Punkt temp = schnitt.schnittpunktTest2(a, b);
if(temp!=null)
schnittpunkte.add(temp);
}
if (c!=null&&schnitt.schnittpunktTest(a, c)) {
System.out.println("ich mache was");
Punkt temp = schnitt.schnittpunktTest2(a, c);
if(temp!=null)
schnittpunkte.add(temp);
}
} else if (akt == akt.getKante().getRechts()) {
int index = kanten.indexOf(akt.getKante());
Kante a = kanten.get(index);
Kante b = null;
Kante c = null;
if (index + 1 < kanten.size()) {
b = kanten.get(index + 1);
}
if(index-1>=0){
c=kanten.get(index - 1);
}
if (b != null&&schnitt.schnittpunktTest(a, b) ) {
System.out.println("ich mache was");
Punkt temp = schnitt.schnittpunktTest2(a, b);
if(temp!=null)
schnittpunkte.add(temp);
}
if (c!=null&&schnitt.schnittpunktTest(a, c)) {
System.out.println("ich mache was");
Punkt temp = schnitt.schnittpunktTest2(a, b);
if(temp != null)
schnittpunkte.add(temp);
}
kanten.remove(akt.getKante());
} else {
System.err.print("SCANNLINE ALGORITHMUS <WEDER LINKES NOCH RECHTES OBJEKT!!!>");
}
}
}
......
