Find the most distant pair of 3D points

#1

Can anyone suggest a good algorithm for quickly finding the two most distant points in the 3D point cloud?
The ConvexHull is not a solution in my case. Usually all my source “clouds” are convex.

I will appreciate any code on any language.

To find the closest point is not a problem. Kd-tree works very well.
To find furthest points in 2D is not a problem either. The Quick Hull does do a job.

#2

have you seen this one?
https://sarielhp.org/p/00/diameter/diam_prog.html

The code provided below can do the following things:

  1. Compute the exact diameter of a point-set in 3d. Seems to be linear time for most ``real’’ inputs. Can be quadratic in the worst case.
    …
...
void   test_itself( gdiam_real  * points, int  num )
{
    GPointPair   pair;

    printf( "Computing the diameter for %d points selected "
            "uniformly from the unit cube\n", num );
    pair = gdiam_approx_diam_pair( (gdiam_real *)points, num, 0.0 );
    printf( "Diameter distance: %g\n", pair.distance );
    printf( "Points realizing the diameter\n"
            "\t(%g, %g, %g) - (%g, %g, %g)\n",
            pair.p[ 0 ], pair.p[ 1 ], pair.p[ 2 ],
            pair.q[ 0 ], pair.q[ 1 ], pair.q[ 2 ] );
...
#3

Thank you, Serejan…
Yes. I saw it. And I agree, it looks like the most promising algorithm and solution.

#4

here is an update about this library.
As I was expected it’s very slow for my task (where most of the objects (clouds) are convex).
The library uses QuickHull for acceleration but it doesn’t work for convex models at all.
so the simple GeoSphere (128 segments; ~164K verts) is processed:
– by gdiam (the library):
points:163842 >> time:6453 heap:248L
– by my algorithm:
points:163842 >> time:148 heap:248L

both are of course c++

…

but teapot (64 segments)
– by gdiam;
131330 >> time:5 heap:248L
– by my algorithm:
131330 >> time:40 heap:248L

#5

there several good ideas and pretty good their implementations in the library. So I continue looking into it

#6

my bad! the algorithm has an option of accuracy of “best” result. Higher epsilon gives dramatic acceleration for symmetrical (or topologically repeatable, or tiled) geometries