कुशल 4x4 मैट्रिक्स उलटा (एफ़िन ट्रांसफॉर्म)

Question

मुझे उम्मीद थी कि कोई 4x4 एफ़िन मैट्रिक्स ट्रांसफॉर्म के लिए एक कुशल सूत्र बता सकता है। वर्तमान में मेरा कोड कॉफ़ैक्टर विस्तार का उपयोग करता है और यह प्रत्येक कॉफ़ैक्टर के लिए एक अस्थायी सरणी आवंटित करता है। इसे पढ़ना आसान है, लेकिन यह धीमा होना चाहिए।

नोट, यह होमवर्क नहीं है और मुझे पता है कि इसे 4x4 सह-कारक विस्तार का उपयोग करके मैन्युअल रूप से कैसे काम करना है, यह सिर्फ दर्द है और वास्तव में मेरे लिए एक दिलचस्प समस्या नहीं है। इसके अलावा मैंने googled और कुछ साइटों के साथ आया है जो आपको पहले से ही फॉर्मूला देते हैं (http://www.euclideanspace.com/maths/algebra/matrix/functions/inverse/fourD/index.htm)। हालांकि कुछ उत्पादों को प्री-कंप्यूटिंग करके शायद इसे अनुकूलित किया जा सकता है। मुझे यकीन है कि कोई इसके लिए एक बिंदु या दूसरे पर "सर्वश्रेष्ठ" सूत्र के साथ आया था?

Answer 1

आपको इस तथ्य का फायदा उठाने में सक्षम होना चाहिए कि मैट्रिक्स एक पूर्ण व्यस्तता पर चीजों को गति देने के लिए तैयार है। अर्थात्, अपने मैट्रिक्स इस

A = [ M b ] 
    [ 0 1 ] 

की तरह लग रहा है, तो जहां एक 4x4 है, एम 3x3 है, ख 3x1 है, और नीचे पंक्ति (0,0,0,1), तो

inv(A) = [ inv(M) -inv(M) * b ] 
     [ 0   1  ] 

है

आपकी स्थिति के आधार पर, वास्तव में inv (A) बनाने के बजाय inv (A) * x के परिणाम की गणना करना तेज़ हो सकता है। उस स्थिति में, चीजें

inv(A) * [x] = [ inv(M) * (x - b) ] 
     [1] = [  1   ] 

जहां x एक 3x1 वेक्टर (आमतौर पर एक 3 डी बिंदु) है।

अंत में, यदि एम (अर्थात अपने कॉलम orthonormal कर रहे हैं) एक रोटेशन का प्रतिनिधित्व करता है, तो आप तथ्य यह है कि निवेश संबंधी निर्णय निर्माताओं (एम) = स्थानांतरित (एम) का उपयोग कर सकते हैं। फिर ए के विपरीत की गणना करना केवल अनुवाद घटक को घटाना और 3x3 भाग के हस्तांतरण से गुणा करना है।

ध्यान दें कि मैट्रिक्स ऑर्थोनॉर्मल है या नहीं, आपको समस्या के विश्लेषण से पता होना चाहिए। रनटाइम के दौरान इसे जांचना काफी महंगा होगा; यद्यपि आप इसे डीबग बिल्ड में करना चाहते हैं ताकि आपकी धारणाएं हो सकें।

आशा है कि के सभी स्पष्ट है ...

Answer 2

मेरा मानना ​​है कि एक उलटा गणना करने का एकमात्र तरीका समीकरण को हल करने के लिए है: एक x = y, जहां y इकाई वैक्टर को फैलाता है, यानी, पहला वाला (1,0,0,0) है, दूसरा (0,1,0,0), आदि

(सहकारकों (क्रेमर के शासन) का उपयोग करना एक बुरा विचार है, जब तक आप उलटा के लिए एक प्रतीकात्मक सूत्र चाहते हैं।)

अधिकांश रेखीय बीजगणित पुस्तकालयों है आपको उन रैखिक प्रणालियों को हल करने और यहां तक ​​कि एक उलटा गणना करने की अनुमति देगा। अजगर में उदाहरण (numpy उपयोग करते हुए):

from numpy.linalg import inv 
inv(A) # here you go 

Answer 3

IIRC आप बहुत एक गुच्छा precomputing (12?) 2x2 निर्धारकों द्वारा कोड और समय हटना कर सकते हैं। मैट्रिक्स को आधा लंबवत में विभाजित करें और ऊपरी और निचले आधे दोनों में प्रत्येक 2x2 की गणना करें। इन छोटे निर्धारकों में से एक का उपयोग प्रत्येक गणना में किया जाता है जिसे आपको बड़ी गणना के लिए आवश्यक होगा और उनमें से प्रत्येक का पुन: उपयोग किया जाएगा।

इसके अलावा, एक अलग निर्धारक फ़ंक्शन का उपयोग न करें - निर्धारक प्राप्त करने के लिए आस-पास के लिए गणना की गई उप-निर्धारकों का पुन: उपयोग करें।

ओह, बस पाया this.

कुछ सुधार आप भी बदलने की अपनी एक खास तरह जानते हुए भी कर सकते हैं कर रहे हैं।

Answer 4

शायद ज़रुरत पड़े किसी ने कुछ टाइपिंग सहेजना चाहते हैं, यहाँ लिंक का एक AS3 संस्करण मैं पेज 9 पर आधारित लिखा था (लाप्लास विस्तार प्रमेय के अधिक कुशल संस्करण) है ऊपर phkahler द्वारा पोस्ट की गई:

public function invert() : Matrix4 { 
    var m : Matrix4 = new Matrix4(); 

    var s0 : Number = i00 * i11 - i10 * i01; 
    var s1 : Number = i00 * i12 - i10 * i02; 
    var s2 : Number = i00 * i13 - i10 * i03; 
    var s3 : Number = i01 * i12 - i11 * i02; 
    var s4 : Number = i01 * i13 - i11 * i03; 
    var s5 : Number = i02 * i13 - i12 * i03; 

    var c5 : Number = i22 * i33 - i32 * i23; 
    var c4 : Number = i21 * i33 - i31 * i23; 
    var c3 : Number = i21 * i32 - i31 * i22; 
    var c2 : Number = i20 * i33 - i30 * i23; 
    var c1 : Number = i20 * i32 - i30 * i22; 
    var c0 : Number = i20 * i31 - i30 * i21; 

    // Should check for 0 determinant 

    var invdet : Number = 1/(s0 * c5 - s1 * c4 + s2 * c3 + s3 * c2 - s4 * c1 + s5 * c0); 

    m.i00 = (i11 * c5 - i12 * c4 + i13 * c3) * invdet; 
    m.i01 = (-i01 * c5 + i02 * c4 - i03 * c3) * invdet; 
    m.i02 = (i31 * s5 - i32 * s4 + i33 * s3) * invdet; 
    m.i03 = (-i21 * s5 + i22 * s4 - i23 * s3) * invdet; 

    m.i10 = (-i10 * c5 + i12 * c2 - i13 * c1) * invdet; 
    m.i11 = (i00 * c5 - i02 * c2 + i03 * c1) * invdet; 
    m.i12 = (-i30 * s5 + i32 * s2 - i33 * s1) * invdet; 
    m.i13 = (i20 * s5 - i22 * s2 + i23 * s1) * invdet; 

    m.i20 = (i10 * c4 - i11 * c2 + i13 * c0) * invdet; 
    m.i21 = (-i00 * c4 + i01 * c2 - i03 * c0) * invdet; 
    m.i22 = (i30 * s4 - i31 * s2 + i33 * s0) * invdet; 
    m.i23 = (-i20 * s4 + i21 * s2 - i23 * s0) * invdet; 

    m.i30 = (-i10 * c3 + i11 * c1 - i12 * c0) * invdet; 
    m.i31 = (i00 * c3 - i01 * c1 + i02 * c0) * invdet; 
    m.i32 = (-i30 * s3 + i31 * s1 - i32 * s0) * invdet; 
    m.i33 = (i20 * s3 - i21 * s1 + i22 * s0) * invdet; 

    return m; 
} 

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

Answer 5

pkhaler और Robin Hilliard पर उत्कृष्ट प्रतिक्रियाओं का पालन करने के लिए, यहां रॉबिन का एक्शनस्क्रिप्ट 3 कोड सी # विधि में परिवर्तित हो गया है।

public static double[,] GetInverse(double[,] a) 
{ 
    var s0 = a[0, 0] * a[1, 1] - a[1, 0] * a[0, 1]; 
    var s1 = a[0, 0] * a[1, 2] - a[1, 0] * a[0, 2]; 
    var s2 = a[0, 0] * a[1, 3] - a[1, 0] * a[0, 3]; 
    var s3 = a[0, 1] * a[1, 2] - a[1, 1] * a[0, 2]; 
    var s4 = a[0, 1] * a[1, 3] - a[1, 1] * a[0, 3]; 
    var s5 = a[0, 2] * a[1, 3] - a[1, 2] * a[0, 3]; 

    var c5 = a[2, 2] * a[3, 3] - a[3, 2] * a[2, 3]; 
    var c4 = a[2, 1] * a[3, 3] - a[3, 1] * a[2, 3]; 
    var c3 = a[2, 1] * a[3, 2] - a[3, 1] * a[2, 2]; 
    var c2 = a[2, 0] * a[3, 3] - a[3, 0] * a[2, 3]; 
    var c1 = a[2, 0] * a[3, 2] - a[3, 0] * a[2, 2]; 
    var c0 = a[2, 0] * a[3, 1] - a[3, 0] * a[2, 1]; 

    // Should check for 0 determinant 
    var invdet = 1.0/(s0 * c5 - s1 * c4 + s2 * c3 + s3 * c2 - s4 * c1 + s5 * c0); 

    var b = new double[4, 4]; 

    b[0, 0] = (a[1, 1] * c5 - a[1, 2] * c4 + a[1, 3] * c3) * invdet; 
    b[0, 1] = (-a[0, 1] * c5 + a[0, 2] * c4 - a[0, 3] * c3) * invdet; 
    b[0, 2] = (a[3, 1] * s5 - a[3, 2] * s4 + a[3, 3] * s3) * invdet; 
    b[0, 3] = (-a[2, 1] * s5 + a[2, 2] * s4 - a[2, 3] * s3) * invdet; 

    b[1, 0] = (-a[1, 0] * c5 + a[1, 2] * c2 - a[1, 3] * c1) * invdet; 
    b[1, 1] = (a[0, 0] * c5 - a[0, 2] * c2 + a[0, 3] * c1) * invdet; 
    b[1, 2] = (-a[3, 0] * s5 + a[3, 2] * s2 - a[3, 3] * s1) * invdet; 
    b[1, 3] = (a[2, 0] * s5 - a[2, 2] * s2 + a[2, 3] * s1) * invdet; 

    b[2, 0] = (a[1, 0] * c4 - a[1, 1] * c2 + a[1, 3] * c0) * invdet; 
    b[2, 1] = (-a[0, 0] * c4 + a[0, 1] * c2 - a[0, 3] * c0) * invdet; 
    b[2, 2] = (a[3, 0] * s4 - a[3, 1] * s2 + a[3, 3] * s0) * invdet; 
    b[2, 3] = (-a[2, 0] * s4 + a[2, 1] * s2 - a[2, 3] * s0) * invdet; 

    b[3, 0] = (-a[1, 0] * c3 + a[1, 1] * c1 - a[1, 2] * c0) * invdet; 
    b[3, 1] = (a[0, 0] * c3 - a[0, 1] * c1 + a[0, 2] * c0) * invdet; 
    b[3, 2] = (-a[3, 0] * s3 + a[3, 1] * s1 - a[3, 2] * s0) * invdet; 
    b[3, 3] = (a[2, 0] * s3 - a[2, 1] * s1 + a[2, 2] * s0) * invdet; 

    return b; 
}