Величайший линейный размер 2d набор точек

Question

Учитывая упорядоченный набор местоположений двумерных пикселей (смежных или смежных по диагонали), которые образуют полный путь без повторов, как определить Величайшее линейное измерение многоугольника, периметр которого составляет этот набор пикселей? (где GLD - наибольшее линейное расстояние любой пары точек в наборе)

Для моих целей очевидное решение O (n ^ 2), вероятно, недостаточно быстрое для цифр в тысячи точек. Существуют ли хорошие эвристические методы или методы поиска, которые приближают сложность времени к O (n) или O (log (n))?

Answer 1

Простой способ - сначала найти выпуклую оболочку точек, что можно сделать за O (n log n) разными способами. [Мне нравится сканирование Грэма (см. анимация ), но алгоритм инкрементный также популярен, как и другие , хотя некоторые принимают больше времени .]

Затем вы можете найти самую дальнюю пару (диаметр), начав с любых двух точек (скажем, x и y) на выпуклой оболочке, двигаясь по часовой стрелке до тех пор, пока она не окажется дальше от x, затем двигаясь по x, снова перемещаясь по y и т. Д. Вы можете доказать, что все это занимает всего O (n) времени (амортизируется). Так что O (n log n) + O (n) = O (n log n) всего и, возможно, O (nh), если вместо этого вы используете упаковку подарков в качестве алгоритма выпуклой оболочки. Эта идея называется вращающимися суппортами , как вы упомянули.

Вот код Дэвида Эппштейна (исследователь вычислительной геометрии; см. Также его Алгоритмы Python и структуры данных для дальнейшего использования).

Все это не очень сложно для кодирования (должно быть не более ста строк; в коде Python выше - менее 50), но прежде чем вы это сделаете, вы должны сначала подумать, действительно ли вам это нужно. Если, как вы говорите, у вас есть только «тысячи точек», тогда тривиальный алгоритм O (n ^ 2) (который сравнивает все пары) будет запущен менее чем за секунду на любом приемлемом языке программирования. Даже с миллионом очков это не должно занять больше часа. : -)

Вы должны выбрать самый простой алгоритм, который работает.

Answer 2

Я портировал код Python на C #. Вроде работает.

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

Answer 3

На этой странице:

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

показывает, что вы можете определить максимальный диаметр выпуклого многоугольника в O (n). Мне просто нужно сначала превратить мою точку в выпуклый многоугольник (вероятно, используя сканирование Грэма).

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

Вот код C #, с которым я столкнулся для вычисления выпуклой оболочки:

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

Answer 4

Мое неординарное решение состоит в том, чтобы попробовать подход двоичного разбиения, где вы рисуете линию где-то посередине и проверяете расстояния всех точек от середины этой линии. Это даст вам 2 предположительно очень далеких очка. Затем проверьте расстояние между этими двумя и повторите вышеуказанную проверку расстояния. Повторите этот процесс некоторое время.

Моя интуиция говорит, что это эвристика, которая поможет вам довольно близко.

Answer 5

Возможно, вы могли бы нарисовать круг, который был бы больше, чем многоугольник, и медленно уменьшить его, проверяя, пересекали ли вы какие-либо точки. Тогда ваш диаметр - это число, которое вы ищете. Не уверен, что это хороший метод, он звучит где-то между O (n) и O (n ^ 2)