unsortierte Punkte verbinden

[BobHirte]

Hi leute. Ich hab im viewerPanel verschiedene Punkte eingetragen. Nun möchte ich die Punkte nach der richtigen Reihenfolge verbinden. In der Datenbank aus der ich die Koordinaten für die Punkte beziehe sind die Punkte allerdings nicht sortiert.
Also ich könnt mir das so vorstellen, dass ich mit dem Punkt ganz unten Anfange, und dann die Abstände zu allen anderen Punkten abchecke und zum kürzesten wird die Route gelegt. Von dem Punkt zum nächsten und so weiter bis alle abgearbeitet sind. Das kann ich aber iwie nicht so umsetzen, gibts vielleicht einen einfacheren weg? Danke im voraus

 

[Landei]

Dazu müsste man wissen, welche Arten von "Figuren" zu erwarten sind, allgemein lässt sich das Problem nicht lösen.

 

[BobHirte]

Also das ganze ist Teil einer Routenplanung. Die einzelnen Punkte sind verschiedene Auffahrten und diese sollen zu der jeweiligen Autobahn verbunden werden. In der Datenbank sind halt immer die Autobahn und die x und y Koordinaten der jeweiligen Auffahrt angegeben. Nun müssen diese halt korrekt verbunden werden.

 

[Landei]

Vielleicht den minimalen Spannbaum berechnen (mit den Algorithmen von Prim oder Kruskal)? Wenn das eine Linie liefert, ist das mit ziemlicher Sicherheit das richtige Ergebnis, wenn sich irgendwo Verzweigungen gebildet haben, ist der Wurm drin...

 

[André Uhres]

... dass ich mit dem Punkt ganz unten Anfange, und dann die Abstände zu allen anderen Punkten abchecke und zum kürzesten wird die Route gelegt. Von dem Punkt zum nächsten und so weiter bis alle abgearbeitet sind.

Hier ist eine mögliche Implementierung deines Ansatzes:

import java.awt.*;
import java.util.*;
import java.util.List;
import javax.swing.*;

public class DrawPointsDemo {

    public DrawPointsDemo() {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.setSize(400, 300);
        f.setLocationRelativeTo(null);
        ViewPanel viewPanel = new ViewPanel(createTestPoints());
        f.add(viewPanel);
        f.setVisible(true);
    }

    private List<FPoint> createTestPoints() {
        List<FPoint> points = new ArrayList<FPoint>();
        points.add(new FPoint(10, 10));
        points.add(new FPoint(10, 100));
        points.add(new FPoint(50, 80));
        points.add(new FPoint(100, 200));
        points.add(new FPoint(150, 250));
        points.add(new FPoint(70, 260));
        points.add(new FPoint(175, 175));
        return points;
    }

    public static void main(final String[] args) {

        Runnable gui = new Runnable() {

            @Override
            public void run() {
                DrawPointsDemo newMain = new DrawPointsDemo();
            }
        };
        SwingUtilities.invokeLater(gui);
    }
}

class ViewPanel extends JPanel {

    private List<FPoint> points;

    public ViewPanel(List<FPoint> points) {
        this.points = points;
    }

    @Override
    protected void paintComponent(final Graphics g) {
        super.paintComponent(g);
        resetVisited();
        //draw lines:
        g.setColor(Color.BLUE);
        FPoint p1 = getStartPoint();
        FPoint p2 = getNextPoint(p1);
        while (p2 != null) {
            g.drawLine(p1.x, p1.y, p2.x, p2.y);
            p1 = p2;
            p2 = getNextPoint(p1);
        }
        //draw points:
        g.setColor(Color.RED);
        for (final FPoint point : points) {
            g.fillOval(point.x - 2, point.y - 2, 4, 4);
        }
    }

    private FPoint getStartPoint() {
        int yB = 0;
        FPoint pB = null;
        for (final FPoint point : points) {
            if (!point.isVisited() && point.y > yB) {
                yB = point.y;
                pB = point;
            }
        }
        if (pB != null) {
            pB.setVisited(true);
        }
        return pB;
    }

    private FPoint getNextPoint(final FPoint p1) {
        if(p1 == null){
            throw new IllegalArgumentException("Argument must not be null");
        }
        FPoint pN = null;
        double distanceN = Double.MAX_VALUE;
        for (final FPoint point : points) {
            if (!point.isVisited()) {
                double distance = point.distance(p1);
                if (distance < distanceN) {
                    distanceN = distance;
                    pN = point;
                }
            }
        }
        if (pN != null) {
            pN.setVisited(true);
        }
        return pN;
    }

    private void resetVisited() {
        for (final FPoint point : points) {
            point.setVisited(false);
        }
    }

    public List<FPoint> getPoints() {
        return points;
    }

    public void setPoints(final List<FPoint> points) {
        this.points = points;
        repaint();
    }
}

class FPoint extends Point {

    private boolean visted;

    public FPoint(final int x, final int y) {
        super(x, y);
    }

    public boolean isVisited() {
        return visted;
    }

    public void setVisited(final boolean visited) {
        this.visted = visited;
    }
}

Gruß,
André

 

[Andi_CH]

	points.add(new FPoint(40, 30));
	points.add(new FPoint(10, 30));
	points.add(new FPoint(40, 10));
	points.add(new FPoint(60, 10));

Hm, Schlaufen sind möglich - ist das die Meinung?

 

[André Uhres]

Schlaufen sind möglich - ist das die Meinung?

Das Beispiel zeigt lediglich eine Mögliche Lösung zu dieser Vorgabe:

... dass ich mit dem Punkt ganz unten Anfange, und dann die Abstände zu allen anderen Punkten abchecke und zum kürzesten wird die Route gelegt. Von dem Punkt zum nächsten und so weiter bis alle abgearbeitet sind.

Wahrscheinlich fehlen noch ein paar grundlegende Angaben, um zu einem realistischen Ergebnis zu kommen.

Gruß,
André

 

[Andi_CH]

Ich habe mich gefragt was "ganz unten" ist - Verwendet wird imho der Punkt der zuerst eingetragen wird, aber ich hab den Algorithmus nicht durchschaut (ich hab es auch noch gar nicht ernsthaft versucht)

Für mich stellt sich eher die Frage wie man Kreuzungen detektieren könnte (Wie sind da die Schlagworte: Auf dem Plan stehen oder keinen Schlauch haben )

 

[André Uhres]

Ich habe mich gefragt was "ganz unten" ist - Verwendet wird imho der Punkt der zuerst eingetragen wird, aber ich hab den Algorithmus nicht durchschaut (ich hab es auch noch gar nicht ernsthaft versucht)

in deinem Beispiel sind unten zwei Punkte. Da die provisorische Spezifikation nichts darüber sagt, welcher der beiden Punkte in dem Fall ausgewählt werden soll, ist der Algorithmus zur Auswahl belanglos.

Gruß,
André