एल्गोरिथ्म बहुभुज

Question

मुझे लगता है कि मेरी समस्या "उत्तल पतवार" से संबंधित है में आसन्न आयतों विलय, लेकिन कोई एक ही है। ड्राइंग में सभी आकार समान चौड़ाई और ऊंचाई के साथ आयताकार हैं। कई एक दूसरे के समीप हैं। मैं उन आसन्न आयताकारों को बहुभुज में जोड़ना चाहता हूं। "उत्तल हल" के विपरीत, अनुसूचित बहुभुज अंदर "खोखले" हो सकते हैं।

क्या कोई खुला स्रोत एल्गोरिदम उपलब्ध है?

Answer 1

मैं General Polygon Clipper की तरह कुछ पर गौर करेंगे। आप मूल रूप से संघ (या) बहुभुज संचालन कर रहे हैं। तथ्य यह है कि वे सभी आयत हैं, गणित को थोड़ा आसान बनाता है, लेकिन यह आसानी से जीपीसी जैसे कुछ के साथ किया जा सकता है।

वहां भाषाओं के बहुत सारे के लिए भाषा का रैपर भी हैं।

Answer 2

, बस का परीक्षण करता है, तो आयतों को छू रहे हैं और उसके बाद उनके अंक के मिलन पर उत्तल पतवार चलाते हैं।

या आप मैन्युअल रूप से भी जो आयतों की ओर छू रहे हैं और एक बहुभुज वस्तु के लिए सही क्रम में बिंदु जोड़ने के लिए परीक्षण कर सकते हैं।

ये मानते हैं कि बंद बहुभुज पर्याप्त होंगे (इसमें छेद नहीं हो सकते हैं)।

Answer 3

यदि आप एक स्थानिक प्रोसेसिंग लाइब्रेरी (जैसे जेटीएस [जावा], एनटीएस [.net] या जीईओएस [सी ++] का उपयोग कर रहे हैं, जो सभी खुले स्रोत हैं और वाणिज्यिक ऐप्स के लिए उपयोग योग्य हैं, जीपीसी के विपरीत) आप केवल यूनियन आयतों।

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

Answer 4

अपने सीमा उचित उपयोग बढ़त मायने रखता है की एक 2 डी सरणी हैं, अन्यथा आप नेस्टेड शब्दकोशों का उपयोग करना होगा।

आप विशिष्ट एक्स, वाई, और अभिविन्यास (लम्बवत या क्षैतिज)

नमूना स्यूडोकोड के संयोग से एक बढ़त पहचान सकते हैं क्योंकि सभी चौड़ाई और ऊंचाई एक ही कर रहे हैं: list_of_edges = नई सूची arr_count = नई int [] [] []

fill_with_zeroes(arr_count) 

foreach rect 
    foreach edge 
     arr_count [edge.x][edge.y][edge.orientation] += 1 

foreach edge in arr_count 
    if count[edge] = 1 
     list_of_edges.add(edge] 

निश्चित रूप से, अगर आप किनारों ऑर्डर करने के लिए चाहते हैं, तो आप एक और समय

foreach edge in arr_count 
    if count[edge] = 1 
     add_recursive(edge) 

add_recursive(x,y): 
    for both horizontal and vertical orientations of edge starting at x, y: 
    count[edge] = 0 
    if (edge.orientation is horizontal) 
     return add_recursive(x+1, y) 
    else 
     return add_recursive(x, y+1) 

सरणी के माध्यम से पारित करना होगा

क्षमा करें, यह स्यूडोकोड बहुत खराब है, लेकिन आप सामान्य विचार

Answer 5

मैं एचटीएमएल 5 कैनवास (गौरवशाली कुछ भी नहीं, एक पहेली के साथ एक प्रयोग परियोजना के हिस्से के रूप में आसन्न बहुभुज मर्ज करने के लिए एक एल्गोरिथ्म लिखना पड़ा मिलना चाहिए :-) परिणामी बहुभुज में छेद स्वाभाविक रूप से समर्थित हैं। जावास्क्रिप्ट दिनचर्या www dot raymondhill dot net/puzzle-rhill/jigsawpuzzle-rhill-3 dot js

में डुप्लिकेट सेगमेंट को हटाने की कुंजी है, लेकिन पॉलीगॉन.प्रोटोटाइप.मेरगे() नामक फ़ंक्शन में पाया जाता है। उल्टी दिशा। असहज स्पष्टीकरण: एक बिंदु {x:?, Y :?} है, एक सेगमेंट {ptA:?, PtB :?} है, एक कंटूर {pts: []} (कनेक्टेड पॉइंट ऑब्जेक्ट्स का संग्रह) है, पॉलीगॉन है {contours: []} (कंटूर वस्तुओं का संग्रह।)

