logo标签列表

如何找到任何给定坐标的正确邻居？

javaalgorithmcoordinates
7
更新：这个问题寻求如何获取给定坐标的一组邻居的指导。
我创建了一个包含坐标的二维数组，
 int[][] coordinates= { { -1, -1 }, { -1, 0 }, { -1, +1 },
            { 0, -1 }, { 0, +1 }, { +1, -1 }, { +1, 0 }, { +1, -1 } };

正如你所看到的，这些是坐标（0,0）的邻居。

现在我正在尝试实现一个方法，它接受两个参数 (int positionX, int positionY)，并使用输入参数值 coordiante(x,y) 作为起始坐标，并查找此坐标的所有邻居。

我的想法是这样的：

    int getNearCoordinates(int positionX, int positionY) {

        for (int[] coordinate: coordinates) {
               //I am not sure what to do after this
        }

    }

我正在尝试使用循环从我创建的二维数组中获取单个坐标，但是我卡在这里了。我如何找到一个合适的方法来适当地找到positionX和positionY的邻居？
什么是邻居？
下图中所有橙色点都是原点(0,0)的邻居。 enter image description here
你想计算两个坐标之间的距离（返回一个 int），还是想获取一个坐标周围的邻居集合（返回八个坐标）？ - slartidan
@slartidan 我想获取邻居集合。 - OPK
这是一个算法问题吗？即如何以最佳时间复杂度或空间复杂度完成此操作？如果是，暂时不要用 Java 来混淆问题。另一方面，如果您已经有了算法并且只需要帮助编写 Java 代码，请发布您想使用的算法。 - Erick G. Hagstrom
我不确定您到底需要什么。您是想生成输入点周围的八个坐标集合吗？还是我们要确定哪些已知坐标是与输入点相邻的？还是其他什么？ - Erick G. Hagstrom
@ErickG.Hagstrom 我想获取任何给定坐标的邻居集。抱歉表述不清，我会更新我的问题。 - OPK
5个回答
6

我建议:

  • 使用专用的类 (Coordinate) 代替 int[]。这会使您的代码更易于扩展 (第三维等) 或更改 (使用 double 替代 int 等)。在示例中，您可以看到一个不可变的类 - 这会阻碍代码产生副作用。
  • 使用 Collection 而不是 Array。这将使处理变得更容易 (您可以简单地添加和删除元素)
  • 使用java8-Streaming-API。它非常快速，并使您的代码更易读。

其他想法:

  • 您甚至可以将getNearCoordinates变成 Coordinate 类的一部分。这将使 new Coordinate(27,35).getNearCoordinates() 可用。
  • 您还可以使用 Map<Axis,Integer> 来存储 x 和 y。这会使您的代码有点难以理解，但会减少重复代码。
  • 您也可以通过使用两个嵌套循环 for (int x = -1; x <= 1; x++) for (int y = -1; y <= 1; y++) use(new Coordinate(x,y)) 生成方向的集合。这将使您的代码更加 简洁，但可能会更难理解。

示例代码:

import java.util.*;
import java.util.stream.Collectors;

public class Snippet {

    // make a class to be more flexible
    class Coordinate {

        // final fields are making this an "imutable"
        final int x;
        final int y;

        /** constructor to take coordinate values */
        Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        /** moves this coordinate by another coordinate */
        Coordinate move(Coordinate vector) {
            return new Coordinate(x + vector.x, y + vector.y);
        }
    }

    /** using Collection instead of Array makes your live easier. Consider renaming this to "directions". */
    Collection<Coordinate> coordinates = Arrays.asList(
            new Coordinate( -1, -1 ), // left top
            new Coordinate( -1,  0 ), // left middle
            new Coordinate( -1, +1 ), // left bottom
            new Coordinate(  0, -1 ), // top
            new Coordinate(  0, +1 ), // bottom
            new Coordinate( +1, -1 ), // right top
            new Coordinate( +1,  0 ), // right middle
            new Coordinate( +1, +1 )  // right bottom
            );

    /** @return a collection of eight nearest coordinates near origin */
    Collection<Coordinate> getNearCoordinates(Coordinate origin) {
        return
                // turn collection into stream
                coordinates.stream()

                // move the origin into every direction
                .map(origin::move)

                // turn stream to collection
                .collect(Collectors.toList());
    }

}

如果没有Java8流API，同样的行为将如下所示:

/** @return a collection of eight nearest coordinates near origin */
Collection<Coordinate> getNearCoordinates(Coordinate origin) {
    Collection<Coordinate> neighbours = new ArrayList<>();

    for (Coordinate direction : coordinates)
        neighbours.add(origin.move(direction));

    return neighbours;
}
我非常喜欢这个答案，但是在这个任务中我只能使用Java 7，不能使用Java 8。 - OPK
@HashMap 我添加了一个“非Java8”实现。 - slartidan
我有一个问题，getNearCoordinates方法返回了一个类型为Coordinate的集合，如果我想获取这些坐标的确切值，该怎么办？例如，对于坐标(1,1)，如何获取所有8个相邻坐标，如下所示：(1,0),(0,0),(2,0),(2,1),(3,1),(2,3),(0,2),(0,1)？ - OPK
4

如果满足以下条件，则两个点A(x1,y1)和B(x2,y2)是相邻的:

 Math.abs(x1-x2) <= 1 && Math.abs(y1-y2) <= 1

如果两个差值都等于零，则A等于B。

2
请记住，任务是评估邻居的集合 - 而不是告诉您某个坐标是否是邻居。 - slartidan
嗨，如果我想排除对角邻居，那么这个条件应该是什么？ - ThanosFisherman
1

使用int[]来表示点并不是最佳实现方式，本答案的目的是展示算法。

如果你在讨论一个无限平面的情况，那么你总会有8个点，所以可以按照以下方式实现：

// first point index, 2nd: 0 = x, 1 = y
public int[][] getNeighbours(int x, int y) {
   int[][] ret = new int[8][2];
   int count = 0;
   for (int i = -1; i <= 1; i++)
      for (int j = -1; j <= 1; j++) {
         if (i == 0 && j == 0)
            continue;
         ret[count][0] = x + i;
         ret[count++][1] = y + j;
      }
   return ret;
}

如果飞机是有界的，那么情况会变得更加有趣，这次使用 ArrayList：

public List<int[]> getNeighbours(int x, int y, int minX, int maxX, int minY, int maxY) {
   List<int[]> ret = new ArrayList<int[]>(8); // default initial capacity is 100
   for (int i = Math.max(x - 1, minX); i <= Math.min(x + 1, maxX); i++)
      for (int j = Math.max(y - 1, minY); j <= Math.min(y + 1, maxY); j++) {
         if (i == x && j == y)
            continue;
         ret.add(new int[] {i, j});
      }
   return ret;
}

后者适用于任何点，即使在平面外部或仅在边界处。
刚刚看到，如果你不喜欢 continue，它可以重写为 if (i != x || j != y) ret.add(...);。 - maraca
0

这似乎很明显，但您可以复制coordinates，并将给定坐标的x和y值添加到每个坐标的值中，例如使用for循环。

0

这取决于你如何定义邻居。下面的代码将测试坐标，并对对角线以及水平和垂直邻居返回true。

if (Math.abs(coordinate[0] - positionX) <= 1 && Math.abs(coordinate[1] - positionY) <= 1)
{
    System.out.println(Arrays.toString(coordinate));
}

请确保导入java.lang.Math 打印坐标仅是示例，但可用于调试。
嗨，如果我想排除对角邻居，应该使用什么条件呢？ - ThanosFisherman
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接