परिवृत्त चक्र और उसके अनुप्रयोग के समीकरण के माध्यम से डेलौनाय स्थिति की जांच के लिए एल्गोरिथ्म का अनुकूलन

मैं आपको इस बारे में एक रहस्य बताऊंगा कि कैसे जल्दी से सत्यापित करें कि दो त्रिकोण के लिए डेलॉनाय शर्त पूरी हो गई है।
वास्तविक अनुकूलन स्वयं नीचे वर्णित है (देखें "गोलाकार सर्कल के समीकरण के माध्यम से डेलॉनाय स्थिति की जांच के लिए एल्गोरिदम का अनुकूलन"), लेकिन मैं क्रम में सब कुछ के बारे में बात करूंगा।

मेरे मामले में, चित्र को अनुरेखण में प्रयोग किया जाता है, विमान को आदिम क्षेत्रों (त्रिकोण) में विभाजित करने के लिए। जैसा कि आप जानते हैं, इसे कई चरणों में भी विभाजित किया गया है: समायोजन, सीमाओं की पहचान, सीमाओं को दरकिनार करना, व्यापक अंतर्विरोध। यह अपने सबसे सामान्य रूप में है। मैं रोकना चाहता हूं, मुझे लगता है, सबसे कठिन चरण में: विमान को स्वीप करना।

प्रवेश द्वार पर

आउटपुट में सीमाओं का पता लगाने और उनका पता लगाने के बाद, मुझे बहुत सारे बाहरी कंट्रोवर्स मिले। प्रत्येक समोच्च समोच्च का एक अलग रंग होता है। प्रत्येक ज्ञात सर्किट में आंतरिक सर्किट की एक ज्ञात संख्या भी होती है।
इस प्रकार, "विमान को उड़ाने" के दृष्टिकोण से, यदि हम बाहरी आकृति को अलग-अलग मानते हैं, तो हमारे पास कई बिंदु हैं, जिनमें से प्रत्येक में दाएं और बाएं एक पड़ोसी है। यानी सभी बिंदुओं को एक श्रृंखला में बंद किया जाता है, एक एकल "हैंगिंग" बिंदु नहीं है, और प्रत्येक श्रृंखला में कम से कम 3 अंक (चित्र 1) शामिल हैं।


चित्र 1

क्या करें?

त्रिकोण के साथ आंकड़े को स्वीप करना आवश्यक है।

खोज

पुस्तक को पढ़ने के बाद [1] मुझे डेलौना त्रिकोण निर्माण की एक भी (कम से कम एक) विधि नहीं मिली जो कम से कम किसी तरह मेरे मामले के लिए उपयुक्त थी। मैंने अन्य पुस्तकों की खोज नहीं की। हां, और यह पर्याप्त था, उसने मेरे सिर के विचारों को क्रम में लाया। नतीजतन, उन्होंने अपनी "साइकिल" का आविष्कार किया।

एल्गोरिथ्म

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


चित्र 2

चित्र 3

चित्र 4

एक और बात: अगले त्रिकोण को सहेजते समय, एक घड़ी की दिशा में (सही तालमेल प्रणाली में) कोने को रिकॉर्ड करना आवश्यक है। यह कंप्यूटिंग संसाधनों को कम करने के लिए भविष्य में काम आएगा।

2) चरण 1 को दोहराएं जब तक हम पूरे विमान को पार नहीं करते।

3) यदि कई क्रम हैं, अर्थात्। एक, और इसके अंदर एक और एक या अधिक आंतरिक आकृति (चित्र 1)। यहां प्रत्येक अनुक्रम पर अलग से विचार करना आवश्यक है। अगले आंतरिक समोच्च ले लो। एक बाहरी और एक आंतरिक से हम दो एकल सर्किट बनाते हैं। ऐसा करने के लिए, एक सर्किट से दूसरे सर्किट में दो "पोर्ट" ढूंढें। "बंदरगाहों" के लिए शर्त: उन्हें एक-दूसरे को काटना नहीं चाहिए (छोरों को छूना भी नहीं चाहिए), समोच्च रेखाओं (चित्रा 5) के साथ प्रतिच्छेद नहीं करना चाहिए।


चित्र 5

चित्र 6
4) अगला, पहले से गठित सभी आंतरिक अनुक्रमों को एक-दूसरे से अलग करना (पैराग्राफ 3) अनुक्रमों को शुरू करना आवश्यक है। आपको उस नए के साथ विलय करने की आवश्यकता है जिसमें नया है। परिभाषा के अनुसार, कोई भी आंतरिक अनुक्रम दूसरों (दोनों एक बाहरी और सभी संभव आंतरिक वाले) के साथ स्पर्श या अंतरंग नहीं करता है, ताकि सब कुछ आसानी से हो जाए।
बंदरगाहों (चित्र 6) को खोजने के बाद, नए अनुक्रमों का निर्माण करना आसान है और उन्हें वर्तमान एल्गोरिथ्म (चित्रा 7) के अंक 1 और 2 के साथ बाईपास करना आसान है।

चित्र 7

