connecter un point à chaque point le plus proche entre les différents points

Question

Salut J'écris une application avec Java. Dans mon application, j'ai besoin d'une méthode pour connecter chaque point à ses deux points les plus proches entre de nombreux points différents (tracer une ligne d'un point à ses deux points les plus proches). Au début, je créé cette méthode de manière à relier chaque point à son point le plus proche:

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(); 
     } 
    } 
} 

mais cette méthode ne fonctionne pas du tout. Pourquoi? où est le problème? Et comment puis-je connecter un point à son point le plus proche.

Answer 1

Je pense que vous avez plusieurs problèmes. Il semble que vous avez une classe comme ceci:

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

Vous devriez probablement ajouter une méthode à votre classe qui ressemble à ceci:

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

Et un autre:

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; 
     } 
    } 
} 

maintenant votre algorithme peut devenir ceci:

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: Votre problème original est probablement que vous indexez "i" dans votre boucle en examinant la valeur de j. En outre, voici une réécriture avec une réécriture simple (et réalisable) de votre code.

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

Cela ne vérifie pas vraiment la distance entre les points. Calculer la distance entre les points en utilisant le théorème de Pythagore et ensuite choisir le plus bas et le deuxième résultat le plus bas. Placez la distance entre les valeurs X, ajoutez le carré de la distance entre les valeurs Y, puis prenez la racine carrée.

Answer 3

Problème 1: Vous n'êtes pas loin de calcul, vous la distance de calcul X + distance en Y.

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

Les bonnes nouvelles sont que des fins de comparaison, vous pouvez déposer la racine carrée. Vous NE POUVEZ PAS supprimer les parties "carré x" et "carré y". Très important. Problème 2: Vous trouvez le point le plus proche deux fois, pas les deux points les plus proches. Voici un algorithme rapide n-sale qui va travailler, mais il laisse certainement place à l'amélioration:

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. 

Notez que cela entraînera un peu de recalcul, donc la place à l'amélioration.

Notez également que cela ne créera PAS de chemin à travers tous vos points.