मर्ज एल्गोरिथ्म सेगमेंट वस्तुओं, जहां डुप्लिकेट समाप्त हो जाते का एक बड़ा वसा पूल में सभी क्षेत्रों इकट्ठा। सबसे पहले, पॉलीगॉन ए को परिभाषित करने वाले सभी रूपों के सभी खंड पूल में जोड़े गए हैं। फिर, सभी बहुभुज बी को परिभाषित सभी आकृति के क्षेत्रों पूल में जुड़ जाते हैं, लेकिन हम परीक्षण करने और डुप्लिकेट के लिए निकाल सकते हैं (आसानी से एक hashkey के रूप में एक प्वाइंट वस्तु का उपयोग किया)।

तो हम पूल (बेतरतीब ढंग से ठीक है) से एक सेगमेंट लेते हैं, और हम "चलना" यह जब तक हम एक "एकतरफ़ा", कि, कोई और अधिक खंड जोड़ा जा सकता है तक पहुँचने। यह एक कंटूर ऑब्जेक्ट बनाता है। जब तक सेगमेंट के पूरे संग्रह का उपयोग नहीं किया जाता है तब तक हम दोहराते हैं। चूंकि सेगमेंट का उपयोग किया जाता है, उन्हें पूल से निकाल दिया जाता है। एक खंड "चलना" का अर्थ है कि हम अपना अंत बिंदु लेते हैं, और हम एक सेगमेंट देखते हैं जो बिंदु से मेल खाता है।

के रूप में कहा, परिणामस्वरूप हम कंटूर वस्तुओं जो बहुभुज को परिभाषित का एक संग्रह है। कुछ रूपों को भर दिया जाएगा, कुछ खोखले हो सकते हैं। निर्धारित करने के लिए एक कंटूर भर जाता है या खोखले परीक्षण का मामला है कि क्या कंटूर दक्षिणावर्त या वामावर्त, या अपने क्षेत्र सकारात्मक है या नकारात्मक है है या नहीं। यह एक सम्मेलन है, मेरे मामले में दक्षिणावर्त आकृति भर रहे हैं, वामावर्त खोखला कर रहे हैं।

यहाँ मेरी कार्यान्वयन है, शून्य से बारीकियों और शून्य से त्रुटि हैंडलिंग। उम्मीद है कि मैं कॉपी किया/पर्याप्त आप अभी किसी और काम करते हैं, संदर्भ के लिए ऊपर मेरी जे एस फ़ाइल को संदर्भित करने के लिए चिपकाया:

// Point object 
function Point(a,b) { 
    // a=x,b=y 
    if (b) { 
     this.x=a; 
     this.y=b; 
     } 
    // a=Point or {x:?,y:?} 
    else if (a) { 
     this.x=a.x; 
     this.y=a.y; 
     } 
    // empty 
    else { 
     this.x=this.y=0; 
     } 
    } 
Point.prototype.toHashkey = function() { 
    return this.x+"_"+this.y; 
    }; 
Point.prototype.clone = function() { 
    return new Point(this); 
    }; 
// Segment object 
function Segment(a,b) { 
    this.ptA = new Point(a); 
    this.ptB = new Point(b); 
    } 
// Contour object 
function Contour(a) { 
    this.pts = []; // no points 
    if (a) { 
     if (a instanceof Array) { // assume array of Point objects 
      var nPts = a.length; 
      for (var iPt=0; iPt<nPts; iPt++) { 
       this.pts.push(a[iPt].clone()); 
       } 
      } 
     } 
    } 
Contour.prototype.clone = function() { 
    return new Contour(this); 
    }; 
Contour.prototype.addPoint = function(p) { 
    this.pts.push(p); 
    }; 
// Polygon object 
function Polygon(a) { 
    this.contours = []; // no contour 
    if (a) { 
     if (a instanceof Polygon) { 
      var contours = a.contours; 
      var nContours = contours.length; 
      for (var iContour=0; iContour<nContours; iContour++) { 
       this.contours.push(new Contour(contours[iContour])); 
       } 
      } 
     else if (a instanceof Array) { 
      this.contours.push(new Contour(a)); 
      } 
     } 
    } 
