लाइन सेगमेंट के संग्रह के गैर-उत्तल ढक्कन का निर्धारण

Question

मेरे पास एक कम्प्यूटेशनल ज्यामिति समस्या है जो मुझे लगता है कि अपेक्षाकृत सरल समाधान होना चाहिए, लेकिन मैं इसे काफी समझ नहीं सकता।

मुझे कई रेखा खंडों द्वारा परिभाषित क्षेत्र की गैर-उत्तल रूपरेखा निर्धारित करने की आवश्यकता है।

मुझे विभिन्न गैर-संवहनी हल एल्गोरिदम (उदा। अल्फा आकार) के बारे में पता है, लेकिन मुझे पूरी तरह से सामान्य एल्गोरिदम की आवश्यकता नहीं है, क्योंकि रेखा खंड अधिकांश मामलों में एक अद्वितीय समाधान को परिभाषित करते हैं।

---

जैसा कि @ जीन-फ्रैंकोइसकोर्बेट ने इंगित किया है, ऐसे मामले हैं जहां कई समाधान हैं। मुझे स्पष्ट रूप से मेरी परिभाषा के बारे में और सोचने की जरूरत है।

हालांकि, मैं जो करने की कोशिश कर रहा हूं वह रिवर्स-इंजीनियर है और एक मालिकाना फ़ाइल प्रारूप का उपयोग करें ताकि मैं अपने और दूसरों द्वारा एकत्र किए गए डेटा पर मूल विश्लेषण चला सकूं। फ़ाइल प्रारूप काफी सरल है, लेकिन सीमा को परिभाषित करने के लिए उपयोग किए जाने वाले एल्गोरिदम का निर्धारण करना काफी कठिन है।

किनारे के कई मामलों में डालकर जिसके परिणामस्वरूप एक गैर-अद्वितीय समाधान होता है, सॉफ़्टवेयर प्रश्न के बिना या तो चेतावनी के बिना दुर्घटनाग्रस्त हो जाता है या चुपचाप फ़ाइल को पढ़ने में विफल रहता है।

इसलिए, जब कई समाधान होते हैं, या तो स्वीकार्य समाधानों में से एक उत्पन्न करते हैं या यह निर्धारित करने में सक्षम होते हैं कि कई समाधान स्वीकार्य होंगे।

---

समस्या परिभाषा:

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

ऐसे मामलों में जहां इस मानदंड को पूरा करने वाले कई समाधान हैं, तो इनमें से कोई भी समाधान स्वीकार्य होगा। (यह निर्धारित करने के लिए जब समाधान में गैर-अद्वितीय है सक्षम होने के लिए अच्छा होगा, लेकिन इस सख्ती से आवश्यक नहीं है।)

---

उदाहरण:

एक उदाहरण के रूप में, मैं इन पंक्तियों के साथ कुछ है :

और मैं निम्नलिखित क्षेत्र चित्रित करने के लिए करना चाहते हैं:

यह भी न काटने वाली वर्गों के लिए काम करना चाहिए। जैसे

मुझे लगता है कि (?) नहीं है या तो मामले में एक अनूठा समाधान, मापदंड रूपरेखा पहले के अधीन है। (संपादित करें: सामान्य रूप से एक अनूठा समाधान नहीं है, क्योंकि @ जीन-फ्रैंकोइसकोर्बेट ने बताया। हालांकि, मुझे अभी भी एक एल्गोरिदम में दिलचस्पी है जो या तो स्वीकार्य समाधानों में से एक उत्पन्न करेगा।)

परीक्षण मामलों

एक टेस्ट केस के लिए, यहाँ कोड उपरोक्त आंकड़े उत्पन्न करने के लिए है। मैं यहां अजगर का उपयोग कर रहा हूं, लेकिन सवाल भाषा-अज्ञेयवादी है।

import matplotlib.pyplot as plt 

def main(): 
    test1() 
    test2() 
    plt.show() 

def test1(): 
    """Intersecting segments.""" 
    segments = [[(1, 1), (1, 3)], 
       [(3.7, 1), (2, 4)], 
       [(2, 0), (3.7, 3)], 
       [(4, 0), (4, 4)], 
       [(4.3, 1), (4.3, 3)], 
       [(0, 2), (6, 3)]] 

    desired_outline = [segments[0][0], segments[5][0], segments[0][1], 
         segments[1][1], segments[2][1], segments[3][1], 
         segments[4][1], segments[5][1], segments[4][0], 
         segments[3][0], segments[1][0], segments[2][0], 
         segments[0][0]] 

    plot(segments, desired_outline) 

