如何从哈希图获得第二大距离？

Question

我试图在 Java 中的 Hashmap 中获取最大和第二大距离。

基本上，我计划从填充有 (x,y) 值的哈希图中选择一个点，将其设置为固定点并计算该点相对于所有其他点的距离。计算完所有可能的距离后，我将固定点更改为 HashMap 中的下一个元素。通过这个过程，我的目标是在哈希图中按距离获得最大和第二大值。

 HashMap<Integer, Integer> corners = getPotentialCorners(image);
        HashMap<Integer, Integer> extremeCorners = new HashMap<>();
        int Blue = new Color(0, 0, 255).getRGB();
        int currentNumberX;
        int currentNumberY;
        int pivotVarX;
        int pivotVarY;
        double distance;
        double Highest = 0;
        double Highest2 = 1;
        int xHighest = 0;
        int yHighest = 0;
        int xHighest2 = 0;
        int yHighest2 = 0;
        for (int i : corners.keySet()) {
            currentNumberX = (i);
            currentNumberY = corners.get(currentNumberX);
            for (int j : corners.keySet()) {
                pivotVarX = j;
                pivotVarY = corners.get(pivotVarX);
                distance = Math.abs(Math.sqrt(Math.pow((pivotVarX - currentNumberX), 2) + Math.pow((pivotVarY - currentNumberY), 2)));
                if (pivotVarX != currentNumberX) {
                    if ((Highest > Highest2)) {
                        xHighest = currentNumberX;
                        yHighest = currentNumberY;
                        Highest2 = distance;
                    }
                    if (distance > Highest2) {
                        Highest2 = distance;
                        xHighest2 = currentNumberX;
                        yHighest2 = currentNumberY;
                    }


                }
            }


        }

用这段代码，我调试了一下，总有一个点是正确的，还有一个点是ALWAYS(0,0)。我知道问题出在我获得第二高点（Highest2，XHighest2，YHighest2）的过程中，但我不知道如何解决它。

Answer 1

正如其他人指出的那样，最好使用 List<Point> 而不是 HashMap，您可以轻松地将其迭代为：

for (Point p: myList) {
   ...
}

或者如果您需要更多地控制迭代哪些元素，您可以使用整数计数器：

for (int j = i+1; j < corners.size(); j++) {
   Point p = corners.get(j);
   ...
}

而不是必须使用 keySet() 和 get() 以及在同一 bin 上使用相同 x-values 映射的所有问题。

此外，还有一些微不足道的速度改进：

无需使用缓慢的 Math.sqrt() 函数（或 Math.abs()，因为平方根始终为正），因为您只比较 larger/smaller 距离。您可以只比较平方距离。
最新的 Java 编译器知道如何优化 Math.pow(int, 2)，但为了确保您不会获得函数调用的开销，您可以通过编写以下内容来帮助编译器：(p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.x-q.y)

为简洁起见，将 current 和 pivot 重命名为 p 和 q，您的代码将如下所示：

List<Point> corners = getPotentialCorners(image);
Double highest = null;
Double highest2 = null;
Point highestP = null, highestQ = null;
Point highestP2 = null, highestQ2 = null;
for (int i = 0; i < corners.size()-1; i++) {
    Point p = corners.get(i);
    for (int j = i+1; j < corners.size(); j++) {
        Point q = corners.get(j);
        double distanceSq = (p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y);
        if (highest == null || distanceSq >= highest) {
            // shift highest to second highest
            highest2 = highest;
            highestP2 = highestP;
            highestQ2 = highestQ;

            highest = distanceSq;
            highestP = p;
            highestQ = q;
        } else if (highest2 == null || distanceSq > highest2) {
            highest2 = distanceSq;
            highestP2 = p;
            highestQ2 = q;
        }
    }
}

如何从哈希图获得第二大距离？

How to get second biggest distance from a Hashmap?

java

sorting

algorithm

image

hashmap