rotation למטריצה

[WolfHead]

rotation למטריצה

יש לי מטריצה (2D) ואני רוצה לעשות לה rotate ב90 מעלות לדוגמא:

1,0,0,0 1,0,0,0 1,0,0,0 1,0,0,0​

יהפך לזה:

1,1,1,1 0,0,0,0 0,0,0,0 0,0,0,0​

יש איזה דרך יעילה לעשות את זה?

 

[WolfHead]

‏

 

[Mapisto]

המממ

#include <iostream.h> int main(){ const int rw = 3, cl = 3; int mat[rw + 1][cl + 1]; int i,j; //intizting for ( i =0; i <= rw;i++) for ( j=0; j <= cl ; j++) mat[j] = 0; //just one value to change mat[0][0] = 1; mat[0][1] = 1; mat[0][2] = 1; mat[0][3] = 1; //temp array int temp[rw + 1][cl + 1]; ; for ( i =0; i <= rw;i++) { for ( j=0; j <= cl ; j++) { temp[j] = mat[cl - j]; cout << temp[j] << " " ; } cout << endl << endl; }; return 0; }​

 

[אינגולמו]

יש כמה

דרכים, אבל אחת נחמדה שאני אוהב, היא פשוט להחזיר ממשק אחר למטרציה - כזה שבו ה-X וה-Y מתפרשים אחרת. בצורה כזו, אינך צריך להעתיק מידע ולהעביר תאים. אני מיד מנסה לכתוב חתיכת קוד קטנה וממשיך את התשובה שלי.

 

[אינגולמו]

אוקיי

הסבר על מה שקורה: MatrixData - מכיל את נתוני המטריצה MatrixInterface - מחלקת אב שמייצגת ממשק כלשהו למידע ב-MatrixData. RotatedMatrixInt - דוגמה לממשק המתייחס למטריצה כאילו היא מסובבת יכולים כמובן להיות עוד ממשקים שעושים דברים אחרים, לדוגמה, מתייחסים למטריצה כאילו היא מורכבת רק מאפסים ואחדים וכו'. Matrix - מחלקת המטריצה למשתמש, אשר אך ורק דרכה עובדים. המשתמש מפעיל טרנספורמציות על המטריצה. המטריצה למעשה רק מחליפה את הממשק הפעיל כרגע. אם סובבתי את המטריצה ימינה, אזי הממשק יתחלף ל-RotatedMatrixInt עם זווית מסויימת. במקרה שלנו, קבעתי את הרביע הראשון עד הרביעי בעזרת המספרים 0 עד 3. רציתי להוסיף גם יישום שמאפשר לבצע כמה טרנספורמציות שונות אחת על השניה. זה דורש קצת יותר מלזכור את "הרביע האחרון". למעשה צריך לנהל מחסנית של טרנספורמציות. אתה מוזמן לנסות. במקרה כזה, אל תשכח שאת המחסנית צריך לרוקן מתישהו. *רק אז* רצוי להתחיל להזיז את האיברים "על אמת", ולקבל מטריצה בלי "הסטוריה", מחסנית ריקה, ולהמשיך משם. עיקרון זה הוא מאוד מקובל בתוכנות שמבצעות הרבה טרנספורמציות על מידע (לאו דווקא מטריצות ולאו דווקא סיבוב).

