अंक के विमान को टेस्सेलेट करें

Question

मेरे पास 3 डी पॉइंट से भरा फ़ाइल है। अंक एक विमान बनाते हैं। यहां एक उदाहरण फ़ाइल है:

25 
1 -1 0 
1 -0.5 0 
1 0 0 
1 0.5 0 
1 1 0 
0.5 -1 0 
0.5 -0.5 0 
0.5 0 0 
0.5 0.5 0 
0.5 1 0 
0 -1 0 
0 -0.5 0 
0 0 0 
0 0.5 0 
0 1 0 
-0.5 -1 0 
-0.5 -0.5 0 
-0.5 0 0 
-0.5 0.5 0 
-0.5 1 0 
-1 -1 0 
-1 -0.5 0 
-1 0 0 
-1 0.5 0 
-1 1 0 

संपादित करें: चूंकि मेरे उदाहरण का सेट बहुत आसान था, यहां एक और जटिल उदाहरण है।

30 
-0.298858 -0.816497 1.11536 
0.0546949 -0.816497 0.761802 
0.408248 -0.816497 0.408248 
0.761802 -0.816497 0.0546949 
1.11536 -0.816497 -0.298858 
-0.462158 -0.489898 0.952056 
-0.108604 -0.489898 0.598502 
0.244949 -0.489898 0.244949 
0.598502 -0.489898 -0.108604 
0.952056 -0.489898 -0.462158 
-0.625457 -0.163299 0.788756 
-0.271904 -0.163299 0.435203 
0.0816497 -0.163299 0.0816497 
0.435203 -0.163299 -0.271904 
0.788756 -0.163299 -0.625457 
-0.788756 0.163299 0.625457 
-0.435203 0.163299 0.271904 
-0.0816497 0.163299 -0.0816497 
0.271904 0.163299 -0.435203 
0.625457 0.163299 -0.788756 
-0.952056 0.489898 0.462158 
-0.598502 0.489898 0.108604 
-0.244949 0.489898 -0.244949 
0.108604 0.489898 -0.598502 
0.462158 0.489898 -0.952056 
-1.11536 0.816497 0.298858 
-0.761802 0.816497 -0.0546949 
-0.408248 0.816497 -0.408248 
-0.0546949 0.816497 -0.761802 
0.298858 0.816497 -1.11536 

ये अंक तो जैसे साजिश रची है:

इस फ़ाइल में कहा गया है वहाँ विमान में 25 अंक हैं कि, और अंक सूचीबद्ध करता है। अंक नियमित रूप से दूरी पर हैं। इस जानकारी के आधार पर, मैं बिंदु डेटा से बाहर त्रिकोण कैसे फार्म और एक std::vector<Tri> में संग्रहीत जहां Tri है एक

struct Tri 
{ 
    double x1, y1, z1; 
    double x2, y2, z2; 
    double x3, y3, z3; 
}; 

भी नोट कर सकता है: समस्या प्रतिबंध: बाहरी पुस्तकालयों की अनुमति नहीं है। सी ++ 0 एक्स के उपयोग की अनुमति नहीं है (कंपाइलर: जी ++ 4.5.2)।

Answer 1

पहली पंक्ति पढ़ें, इसे N पर कॉल करें। शेष बिंदुओं को एक सरणी A में पढ़ें।

Point xdir = A[1] - A[0]; 
int xdim = 2; 
while (A[xdim] - A[xdim-1] == xdir) xdim++; 
int ydim = N/xdim; 
for (int y = 0; y < ydim-1; y++) { 
    for (int x = 0; x < xdim-1; x++) { 
     addTriangle(A[y*xdim+x],A[(y+1)*xdim+x],A[(y+1)*xdim+(x+1)]); 
     addTriangle(A[y*xdim+x],A[y*xdim+(x+1)],A[(y+1)*xdim+(x+1)]); 
    } 
} 

बेशक, यह मानता है कि आप वास्तव में ग्रिड ऑर्डर में अपने सभी अंक प्राप्त कर रहे हैं। यदि नहीं, तो उन्हें पहले क्रमबद्ध करें।

Answer 2