Polygon.prototype.merge = function(other) { 
    // A Javascript object can be used as an associative array, but 
    // they are not real associative array, as there is no way 
    // to query the number of entries in the object. For this 
    // reason, we maintain an element counter ourself. 
    var segments={}; 
    var contours=this.contours; 
    var nContours=contours.length; 
    var pts; var nPts; 
    var iPtA; var iPtB; 
    var idA; var idB; 
    for (var iContour=0; iContour<nContours; iContour++) { 
     pts = contours[iContour].pts; 
     nPts = pts.length; 
     iPtA = nPts-1; 
     for (iPtB=0; iPtB<nPts; iPtA=iPtB++) { 
      idA = pts[iPtA].toHashkey(); 
      idB = pts[iPtB].toHashkey(); 
      if (!segments[idA]) { 
       segments[idA]={n:0,pts:{}}; 
       } 
      segments[idA].pts[idB] = new Segment(pts[iPtA],pts[iPtB]); 
      segments[idA].n++; 
      } 
     } 
    // enumerate segments in other's contours, eliminate duplicate 
    contours = other.contours; 
    nContours = contours.length; 
    for (iContour=0; iContour<nContours; iContour++) { 
     pts = contours[iContour].pts; 
     nPts = pts.length; 
     iPtA=nPts-1; 
     for (iPtB=0; iPtB<nPts; iPtA=iPtB++) { 
      idA = pts[iPtA].toHashkey(); 
      idB = pts[iPtB].toHashkey(); 
      // duplicate (we eliminate same segment in reverse direction) 
      if (segments[idB] && segments[idB].pts[idA]) { 
       delete segments[idB].pts[idA]; 
       if (!--segments[idB].n) { 
        delete segments[idB]; 
        } 
       } 
      // not a duplicate 
      else { 
       if (!segments[idA]) { 
        segments[idA]={n:0,pts:{}}; 
        } 
       segments[idA].pts[idB] = new Segment(pts[iPtA],pts[iPtB]); 
       segments[idA].n++; 
       } 
      } 
     } 
    // recreate and store new contours by jumping from one point to the next, 
    // using the second point of the segment as hash key for next segment 
    this.contours=[]; // regenerate new contours 
    var contour; 
    for (idA in segments) { // we need this to get a starting point for a new contour 
     contour = new Contour(); 
     this.contours.push(contour); 
     for (idB in segments[idA].pts) {break;} 
     segment = segments[idA].pts[idB]; 
     while (segment) { 
      contour.addPoint(new Point(segment.ptA)); 
      // remove from collection since it has now been used 
      delete segments[idA].pts[idB]; 
      if (!--segments[idA].n) { 
       delete segments[idA]; 
       } 
      idA = segment.ptB.toHashkey(); 
      if (segments[idA]) { 
       for (idB in segments[idA].pts) {break;} // any end point will do 
       segment = segments[idA].pts[idB]; 
       } 
      else { 
       segment = null; 
       } 
      } 
     } 
    }; 

जब हम "सैर" एक समोच्च बनाने के लिए खंड, वहाँ एक मामला है, जहां एक

+------+-------+ 
| Poly A  | two segments sharing same start point Z 
|    | 
+  +---<---Z---->---+ 
|  |  | Poly B | 
|  |  |  | 
+  +-------+--------+ 
|      | 
|      | 
+------+-------+--------+ 

कौन सा करने के लिए दो वैध परिणाम नेतृत्व कर सकते हैं (कलन विधि ऊपर एक या अन्य करने के लिए बेतरतीब ढंग से नेतृत्व करेंगे):

परिणाम 1, एक भरा समोच्च: खंड एक से अधिक खंड से कनेक्ट कर सकते

+------+--->---+ 
| Poly A  | 
|    | 
+  +---<---+---->---+ 
|  |  |  | 
|  |  |  | 
+  +--->---+  + 
|      | 
|      | 
+------+---<---+--------+ 

परिणाम 2, एक भरा समोच्च, एक खोखला समोच्च:

+------+--->---+ 
| Poly A  | 
|    | 
+  +---<---+---->---+ 
|  | Hole A|  | 
|  |  |  | 
+  +--->---+  + 
|      | 
|      | 
+------+---<---+--------+ 

यह एक समस्या है, हालांकि नहीं होना चाहिए, के रूप में अपने कोड पहले से ही छेद को संभालने के लिए तैयार रहना चाहिए।

अन्य महत्वपूर्ण विस्तार: उपरोक्त एल्गोरिथ्म, मध्यवर्ती अंक ('+') से छुटकारा नहीं है मिल वास्तव में वे उम्मीद कर रहे हैं या फिर एल्गोरिथ्म काम नहीं करेगा, निम्नलिखित मामले में:

+------>-------+ 
| Poly A  | 
|    | 
|    | +---->---+ 
|    | | Poly B | 
|    | |  | 
|    | +----<---+ 
|    | 
|    | 
+------<-------+ 

