अनियमित आकार वाले बहुभुज के "दृश्य" केंद्र को खोजने का सबसे तेज़ तरीका क्या है?

Question

मुझे एक बिंदु खोजने की जरूरत है जो एक अनियमित आकार वाले बहुभुज का दृश्य केंद्र है। दृश्य केंद्र से, मेरा मतलब एक बिंदु है जो बहुभुज के बड़े क्षेत्र के केंद्र में दिखाई देता है। आवेदन बहुभुज के अंदर एक लेबल डालना है। ,

https://web.archive.org/web/20150708063910/http://proceedings.esri.com/library/userconf/proc01/professional/papers/pap388/p388.htm

इस प्रयोग की जाने वाली है, तो क्या बफर को खोजने के लिए एक प्रभावी और तेज़ तरीका है:

यहाँ एक समाधान बफरिंग के अंदर का उपयोग करता है है? यदि किसी अन्य तरीके का उपयोग किया जाना है, तो वह वही तरीका है?

वास्तव में कठिन बहुभुज का एक अच्छा उदाहरण एक विशाल मोटी यू (एरियल ब्लैक या इंपैक्ट या कुछ ऐसे फ़ॉन्ट में लिखा गया है) है।

Answer 1

आप एक द्विआधारी छवि में बहुभुज परिवर्तित कर सकते हैं, तो आप नींव है कि छवि प्रसंस्करण के क्षेत्र में मौजूद है, उदा .: A Fast Skeleton Algorithm on Block Represented Binary Images उपयोग कर सकते हैं।

लेकिन यह विघटन त्रुटियों और अतिरिक्त कार्य के कारण सामान्य मामले में वास्तव में उचित नहीं है।

हालांकि, हो सकता है आप इन उपयोगी पाते हैं:

• Straight skeleton of a simple polygon
• Determining the Skeleton of a Simple Polygon in (Almost) Linear Time

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

Answer 2

यह समस्या शायद एक समान घनत्व मानते हुए "द्रव्यमान का केंद्र" ढूंढने के समान होगी।

संपादित करें: यह विधि काम नहीं करेगा बहुभुज बहुभुज में से प्रत्येक के किनारे की "छेद"

Answer 3

कंप्यूट केंद्र स्थिति (एक्स, वाई) है, तो। आप प्रत्येक किनारे के सिरों की स्थिति के बीच अंतर ढूंढकर ऐसा कर सकते हैं। प्रत्येक आयाम में प्रत्येक केंद्र का औसत लें। यह बहुभुज का केंद्र होगा।

Answer 4

मुझे लगता है कि यदि आपने बहुभुज को इसके शीर्षकों में वापस तोड़ दिया है, और फिर सबसे बड़ा उत्तल ढक्कन खोजने के लिए एक फ़ंक्शन लगाया है, और फिर उस उत्तल हॉल से केंद्र को ढूंढें, तो यह "स्पष्ट" केंद्र के साथ मिलकर मिल जाएगा।

सबसे बड़ा उत्तल पतवार कोने दिया ढूँढना: Look under the Simple Polygon paragraph.

औसत उत्तल पतवार के कोने केंद्र खोजने के लिए।

Answer 5

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

एक एल्गोरिथ्म में यह पूरा करने के लिए कैसे दुर्भाग्य से मेरे लिए बहुत स्पष्ट नहीं है ....

Answer 6

आप अनुभवहीन केंद्र में लेबल जगह किया जा सका (बाउंडिंग बॉक्स के, शायद), और फिर ले यह आधारित स्थानीय बहुभुज किनारों और लेबल के बीबी के चौराहे पर? घुमावदार किनारों के मानक के साथ आगे बढ़ें, और यदि एकाधिक किनारों को छेड़छाड़ की जाती है, तो उनके आदर्शों को आंदोलन के लिए योग करें?

बस अनुमान लगा रहा है; इस तरह की समस्या में मैं शायद इसे तब तक हल करने का प्रयास करूंगा जब तक कि प्रदर्शन चिंता का अधिक न हो।

Answer 7

क्या आपने सेंट्रॉइड फॉर्मूला का उपयोग करने में देखा है?

http://en.wikipedia.org/wiki/Centroid

http://en.wikipedia.org/wiki/K-means_algorithm

Answer 8

बहुभुज के "incircle" (इसके अंदर फिट बैठता सबसे बड़ा सर्कल), और फिर उस केंद्र के लेबल को केंद्रित करने के बारे में कैसे? यहाँ लिंक की एक जोड़ी पाने के लिए आप शुरू कर रहे हैं:

http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/144373.html?1219439473

यह हर बहुभुज, सबसे अधिक संभावना है पर पूरी तरह से काम नहीं करेगा; एक बहुभुज जो एक सी की तरह दिखता है, उस लेबल को कुछ हद तक अप्रत्याशित स्थान पर रखा जाएगा। लेकिन फायदा यह होगा कि लेबल हमेशा बहुभुज के ठोस हिस्से को ओवरलैप करेगा।

Answer 9

अभी विस्तारित करने या परीक्षण करने के लिए अधिक समय नहीं है, लेकिन जब मुझे मौका मिलता है तो मैं और अधिक करने की कोशिश करूंगा।

सेंट्रॉइड का उपयोग अपनी प्राथमिक विधि के रूप में करें। यह देखने के लिए परीक्षण करें कि क्या केंद्र पॉलीगॉन के भीतर है; यदि नहीं, तो से निकटतम बिंदु और बहुभुज के दूसरी तरफ एक रेखा खींचना। बहुभुज के भीतर की रेखा के उस भाग के मध्य बिंदु पर, अपना लेबल रखें।