विमान पर ग्रिड को लाइनों के एक सेट में अलग करें। छत को प्रत्येक रेखा के आसन्न बिंदुओं को एक रेखा पर ले कर दिया जाता है और जोड़ी के प्रत्येक सदस्य के निकटतम बिंदु को जोड़ी में निकटतम बिंदु जोड़कर दिया जाता है।

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

Answer 3

शायद Delaunay Triangulation आपकी मदद करता है? यह link डेलाउने त्रिभुज

प्राप्त करने के लिए कुछ एल्गोरिदम प्रदान करता है एक और एल्गोरिदम here दिया जाता है।

Answer 4

टेस्सेलेशन एल्गोरिदम के लिए, सदिश को बनाने का प्रयास करें, और आसन्न बिंदुओं के दाएं त्रिकोण (उन्हें ओवरलैप किए बिना)। 0 < i < m-1 और 0 < j < n-1 के लिए

• {(i,j),(i+1,j),(i+1,j+1)}: मान लें कि आप सही क्रम में एक m x n मैट्रिक्स में सभी बिंदुओं को संग्रहीत किया है, तो आप त्रिकोण के इस सेट बना सकते हैं।
• {(i,j+1), (i+1,j+1), (i,j)0 < i < m-1 और 0 < j < n-1 के लिए।

मैट्रिक्स में बिंदु की अनुक्रमणिका जोड़ी के लिए मैंने त्रिकोण के लिए {p1, p2, p3} और (x, y) फ़ॉर्म का उपयोग किया। आपके मामले में, इन एम और एन चर 5 के बराबर हैं।

Answer 5

शिखर के सेट से त्रिकोणों का एक सेट प्राप्त करने के लिए कई अलग-अलग तरीके हैं, इसलिए मुझे यकीन नहीं है कि मैं पूरी समस्या आवश्यकताओं को समझता हूं।

लेकिन मेरे दृष्टिकोण शायद कुछ इस तरह दिखेगा:

1. चल बिन्दु पूर्णांकन और/या डेटा सटीकता मुद्दों के लिए खाते में करने के लिए, मैं पहली बार विमान को एक सामान्य वेक्टर निर्धारित करेंगे, एक कम से कम की तरह कुछ का उपयोग कर वर्ग फिट एल्गोरिदम। कि सामान्य वेक्टर उपयोग करने के लिए की तरह कुछ सामान्य विमान सवालों निर्धारित करने के लिए (हालांकि आप हवाई जहाज ही है, सिर्फ दिशा की जरूरत नहीं है।)

2. लिखें एल्गोरिदम "त्रिकोण के भीतरी इलाकों में बिंदु डी है?" और "सेगमेंट एबी और सीडी छेड़छाड़ करते हैं?" (विमान प्रक्षेपण में)।

आप इनपुट यह इस बिंदु से आसान बना देता है कि, या एक मौजूदा विमान एल्गोरिथ्म का उपयोग करना चाहते, महान करने के लिए कुछ ज्ञात संरचना है।

तुम सिर्फ गैर-अतिव्यापी त्रिकोण कि उत्तल पतवार tesselate के किसी सेट प्राप्त करना चाहते हैं:

1. किसी भी तीन अंकों के साथ आरंभ और एक भी त्रिकोण। अब तक कवर किए गए क्षेत्र की सीमा बहुभुज बनाने वाले शिखर के क्रमबद्ध चक्र को भी याद रखें। फिर एक समय में बाकी बिंदुओं को जोड़ें।

2. यदि जोड़ने के लिए नया बिंदु मौजूदा त्रिकोण के इंटीरियर में है, तो उस त्रिभुज को तीन subtriangles से प्रतिस्थापित करें।

3. अन्यथा, निर्धारित करें कि सीमा पॉलीगॉन शिखर से नई बिंदु पर कौन सी एन (एन> = 2) लाइन सेगमेंट सीमा पॉलीगॉन को छेड़छाड़ नहीं करते हैं। जोड़ें (एन -1) नए त्रिकोण। नया बिंदु सीमा बहुभुज में एक नए चरम के रूप में (एन -2) पुराने अंक बदलता है।

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