2008-11-26 11 views
11

2 डी पिक्सेल स्थानों (आसन्न या आसन्न-विकर्ण) के एक क्रमबद्ध सेट को देखते हुए जो दोहराए बिना पूरा पथ बनाता है, मैं बहुभुज के सबसे महान रैखिक आयाम को कैसे निर्धारित करूं जिसका परिधि सेट है पिक्सल का? (जहां जीएलडी सेट में किसी भी अंक की सबसे बड़ी रैखिक दूरी है)अंक के सबसे बड़े रैखिक आयाम 2 डी सेट

मेरे उद्देश्यों के लिए, स्पष्ट ओ (एन^2) समाधान शायद हजारों अंकों के आंकड़ों के लिए पर्याप्त तेज़ नहीं है। क्या अच्छे हेरिस्टिक्स या लुकअप विधियां हैं जो ओ (एन) या ओ (लॉग (एन)) के करीब समय जटिलता लाती हैं?

उत्तर

18

पॉइंट्स के उत्तल ढक्कन को खोजने के लिए एक आसान तरीका है, जिसे ओ (एन लॉग एन) समय में कई तरीकों से किया जा सकता है। [मैं Graham scan चाहते (animation देखें), लेकिन incremental एल्गोरिथ्म भी लोकप्रिय है, के रूप में others कर रहे हैं, हालांकि कुछ more time ले।]

तो आप किसी भी दो अंक के साथ शुरू करने से सब से अधिक दूर जोड़ी (व्यास) प्राप्त कर सकते हैं (जैसे कि एक्स और वाई) उत्तल हॉल पर, जब तक यह एक्स से सबसे दूर नहीं है, तब तक घड़ी की दिशा में आगे बढ़ना, फिर x को ले जाना, फिर से चलना, आदि। आप साबित कर सकते हैं कि यह पूरी चीज केवल ओ (एन) समय (अमूर्त) लेती है। तो यह ओ (एन लॉग एन) + ओ (एन) = ओ (एन लॉग एन) सभी में है, और संभवतः ओ (एनएच) यदि आप उपहार के रूप में अपने उत्तल हॉल एल्गोरिदम के रूप में उपहार-रैपिंग का उपयोग करते हैं। जैसा कि आपने उल्लेख किया है, इस विचार को rotating calipers कहा जाता है।

यहां code by David Eppstein (कम्प्यूटेशनल ज्यामिति शोधकर्ता; भविष्य के संदर्भ के लिए भी उनके Python Algorithms and Data Structures देखें)।

यह सब कोड के लिए बहुत मुश्किल नहीं है (सबसे अधिक सौ लाइनें होनी चाहिए; ऊपर पाइथन कोड में 50 से कम है), लेकिन इससे पहले कि आप इसे पहले मान लें कि आपको वास्तव में इसकी आवश्यकता है या नहीं। यदि, जैसा कि आप कहते हैं, आपके पास केवल "हजारों अंक" हैं, तो तुच्छ ओ (एन^2) एल्गोरिदम (जो सभी जोड़ों की तुलना करता है) किसी भी उचित प्रोग्रामिंग भाषा में एक सेकंड से भी कम समय में चलाया जाएगा। यहां तक ​​कि एक लाख अंक के साथ इसे एक घंटे से अधिक समय नहीं लेना चाहिए। :-)

आपको सरलतम एल्गोरिदम चुनना चाहिए जो काम करता है।

2

इस पृष्ठ परः

यह पता चलता है कि आप हे (एन) में एक उत्तल बहुभुज की अधिकतम व्यास निर्धारित कर सकते हैं। मुझे बस अपना पॉइंट सेट पहले उत्तल बहुभुज में बदलना होगा (शायद ग्राहम स्कैन का उपयोग करना)।

0

आप शायद उस मंडली में शामिल से बड़ा था आकर्षित कर सकता है:

यहाँ कुछ सी # कोड मैं उत्तल पतवार की गणना के लिए भर में आया है बहुभुज और धीरे-धीरे इसे कम करें, जांच करें कि आपने अभी तक किसी भी बिंदु को छेड़छाड़ की है या नहीं। फिर आपका व्यास वह नंबर है जिसे आप ढूंढ रहे हैं। अगर यह एक अच्छा तरीका है सुनिश्चित नहीं हैं, यह हे (एन) और O (n^2)

+0

आप केंद्र कहां रखते हैं? शायद सेंट्रॉइड के पास लेकिन मैं शर्त लगाता हूं कि मैं उन परिस्थितियों के साथ आ सकता हूं जहां उस सर्कल का केंद्र उस पर महत्वपूर्ण प्रभाव डालता है कि आपको सही जीएलडी मिलती है या नहीं। –

+2

यह अवधारणात्मक रूप से त्रुटिपूर्ण है - एक समतुल्य त्रिकोण का circumcircle व्यास जीएलडी sqrt (3) बार है, जो पक्ष की लंबाई के बराबर है, – Jimmy

0

मेरे ऑफ-द-कफ समाधान जहाँ आप एक लाइन somwwhere आकर्षित, एक द्विआधारी विभाजन दृष्टिकोण की कोशिश करना है के बीच कहीं न कहीं लगता है बीच में और उस रेखा के बीच से सभी बिंदुओं की दूरी की जांच करें। जो आपको 2 संभवतः बहुत दूर अंक प्रदान करेगा। फिर उन दोनों की दूरी की जांच करें और उपरोक्त दूरी की जांच दोहराएं। थोड़ी देर के लिए इस प्रक्रिया को दोहराएं।

मेरा आंत कहता है कि यह एक एन लॉग एन हेरिस्टिक है जो आपको सुंदर बंद कर देगा।

2

मैंने पायथन कोड को सी # पर पोर्ट किया। ऐसा लगता है कि काम करता है।

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