What is correct implementation in order to query farthest(not closest) point?

[timetravelCat]

I'm trying to use k-d tree in order to query fastest point,

What i tried was

1. Implement custom metric, returning negative distance.

struct InverseDistanceMetric
{
    using ElementType = int;
    using DistanceType = double;
    using IndexType = unsigned int;

    const PointCloudAdapator& pointCloud;

    InverseDistanceMetric(const PointCloudAdapator& _pointCloud) : pointCloud(_pointCloud) {}

    DistanceType evalMetric(const ElementType* a, const IndexType b_idx, size_t size, DistanceType worst_dist = -1.0) const
    {
        DistanceType result = DistanceType();
        const ElementType* last      = a + size;
        const ElementType* lastgroup = last - 3;
        size_t d = 0;

        /* Process 4 items with each loop for efficiency. */
        while (a < lastgroup)
        {
            const ElementType diff0 = a[0] - pointCloud.kdtree_get_pt(b_idx, d++);
            const ElementType diff1 = a[1] - pointCloud.kdtree_get_pt(b_idx, d++);
            const ElementType diff2 = a[2] - pointCloud.kdtree_get_pt(b_idx, d++);
            const ElementType diff3 = a[3] - pointCloud.kdtree_get_pt(b_idx, d++);

            result -= static_cast<DistanceType>(diff0 * diff0);
            result -= static_cast<DistanceType>(diff1 * diff1);
            result -= static_cast<DistanceType>(diff2 * diff2);
            result -= static_cast<DistanceType>(diff3 * diff3);

            a += 4;
            if ((worst_dist > 0) && (result > worst_dist)) {
                return result;
            }
        }

        /* Process last 0-3 components.  Not needed for standard vector lengths. */
        while (a < last)
        {
            const ElementType diff = *a++ - pointCloud.kdtree_get_pt(b_idx, d++);
            result -= static_cast<DistanceType>(diff * diff);
        }

        return result;
    }

    DistanceType accum_dist(const ElementType& a, const ElementType& b, const size_t) const
    {
        return -static_cast<DistanceType>((a - b)*(a - b));
    }
};

And i created 3x3x3 3D points, ([0,0,0]~[2,2,2])
query 4 points from (0, 0, 0) results what i expected, (2, 2, 2), (1, 2, 2), (2, 2, 1), (2, 1,2). with distances -12, -9, -9, -9

However, query 4 points from (2, 2, 2) results not (0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1) but (1 ,0 ,0), (0 ,0 ,2), (2 ,0 ,0), (1 ,1 ,0) with distances -9, -8, -8, 6.

Then i tried
2) enforce positive (Just for temporary testing, Numerically unstable maybe.)

struct InverseDistanceMetric
{
    using ElementType = int;
    using DistanceType = double;
    using IndexType = unsigned int;

    const PointCloudAdapator& pointCloud;

    InverseDistanceMetric(const PointCloudAdapator& _pointCloud) : pointCloud(_pointCloud) {}

    DistanceType evalMetric(const ElementType* a, const IndexType b_idx, size_t size, DistanceType worst_dist = -1.0) const
    {
        DistanceType result = DistanceType();
        const ElementType* last      = a + size;
        const ElementType* lastgroup = last - 3;
        size_t d = 0;

        /* Process 4 items with each loop for efficiency. */
        while (a < lastgroup)
        {
            const ElementType diff0 = a[0] - pointCloud.kdtree_get_pt(b_idx, d++);
            const ElementType diff1 = a[1] - pointCloud.kdtree_get_pt(b_idx, d++);
            const ElementType diff2 = a[2] - pointCloud.kdtree_get_pt(b_idx, d++);
            const ElementType diff3 = a[3] - pointCloud.kdtree_get_pt(b_idx, d++);

            result -= static_cast<DistanceType>(diff0 * diff0);
            result -= static_cast<DistanceType>(diff1 * diff1);
            result -= static_cast<DistanceType>(diff2 * diff2);
            result -= static_cast<DistanceType>(diff3 * diff3);
            result += 4000.0;


            a += 4;
            if ((worst_dist > 0) && (result > worst_dist)) {
                return result;
            }
        }

        /* Process last 0-3 components.  Not needed for standard vector lengths. */
        while (a < last)
        {
            const ElementType diff = *a++ - pointCloud.kdtree_get_pt(b_idx, d++);
            
            result -= static_cast<DistanceType>(diff * diff);
            result += 1000.0;
        }

        return result;
    }

    DistanceType accum_dist(const ElementType& a, const ElementType& b, const size_t) const
    {
        return -static_cast<DistanceType>((a - b)*(a - b)) + 1000.0;
    }
};

I add 1000.0 per each distance calculation in order to enforce positive.
In this case, it worked, but its hard to set the magic number 1000.0

3. I tried inverse distance (1.0/(dist*dist))

struct InverseDistanceMetric
{
    using ElementType = int;
    using DistanceType = double;
    using IndexType = unsigned int;

    const PointCloudAdapator& pointCloud;

    InverseDistanceMetric(const PointCloudAdapator& _pointCloud) : pointCloud(_pointCloud) {}

    DistanceType evalMetric(const ElementType* a, const IndexType b_idx, size_t size, DistanceType worst_dist = -1.0) const
    {
        DistanceType result = DistanceType();
        const ElementType* last      = a + size;
        const ElementType* lastgroup = last - 3;
        size_t d = 0;

        /* Process 4 items with each loop for efficiency. */
        while (a < lastgroup)
        {
            const ElementType diff0 = a[0] - pointCloud.kdtree_get_pt(b_idx, d++);
            const ElementType diff1 = a[1] - pointCloud.kdtree_get_pt(b_idx, d++);
            const ElementType diff2 = a[2] - pointCloud.kdtree_get_pt(b_idx, d++);
            const ElementType diff3 = a[3] - pointCloud.kdtree_get_pt(b_idx, d++);

            result += diff0 ? 1.0/static_cast<DistanceType>(diff0 * diff0) : INFINITY;
            result += diff1 ? 1.0/static_cast<DistanceType>(diff1 * diff1) : INFINITY;
            result += diff2 ? 1.0/static_cast<DistanceType>(diff2 * diff2) : INFINITY;
            result += diff3 ? 1.0/static_cast<DistanceType>(diff3 * diff3) : INFINITY;

            a += 4;
            if ((worst_dist > 0) && (result > worst_dist)) {
                return result;
            }
        }

        /* Process last 0-3 components.  Not needed for standard vector lengths. */
        while (a < last)
        {
            const ElementType diff = *a++ - pointCloud.kdtree_get_pt(b_idx, d++);
            
            result += diff ? 1.0/static_cast<DistanceType>(diff * diff) : INFINITY;
        }

        return result;
    }

    DistanceType accum_dist(const ElementType& a, const ElementType& b, const size_t) const
    {
        return (a-b) ? 1.0/static_cast<DistanceType>((a - b)*(a - b)) : INFINITY;
    }
};

However in this case, fail to query if one of dimension is same.

Is distance must be positive? or Is it a bug and could be fixed?