class MatrixData { int* m_arr; int m_width, m_height; public: MatrixData(int y, int x) { m_arr = new int[x*y]; m_width = x; m_height = y; } int Width() const { return m_width; } int Height() const { return m_height; } int& operator()(int y, int x) { return m_arr[y*m_width + x]; } }; class MatrixInterface { protected: MatrixData* m_data; public: MatrixInterface(MatrixData* pData) : m_data(pData) {} virtual int Width() const { return m_data->Width(); } virtual int Height() const { return m_data->Height(); } virtual int& operator()(int y, int x) { return (*m_data)(y,x); } }; class RotatedMatrixInt : public MatrixInterface { int m_nAngle; public: RotatedMatrixInt(MatrixData* pData, int angle) : MatrixInterface(pData), m_nAngle(angle) {} virtual int Width() const { return m_nAngle%2?m_data->Height():m_data->Width(); } virtual int Height() const { return m_nAngle%2?m_data->Width():m_data->Height(); } virtual int& operator()(int y, int x) { switch (m_nAngle) { case 1: return (*m_data)(Width()-x-1, y); case 2: return (*m_data)(Height()-y-1, Width()-x-1); case 3: return (*m_data)(x, Width()-y-1); default: return (*m_data)(y,x); } } }; class Matrix { MatrixInterface* m_intf; MatrixData* m_data; int m_nAngle; void ReplaceInterface(MatrixInterface* newIntf) { if (m_intf) delete m_intf; m_intf = newIntf; } public: Matrix(int y, int x) { m_data = new MatrixData(y,x); m_intf = new MatrixInterface(m_data); m_nAngle = 0; } int& operator()(int y, int x) { return (*m_intf)(y,x); } int Width() const { return m_intf->Width(); } int Height() const { return m_intf->Height(); } void RotateRight() { if (m_nAngle == 3) m_nAngle = -1; ReplaceInterface(new RotatedMatrixInt(m_data, ++m_nAngle)); } void RotateLeft() { if (m_nAngle == 0) m_nAngle = 4; ReplaceInterface(new RotatedMatrixInt(m_data, --m_nAngle)); } }; void main() { Matrix m(4,3); int i, j; for (i = 0; i < m.Height(); ++i) for (j = 0; j < m.Width(); ++j) m(i,j) = (i+1)*(j+1); for (i = 0; i < m.Height(); ++i) { for (j = 0; j < m.Width(); ++j) printf("%4u ", m(i,j)); printf("\n"); } m.RotateRight(); printf("\n\n"); for (i = 0; i < m.Height(); ++i) { for (j = 0; j < m.Width(); ++j) printf("%4u ", m(i,j)); printf("\n"); } }​

 

[אינגולמו]

תיקון קל

בשורת ה-case 3, צריך לקרוא ל-HEIGHT ולא ל-WIDTH. זוהי השורה הנכונה:

case 3: return (*m_data)(x, Height()-y-1);​

 

[אלדד28]

יש לך אולי רעיון טוב למצב שבו...

לא אתה כתבת את המטריצה? (נגיד, D3DMATRIX).

 

[אינגולמו]

מה הבעיה?

פשוט מחליפים את היישום של MatrixData בכל יישום אחר, נניח D3DMATRIX. מבחינה טכנית אולי עדיף ש-MatrixData יהיה TEMPLATE, אבל אלה כבר פרטים קטנים.

 

[אלדד28]

העניין הוא,

שאתה מניח ש-MatrixData מספקת לך אוסף פעילויות מסוים, ואז אתה עוטף אותה. אני לא רוצה overhead בכלל על הפעילות. סביר להניח שאפשר לעשות את זה בעזרת inline-ים שונים ומשונים.

 

[אינגולמו]

תסכים איתי

שיש כ"כ הרבה יישומים של מטריצות, כך שאם אתה רוצה שכולן יפעלו דרך אותו INTERFACE, סביר להניח שצריך להיות איזה PROXY או BRIDGE בדרך? אז MATRIXDATA ישמש בתפקיד הזה.... איזה OVERHEAD יש פה? שצריך להגדיר INTERFACE סטנדרטי שיעטוף יישום MATRIX מסויים?

 

[אלדד28]

אני מדבר על

overhead בזמן ריצה, לא בזמן הפיתוח. וכן, ברור - יש הרבה יישומים של מטריצה, השאלה היא אם באמת המטרה היא כמו שאמרת, שכולן תעבודנה דרך אותו i/f. במטריצה של D3D למשל, העניין העיקרי הוא - כמו שאתה יודע - הביצועים, ולכן כל קריאה מיותרת לפונקציה תהיה... מיותרת