5) चौथे चरण के बाद, हमारे पास त्रिकोणों की एक सूची है (चित्र 8)। ऐसा लगता है कि जैसे उन्होंने पहले ही कार्य पूरा कर लिया है, लेकिन यह चित्र को सुंदर बनाने के लिए बना हुआ है: जाँच करें कि Delaunay शर्त पूरी हुई है (चित्र 9)।

चित्र 8

चित्र 9

6) आगे देखते हुए मैं छठे बिंदु के बारे में बताऊंगा। इसमें आइटम नंबर 5 द्वारा प्राप्त त्रिकोणों की सूची के माध्यम से एक अनुक्रमिक रन होता है। सबसे पहले, हम सभी त्रिभुजों को "गंदा" लेबल करते हैं। प्रत्येक चक्र में, हम प्रत्येक त्रिकोण के लिए Delaunay स्थिति की जांच करते हैं। यदि शर्त पूरी नहीं हुई है, तो पुनर्निर्माण करें और पड़ोसियों और वर्तमान त्रिकोण "गंदे" को चिह्नित करें। यदि स्थिति संतुष्ट है, तो इसे साफ करें। एल्गोरिथ्म के मेरे कार्यान्वयन में, प्रत्येक त्रिकोण में अपने पड़ोसियों के लिए एक संदर्भ है। इस मामले में, 6 आइटम सबसे तेज है।

पाँचवें चरण के बारे में और पढ़ें।

अब, जहां तक ​​मुझे पता है, यह निर्धारित करने के दो संभावित तरीके हैं कि क्या त्रिकोण डेलुनाय स्थिति को संतुष्ट करते हैं या नहीं: 1) विपरीत कोणों का योग जांचें। यह 180 से कम होना चाहिए। 2) परिचालित सर्कल के केंद्र की गणना करें और 4 वें बिंदु तक दूरी की गणना करें। हर कोई जानता है कि अगर बिंदु गोल घेरे के बाहर है तो डेलुनाय स्थिति संतुष्ट है।

गणना की शक्ति संख्या 1: गुणन / विभाजन के 10 संचालन और जोड़ / घटाव के 13 संचालन।
गणना की शक्ति संख्या 2: गुणन / विभाजन के 29 संचालन और जोड़ / घटाव के 24 संचालन।

कंप्यूटिंग शक्ति के दृष्टिकोण से, जिसे पुस्तक [1] में उदाहरण के लिए गणना की जाती है, विकल्प नंबर 1 अधिक लाभदायक है। उन्होंने इसे महसूस किया, यदि नहीं ... (चित्र 10)। जैसा कि "कन्वेयर" पर इस पद्धति को स्थापित करने के बाद निकला, परिणामस्वरूप अनिश्चितता। यह एक विकल्प है जब कोण ए खुद 180 डिग्री से अधिक है। यह पुस्तक में माना जाता है [1] अलग निजी तरीकों में से एक। और इसके साथ इसके सभी लालित्य, पारदर्शिता और प्रदर्शन गायब हो जाते हैं। और बाद में यह भी पता चला कि विधि संख्या 2 को बहुत महत्वपूर्ण रूप से अनुकूलित किया जा सकता है।


चित्र 10

परिवृत्त चक्र के समीकरण के माध्यम से Delaunay स्थिति की जांच के लिए एल्गोरिथ्म का अनुकूलन

अगला शुद्ध गणित है।

तो हमारे पास है:
बिंदु A (X1, y1), B (x2, y2), C (x3, y3) के माध्यम से गुजरने वाले वृत्त के समीकरण द्वारा बिंदु M (X, Y) के लिए स्थिति की जाँच फॉर्म में लिखी जा सकती है:

(ए X (एक्स ^ 2 + वाई ^ 2) - बी c एक्स + सी ⋅ वाई - डी) ≥ साइन ए ⋅ 0

विवरण शानदार पुस्तक [1] में पाया जा सकता है। (नहीं, मैं उसका लेखक नहीं हूं)
तो, साइन इन करें बाईपास दिशा का एक संकेत है, शुरू से ही मैंने त्रिकोण को दक्षिणावर्त बनाया, ताकि इसे छोड़ा जा सके (यह एक के बराबर है)।

अगला, निर्देशांक के केंद्र को M पर ले जाना, हम प्राप्त करते हैं (चित्र 11):

ए (एक्स 1 - एक्स, वाई 1 - वाई), बी (एक्स 2 - एक्स, वाई 2 - वाई), बी (एक्स 3 - एक्स, वाई 3 - वाई);

-ड> = 0

चित्र 11

क्या यह सिर्फ इतना ही नहीं है?

d <= 0

पुस्तक के अनुसार, फिर से, [1]

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)*(y1*x2 - x1*y2) <= 0 

हमारे पास: गुणा / भाग के 15 ऑपरेशन और जोड़ / घटाव के 14 ऑपरेशन हैं।

आपका ध्यान देने के लिए धन्यवाद। आलोचना की प्रतीक्षा है।

प्रयुक्त साहित्य की सूची

1. स्कोवर्त्सोव ए.वी. Delaunay त्रिकोण और इसके अनुप्रयोग। - टॉम्स्क: पब्लिशिंग हाउस टॉम। विश्वविद्यालय, 2002 ।-- 128 एस। आईएसबीएन 5-7511-1501-5