異なるポイント間の2つの最も近いポイントにポイントを接続します

Question

こんにちは、私はjavaでアプリケーションを書いています。私のアプリケーションでは、ポイントを2つの最も近いポイントに接続する方法が必要です（ポイントから2つの最も近いポイントまで直線を描きます）。最初に、この方法を作成して、各点を最も近い点に接続しました。

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

ただし、この方法はまったく機能しません。どうして？問題はどこだ？そして、どのようにポイントをその2つの最も近いポイントに接続することができますか？

Answer 1

あなたにはいくつかの問題があると思います。

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

あなたはおそらくあなたのクラスにメソッドを追加する必要があり、次のようになります：

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

そしてもう一つ：今

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

あなたは、このようなクラスを持っているように見えますアルゴリズムは次のようになります。

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

編集：あなたの元の問題はおそらく、ループのjの値を調べる "i"のインデックスです。また、ここでは簡単な（そして実行可能な）コードの書き換えによる書き換えがあります。

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

これは実際にポイント間の距離をチェックしていません。ピタゴラスの定理を使って点間の距離を計算し、次に最も低い結果と2番目に低い結果を選択します。 X値の間隔を四角にし、Y値の間の距離の二乗を加え、平方根を取ってください。

Answer 3

問題1：あなたが距離を計算していない、あなたはY.

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

にX +距離の距離を計算している良いニュースは、比較のために、あなたは平方根をドロップすることができるということです。あなたは "正方形のx"と "正方形のy"部分を削除することはできません。非常に重要。

問題2：最も近い2点ではなく、最も近い点を2点見つけようとしています。これは、再計算のかなり、改善のための部屋を引き起こすこと

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. 

注：それは確かに改善の余地を残しているが、ここでうまくいく間に合わせのn-アルゴリズムは、です。

これは、すべてのポイントを通るパスを作成しません。