最大線性尺寸的2D組點

Question

的是集像素？ （其中GLD是在該組的任何一對點的最大直線距離）

對於我而言，明顯的爲O（n^2）的解決方案是可能不夠快的千點的數字。是否有很好的啓發式或查找方法使時間複雜度更接近O（n）或O（log（n））？

Answer 1

一個簡單的方法是，首先找到了點，這可以在O完成的凸包（N日誌N）在許多方面的時間。 [我喜歡Graham scan（見animation），但incremental算法也很受歡迎，因爲是others，雖然有些採取more time]

然後你可以用任意兩點開始找到最遠對（直徑）（比方說x和y），順時針移動y直到離x最遠，然後移動x，再移動y等等。您可以證明整個事物只需要O（n）個時間（攤銷）。因此，如果使用禮品包裝作爲凸包算法，那麼它總是O（n log n）+ O（n）= O（n log n），可能O（nh）。正如你所提到的，這個想法被稱爲rotating calipers。

這裏是code by David Eppstein（計算幾何研究員;另見他的Python Algorithms and Data Structures供將來參考）。

所有這些都不是很難編碼（最多應該是100行;在上面的Python代碼中應該少於50行），但在你做之前 - 你應該首先考慮你是否真的需要它。如果像你說的那樣，你只有「數千個點」，那麼用任何合理的編程語言都可以在不到一秒的時間內運行微不足道的O（n^2）算法（比較所有的對）。即使有一百萬分，也不應超過一個小時。 :-)

你應該選擇最簡單的算法。

Answer 2

在此頁面：

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

它表明你能夠確定爲O（n）凸多邊形的最大直徑。我只需要將我的點集首先變成凸多邊形（可能使用Graham掃描）。

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

下面是一些C＃代碼，我遇到了用於計算凸包：

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

Answer 3

也許你可以畫一個圓，這是比我的大多邊形並慢慢收縮它，檢查你是否已經與任何點相交。那麼你的直徑就是你正在尋找的數字。 不知道這是否是一種好方法，它聽起來介於O（n）和O（n^2）之間

Answer 4

我的最新解決方案是嘗試一種二進制分區方法，您可以在其中繪製一條線在中間並檢查距該線中間的所有點的距離。 這將爲您提供2推測非常遠的點。然後檢查這兩者的距離並重覆上述距離檢查。重複這個過程一段時間。

我的直覺說，這是一個N爲log N啓發式，將讓你非常接近。

Answer 5

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