किसी छवि में आयत के सेट को मर्ज करने का सबसे अच्छा तरीका क्या है?

Question

यह होमवर्क प्रश्न नहीं है :)

मेरे पास एक छवि में बिखरे आयतों का एक सेट है। मैं छेड़छाड़ वाले आयत के प्रत्येक समूह के विलय (संघ बनाना) बनाना चाहता हूं। यदि एक आयत अपने पड़ोसियों को छेड़छाड़ नहीं करता है, तो यह छूटे रहेंगे।

समस्या यह है कि विलय आयताकार आयताकारों को छेड़छाड़ कर सकते हैं जो पहले विचार नहीं किए गए थे; विलय आयताकार नए विलय वाले आयताकारों को भी छेड़छाड़ कर सकते हैं। मैं उन मामलों को पकड़ना चाहता हूं।

तो, मेरे दिमाग में, इसे पुनरावृत्त करने की आवश्यकता है (सेट में हर दूसरे रेक्ट के खिलाफ प्रत्येक आयत की कोशिश करें) और रिकर्सिव (मर्ज किए गए रीक्ट सहित सेट के खिलाफ प्रत्येक मर्ज किए गए रेक्ट को आजमाएं)।

मैं इसके बारे में कैसे जा सकता हूं? मैं जावा में काम कर रहा हूं, लेकिन यह भाषा-उन्मुख एक की तुलना में एक एल्गोरिदमिक प्रश्न है।

धन्यवाद!

संपादित करें: खराब तरीके से बेहतर तरीके से चित्रित करने के लिए प्रासंगिक कोड जोड़ा गया जिसमें मैं इसे अभी प्रबंधित कर रहा हूं।

public static List<BinaryRegion> mergeRegions(List<BinaryRegion> regions) 
{ 
    List<BinaryRegion> merged = new ArrayList<BinaryRegion>(); 
    geoModel = new GeometryFactory(); 

    Polygon polys[] = new Polygon[regions.size()]; 
    for (int i = 0; i < regions.size(); i++) 
    { 
     Polygon p = convertRectangleToPolygon(regions.get(i) 
       .getBoundingBox()); 
     polys[i] = p; 
    } 

    System.out.println("Converted " + regions.size() + " polys"); 

    for (int i = 0; i < regions.size(); i++) 
    { 
     System.out.println("Sending in poly " + i); 
     ArrayList<Polygon> result = mergePoly(polys[i], polys); 
     System.out.println("After run, size=" + result.size()); 
    } 
    return merged; 

} 

private static ArrayList<Polygon> mergePoly(Polygon p, Polygon[] polys) 
{ 
    ArrayList<Polygon> merges = new ArrayList<Polygon>(); 

    for (int i = 0; i < polys.length; i++) 
    { 
     if (p.equals(polys[i])) 
      System.out.println("found the exact match at " + i); 
     else if (p.intersects(polys[i])) 
     { 
      System.out.println("Found intersection at " + i); 
      System.out.println("Other poly is area "+polys[i].getArea()); 
      Polygon u = (Polygon) p.union(polys[i]); 
      System.out.println("Merge size="+u.getArea()); 
      merges.add(u); 
     } 
     else 
      merges.add(polys[i]); 
    } 
    return merges; 
} 

Answer 1

नहीं पूरी तरह यकीन नहीं है कि यह नेस्टेड पुनरावृत्ति दृष्टिकोण वास्तव में जाने के लिए (विशेष रूप से के बाद से मैं कैसे वास्तव में आप mergePoly करने के लिए अपने कॉल के बाद मर्ज किए गए क्षेत्रों संभाल रहे हैं नहीं दिख रहा है) तरीका है। अन्य सभी बहुभुजों की तुलना में एक समय में एक बहुभुज के साथ काम करने के बजाय, आप मध्यवर्ती कदम क्यों नहीं रखते हैं और विलय को फिर से शुरू नहीं करते हैं जब तक कि कोई और चौराहे न हो? की तर्ज पर कुछ:

private static ArrayList<Polygon> mergePoly(Polygon[] polys) 
{ 
    List<Polygon> polygons = new ArrayList<Polygon>(Arrays.asList(polys)); 
    boolean foundIntersection = false; 
    do 
    { 
     foundIntersection = false; 
     for (int i = 0; i < polygons.size(); i++) 
     { 
      Polygon current = polygons.get(i); 
      for (int j = i + 1; j < polygons.size(); j++) 
      { 
       if (current.intersects(polygons.get(j))) 
       { 
        foundIntersection = true; 
        current = (Polygon)current.union(polygons.remove(j--)); 
        System.out.println("Merge size="+u.getArea()); 
       } 
      } 
      polygons.set(i, current); 
     } 
    } while(foundIntersection); 
    return polygons; 
} 

थोड़ा समय के बाद से मैं जावा के साथ काम किया गया है, लेकिन तर्क सुंदर आत्म व्याख्यात्मक है। आप बहुभुज के दो पुनरावृत्तियों का प्रदर्शन करते हैं। बाहरी पुनरावृत्ति आपका "वर्तमान" बहुभुज है, कि आप सभी आंतरिक बहुभुजों को विलय कर देंगे (संग्रह के साथ उन्हें हटाकर)। प्रत्येक बाहरी पुनरावृत्ति के बाद, आप उस सूचकांक पर (संभवतः) मर्ज किए गए बहुभुज के साथ तत्व सेट करेंगे, और श्रृंखला में अगले बहुभुज पर जाएं। आप इसे तब तक जारी रखेंगे जब तक आप अब विलय नहीं कर लेते। बस ध्यान रखें कि यह एक बेहद बेवकूफ कार्यान्वयन है, और आप इसे "हिस्सों" में तोड़ने और इन छोटे सबसेट्स (विलय के बारे में सोचने) में विलय करने से बेहतर हो सकते हैं।

Answer 2

आप स्वीप लाइन एल्गोरिथ्म का उपयोग प्रभावी रूप से आयतों के सेट विलय करने के लिए आयत (example1, example2) और यू nion-find algorithm के चौराहों को खोजने के लिए कर सकते हैं।