עדיין נדמה לי שאפשר באמת להשתמש בשיטה שלך בכלליות דרך פונקציות inline-יות ולא לגרום ל-overhead. שאלה אחרת - אם רוצים הפיכה של 180 מעלות, צריך לעבור פעמיים דרך כל פונקציה?

 

[אינגולמו]

יכול להיות...

זה עניין די טריביאלי להתחיל לנסות ולבדוק... אתה מוזמן

אבל בכל מקרה, ברגע שטרנספורמציה על מטריצה היא בזמן קבוע, זה כבר עדיף על הרבה מאוד דברים

ובמקרה שמיישמים מחסנית של טרנספורמציות, כמו שהצעתי לבחור, אזי סדר גודל זמן הגישה לאיבר הופך להיות O של K (כאשר K מספר הטרנספורמציות) - וזה מצב מצויין.

 

[אלדד28]

../images/Emo45.gif הבעיה המרכזית היא שטרנספורמציה

על מטריצה באופן המקובל היא הכפלה במטריצה אחרת, ולא רק גישה בסדר שונה לאיברי המטריצה.

 

[voguemaster]

בכל מקרה...

בעזרת טרנספוז פשוט אפשר לבצע סיבובים של מטריצות ב-90 מעלות..

 

[אינגולמו]

השאלה היתה

שאלה של יעילות ה-TRANSPOSE, ולא רק שאלת ה"איך מסובבים"...

 

[voguemaster]

היעילות היא n^2

תמיד תהיה. גם אצלך. מה בדיוק הרווחת מלבד קצת אבסטרקציה ?

 

[אלדד28]

לא, לא, פספסת את הפתרון שלו.

ספציפית ל-90 מעלות אתה יכול להשתמש בטריק שמתייחס לעמודות כאל שורות ולהיפך. במקרה כזה זה כאילו תחליף את [mat[3][4 ב - [mat[4][3. את זה אפשר לעשות בעזרת inline functions בזמן קבוע שלא יוריד במאומה מיעילות התוכנית (אבל בהחלט ייתן לך מטריצה מסובבת). שים לב שמדובר על סיבוב של המטריצה, לא סיבוב ערכי המטריצה.

 

[אינגולמו]

עברת על הקוד שלי?

היעילות של הטרנספורמציה היא O של 1!!! אני לא מפעיל שום פעולה על המטריצה המקורית - רק מחליט להסתכל עליה דרך פונקציה (במקרה הזה, הפונקציה "משחקת" עם ערכי X ו-Y).

 

[voguemaster]

עברתי וגם הבנתי

 

[אינגולמו]

אין בעיה במנגנון שהצעתי

ואפשר ליישם גם INTERFACE שמכיל מטריצה שלמה, ולא רק פונקציה בודדת שמשנה את X ו-Y. תנסה ותראה. בזמן הטרנספורציה, רק מחליפים INTERFACE בזמן קבוע. אח"כ, זמן הגישה לאיברים יקח יותר מזמן קבוע (תלוי במספר וסוג הטרנספורמציות), אבל כמו שאמרתי, אפשר תמיד ליישם פעולת DELETE HISTORY או משהו דומה, שמנקה את מחסנית הטרנספורמציות, ואז אתה מקבל מטריצה "סופית", שזמן הגישה לכל איבר שלה הוא קבוע. וד"א לשאלתך הקודמת על D3DMATRIX... למה בכלל לעטוף אותה בכזה מנגנון? ברור לך שאם מהירות היא מה שאתה מחפש, אז פשוט תעבוד ישירות איתה ולא עם מנגנון פולימורפי. וזה תמיד נכון גם בלי שום קשר ל-INLINE. סה"כ D3DMATRIX היא למטרה מאוד ספציפית (לדוגמה יש לה גודל קבוע). מצד שני, אם אתה מעוניין ב-PORTING, אז המעטפת שהצעתי יכולה להיות פיתרון טוב כדי ליישם, נניח, תוכנה לעיצוב תלת מימדי... משהו פחות REALTIME'י אם תרצה. גמישות על חשבון מהירות. מה חדש?