verbinden Sie einen Punkt mit jedem zwei nächsten Punkt zwischen verschiedenen Punkten

Question

Hallo Ich schreibe eine Anwendung mit Java. In meiner Anwendung brauche ich eine Methode, um jeden Punkt mit seinen zwei nächsten Punkten zwischen vielen verschiedenen Punkten zu verbinden (zeichne eine Linie von einem Punkt zu seinen zwei nächsten Punkten). Zuerst habe ich diese Methode, um jeden Punkt zu seinen engsten Punkt zu verbinden:

public void connectingPoints() 
    { 

     ArrayList<Point> externals = new ArrayList<Point>(); 
     for(int i = 0; i<externals.size(); i++) 
     { 
      Point point = externals.get(i); 
      Point minPoint = externals.get(i+1); 
      int minXDistance = minPoint.x-point.x; 
      int minYDistance = minPoint.y-point.y; 

      for(int j = 1; j<externals.size();i++) 
      { 
       if((externals.get(j+1).x-point.x<minXDistance)&&(externals.get(j+1).y-point.y<minYDistance)) 
       { 
        minPoint = externals.get(j+1); 
       } 
      } 
      getGraphics().drawLine(point.x, point.y, minPoint.x, minPoint.y); 
      repaint(); 
     } 
    } 
} 

aber dieses nicht Methode funktioniert überhaupt nicht. Warum? Wo ist das Problem? Und wie kann ich einen Punkt mit seinem 2 nächsten Punkt verbinden.

Answer 1

Ich denke, Sie haben mehrere Probleme. Es sieht aus wie Sie eine Klasse wie dieses:

public class Point { 
    public double x; 
    public double y; 
} 

Sie sollten wahrscheinlich eine Methode Ihrer Klasse hinzufügen, die wie folgt aussieht:

public double distance(Point p) { 
    return Math.hypot(this.x - p.x, this.y - p.y); 
} 

Und noch eins: Jetzt

public Point getClosestPoint(List<Point> pts) { 
    double minDistSoFar = Double.MAX_VALUE; 
    Point rval = null; 

    for (Point p : pts) { 
     if (p.x == this.x && p.y == this.y) { 
      continue; 
     } 

     double pDist = this.distance(p); 
     if (pDist < minDistSoFar) { 
      minDistSoFar = pDist; 
      rval = p; 
     } 
    } 
} 

Ihr Algorithmus kann dies werden:

public void connectingPoints() 
{ 
    ArrayList<Point> externals = new ArrayList<Point>(); 
    for(Point p : externals) { 
     Point minPoint = p.getClosestPoint(externals); 
     getGraphics().drawLine(point.x, point.y, minPoint.x, minPoint.y); 
     repaint(); 
    } 
} 

EDIT: Ihr ursprüngliches Problem ist wahrscheinlich, dass Sie "i" in Ihrer Schleife indexieren, um den Wert von j zu untersuchen. Auch hier ist ein Neuschreiben mit einem einfachen (und praktikablen) Neuschreiben Ihres Codes.

public void connectingPoints() 
{ 
    ArrayList<Point> externals = new ArrayList<Point>(); 
    for(int i = 0; i<externals.size(); i++) 
    { 
     Point point = externals.get(i); 
     Point minPoint = externals.get((i+1) % externals.size()); 
     int minXDistance = minPoint.x-point.x; 
     int minYDistance = minPoint.y-point.y; 
     double minDist = Math.hypot(minXDistance, minYDistance); 

     for(int j = 0; j < externals.size(); j++) // <- you had i++ here! 
     { 
      if (i == j) { 
       continue; 
      } 

      Point testPt = externals.get(j); 
      double dist = Math.hypot(point.x - testPt.x, point.y - testPt.y); 
      if (dist < minDist) 
      { 
       minDist = dist; 
       minPoint = testPt; 
      } 
     } 
     getGraphics().drawLine(point.x, point.y, minPoint.x, minPoint.y); 
     repaint(); 
    } 
} 

Answer 2

Das ist nicht wirklich die Entfernung zwischen den Punkten zu überprüfen. Berechnen Sie den Abstand zwischen den Punkten mit dem Satz des Pythagoras und wählen Sie dann das niedrigste und das zweitniedrigste Ergebnis. Platzieren Sie den Abstand zwischen X-Werten, fügen Sie das Quadrat der Entfernung zwischen den Y-Werten hinzu, und nehmen Sie dann die Quadratwurzel.

Answer 3

Problem 1: Sie sind nicht Abstand Berechnen Sie Rechen Abstand in X + Abstand in Y.

distance = sqrt(x^2 + y^2) 

Die gute Nachricht ist, dass zu Vergleichszwecken können Sie die Quadratwurzel fallen. Sie können den Bereich "Quadrat x" und "Quadrat y" NICHT löschen. Sehr wichtig.

Problem 2: Sie finden den nächsten Punkt zweimal, nicht die nächsten zwei Punkte. Hier ist eine schnelle-n-dirty-Algorithmus, wird funktionieren, obwohl es sicherlich Raum für Verbesserungen lässt:

For each point 
    calculate and store distances to all the other points 
    // use a sorted map for the above. 
    grab the closest two points and draw your lines. 

Beachten Sie, dass dies ziemlich viel Neuberechnung verursachen, wodurch der Raum für Verbesserungen.

Beachten Sie auch, dass dies nicht einen Pfad durch alle Ihre Punkte erstellen wird.