मैं एक कुशल एल्गोरिदम खोज रहा हूं जो यह निर्धारित करता है कि पॉलीहेड्रॉन उत्तल है या नहीं।मैं कैसे निर्धारित करूं कि पॉलीहेड्रॉन उत्तल है या नहीं?
मैंने यह जांचकर शुरू किया कि यूलर विशेषता 2 है। और मैं यह भी जांच रहा हूं कि हर चेहरा उत्तल है। लेकिन वह अभी भी बहुत से मामलों को पकड़ नहीं पाता है।
मेरे पास एक और विचार था: प्रत्येक चेहरे के लिए जांच करें कि सभी वें ई अन्य चेहरे उस चेहरे के एक ही तरफ झूठ बोलते हैं।
आप प्रत्येक चेहरे (क्रॉस-प्रोडक्ट द्वारा) के लिए सामान्य वेक्टर की गणना करके और फिर प्रत्येक वेक्टर के लिए एक कशेरुक (चेहरे) से अन्य सभी के लिए डॉट-उत्पाद की गणना करके इसकी जांच कर सकते हैं। संकेत एक ही होना चाहिए।
एल्गोरिदम दोनों काम करना चाहिए, लेकिन गणना समय में भिन्न हो सकता है।
इस की जाँच करें: http://liam.flookes.com/cs/geo/
असल:
ग्रेट, धन्यवाद। क्या शिखर का औसत हमेशा उत्तल पॉलीहेड्रॉन के लिए आंतरिक होता है? –
इस बिंदु को यादृच्छिक रूप से नहीं चुना जा सकता है और आपके पास झूठी-सकारात्मक होगी, है ना? – Kryptos
@ चार्ल्स: हाँ, यह एक उत्तल शरीर दिया गया है। @ क्रिप्टोस इसे यादृच्छिक रूप से चुना जा सकता है, लेकिन आपको चेहरे के सभी विमानों के साथ छेड़छाड़ के लिए बिंदु पी और चेहरे ए के बीच की तार की जांच करनी होगी। तार पी-ए चेहरा बी_ के चेहरे बी _outside के विमान को छेड़छाड़ कर सकता है। –