Hallo,
ich möchte den Lee-Algorithmus implementieren, komme im Moment aber nicht weiter. Also der Lee-Alg. findet einen Weg, in dem er vom Startpunkt beginnend alle Nachbarn einer Kachel durchnummeriert (Expansion), am Ziel angekommen werden die Werte absteigend gespeichert(Rückverfolgung).
Die Expansion klappt, jetzt weiß ich bei der Rückverfolgung nicht, wie 1.Richtungsänderungen bestimme, also wenn die Linie nach links wechselt, und 2. wie ich genau an diesem Punkt die Koordinaten zurückbekomme. Vielleicht hat ja jemand schon mal den Lee-Algorithmus implementiert??
Das Problem ist die Methode backtracking().
ich möchte den Lee-Algorithmus implementieren, komme im Moment aber nicht weiter. Also der Lee-Alg. findet einen Weg, in dem er vom Startpunkt beginnend alle Nachbarn einer Kachel durchnummeriert (Expansion), am Ziel angekommen werden die Werte absteigend gespeichert(Rückverfolgung).
Die Expansion klappt, jetzt weiß ich bei der Rückverfolgung nicht, wie 1.Richtungsänderungen bestimme, also wenn die Linie nach links wechselt, und 2. wie ich genau an diesem Punkt die Koordinaten zurückbekomme. Vielleicht hat ja jemand schon mal den Lee-Algorithmus implementiert??
Das Problem ist die Methode backtracking().
Java:
import java.util.ArrayList;
public class Grid {
private short[][] grid;
private int moveX;
private int moveY;
Rectangle originalRectangle;
public short distance = 0;
public Grid(Rectangle r) {
grid = new short[r.getHeight()][r.getWide()];
moveX = r.getMinX();
moveY = r.getMinY();
originalRectangle = r;
}
// überprüfe ob im Raster
public boolean imOriginalRaster(Point p) {
if (p.x > originalRectangle.up.p2.x && p.y < originalRectangle.up.p2.y
&& p.x < originalRectangle.bottom.p2.x
&& p.y > originalRectangle.bottom.p2.y)
return true;
return false;
}
public boolean inMovedGrid(Point p) {
if (p.x >= 0 && p.y < grid.length && p.x < grid[0].length && p.y >= 0)
return true;
return false;
}
// bekommt innenliegendes Rechteck mit Originalkoordinaten
// verschiebt es und setzt Pixel auf -1
public void insertRectangle(Rectangle r) {
// überprüfe on sich im RasterRechteck andere Rechtecke befinden
if (r.left.p1.x > originalRectangle.up.p2.x
&& r.left.p1.y < originalRectangle.up.p2.y
&& r.right.p1.x < originalRectangle.bottom.p2.x
&& r.right.p1.y > originalRectangle.bottom.p2.y) {
// System.out.println(r + "diese sind im RasterRechteck");
// int aktuellerRasterWert = raster[1927][2127];
// System.out.println(aktuellerRasterWert + "aktuellerRasterWert ");
// Verschiebung des Rechtecks;
r.left.p1.x = r.left.p1.x - moveX;
r.left.p1.y = r.left.p1.y - moveY;
r.right.p1.x = r.right.p1.x - moveX;
r.right.p1.y = r.right.p1.y - moveY;
Point rp1 = new Point(r.left.p1.x, r.left.p1.y);
Point rp2 = new Point(r.right.p1.x, r.right.p1.y);
int point = 0;
String originalLine = null;
Bbox pb1 = new Bbox(rp1, rp2, point, originalLine);
r = pb1.getRectangle();
// //Pixel setzen
for (int i = r.getMinY(); i < r.getMinY() + r.getHeight(); i++) {
for (int j = r.getMinX(); j < r.getMinX() + r.getWide(); j++) {
grid[i][j] = -1;
// System.out.println(raster[i][j] + "raster");
}
}
}
}
public Point moveStartPoint(Polyline pl) {
return new Point(pl.getStartPoint().x - moveX, pl.getStartPoint().y
- moveY);
}
public Point moveEndPoint(Polyline pl) {
// System.out.println(pl.getEndPunkt().x-verschiebeX+"....");
return new Point(pl.getEndPoint().x - moveX, pl.getEndPoint().y - moveY);
}
// Methode die zur Berechnung des neuen Weges aufgerufen wird
public Polyline findNewPolyline(Polyline pl) {
// Aufpassen beim Ermitteln von Start und Endpunkte diese verschieben!!
// TODO noch nicht definiert!
return null;
}
public void markingAllNeighbours(Point start, Point end) {
// startpunkt ist -2 endpunkt -3
// TODO wieder ändern wenn richtige Punkte übergeben werden
Point moveStartPoint = new Point(start.x - moveX, start.y - moveY);
Point moveEndPoint = new Point(end.x - moveX, end.y - moveY);
grid[moveStartPoint.y][moveStartPoint.x] = -2;
grid[moveEndPoint.y][moveEndPoint.x] = -3;
// vom startpunkt aus alle direkten Nachbarn markieren wenn sie noch
// nicht markiert sind
// für alle neu markierten Nachbarn wieder die direkten Nachbarn
// markiern
// solange bis der Endpunkt erreicht ist
ArrayList<Point> pointsToBeDone = new ArrayList<Point>();
ArrayList<Point> tmp = new ArrayList<Point>();
pointsToBeDone.add(moveStartPoint);
// ...............................................................................................
while (!pointsToBeDone.isEmpty()) {
// System.out.println(entfernung +" " +
// nochAbZuArbeitendePunkte.size());
distance++;
tmp = new ArrayList<Point>();
for (Point p : pointsToBeDone) {
if (!p.equals(start)) {
grid[p.y][p.x] = distance;
}
}
for (Point p : pointsToBeDone) {
tmp.addAll(markingNeighbour(p));
}
pointsToBeDone = new ArrayList<Point>();
for (Point n : tmp) {
if (!pointsToBeDone.contains(n)) {
pointsToBeDone.add(n);
}
}
// TODO abbrechen wenn Endpunkt erreicht
if (pointsToBeDone.contains(moveEndPoint)) {
pointsToBeDone.clear();
}
}
}
private ArrayList<Point> markingNeighbour(Point p) {
ArrayList<Point> neighbour = new ArrayList<Point>();
int neighbourLeft = -1;
int neighbourRight = -1;
int neighbourUp = -1;
int neighbourBottom = -1;
if (inMovedGrid(getLeft(p))) {
neighbourLeft = grid[getLeft(p).y][getLeft(p).x];
}
if (inMovedGrid(getRight(p))) {
neighbourRight = grid[getRight(p).y][getRight(p).x];
}
if (inMovedGrid(getBottom(p))) {
neighbourUp = grid[getBottom(p).y][getBottom(p).x];
}
if (inMovedGrid(getUp(p))) {
neighbourBottom = grid[getUp(p).y][getUp(p).x];
}
// gibt alle noch nicht markierten Nachbarn zurück (im Raster!)
// aufpassen das nur Punkte innerhalb des Rasters zurückgeliefert werden
if (0 == neighbourLeft) {
neighbour.add(getLeft(p));
}
if (0 == neighbourRight) {
neighbour.add(getRight(p));
}
if (0 == neighbourUp) {
neighbour.add(getBottom(p));
}
if (0 == neighbourBottom) {
neighbour.add(getUp(p));
}
return neighbour;
}
public Point getLeft(Point p) {
return new Point(p.x - 1, p.y);
}
public Point getRight(Point p) {
return new Point(p.x + 1, p.y);
}
public Point getBottom(Point p) {
return new Point(p.x, p.y - 1);
}
public Point getUp(Point p) {
return new Point(p.x, p.y + 1);
}
public String toString() {
// String ret = "Raster " + raster.length + " " + raster[0].length;
String ret = null;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
ret += "|" + grid[i][j];
}
// ret +="\n";
}
return ret;
}
public void backtracking(Point end, Point start) {
ArrayList<Short> stp = new ArrayList<Short>();
int i = 0;
int j = 0;
while (i < start.y - moveY && j < start.x - moveX) {
if (grid[i][j] > grid[i + 1][j + 1]) {
stp.add(grid[i][j]);
}
i++;
j++;
}System.out.println(stp);
ArrayList<Point> newPolyline = new ArrayList<Point>();
}
}
