соединить точку с каждыми двумя ближайшими точками между разными точками

Question

Привет, я пишу приложение с Java.В моем приложении мне нужен метод для соединения каждой точки с ее двумя ближайшими точками между многими различными точками (нарисуйте линию от точки к двум ее ближайшим точкам).Сначала я создал этот метод, чтобы соединить каждую точку с ближайшей точкой:

  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

Это на самом деле не проверка расстояния между точками.Рассчитайте расстояние между точками, используя теорему Пифагора, а затем выберите самый низкий и второй самый низкий результат.Возведите в квадрат расстояние между значениями X, добавьте квадрат расстояния между значениями Y и затем возьмите квадратный корень.

Answer 2

Я думаю, у вас есть несколько проблем. Похоже, у вас есть такой класс:

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

РЕДАКТИРОВАТЬ: Ваша первоначальная проблема, вероятно, заключается в том, что вы индексируете «i» в своем цикле, исследуя значение j. Кроме того, здесь есть перезапись с простым (и работоспособным) переписыванием вашего кода.

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 3

Проблема 1: Вы не вычисляете расстояние, вы вычисляете расстояние в X + расстояние в Y.

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

Хорошая новость заключается в том, что для сравнения вы можете удалить квадратный корень.Вы НЕ МОЖЕТЕ отбросить часть "квадратный х" и "квадратный у".Очень важно.

Проблема 2: Вы дважды находите ближайшую точку, а не две ближайшие.Вот алгоритм quick-n-dirty, который сработает, хотя он, безусловно, оставляет место для улучшений:

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.

Обратите внимание, что это приведет к небольшому пересчету, а значит, и к улучшению.

Также обратите внимание, что это НЕ создаст путь через все ваши точки.