Greatest linear dimension 2d set of points

Question

Given an ordered set of 2D pixel locations (adjacent or adjacent-diagonal) that form a complete path with no repeats, how do I determine the Greatest Linear Dimension of the polygon whose perimeter is that set of pixels? (where the GLD is the greatest linear distance of any pair of points in the set)

For my purposes, the obvious O(n^2) solution is probably not fast enough for figures of thousands of points. Are there good heuristics or lookup methods that bring the time complexity nearer to O(n) or O(log(n))?

Answer 1

My off-the-cuff solution is to try a binary partitioning approach, where you draw a line somwwhere in the middle and check distances of all points from the middle of that line. That would provide you with 2 Presumably Very Far points. Then check the distance of those two and repeat the above distance check. Repeat this process for a while.

My gut says this is an n log n heuristic that will get you Pretty Close.

Answer 2

On this page:

• http://en.wikipedia.org/wiki/Rotating_calipers
• http://cgm.cs.mcgill.ca/~orm/diam.html

it shows that you can determine the maximum diameter of a convex polygon in O(n). I just need to turn my point set into a convex polygon first (probably using Graham scan).

• http://en.wikipedia.org/wiki/Convex_hull_algorithms

Here is some C# code I came across for computing the convex hull:

• http://www.itu.dk/~sestoft/gcsharp/index.html#hull

Answer 3

An easy way is to first find the convex hull of the points, which can be done in O(n log n) time in many ways. [I like Graham scan (see animation), but the incremental algorithm is also popular, as are others, although some take more time.]

Then you can find the farthest pair (the diameter) by starting with any two points (say x and y) on the convex hull, moving y clockwise until it is furthest from x, then moving x, moving y again, etc. You can prove that this whole thing takes only O(n) time (amortized). So it's O(n log n)+O(n)=O(n log n) in all, and possibly O(nh) if you use gift-wrapping as your convex hull algorithm instead. This idea is called rotating calipers, as you mentioned.

Here is code by David Eppstein (computational geometry researcher; see also his Python Algorithms and Data Structures for future reference).

All this is not very hard to code (should be a hundred lines at most; is less than 50 in the Python code above), but before you do that -- you should first consider whether you really need it. If, as you say, you have only "thousands of points", then the trivial O(n^2) algorithm (that compares all pairs) will be run in less than a second in any reasonable programming language. Even with a million points it shouldn't take more than an hour. :-)

You should pick the simplest algorithm that works.

Answer 4

You could maybe draw a circle that was bigger than the polygon and slowly shrink it, checking if youve intersected any points yet. Then your diameter is the number youre looking for. Not sure if this is a good method, it sounds somewhere between O(n) and O(n^2)

Answer 5

I ported the Python code to C#. It seems to work.

using System;  
using System.Collections.Generic;  
using System.Drawing;  

// Based on code here:  
//   http://code.activestate.com/recipes/117225/  
// Jared Updike ported it to C# 3 December 2008  

public class Convexhull  
{  
    // given a polygon formed by pts, return the subset of those points  
    // that form the convex hull of the polygon  
    // for integer Point structs, not float/PointF  
    public static Point[] ConvexHull(Point[] pts)  
    {  
        PointF[] mpts = FromPoints(pts);  
        PointF[] result = ConvexHull(mpts);  
        int n = result.Length;  
        Point[] ret = new Point[n];  
        for (int i = 0; i < n; i++)  
            ret[i] = new Point((int)result[i].X, (int)result[i].Y);  
        return ret;  
    }  

    // given a polygon formed by pts, return the subset of those points  
    // that form the convex hull of the polygon  
    public static PointF[] ConvexHull(PointF[] pts)  
    {  
        PointF[][] l_u = ConvexHull_LU(pts);  
        PointF[] lower = l_u[0];  
        PointF[] upper = l_u[1];  
        // Join the lower and upper hull  
        int nl = lower.Length;  
        int nu = upper.Length;  
        PointF[] result = new PointF[nl + nu];  
        for (int i = 0; i < nl; i++)  
            result[i] = lower[i];  
        for (int i = 0; i < nu; i++)  
            result[i + nl] = upper[i];  
        return result;  
    }  