def test2(): 
    """Non-intersecting segments.""" 
    segments = [[(0, 1), (0, 3)], 
       [(1, 0), (1, 4)], 
       [(2, 1), (2, 3)], 
       [(3, 0), (3, 4)]] 

    desired_outline = [segments[0][0], segments[0][1], segments[1][1], 
         segments[2][1], segments[3][1], segments[3][0], 
         segments[2][0], segments[1][0], segments[0][0]] 

    plot(segments, desired_outline) 


def plot(segments, desired_outline): 
    fig, ax = plt.subplots() 
    plot_segments(ax, segments) 
    ax.set_title('Segments') 

    fig, ax = plt.subplots() 
    ax.fill(*zip(*desired_outline), facecolor='gray') 
    plot_segments(ax, segments) 
    ax.set_title('Desired Outline') 

def plot_segments(ax, segments): 
    for segment in segments: 
     ax.plot(*zip(*segment), marker='o', linestyle='-') 
    xmin, xmax, ymin, ymax = ax.axis() 
    ax.axis([xmin - 0.5, xmax + 0.5, ymin - 0.5, ymax + 0.5]) 

if __name__ == '__main__': 
    main() 

कोई विचार?

मुझे लगता है कि सॉफ्टवेयर है जिसका नतीजा रहा पुन: पेश करने की कोशिश कर रहा हूँ प्रणाली की "आंतरिक" समन्वय किसी प्रकार में एक रेडियल स्वीप एल्गोरिथ्म का उपयोग करता है (जैसे एक x-prime और y-prime बढ़ाया के साथ समन्वय प्रणाली और साथ घुमाया शुरुआत कर रहा हूँ अंक के प्रसार से परिभाषित मूल अक्ष। इससे समस्या अधिक "परिपत्र" बन जाती है।) हालांकि, यह समाधान उत्पन्न करता है जहां कई मामलों में रूपरेखा रेखा खंडों को छेड़छाड़ करती है। यह पता लगाने के लिए काफी आसान है और वहां से बलपूर्वक मजबूर है, लेकिन निश्चित रूप से एक बेहतर तरीका है?

Answer 1

1. एक सुरक्षित प्रारंभिक बिंदु चुनें। उदाहरण हो सकता है अधिकतम एक्स के साथ एंडपॉइंट। लाइन सेगमेंट के साथ
2. मार्च।
3. किसी भी चौराहे का सामना करने पर, हमेशा इस नए सेगमेंट के साथ बाएं मुड़ें और मार्च करें।
4. एक एंडपॉइंट का सामना करने पर, इसे रिकॉर्ड करें। गोटो 2.
5. जब आप अपने शुरुआती बिंदु पर वापस आ गए हैं तो रोकें। रिकॉर्ड किए गए एंडपॉइंट्स की आपकी सूची अब आपके अवतल हल के शिखर की ऑर्डर की गई सूची बनाती है।

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

संपादित ... या बल्कि, दूरस्थ क्षेत्रों कर सकते हैं दो अनूठे समाधान संभव बनाते हैं - सही लेआउट के आधार पर। सबूत: नीचे एक उदाहरण है जहां मैंने जो पीला सेगमेंट जोड़ा है, वह दो समाधान संभव बनाता है (नीली और भूरे रंग की हाथ से तैयार लाइनें)। पीले सेगमेंट उन्मुख लंबवत तरीके से जिस तरह से खींचा गया है, केवल एक समाधान संभव होगा। आपकी समस्या की तरह लगता है खराब परिभाषित किया गया है।

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

संपादित इस कुछ और सोचा देने के बाद काले, जैसे अतिरिक्त, अनुचित अंक के साथ छेड़छाड़ की। तो बहुत सारे अंक हो सकते हैं।

उत्तर तो निश्चित रूप से कुछ छंटनी करने के लिए उत्तर है। यह काफी जटिल छिद्र होगा, विशेष रूप से यदि आपके पास काले, जैसे "लगातार" रिक्त स्थान "हो सकते हैं, तो मेरे पास दिमाग में एक स्मार्ट एल्गोरिदम नहीं है।लेकिन यहां तक ​​कि अंधा, क्रूर बल संभव हो सकता है। प्रत्येक बिंदु को या तो स्वीकार किया जा सकता है या अस्वीकार कर दिया जा सकता है, इसलिए यदि आपके पास एन आपके अवतल हल में उचित रूप से उम्मीदवार बिंदुओं का आदेश दिया गया है, तो केवल 2^एन जांच करने की संभावनाएं हैं। यह तरीका है, रास्ता क्रमिक क्रम की आपकी मूल समस्या के लिए ब्रूट फोर्स की तुलना में कम संभावनाएं, जिसमें SUM of (n!/(n-k)!) for k=1:(n-1) संभावनाएं होंगी (मेरे नोटेशन क्षमा करें)। तो यह एल्गोरिदम आपकी समस्या को काफी कम करता है।

मुझे लगता है कि यह जाने का रास्ता है।

Answer 2

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