टेट्राहेड्रॉन

Question

के अंदर पूर्णांक निर्देशांक के साथ सभी बिंदु खोजें I tetrahedron (मैं किसी भी तरह से उनके माध्यम से लूप करने में सक्षम होना चाहता हूं) के अंदर पूर्णांक समन्वय वाले सभी बिंदुओं को खोजने का प्रयास कर रहा हूं। मैं चार बिंदुओं (ए, बी, सी, डी) के निर्देशांक जानता हूं जो टेट्राहेड्रॉन को परिभाषित करते हैं।

मैं वर्तमान में जो कर रहा हूं वह मुझे टेट्राहेड्रॉन का बाध्यकारी बॉक्स (ए, बी, सी, डी के न्यूनतम और अधिकतम एक्स, वाई, जेड निर्देशांक) और फिर अंदर के सभी बिंदुओं के माध्यम से एक लूप करें बंद डब्बा। इस तरह के प्रत्येक बिंदु के लिए, मैं बैरीसेंट्रिक निर्देशांक (the equations from Wikipedia का उपयोग करके) की गणना करता हूं और जांच करता हूं कि बिंदु टेट्राहेड्रॉन के अंदर है (यदि बैरिएंट्रिक निर्देशांक में से कोई नकारात्मक या 1 से बड़ा है, तो बिंदु अंदर नहीं है)।

क्या ऐसा करने का कोई बेहतर तरीका है? वर्तमान में लगभग 1/6 मौका है कि जिस बिंदु पर मैं परीक्षण कर रहा हूं (बाउंडिंग बॉक्स से) वास्तव में टेट्राहेड्रॉन के अंदर स्थित है, इसलिए मुझे लगता है कि मैं बहुत अधिक अनावश्यक गणना कर रहा हूं।

मैं टेट्राहेड्रा की एक सूची के साथ काम कर रहा हूं जिसे मैंने बड़ी मात्रा में त्रिभुज करके उत्पन्न किया है (मैं वॉल्यूम का विस्तार कर रहा हूं और टेट्राहेड्रल इंटरपोलेशन का उपयोग करके लापता मूल्यों को अलग करना चाहता हूं)। मैं किसी बाहरी पुस्तकालय का उपयोग नहीं कर रहा हूं।

Answer 1

में सुधार के लिए एक और विचार:

जांच कर लें कि z- अक्ष के लिए एक "छड़ी" समानांतर (अर्थात एक्स = 4, वाई = 6) चतुर्पाश्वीय के माध्यम से चलाता है। यदि नहीं, तो (x = 4, y = 5, z) के साथ कोई मान नहीं हो सकता है।

अन्यथा, यह पता लगाएं कि रॉड टेट्राहेड्रॉन के किनारे को छेड़छाड़ करती है (यह पता लगाने के द्वारा कि टेट्राहेड्रॉन के किनारे बनाने वाले विमान इसे छेड़छाड़ करते हैं)।

ये विमान z = 1.3 और z = 10.04 पर छेड़छाड़ करते हैं। फिर आप सभी बिंदुओं (4,5, 2) से (4,5,10) अंदर जानते हैं।

एक्स और वाई के सभी मानों के लिए दोहराएं।

यह अभ्यास में तेज़ी से होना चाहिए, क्योंकि यह आपको 1 लूप बचाएगा।

Answer 2

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

यह जांचने का एक आसान तरीका है कि दिया गया बिंदु टेट्राहेड्रॉन के अंदर या बाहर है या नहीं। यह जांचने की मात्रा है कि किस आधा अंतरिक्ष बिंदु टेट्राहेड्रॉन के 4 किनारों में से प्रत्येक के संबंध में है:

प्रत्येक पक्ष को 3 अंक (ए, बी, सी) द्वारा परिभाषित किया गया है। फिर एक विमान सामान्य है (सी-ए) एक्स (बी-ए) (यह विमान में वैक्टरों का क्रॉस उत्पाद है)। यदि यह निर्देशांक हैं (ए, बी, सी), तो विमान समीकरण F(x,y,z) = ax+by+cz = 0 है। किसी दिए गए बिंदु (x0, y0, z0) के लिए F (x0, y0, z0) का संकेत निर्धारित करता है कि कौन से आधे-प्लेन बिंदु हैं।

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