java - 从数组中找到最近的 2 个点

Question

我正在尝试从数组中获取距离另一个点最近的 2 个点。

这里我只得到最便宜的。 (i+=6 因为我将 POSITION 和 COLOR 保存到数组中)但是我怎样才能得到 2. 最接近的呢？

nIdx = 0;
float dst1;
float dst2 = sqrt(vert[0] - x) + sqrt(vert[1] - y);
for (int i = 6; i < vert.length; i+=6) {
    dst1 = sqrt(vert[i] - x) + sqrt(vert[i+1] - y);
    if (dst2 > dst1) {
        nIdx = i;
        dst2 = dst1;
    }
}

我尝试这样做:

if (dst2 > dst1) {
    n2Idx = nIdx;
    nIdx = i;
    dst2 = dst1;
}

这在某些情况下确实有效。但是如果nIdx确实切换到拳头索引。 n2Idx 不会更改为 nIdx 的最后一个。

好吧，我想我做错了一些事情:

float dst1 = sqrt(vert[0] - x) + sqrt(vert[1] - y);
float dst2 = sqrt(vert[6] - x) + sqrt(vert[7] - y);
for (int i = 0; i < vert.length; i+=6) {
    float dst = sqrt(vert[i] - x) + sqrt(vert[i+1] - y);
    //noinspection StatementWithEmptyBody
    if (dst >= dst2) {
    } else if (dst <= dst1) {
        dst2 = dst1;
        dst1 = dst;
    } else {
        dst2 = dst;
    }
}

Answer 1

将 dst1 和 dst2 视为有序对，即 dst1 较小，dst2 较大(或两个距离相等)。当您遍历点列表时，计算候选距离 dst，并执行以下操作之一:

• 如果 dst 大于或等于 dst2，则不执行任何操作
• 如果dst小于或等于dst1，则将dst1移动到dst2，并分配 >dst 到 dst1
• 否则，将 dst 分配给 dst2。

循环完成后，dst1 和 dst2 将具有两个最小距离:

index ind1 = 0;
index ind2 = 6;
float dst1 = sqrt(vert[ind1] - x) + sqrt(vert[ind1+1] - y);
float dst2 = sqrt(vert[ind2] - x) + sqrt(vert[ind2+1] - y);
// Make sure dst1 and dst2 are ordered to begin with
if (dst2 < dst1) {
    float td = dst1;
    dst1 = dst2;
    dst2 = td;
    ind1 = 6;
    ind2 = 0;
}
// Start loop at 12, because we have processed the first two indexes
for (int i = 12 ; i < vert.length; i += 6) {
    float dst = sqrt(vert[i] - x) + sqrt(vert[i+1] - y);
    if (dst >= dst2) {
        continue;
    }
    if (dst <= dst1) {
        dst2 = dst1;
        ind2 = ind1;
        dst1 = dst;
        ind1 = i;
    } else {
        dst2 = dst;
        ind2 = i;
    }
}