排序坐标问题

Question

我一直对此感到困惑 - 我认为这很简单，但我的几何/代数非常垃圾，而且我不记得学生时代如何做这些事情！

编辑：我有一个有人站在他们旁边的坐标列表 - 我需要一种算法来在列表（数组）中从左上角到右下角对人们进行排序，第二个标准要求更接近左上角原点的坐标优先所有其他人 - 你会怎么做？

代码应将顺序显示为：

1. 汤姆
2. 哈利
3. 鲍勃
4. 戴夫

见下图：

Answer 1

从您的排序来看，您似乎将 y 位置置于比 x 位置更高的优先级，因此在比较两个人时，类似的操作会起作用：

if (a.y > b.y)
// a is before b
else if (a.x < b.x)
// a is before b
else
// b is before a

编辑更新此比较仍然适用于您的新标准。Y 位置仍然优先于 X 位置。如果 Y 值相等，则最靠近左上角的点将是 X 值较小的点。如果你想让你的对象成为一个比较器，将其实现为你的比较器函数将允许你执行 ArrayList.sort() ，其中负数表示第一个人在第二个人之前：

public int compareTo(person a, person b) {
    if (a.y == b.y)
       return a.x-b.x
    else
       return b.y-a.y
}

//compareTo(Tom, Harry) == -50 (tom is before harry)
//compareTo(Tom, Bob) == -25 (tom is before bob)
//compareTo(Dave, Bob) == 30 (dave is after bob)

Answer 2

根据它们距 2D 空间左上角的距离对它们进行排序，在本例中为 (0, 100)。

编辑：

显然，这意味着您会遇到这样的情况：两个人距左上角等距，但他们彼此却相距甚远。

在这种情况下，您需要指定如何对此类人员进行排序。如果你想选择地位更高的人，你可以先按y坐标排序。同样，您可以选择其他一些标准。

所有其他排序算法都会遇到相同的问题，即当两个项目具有相同的排序键时该怎么办。那么根据定义，他们 是 被认为是相同的，直到您提出辅助排序标准。

Answer 3

我会说：

orderValue = x+(100-y)

然后根据距左上角“最接近”的最小 orderValue（根据投影到线 y=100-x 上的距离）进行排序。

Answer 4

如果您知道 X 的最大数量级，请按（对于给定示例）100 * (100 - Y) + X 排序。

Answer 5

比较器看起来像这样：

int d = o2.y - o1.y;
if (d == 0)
    d = o1.x - o2.x;
return d;

这将首先按 Y 排序，然后按 X 排序（对于具有相同 Y 的所有对象）。

[编辑] 修复了 Y 排序顺序。

Answer 6

也许您可以查看半正矢公式，该公式在导航中用于计算两点的接近度。然而，这主要适用于球体上的点。http://en.wikipedia.org/wiki/Haversine_formula