क्योंकि सेंट्रॉइड के नजदीक स्थित बिंदु काफी बड़े क्षेत्र से बंधने की संभावना है, मुझे लगता है कि यह Kyralessa के incircles के समान परिणाम दे सकता है। बेशक, यदि आपके पास छेद के साथ बहुभुज था तो यह बेर्सक हो सकता है। उस स्थिति में, incircles शायद बेहतर बेहतर होगा। दूसरी ओर, यह सामान्य मामलों के लिए (त्वरित?) केंद्र विधि के लिए डिफ़ॉल्ट है।

Answer 10

मैं यह नहीं कह रहा हूं कि यह सबसे तेज़ है, लेकिन यह आपको बहुभुज के अंदर एक बिंदु देगा। Straight Skeleton की गणना करें। जिस बिंदु को आप ढूंढ रहे हैं वह इस कंकाल पर है। उदाहरण के लिए आप बाध्यकारी बॉक्स के केंद्र में सबसे छोटी सामान्य दूरी के साथ एक चुन सकते हैं।

Answer 11

Centroid विधि पहले से ही कई बार सुझाई गई है। मुझे लगता है कि यह एक उत्कृष्ट संसाधन है कि इस प्रक्रिया (और बहुभुज के साथ कई अन्य उपयोगी चाल) का वर्णन बहुत सहज है:

http://paulbourke.net/geometry/polygonmesh/centroid.pdf

इसके अलावा, एक सरल यूआई लेबल रखने के लिए, यह पर्याप्त बस सीमांकन की गणना करने के हो सकता है बहुभुज के बॉक्स (एक आयत द्वारा निम्नतम और उच्चतम एक्स और बहुभुज में किसी भी शीर्ष के y निर्देशांक परिभाषित), और में अपने केंद्र के हो रही है:

{ 
    x = min_x + (max_x - min_x)/2, 
    y = min_y + (max_y - min_y)/2 
} 

इसमें कुछ समय केन्द्रक की गणना की तुलना में तेजी है, जो हो सकता है एक वास्तविक समय या एम्बेडेड आवेदन के लिए महत्वपूर्ण हो।

यह भी ध्यान दें कि यदि आपके बहुभुज स्थिर हैं (वे फ़ॉर्म नहीं बदलते हैं), तो आप बीबी केंद्र/जन गणना के केंद्र (उदाहरण के लिए बहुभुज के पहले चरम) के परिणाम को सहेजकर अनुकूलित कर सकते हैं। बहुभुज की डेटा संरचना।

Answer 12

आप मास के केंद्र (या गुरुत्वाकर्षण का केंद्र) विधि है जो सिविल इंजीनियरिंग में प्रयोग किया जाता है का उपयोग कर सकते हैं, यहाँ विकिपीडिया से एक उपयोगी लिंक है:

http://en.wikipedia.org/wiki/Center_of_mass

Answer 13

कैसे के बारे में:

हैं बहुभुज के केन्द्रक, है अंदर बहुभुज तो इसका इस्तेमाल किसी और:

1) बहुभुज के माध्यम से बहुभुज विभाजित बराबर क्षेत्र

के दो हिस्सों में केन्द्रक से एक लाइन का विस्तार

2) "दृश्य केन्द्र" निकटतम बिंदु के बीच आधे रास्ते बिंदु जहां लाइन से छू परिधि और अगले अंक दिशा में परिधि केन्द्रक

यहाँ से दूर जा काटने है चित्रों के एक जोड़े हैं यह वर्णन करने के लिए:

Answer 14

मैं MapBox से करने के लिए एक बहुत अच्छा समाधान Polylabel कहा जाता है मिल गया है। पूरा स्रोत उनके Github पर भी उपलब्ध है।

अनिवार्य रूप से यह बहुभुज के दृश्य केंद्र को खोजने का प्रयास करता है क्योंकि टी ऑस्टिन ने कहा था।

कुछ विवरण सुझाव है कि यह एक व्यावहारिक समाधान हो सकता है:

दुर्भाग्य से, की गणना [आदर्श समाधान] दोनों जटिल और धीमी है। समस्या के प्रकाशित समाधानों को या तो प्रतिबंधित डेलाउने त्रिकोण या प्रीप्रोकैसिंग चरणों के रूप में एक सीधे कंकाल की गणना करना आवश्यक है - जिनमें से दोनों धीमे और त्रुटि-प्रवण हैं।

हमारे उपयोग के मामले में, हमें एक सटीक समाधान की आवश्यकता नहीं है - हम पर अधिक गति प्राप्त करने के लिए कुछ सटीकता का व्यापार करने के इच्छुक हैं। जब हम पर एक मानचित्र डाल रहे हैं, तो गणितीय रूप से परिपूर्ण होने के लिए से मिलीसेकंड में इसकी गणना करना अधिक महत्वपूर्ण है।

हालांकि उपयोग के बारे में एक त्वरित नोट। स्रोत कोड जावास्क्रिप्ट के लिए अच्छा काम करता है बॉक्स से बाहर लेकिन यदि आप एक "सामान्य" बहुभुज के साथ इस प्रयोग पर इरादा तो आप एक खाली सरणी में लपेट चाहिए के रूप में कार्य यहाँ GeoJSONPolygons ले बजाय सामान्य बहुभुज यानी की तुलना में

var myPolygon = [[x1, y1], [x2, y2], [x3, y3]]; 
var center = polylabel([myPolygon]);