2008-11-26 9 views
11

Angesichts einer geordneten Menge von 2D-Pixelpositionen (benachbart oder nebendiagonal), die einen vollständigen Pfad ohne Wiederholungen bilden, wie ermittele ich die größte lineare Bemaßung des Polygons, dessen Umfang dieser Satz ist von Pixeln? (wo der GLD der größte lineare Abstand eines Paares von Punkten in dem Satz ist)Größte lineare Bemaßung 2d Punktmenge

Für meine Zwecke ist die offensichtliche O (n^2) -Lösung wahrscheinlich nicht schnell genug für Zahlen von Tausenden von Punkten. Gibt es gute Heuristiken oder Nachschlagmethoden, die die Zeitkomplexität näher zu O (n) oder O (log (n)) bringen?

Antwort

18

Ein einfacher Weg ist, zuerst die konvexe Hülle der Punkte zu finden, was in vielerlei Hinsicht in O (n log n) -Zeit geschehen kann. [Ich mag Graham scan (siehe animation), aber der incremental Algorithmus ist auch sehr beliebt, wie others sind, obwohl einige more time nehmen.]

Dann können Sie das am weitesten Paar finden (der Durchmesser) durch mit zwei Punkten beginnen (zB x und y) auf der konvexen Hülle, bewegt sich im Uhrzeigersinn, bis es am weitesten von x entfernt ist, dann bewegt sich x, bewegt sich wieder, usw. Sie können beweisen, dass diese ganze Sache nur O (n) Zeit (amortisiert) dauert. Also ist es O (n log n) + O (n) = O (n log n) in allen und möglicherweise O (nh), wenn Sie stattdessen Geschenkverpackung als Ihren konvexen Hüllenalgorithmus verwenden. Diese Idee heißt rotating calipers, wie Sie bereits erwähnt haben.

Hier ist code by David Eppstein (Computational Geometrie Forscher; siehe auch seine Python Algorithms and Data Structures für zukünftige Referenz).

All dies ist nicht sehr schwer zu programmieren (sollte höchstens hundert Zeilen sein; ist weniger als 50 im obigen Python-Code), aber bevor Sie das tun - sollten Sie zuerst überlegen, ob Sie es wirklich brauchen. Wenn Sie, wie Sie sagen, nur "Tausende von Punkten" haben, wird der triviale O (n^2) -Algorithmus (der alle Paare vergleicht) in weniger als einer Sekunde in einer vernünftigen Programmiersprache ausgeführt. Selbst mit einer Million Punkten sollte es nicht länger als eine Stunde dauern. :-)

Sie sollten den einfachsten Algorithmus auswählen, der funktioniert.

0

Sie vielleicht einen Kreis ziehen könnte, das größer war als das Polygon und verkleinere es langsam, indem du nachprüfst, ob du noch Punkte durchkreuzt hast. Dann ist Ihr Durchmesser die Nummer, nach der Sie suchen. Nicht sicher, ob dies eine gute Methode ist, es klingt irgendwo zwischen O (n) und O (n^2)

+0

Wo platzieren Sie das Zentrum? Wahrscheinlich in der Nähe des Schwerpunkts, aber ich wette, ich könnte Situationen finden, in denen die Mitte dieses Kreises einen wichtigen Einfluss darauf hatte, ob Sie die richtige GLD finden oder nicht. –

+2

Dies ist konzeptuell fehlerhaft - der Umkreis-Durchmesser eines gleichseitigen Dreiecks ist sqrt (3) mal die GLD, die gleich der Seitenlänge ist, – Jimmy

0

Meine off-the-man-Lösung ist eine binäre Partitionierung Ansatz versuchen, wo Sie eine Linie soomwhere zeichnen in der Mitte und überprüfe die Abstände aller Punkte von der Mitte dieser Linie. Das würde Ihnen 2 vermutlich sehr Far Punkte geben. Dann überprüfen Sie den Abstand dieser beiden und wiederholen Sie die obige Abstandsprüfung. Wiederholen Sie diesen Vorgang für eine Weile.

Mein Darm sagt, das ist eine n Log n Heuristik, die Sie ziemlich nah bekommen wird.

2

Ich portierte den Python-Code nach C#. Es scheint zu funktionieren.

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