计算笛卡尔（二维）坐标系的数值索引

Question

给定笛卡尔（二维）坐标系，如下所示：

是否有可能——如果有，如何——为每个字段计算一个唯一的、可排序的索引？这意味着，使用 x 和 y 坐标，我想计算一个从左到右、自上而下升序的索引号。例如：

（仅）必须满足以下条件：

索引号必须是唯一的（即使对于较大的系统）
数字必须从左到右和从上到下递增（但不一定连续）
必须是完整的正整数值
必须在 Java

我还发现了什么：加法、乘法和幂（例如 x*y 或 x^y）不起作用，因为不同的字段获得相同的索引。

方法体可能如下所示：

public Integer getIndex(Integer xCoordinate, Integer yCoordinate) {
  // ...
}

顺便说一句：坐标总是正数 (0 <= x < n)

感谢任何建议。

解决方案：

我在没有计算索引的情况下解决了这个问题，并使用了 Teepeemm 提出的简单比较（见评论）

Answer 1

根据您的示例，显而易见的答案是使用：

index = (#cols * row + col)

但这取决于提前知道列数，并且列数足够小，不会溢出。

另一种方法是沿对角线索引：

index = ((row + col) * (row + col + 1))/2 + row

因此您的索引看起来像：

  0   2   5   9
  1   4   8  13
  3   7  12  18
  6  11  17  24

顺便说一句，因为你在做算术，你最好使用原始 int 而不是盒装 Integer 以避免创建不必要的 Integer 对象（有效 Java 第二版项目 5).

Answer 2

实际上包含了您需要的一切。根据您的评论，您不知道列数。在这种情况下，你必须假设最坏的情况：如果你不知道是否有少于 64k 列和少于 64k 行，那么你甚至不知道是否有足够的 int 来表示完全不同的指数。

因此，一种解决方案（即 "as generic as possible"，给定这些未知数）是将 y 值不乘以列数，而是乘以 的最大数量可以合理计算索引的列。如果您知道行的最大数量，那么您可以在此处选择一个合适的数字，但如果您不知道，则必须乘以 65536 - 这可以作为左-移位 16 位。（如有必要，请考虑此处的符号位）。

结果可能是

Shuffled: [(1,0), (2,1), (2,2), (0,2), (2,0), (1,1), (1,2), (0,0), (0,1)]
Sorted  : [(0,0), (1,0), (2,0), (0,1), (1,1), (2,1), (0,2), (1,2), (2,2)]
Indices:
      0       1       2 
  65536   65537   65538 
 131072  131073  131074

这是一个示例实现：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class AscendingIndices
{
    public static void main(String[] args)
    {
        List<Coordinate> coordinates = new ArrayList<Coordinate>();
        for (int x=0; x<3; x++)
        {
            for (int y=0; y<3; y++)
            {
                coordinates.add(new Coordinate(x,y));
            }
        }
        Collections.shuffle(coordinates);
        System.out.println("Shuffled: "+coordinates);        
        Collections.sort(coordinates);
        System.out.println("Sorted  : "+coordinates);

        System.out.println("Indices:");
        for (int y=0; y<3; y++)
        {
            for (int x=0; x<3; x++)
            {
                Coordinate c = new Coordinate(x,y);
                System.out.printf("%7d ", c.getIndex());
            }
            System.out.printf("\n");
        }

   }
}

class Coordinate implements Comparable<Coordinate>
{
    private final int x;
    private final int y;

    Coordinate(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    int getIndex()
    {
        return x + (y << 16);
    }


    @Override
    public String toString()
    {
        return "("+x+","+y+")";
    }

    @Override
    public int compareTo(Coordinate o)
    {
        return Integer.compare(getIndex(), o.getIndex());
    }

}

计算笛卡尔（二维）坐标系的数值索引

Calculation of a numeric index for a Cartesian (two-dimensional) coordinate system

java

math

coordinates

coordinate-systems

解决方案：