    // returns the two points that form the diameter of the polygon formed by points pts  
    // takes and returns integer Point structs, not PointF  
    public static Point[] Diameter(Point[] pts)  
    {  
        PointF[] fpts = FromPoints(pts);  
        PointF[] maxPair = Diameter(fpts);  
        return new Point[] { new Point((int)maxPair[0].X, (int)maxPair[0].Y), new Point((int)maxPair[1].X, (int)maxPair[1].Y) };  
    }  

    // returns the two points that form the diameter of the polygon formed by points pts  
    public static PointF[] Diameter(PointF[] pts)  
    {  
        IEnumerable<Pair> pairs = RotatingCalipers(pts);  
        double max2 = Double.NegativeInfinity;  
        Pair maxPair = null;  
        foreach (Pair pair in pairs)  
        {  
            PointF p = pair.a;  
            PointF q = pair.b;  
            double dx = p.X - q.X;  
            double dy = p.Y - q.Y;  
            double dist2 = dx * dx + dy * dy;  
            if (dist2 > max2)  
            {  
                maxPair = pair;  
                max2 = dist2;  
            }  
        }  

        // return Math.Sqrt(max2);  
        return new PointF[] { maxPair.a, maxPair.b };  
    }  

    private static PointF[] FromPoints(Point[] pts)  
    {  
        int n = pts.Length;  
        PointF[] mpts = new PointF[n];  
        for (int i = 0; i < n; i++)  
            mpts[i] = new PointF(pts[i].X, pts[i].Y);  
        return mpts;  
    }  

    private static double Orientation(PointF p, PointF q, PointF r)  
    {  
        return (q.Y - p.Y) * (r.X - p.X) - (q.X - p.X) * (r.Y - p.Y);  
    }  

    private static void Pop<T>(List<T> l)  
    {  
        int n = l.Count;  
        l.RemoveAt(n - 1);  
    }  

    private static T At<T>(List<T> l, int index)  
    {  
        int n = l.Count;  
        if (index < 0)  
            return l[n + index];  
        return l[index];  
    }  

    private static PointF[][] ConvexHull_LU(PointF[] arr_pts)  
    {  
        List<PointF> u = new List<PointF>();  
        List<PointF> l = new List<PointF>();  
        List<PointF> pts = new List<PointF>(arr_pts.Length);  
        pts.AddRange(arr_pts);  
        pts.Sort(Compare);  
        foreach (PointF p in pts)  
        {  
            while (u.Count > 1 && Orientation(At(u, -2), At(u, -1), p) <= 0) Pop(u);  
            while (l.Count > 1 && Orientation(At(l, -2), At(l, -1), p) >= 0) Pop(l);  
            u.Add(p);  
            l.Add(p);  
        }  
        return new PointF[][] { l.ToArray(), u.ToArray() };  
    }  

    private class Pair  
    {  
        public PointF a, b;  
        public Pair(PointF a, PointF b)  
        {  
            this.a = a;  
            this.b = b;  
        }  
    }  

    private static IEnumerable<Pair> RotatingCalipers(PointF[] pts)  
    {  
        PointF[][] l_u = ConvexHull_LU(pts);  
        PointF[] lower = l_u[0];  
        PointF[] upper = l_u[1];  
        int i = 0;  
        int j = lower.Length - 1;  
        while (i < upper.Length - 1 || j > 0)  
        {  
            yield return new Pair(upper[i], lower[j]);  
            if (i == upper.Length - 1) j--;  
            else if (j == 0) i += 1;  
            else if ((upper[i + 1].Y - upper[i].Y) * (lower[j].X - lower[j - 1].X) >  
                (lower[j].Y - lower[j - 1].Y) * (upper[i + 1].X - upper[i].X))  
                i++;  
            else  
                j--;  
        }  
    }  

    private static int Compare(PointF a, PointF b)  
    {  
        if (a.X < b.X)  
        {  
            return -1;  
        }  
        else if (a.X == b.X)  
        {  
            if (a.Y < b.Y)  
                return -1;  
            else if (a.Y == b.Y)  
                return 0;  
        }  
        return 1;  
    }  
}