Kích thước tuyến tính lớn nhất 2d của các điểm

Question

Đặt một tập hợp các vị trí pixel 2D (liền kề hoặc đường chéo liền kề) tạo thành đường dẫn hoàn chỉnh không lặp lại, làm cách nào để xác định Kích thước tuyến tính lớn nhất của đa giác có chu vi pixel? (trong đó GLD là khoảng cách tuyến tính lớn nhất của bất kỳ cặp điểm nào trong tập hợp)

Vì mục đích của tôi, giải pháp O (n^2) rõ ràng có thể không đủ nhanh đối với số nghìn điểm. Có phương pháp chẩn đoán hay tra cứu tốt mang lại độ phức tạp thời gian gần hơn với O (n) hoặc O (log (n)) không?

Answer 1

Một cách dễ dàng là trước tiên hãy tìm thân lồi của các điểm, có thể được thực hiện trong thời gian O (n log n) theo nhiều cách. [Tôi thích Graham scan (xem animation), nhưng các thuật toán incremental cũng rất phổ biến, như là others, mặc dù một số mất more time.]

Sau đó, bạn có thể tìm thấy các cặp xa nhất (đường kính) bằng cách bắt đầu với bất kỳ hai điểm (nói x và y) trên thân lồi, di chuyển y theo chiều kim đồng hồ cho đến khi nó dài nhất từ ​​x, sau đó di chuyển x, di chuyển y lần nữa, vv Bạn có thể chứng minh rằng toàn bộ điều này chỉ mất O (n) thời gian (khấu hao). Vì vậy, nó là O (n log n) + O (n) = O (n log n) trong tất cả, và có thể O (nh) nếu bạn sử dụng gói quà như thuật toán thân lồi của bạn thay thế. Ý tưởng này được gọi là rotating calipers, như bạn đã đề cập.

Đây là code by David Eppstein (nhà nghiên cứu hình học tính toán; xem thêm số Python Algorithms and Data Structures để tham khảo sau này).

Tất cả điều này không khó mã (tối đa là 100 dòng; ít hơn 50 mã Python ở trên), nhưng trước khi bạn làm điều đó - trước hết bạn nên cân nhắc xem bạn có thực sự cần nó hay không. Nếu, như bạn nói, bạn chỉ có "hàng ngàn điểm", sau đó thuật toán O (n^2) tầm thường (so sánh tất cả các cặp) sẽ được chạy trong chưa đầy một giây trong bất kỳ ngôn ngữ lập trình hợp lý nào. Ngay cả với một triệu điểm nó không nên mất hơn một giờ. :-)

Bạn nên chọn thuật toán đơn giản nhất hoạt động.

Answer 2

Trên trang này:

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

nó cho thấy rằng bạn có thể xác định đường kính tối đa của một đa giác lồi trong thời gian O (n). Tôi chỉ cần biến điểm của tôi thành một đa giác lồi đầu tiên (có thể sử dụng Graham scan).

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

Dưới đây là một số mã C# Tôi đã xem qua cho máy tính thân lồi:

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

Answer 3

Bạn có thể có thể vẽ một vòng tròn đó là lớn hơn đa giác và từ từ co lại, kiểm tra xem bạn đã giao cắt với bất kỳ điểm nào chưa. Sau đó, đường kính của bạn là số bạn đang tìm kiếm. Không chắc chắn đây có phải là phương pháp tốt hay không, âm thanh ở đâu đó giữa O (n) và O (n^2)

Answer 4

Giải pháp off-the-cuff của tôi là thử phương pháp phân vùng nhị phân, nơi bạn vẽ một đường ở giữa và kiểm tra khoảng cách của tất cả các điểm từ giữa dòng đó. Điều đó sẽ cung cấp cho bạn 2 điểm Rất có thể là Rất xa. Sau đó kiểm tra khoảng cách của hai và lặp lại kiểm tra khoảng cách trên. Lặp lại quá trình này trong một thời gian.

Đường ruột của tôi cho biết đây là một nhật ký n heuristic sẽ mang lại cho bạn Pretty Close.

Answer 5

Tôi đã chuyển mã Python sang C#. Dường như nó hoạt động.

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