मेरी समझ यह है कि यह आपके पास है। मुझे लगता है एल्गोरिथ्म खोजने और पहले से अन्तर्विभाजक अंक जोड़कर इस तरह के मामले का समर्थन करने के लिए बढ़ाया जा सकता है (यह मेरे मामले में अनावश्यक था):

+------>-------+ 
| Poly A  | 
|    | 
|    + +---->---+ 
|    | | Poly B | 
|    | |  | 
|    + +----<---+ 
|    | 
|    | 
+------<-------+ 

आशा इस मदद करते हैं।

पी.एस .: आप कर सकते हैं 'परीक्षण' पहेली के साथ एल्गोरिथ्म, टुकड़ों को एक साथ तड़क छेद उत्पन्न करने के लिए, आदि .: http://www.raymondhill.net/puzzle-rhill/puzzle-rhill.php?puzzlePieces=16&puzzleComplexity=1&puzzleURL=http://www.public-domain-photos.com/free-stock-photos-4/travel/los-angeles/los-angeles-skyline.jpg&puzzleRotate=0&puzzleVersion=3

Answer 6

निम्नलिखित की कोशिश कर के बारे में कैसे। मुझे लगता है कि यह ठीक से डिजाइन किए जाने पर काम करेगा।

1. सबसे छोटा प्रतीक आयत, मूल रूप से अधिकतम x, min-x और max-y और min-y खोजें।यह ड्राइंग के लिए हमारे कैनवास होगा। बिट्स डीएक्स एक्स डीई की एक 2 डी सरणी शुरू करें जहां डीएक्स, डीई इस बाहरी आयत की चौड़ाई है, सभी 0 के लिए।

2. हमारा उद्देश्य समोच्चों को मूल रूप से आयताकारों के कुछ कोनों को ढूंढना है ताकि हम इस समस्या को उस स्तर तक सीमित कर सकें जहां हम इसे कम्प्यूटेशनल रूप से संभाल सकें, एक बार हमारे पास अंक हैं जो हम वास्तविक निर्देशांक प्राप्त करने के लिए बढ़ा सकते हैं ।

3. उपर्युक्त 2 डी सरणी के माध्यम से स्कैन करें और एक बिंदु 1 को चिह्नित करें यदि यह किसी दिए गए आयत में निहित है।

4. अब 2 डी सरणी स्कैन करें और उन बिंदुओं को देखें जिनके पड़ोस में 3: 1 विभाजन है, जिसका अर्थ है कि 3 पक्षों में इसका 1 एस और एक तरफ 0 या इसके विपरीत है। ये अंक वे हैं जो समोच्च को परिभाषित करेंगे।

मुझे लगता है कि अगर हम बुद्धिमानी से समस्या नीचे पैमाने पर कर सकते हैं जटिलता managiable हो जाएगा।

Answer 7

मैं एक बहुत सरल रास्ता मिल गया है:

1. एक काले रंग की छवि बनाएं।
2. सफेद रंग में छवि पर भरे आयताकार बनाएं। इसके साथ सभी ओवरलैप्ड आयतों को जोड़ा जाएगा।
3. ब्लॉब के रूप में खोजें।

यही है!

Answer 8

मुझे पहले भी इसी तरह की समस्या थी। मैं बिल्कुल नहीं जानता कि आप कैसे गठबंधन करते हैं, लेकिन मेरा हमेशा एक दूसरे के लिए 5 मीटर अलग दूरी पर था।

मेरा समाधान एक्स समन्वय द्वारा आदेश बिंदु को प्राप्त किया गया था।

दो सूचियां थीं, जिन्हें पिछले कहा जाता था और एक जिसे वर्तमान कहा जाता था।

यदि वर्तमान खाली था तो बिंदु को वर्तमान में जोड़ें। यदि वर्तमान खाली नहीं है तो जांच करें कि बिंदु वर्तमान में बिंदुओं में से एक के निकट है (पीछे की ओर सूची चलाएं क्योंकि हालिया बिंदु एक निकटतम बिंदु है)

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

आपके अंक कैसे प्राप्त किए जाते हैं (ऑर्डर) के आधार पर, आपको सभी अंतिम बहुभुजों को फिर से जांचने की आवश्यकता हो सकती है कि वे किसी भी अन्य बहुभुज के समीप हैं या नहीं।

टेक्स्ट की लंबी दीवार के लिए खेद है, अगर आप कोड करना चाहते हैं तो मुझे बताएं, यह सी # में है और बहुत साफ नहीं है।