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

Question

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

这里我只取最便宜的。（i+=6 因为我将 POSITION 和 COLOR 保存到数组中）但是我怎样才能得到 2. closest？

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;
    }
}

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

Find the 2 nearest points from a array

java

nearest-neighbor